Pathfinding Demystified (Part II): Search Strategies

Introduction

The first article in this series presented the generic pathfinding algorithm. If you didn’t fully understand it, please go back and re-read 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 innocent-looking 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*.