A Star Search version 1

After a few days I’ve got my A Star pathfinding algorithm working. This search method is guaranteed to find the optimal path to the goal node. The cost of each node is calculated using the following algorithm:

f=g+h where f = total cost of the node; g=cost from start node to current node; h=estimated cost to goal node;

Nodes with a lower f cost are expanded.

The h value is calculated by getting the distance between two hexagons, to achieve this the coordinate system needs to offset the y axis but keep the x axis across. Then the following function will get the distance to the goal hexagon, with each hexagon travelled adding 1 to the distance.

int dx = hexB.posX – hexA.posX;
int dy = hexB.posY – hexA.posY;

if (Sign(dx) != Sign(dy))
return abs(dx) + abs(dy);
else
return std::max(abs(dx), abs(dy));

Key:
S=start node
F=finish(goal) node
Black=wall
Blue=evaluated node
Green=node on optimal path

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s