Pathfinding Demystified (Part III): A* Demystified
Introduction
The first article in this series presented the generic pathfinding algorithm; every pathfinding algorithm is a slight variation of it.
The second article revealed the secret behind the different search algorithms: it all comes down to the choose_node
function. It also presented a reasonably simple choose_node
that yields an algorithm called Uniform Cost Search.
This algorithm is pretty good: it will find the shortest path from the start node to the goal node. However, it’s somewhat wasteful: it considers paths that a human clearly sees as “wrong”  they tend to move away from the goal. Can we avoid this?
The Magical Algorithm
Imagine we’re running a search algorithm in a special computer which has a chip that can do magic (bear with me). With this awesome chip, we can express choose_node
in a very simple way which is guaranteed to produce the shortest path without losing any time exploring partial paths that won’t lead anywhere:
function choose_node (reachable): return magic(reachable, "whatever node is next in the shortest path")
Tempting, but magic chips still require somewhat lower level code. This would be a good approximation:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, "shortest path to the goal") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
This is a great way to choose the next node: we choose the node that yields the shortest path from the start node to the goal node, which is exactly what we’re looking for.
We have also minimized the use of magic: we know exactly what’s the cost from the start node to each node (that’s node.cost
), and we use magic only to divine the cost from the node to the goal node.
The NonMagical but Pretty Awesome A*
Unfortunately, magic chips are quite new, and we want to support legacy hardware. Most of the code is fine, except for this line:
# Throws MuggleProcessorException cost_node_to_goal = magic(node, "shortest path to the goal")
So we can’t use magic to know the cost of the path we haven’t explored yet. Fine. Let’s make a guess, then. We’re optimistic, so we’ll assume there’s nothing between the current node and the goal node, and we can just go straight:
cost_node_to_goal = distance(node, goal_node)
Note that the shortest path and the minimum distance are different: the minimum distance assumes there are absolutely no obstacles between the current node and the goal node.
This estimate can be quite simple. In our gridbased examples, it’s the Manhattan distance between the two nodes (that is, abs(Ax  Bx) + abs(Ay  By)
). If you could move in diagonals, it would be sqrt( (Ax  Bx)^2 + (Ay  By)^2 )
, and so on. The really important thing is to never overestimate the cost.
So here’s a nonmagical version of choose_node
:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
The function that estimates the distance from a node to the goal is called an heuristic, and this search algorithm, ladies and gentlemen, is called… A*.
Live Demo
While you recover from the shock of realizing that the mysterious A* is actually that simple, here’s a demo you can play with. Unlike the previous example, you’ll notice the search wastes very little time going in the wrong direction.
reachable = [] explored = []

Conclusion
We have finally arrived at the A* algorithm, which is nothing more than the generic search algorithm described in the first article, with some improvements described in the second article, and using a choose_node
function that chooses the node we estimate will get us closer to the goal. That’s it.
For reference, here’s the full pseudocode of the main method:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty: # Choose some node we know how to reach. node = choose_node(reachable) # If we just got to the goal node, build and return the path. if node == goal_node: return build_path(goal_node) # Don't repeat ourselves. reachable.remove(node) explored.add(node) # Where can we get from here that we haven't explored before? new_reachable = get_adjacent_nodes(node)  explored for adjacent in new_reachable: # First time we see this node? if adjacent not in reachable: reachable.add(adjacent) # If this is a new path, or a shorter path than what we have, keep it. if node.cost + 1 < adjacent.cost: adjacent.previous = node adjacent.cost = node.cost + 1 # If we get here, no path was found :( return None
The build_path
method:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
And the choose_node
method that makes it A*:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
That’s it.
So why is there a Part IV?
Now that you understand how A* works, I want to explore some of the incredible applications it can have, way beyond searching for paths in a square grid.