A* Pathfinding: Finding the Way Through a Grid

Few things betray an unfinished game as quickly as a character who cannot find its way. A soldier walks into a wall and stays there, pressing forward with dumb persistence; a villager takes a route around the entire map to reach a house across the street. Players forgive a great deal, but they notice at once when a creature in the world seems unable to see it, and the quiet machinery that prevents this, in a great many games, is a single algorithm known as A*.

A* was published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael, researchers at the Stanford Research Institute, as part of the work on Shakey, a mobile robot that needed to plan its movements. More than half a century later, the same idea guides units across strategy maps, monsters through dungeons and characters over the navigation meshes that Unity bakes from level geometry. Few algorithms have aged so well, and its endurance is no accident.

The algorithm is short enough to fit on a page, yet it rewards a slow reading. Its behaviour depends on a handful of numbers and on one decision, the choice of estimate, that determines whether it is fast, whether it is correct, and whether those two virtues can be had together. A grid is the clearest place to learn it, since every step can be counted by hand.

Searching a graph

Pathfinding is a search through a graph: a set of nodes connected by edges, each edge carrying a cost. On a grid, the nodes are cells and the edges connect each cell to its neighbours, four of them if movement is restricted to the cardinal directions, eight if diagonals are allowed. A cell occupied by a wall or a cliff is simply removed from the graph, or given no edges, so that no path can pass through it.

The same algorithm works on any graph, which is why it survives the move from grids to more sophisticated representations. Unity's navigation system divides walkable surfaces into convex polygons, a navmesh, and a NavMeshAgent asks the engine for a path through those polygons; the search underneath is a variant of A* over the polygon graph. Waypoint networks and hexagonal maps are searched in the same way, with only the definition of neighbours and costs changing.

The naive approach to finding a path would be to explore outward in every direction until the goal is stumbled upon. That works, and with uniform costs it is called breadth first search, but it wastes effort on directions that lead away from the goal. A* keeps the thoroughness of such a search while adding a sense of direction, and the way it does so is captured in three numbers it keeps for every node it touches.

Three numbers: g, h and f

The first number, g, is the cost of the best path found so far from the start to the node. It is known exactly, because it is the sum of the edge costs actually traversed. The second number, h, is the heuristic: an estimate of the cost from the node to the goal. It is a guess, since the true remaining cost is precisely what the algorithm is trying to discover. The third, f, is simply their sum, f = g + h.

The value f is the algorithm's estimate of the total cost of a path that runs from the start through this node to the goal. A* always chooses to expand the node with the lowest f next, which balances two opposing impulses. A low g favours nodes near the start, the cautious instinct of a breadth first search; a low h favours nodes near the goal, the eager instinct of a search that rushes straight ahead. The sum keeps both in check.

The quality of h therefore shapes everything. If h were perfect, equal to the true remaining cost, A* would walk straight along the optimal path and expand almost nothing else. If h is zero everywhere, the algorithm loses all sense of direction and expands nodes purely by distance from the start, which is exactly Dijkstra's algorithm, published by Edsger Dijkstra in 1959. A* can be understood as Dijkstra's algorithm with a compass added.

The open and closed sets

A* keeps two collections. The open set holds nodes that have been discovered but not yet expanded, and it is usually implemented as a priority queue ordered by f, often a binary heap, so the lowest f can be removed quickly. The closed set holds nodes that have already been expanded, whose best cost is settled. At the start, the open set contains only the start node, with g equal to zero and f equal to its heuristic.

Each step of the loop removes the node with the lowest f from the open set. If it is the goal, the search is finished. Otherwise the node is moved to the closed set, and each of its neighbours is considered. For every neighbour not already closed, the algorithm computes a tentative g, the current node's g plus the cost of the edge between them. If the neighbour is new, or if this tentative g is lower than its previous g, the neighbour's costs are updated.

Whenever a neighbour's g is improved, the algorithm also records which node it came from, its parent. These parent links are what turn a search into a path. When the goal is finally removed from the open set, the route is recovered by following parent links backward from the goal to the start and then reversing the list. Nothing else needs to be stored; the parents encode the whole answer.

