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 Non-Magical 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 grid-based 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 non-magical 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.