A* Pathfinding Tutorial : Part 2

Welcome to part two in my series on pathfinding. In this tutorial we will be looking at the actual A* algorithm before we actually start implementing it in code in the next tutorial.

This tutorial will be mostly theory based with very little coding so please stick with it as it is really important to understand the actual algorithm before trying to translate it into code!

Before we can start looking at how the A* algorithm actually works, we will need to define a few key terms that will make describing the algorithm a lot easer :

• The G Value – Each node will have an associated G value, this is how far we would have to travel to get from the starting node to this node.
• The H Function (The Heuristic Function) – This is a method that will help us to estimate how far we would have to move to get from one node to another node “as the crow flies”. The method will not take into account any obstacles which is why it will only be an estimate.
• The F Value – Each node will also have an associated F value. This is a rough estimate of how far we would have to travel to get from the starting node to the end node if the path crosses this node. To work out an F value we can do the following : F = G + H – it is basically how far we will have already had to travel to get to this node add a rough estimate of how much further we need to travel.
• The Open List – This is basically a big list of all the nodes that are being considered to be included in the final path.
• The Closed List – This is a list of all of the nodes that have already have been looked at, we will use this to make sure we don’t consider each node more than once.
• The Parent Reference – Each node will have a reference to the node that added this node to the Open List. When the algorithm has finished, we will use the reference to the node’s Parent to trace the final path from the end node to the start node ( I will cover this in more detail later ).

So now that we have all of the definitions out of the way we can look at the actual algorithm, if at first it seems to make no sense, don’t worry about it, just try and keep reading it through and then when we come to actually implement it in code it should make a lot more sense. It will normally take a couple of implementations to fully understand the algorithm.

So basically the algorithm works like this :

1) Clear the Open and Closed Lists and reset each node’s F and G values in case they are still set from the last time we tried to find a path.

2) Set the start node’s G value to 0 and its F value to the estimated distance between the start node and goal node (this is where our H function comes in) and add it to the Open List.

3) While there are still nodes to look at in the Open list :

a) Loop through the Open List and find the node that has the smallest F value (We will refer to this node as the Active Node).

b) If the Open List empty or no node can be found, no path can be found so the algorithm terminates.

c) If the Active Node is the goal node, we will find and return the final path.

d) Else, for each of the Active Node’s neighbours :

i) Make sure that the neighbouring node can be walked across.

ii) Calculate a new G value for the neighbouring node ( This will be the Active Node’s G value + the cost of moving to the neighbour node – I will discuss this later)

iii) If the neighbouring node is not in either the Open List or the Closed List :

(1) Set the neighbouring node’s G value to the G value we just calculated.

(2) Set the neighbouring node’s F value to the new G value + the estimated distance between the neighbouring node and goal node.

(3) Set the neighbouring node’s Parent property to point at the Active Node.

(4) Add the neighbouring node to the Open List.

iv) Else if the neighbouring node is in either the Open List or the Closed List :

(1) If our new G value is less than the neighbouring node’s G value, we basically do exactly the same steps as if the nodes are not in the Open and Closed Lists except we do not need to add this node the Open List again.

e) Remove the Active Node from the Open List and add it to the Closed List

And that’s all that this algorithm does, it basically just takes the node that is ‘closest’ to the goal node and keeps hoping across the neighbouring nodes until it reaches the goal node.

In the next tutorial, we will be going through this algorithm step by step and implementing it in code, but in the mean time I would highly recommend that you try and code this by yourself first! I know it may look pretty complicated but if you break follow it through step by step it is actually pretty simple.

The first thing you will need to do is add the new fields to the SearchNode class, a couple of floats for the F and G values and a SearchNode property for the Parent field. Then our Pathfinder class is going to need two new lists to represent the Open and Closed Lists.

The only thing that won’t be easy to code is the code that will return the final path, but you can always just miss that step… ;)

I hope you have found this tutorial useful and please let me know if anything in it was poorly explained or not explained in enough detailed or even is something was missed out completely and I will do my best to fix it.

Thank you for reading!

I would just like to mention a few of the sources that helped me when I was learning about A* :

• “http://www.policyalmanac.org/games/aStarTutorial.htm” (Patrick Lester)
• “http://en.wikipedia.org/wiki/A*_search_algorithm”
• “Programming and RTS Game with Direct3D” (Carl Granberg)