If the open set ever becomes empty before the goal is reached, there is no path, and A* reports failure honestly. This matters in games more than it might seem. A unit ordered to walk into a sealed courtyard should be told that the courtyard is unreachable, rather than searching forever or wandering to the nearest wall, and on a large map an unreachable goal is the most expensive query of all, since the search must exhaust every reachable cell before giving up.

Choosing a heuristic

A heuristic is admissible if it never overestimates the true cost to the goal. Hart, Nilsson and Raphael showed that with an admissible heuristic, A* is guaranteed to find a shortest path. Many practical heuristics are also consistent, meaning the estimate never drops by more than the cost of a single step between neighbours; with a consistent heuristic, a node's cost is final the moment it is closed, and the closed set never needs to be reopened.

On a four way grid with unit costs, the natural heuristic is Manhattan distance: the horizontal difference plus the vertical difference between the node and the goal. It is admissible because no four way path can be shorter than that. On an eight way grid where diagonal steps cost the square root of two, roughly 1.414, Manhattan distance can overestimate, since a diagonal covers both axes at once. There the correct choice is octile distance.

Octile distance takes the larger of the two differences, adds the smaller one multiplied by the square root of two minus one, and so counts as many diagonal steps as possible before finishing in a straight line. For a goal three cells across and two cells down, it gives 3 plus 2 times 0.414, about 3.83, which is exactly the length of the best path on an open grid. Manhattan would say 5, an overestimate.

Euclidean distance, the straight line between two points, never overestimates on either kind of grid and suits movement at any angle, as across a navmesh. For the same goal it gives the square root of 13, about 3.61. On grids it underestimates more than necessary, so A* expands more nodes than it would with octile. The general rule is that the closer an admissible heuristic comes to the true cost, the less work A* does.

A small grid solved by hand

Consider a grid five cells wide and three cells tall, with four way movement and every step costing one. The start lies in the left column of the middle row, the goal in the right column of the same row. A wall fills the top and middle cells of the centre column, leaving a gap only along the bottom row. The heuristic is Manhattan distance, so the start has g of 0, h of 4 and f of 4.

Expanding the start discovers three neighbours. The cell to its right has g of 1 and h of 3, so f is 4. The cells above and below the start each have g of 1 but h of 5, giving f of 6. The cell to the right has the lowest f and is expanded next. Its right hand neighbour is wall, so it adds only the cells above and below it, each with g of 2, h of 4 and f of 6.

At this point every node in the open set has f of 6, while the straight line estimate had promised 4. That rise is the wall announcing itself: going around it costs two extra steps, one down and one back up. With ties broken in favour of lower h, the search proceeds along the bottom row, through the gap at g of 3, then to g of 4 and g of 5, and reaches the goal with g of 6. The path found is six steps long, and no shorter route exists.

A* in practice

In shipped games, the algorithm is rarely run in its textbook form. Large maps are often searched hierarchically, first across coarse regions and then within the few regions the route crosses. Results are cached and shared, so that a hundred soldiers ordered to the same gate do not each search separately. Some games deliberately inflate the heuristic slightly, trading the guarantee of the shortest path for much faster searches, on the reasoning that a nearly optimal route is invisible to the player.

Searches also need limits. A per frame budget on the number of nodes expanded, with the search resumed on the following frame, prevents a single long path from causing a visible stutter. When many units move at night toward a settlement, as the dead do in Crown & Ashes, the cost of pathfinding is multiplied by every one of them, and techniques such as flow fields, which compute one shared field of directions toward a single goal, often replace individual searches entirely.

For all its refinements, the heart of A* remains the same small idea set down in 1968: keep the cost you know, add an honest guess at the cost you do not, and always follow the most promising lead. There is something almost moral in that arrangement, a search that is rewarded for humility, punished for overconfidence, and that will, given an estimate which never lies upward, carry its traveller home by the shortest road.