If you’re a game developer, you might have always wanted to implement A* as character (or enemy) pathfinding. I know a couple of years ago I did, but with my level of programming at the time I had issues with the current articles out there. I wanted to write this as an easy introduction with a clear source code example to A* pathfinding so anyone can easily pick it up and use it in their game.
F = G + H
One important aspect of A* is
f = g + h. The f, g, and h variables are in our Node class and get calculated every time we create a new node. Quickly I’ll go over what these variables mean.
- F is the total cost of the node.
- G is the distance between the current node and the start node.
- H is the heuristic — estimated distance from the current node to the end node.
Let’s take a look at a quick graphic to help illustrate this.
Awesome! Let’s say
node(0) is our starting position and
node(19) is our end position. Let’s also say that our current node is at the the red square
G is the distance between the current node and the start node.
If we count back we can see that
node(4) is 4 spaces away from our start node.
We can also say that G is 1 more than our parent node (
node(3)). So in this case for
currentNode.g = 4.
H is the heuristic — estimated distance from the current node to the end node.
So let’s calculate the distance. If we take a look we’ll see that if we go over 7 spaces and up 3 spaces, we’ve reached our end node (
Let’s apply the Pythagorean Theorem!
a² + b² = c². After we’ve applied this, we’ll see that
currentNode.h = 7² + 3². Or
currentNode.h = 58.
But don’t we have to apply the square root to 58? Nope! We can skip that calculation on every node and still get the same output. Clever!
With a heuristic, we need to make sure that we can actually calculate it. It’s also very important that the heuristic is always an underestimation of the total path, as an overestimation will lead to A* searching for through nodes that may not be the ‘best’ in terms of
F is the total cost of the node.
So let’s add up h and g to get the total cost of our node.
currentNode.f = currentNode.g + currentNode.h. Or
currentNode.f = 4+ 58. Or
currentNode.f = 62.
Time to use
f = g + h
Alright, so that was a lot of work. Now with all that work, what am I going to use this
f value for?
With this new
f value, we can look at all our nodes and say, “Hey, is this the best node I can pick to move forward with right now?”. Rather than running through every node, we can pick the ones that have the best chance of getting us to our goal.
Here’s a graphic to illustrate. On top, we have Dijkstra’s Algorithm, which searches without this
f value, and below we have A* which does use this
So taking a look at Dijkstra’s algorithm, we see that it just keeps searching. It has no idea which node is ‘best’, so it calculates paths for them all.
With A*,we see that once we get past the obstacle, the algorithm prioritizes the node with the lowest
f and the ‘best’ chance of reaching the end.
A⭐️ Method Steps — from Patrick Lester
I’ve pasted the steps for A* from Patrick Lester’s article that you can check out here. The same website is also listed below in resources. This is an insanely good explanation, and is why I decided to go with it rather than writing it again.
1. Add the starting square (or node) to the open list.
2. Repeat the following:
A) Look for the lowest F cost square on the open list. We refer to this as the current square.
B). Switch it to the closed list.
C) For each of the 8 squares adjacent to this current square …
- If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
- If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
- If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
D) Stop when you:
- Add the target square to the closed list, in which case the path has been found, or
- Fail to find the target square, and the open list is empty. In this case, there is no path.
3. Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
Following the example below, you should be able to implement A* in any language.
// A* (star) Pathfinding// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes// Add the start node
put the startNode on the openList (leave it's f at zero)// Loop until you find the end
while the openList is not empty // Get the current node
let the currentNode equal the node with the least f value
remove the currentNode from the openList
add the currentNode to the closedList // Found the goal
if currentNode is the goal
Congratz! You've found the end! Backtrack to get path // Generate children
let the children of the currentNode equal the adjacent nodes
for each child in the children // Child is on the closedList
if child is in the closedList
continue to beginning of for loop // Create the f, g, and h values
child.g = currentNode.g + distance between child and current
child.h = distance from child to end
child.f = child.g + child.h // Child is already in openList
if child.position is in the openList's nodes positions
if the child.g is higher than the openList node's g
continue to beginning of for loop // Add the child to the openList
add the child to the openList
Source Code (in Python 🐍)
There are some awesome websites below you should check out. I especially recommend A* Pathfinding for Beginners.