Pathfinding Demystified (Part II): Search Strategies
Generic Search Algorithm  Search Strategies  A* Demystified  Practical A*
Introduction
The first article in this series presented the generic pathfinding algorithm. If you didn’t fully understand it, please go back and reread it, because it’s essential to understand what follows. Once you get it, A* will be the most natural thing in the world.
The Secret Sauce
I left two open questions at the end of the previous article: if every pathfinding algorithm uses the same code, what makes A* behave like A*? And why did the demo find different paths sometimes?
The answers to both questions are quite related. Even though the algorithm is well defined, there’s one aspect that I left purposely vague, and which as it turns out, it’s the key to explain how search algorithms behave:
node = choose_node(reachable)
That innocentlooking line is what makes each search algorithm different to the others. The choice of what choose_node
does makes all the difference in the world.
So why did the demo find different paths? Because its choose_node
method picked a node randomly.
Length Does Matter
Before diving into the different behaviors of the choose_node
function, we need to fix a slight oversight of the algorithm as explained before.
Whenever we considered the nodes adjacent to the current one, we ignored those we already knew how to reach:
if adjacent not in reachable:
adjacent.previous = node # Remember how we got there.
reachable.add(adjacent)
This is a mistake: what if we have just discovered a better way to reach it? In that case, we should adjust the node’s previous
link to reflect this shorter path.
In order to do this, we need to know the length of the path from the start node to any reachable node. We’ll call this the cost
of the path. For now let’s assume moving from a node to one of its adjacent nodes has a fixed cost of 1
.
Before starting the search, we set the cost
of each node to infinity
; this makes any path shorter than that. We also set the cost
of the start_node
to 0
.
So here’s how the code looks now:
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
Uniform Cost Search
Let’s now focus on the choose_node
method. Choosing a node at random clearly isn’t a good idea if we’re trying to get the shortest possible path.
A better idea is to choose the node we can reach from the start node with the shortest path; this will generally choose shorter paths over longer ones. This doesn’t mean longer paths won’t be considered, just that shorter paths will be considered first. Since the algorithm stops as soon as a valid path is found, this should get us short paths.
Here’s a possible choose_node
function:
function choose_node (reachable):
best_node = None
for node in reachable:
if best_node == None or best_node.cost > node.cost:
best_node = node
return best_node
Intuitively, this algorithm’s search expands “radially” from the start node until it reaches the end node. Here’s a live demo of this behavior:
reachable = [] explored = []

Conclusion
A very simple change in the way we choose what node to consider next gives us a pretty good search algorithm: it does find the shortest path from the start node to the goal node.
But this is still a dumb algorithm, in a way. It keeps looking everywhere until it stumbles upon the goal node. In the example above, what’s the point of looking in the direction of A when we’re obviously getting farther away from the goal?
Can we make choose_node
smarter? Can we make it steer the search towards the goal, even without knowing the right way beforehand?
It turns out we can  in the next article, we’ll finally arrive at the choose_node
which makes the general pathfinding algorithm become A*.