Lesson 7 · Essential

Searching a grid, from Dijkstra to A*

A decision says where to go; a search finds the way. Dijkstra and A* stepped one expansion at a time on a small map, what g, h and f mean, what makes a heuristic admissible and consistent, why ties matter on open ground, and what Weighted A* and greedy search trade away for speed.

The decision lessons end with an agent that wants to be somewhere else. Getting there is a graph search: the map is a set of nodes (here, the cells of a grid), joined by edges with costs (a step costs 1, a diagonal step √2 ≈ 1.41), and we want the cheapest chain of edges from a start node to a goal node.

The three lessons in this part explain the pathing lab, which runs these searches side by side on the same maps. This one is the search itself. The next makes it fast, and the one after makes its paths look like something a person would walk.

One loop, two orders

Every search here is the same loop. Keep an open list of nodes found but not yet looked at, starting with just the start. Repeatedly take the most promising node off it and expand it: for each neighbour, work out the cost of reaching it through this node, and if that’s cheaper than any route found so far, remember it (cost and parent) and put the neighbour on the open list. Stop when the goal comes off the list; follow parents back to the start for the path.

// g[n]: cost of the best route found so far from the start to n. parent[n]: where it came from.
g[start] = 0;
open.push(start, priority(start));
while (!open.empty()) {
    Node cur = open.pop();                         // lowest priority
    if (closed[cur]) continue;                     // a stale duplicate: we found a cheaper way since
    closed[cur] = true;
    if (cur == goal) return trace(parent, goal);
    for (auto [next, cost] : neighbours(cur)) {
        float ng = g[cur] + cost;
        if (ng < g[next]) {                        // a cheaper way to reach next
            g[next] = ng;
            parent[next] = cur;
            open.push(next, priority(next));       // no decrease-key: push again, skip the old one later
        }
    }
}
return no_path;

What “most promising” means is the whole difference between the algorithms. Dijkstra’s algorithm takes the node with the lowest g, the cost from the start. It spreads evenly in every direction, like a ripple, and the first time the goal comes off the list its g is the cheapest possible. A* (Hart, Nilsson and Raphael, 1968) adds h, a guess of the cost still to go, and takes the lowest f = g + h: the estimated cost of a whole route through that node.

Loading…

On this 24 × 16 map Dijkstra expands 319 cells before it reaches the goal, almost every open cell on the map; A* expands 59 and finds a path of the same cost, 23.73. Step through either one: the ringed cell, the next to come off the open list, always has the lowest f there (for Dijkstra, f is just g). Hover a cell for its numbers: every cell already expanded has an f no larger than the ringed cell’s, so the search grows outward in order of f, a ripple of rising g for Dijkstra and a wedge for A*.

Step through A* and Dijkstra side by side in the pathing lab →

Dijkstra isn’t the loser here, it answers a different question. When you want the cost from one place to everywhere (a flow field that many units follow, the nearest cover, an influence map), let it run to the end; that’s what the influence lesson’s flood is. For one start and one goal, A* does less work for the same answer.

The heuristic

The guess decides how much of the map A* looks at, and whether the path it returns is still the cheapest. Two properties matter:

Admissible: h never overestimates the real remaining cost. Then A* returns a cheapest path.
Consistent (or monotone): h never drops by more than an edge costs, h(a) ≤ cost(a, b) + h(b). Then no node ever has to be expanded twice, and the loop above (which skips closed nodes) is correct. Consistent implies admissible.

Within those rules, bigger is better: the closer h is to the real cost, the fewer nodes A* expands. With a perfect h it would walk straight down the path; with h = 0 it is Dijkstra.

On an 8-way grid the right guess is octile distance, the exact cost on an empty map: max(dx, dy) + (√2 − 1) · min(dx, dy). Straight-line (Euclidean) distance is also admissible, but lower, so it searches more. Manhattan distance, dx + dy, is right for a 4-way grid but charges 2 for a diagonal step that costs 1.41, so on an 8-way grid it overestimates.

Loading…

On this scattered map, with no guess (Dijkstra) the search expands 1,034 cells; with Euclidean distance 764; with octile 683, all three finding the cheapest path, cost 66.38. Manhattan expands only 523 cells, and its path costs 68.38, 3.0% more: it’s no longer admissible, so A* stops being sure of the cheapest path.

Ties

On open ground many routes cost exactly the same: right, right, down-right is as good as down-right, right, right. Their cells all have the same f, and A* is free to expand them in any order. If it picks badly, it expands the whole region of equal f before it finishes.

The usual fix: among nodes with equal f, prefer the one with the larger g, the one further along its route and so nearer the goal. A* then runs down one of the equal routes instead of exploring all of them. It costs nothing (it’s a second key in the priority queue) and doesn’t change the cost of the path.

Loading…

Crossing this empty 48 × 30 map diagonally, the path costs 47.70 whichever way ties go. Preferring the smaller g, A* expands 418 cells; leaving ties to whatever the priority queue does, 226; preferring the larger g, 40. Every search in the lab breaks ties toward the larger g. Amit Patel’s heuristics page describes another common trick with the same effect: multiply h by a factor just above 1 (say 1.001). That breaks ties toward the goal, at the cost of a very slight overestimate.

Trading quality for speed

Sometimes nearly cheapest is fine, and much faster is worth having. Weighted A* uses f = g + w · h with w > 1: it trusts the guess more and heads for the goal harder. Its path costs at most w times the cheapest, and usually far less than that. Greedy best-first goes all the way, f = h: it ignores the cost already walked and always takes the node that looks closest to the goal.

Pick 2 × octile and h only in the heuristic widget above. Weighted A* expands 94 cells and its path costs 3.7% more than the cheapest; greedy expands 87, and its path costs 8.0% more, because it goes wherever looks closest and finds out late. Greedy is worst in a U-shaped trap: walking into the cup always looks like progress.

On a big map the gap is larger. On the lab’s 256 × 160 town, Weighted A* with w = 2 expands 17 times fewer nodes than A*, for a path 1.9% longer. That makes it the cheapest speed-up there is, and the first to try when a game can live with paths a few percent longer.

Compare A* and Weighted A* on the big town in the pathing lab →

Takeaways

A search keeps an open list and repeatedly expands the most promising node; the algorithms differ only in what “most promising” means.
Dijkstra orders by g, cost so far: right when you want distances to everywhere. A* orders by f = g + h: right for one start and one goal.
A heuristic must be admissible (never overestimates) for the cheapest path, and consistent for each node to be expanded once. On an 8-way grid, use octile distance.
Break ties toward the larger g: it costs nothing and saves most of the work on open ground.
Weighted A* trades a bounded amount of path quality for a large cut in work; greedy trades an unbounded amount.

In the lab

The lab’s Search concept cards cover all of this, with every algorithm on every map, and a hover inspector that shows any cell’s g, h and f at any step of the search.

Open Octile against Manhattan in the pathing lab →

Searching a grid, from Dijkstra to A*

One loop, two orders

The heuristic

Ties

Trading quality for speed

Takeaways

In the lab

Further reading