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);
return std::max(abs(dx), abs(dy));
Green=node on optimal path