Field notes on a guided search
How a simple estimate transforms a blind search into a guided one — and why the guarantee holds.
The simplest map-search problem is this: given a grid with a start, a goal, and some walls, find the shortest sequence of steps from start to goal. A program that solved it by trying every possible path first would be correct. It would also be impractical — on any reasonably sized grid, the number of paths is too large to enumerate before the reader has aged considerably.
There are smarter approaches. The one this piece is about — A*, invented in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael — adds one ingredient to a basic search that changes its character completely: an estimate of how far each cell is from the goal. That estimate, if it follows a single rule, lets the search skip most of the grid without sacrificing correctness. The path it finds is still the shortest one. It just finds it faster.
A start, a goal, and something in the way
The map is a grid. Each cell is either passable or a wall. An agent can move to any of its four neighbours — up, down, left, right — as long as the destination is passable. Each move costs one step. The goal is to get from the start to the goal in as few steps as possible.
That's the whole problem. The walls make it interesting: they can force long detours even when the goal is close as the crow flies. The map below is the one this piece uses throughout. Three vertical barriers with two gaps each. Start on the left, goal on the upper right.
Each barrier has a gap near the top (row 2) and a gap near the middle (row 5). The start is in row 6, the goal in row 3. This arrangement matters: the two routes to the goal look different depending on how you measure progress.
The same maze, three different strategies
Three strategies, three different outcomes. Each uses a priority rule to decide which cell to expand next.
Uniform search (BFS) expands cells in order of how many steps they took to reach — closest to the start first. It spreads as a wavefront and always finds the shortest path, but it explores in all directions equally. It has no sense of where the goal is.
Greedy best-first expands cells in order of estimated distance to the goal — call this h. Manhattan distance is a natural choice: the number of steps it would take if there were no walls. Greedy is fast: it ignores most of the grid by rushing toward the goal. But it ignores how far it's already come. On this maze, greedy threads through the upper gaps (row 2), because those cells are closest to the goal by Manhattan distance. The path it finds is longer than necessary.
A* combines both. It expands cells in order of g + h: exact steps from start plus estimated steps to goal. The lower gaps (row 5) look less appealing than the upper gaps to a heuristic-only search, but A* accounts for the fact that reaching row 2 from start costs four extra steps. It correctly identifies the middle-gap route as shorter overall.
(BFS)
The key numbers: BFS and A* both find the 20-step path — the true shortest. Greedy finds a 22-step path. Greedy also expands far fewer cells than BFS, which is why it's tempting: it's fast. But it trades correctness for speed. A* gets the best of both — nearly as focused as greedy, with the same guarantee as BFS.
Two numbers, one priority: g + h = f
The greedy search had the right instinct — using the distance-to-goal estimate to guide expansion — but it was missing one piece. It knew how far the goal was, but not how far it had come. A cell might be close to the goal but only reachable via a long detour; greedy would eagerly expand it, not knowing the detour's cost.
The fix is to account for both. Every cell carries two numbers: g, the exact cost from start to this cell, and h, the Manhattan distance from this cell to the goal. Their sum f = g + h is the total estimated path length through this cell. Expanding lowest-f cells first gives a search that is simultaneously directed (like greedy) and cost-aware (like BFS).
A cell with a low f is either close to the start and close to the goal, or far from the start but very close to the goal — either way, it looks like a good next step. A cell with a high f is probably far from both, or forced into a long detour by a wall. It waits.
The exhibit below shows A* partway through a smaller grid. Hover any visited cell to inspect its scores. Notice how cells on the direct route toward the goal have f equal to the optimal path length, while cells deflected by the barrier have higher f values.
The cells with the highest f values are the ones A* most aggressively deprioritizes. They're reachable, but by a route that the arithmetic says can't improve on the best path seen so far. They wait in the open set until everything cheaper has been checked — which, if the search succeeds, means they may never be expanded at all.
Why the estimate can be trusted
The key property is admissibility. Manhattan distance — used here as h — never overestimates the true remaining cost on a grid where each step costs one unit and walls can only block, never shorten, a route. An admissible heuristic is a lower bound: the true distance to the goal is at least h, possibly more if walls force a detour. Manhattan distance never inflates that estimate.
Because h is a lower bound, f = g + h is a lower bound on the true cost of any complete path that passes through a given cell. A cell at exact distance g from the start, with heuristic value h, cannot be on any path shorter than g + h. A* uses this to prune: it never expands a cell whose f exceeds the cost of the best complete path found so far. When the goal cell reaches the front of the open set, h(goal) = 0, so f = g — the exact cost of the path just found. Nothing remaining in the open set has lower f, and therefore nothing can lead to a shorter path. The search is provably done.
This is why the guarantee holds for A* and not for greedy. Greedy ranks by h alone, which is not a lower bound on path cost — a cell that looks close to the goal may have accumulated a large g to get there. A* combines both terms precisely because their sum is a lower bound. The heuristic earns its keep by making that bound tight enough to prune most of the grid, without ever making it loose enough to discard a better path.
Where this algorithm came from
The shortest-path problem in graphs was first solved systematically by Edsger Dijkstra in 1959. His algorithm — which expands nodes in order of their distance from the source, stopping when the destination is reached — is exactly the uniform search in §2. It guarantees shortest paths on any non-negative-weight graph. For a grid where all edges have equal cost, it degenerates to breadth-first search.
In 1968, Peter Hart, Nils Nilsson, and Bertram Raphael published "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in IEEE Transactions on Systems Science and Cybernetics. Their algorithm — which they called A* — augmented Dijkstra with a heuristic function h that estimated remaining cost. They proved that if h is admissible (never overestimates), A* is both complete (always finds a path if one exists) and optimal (the path it finds is shortest). The 1968 paper remains the canonical reference.
A* became a foundational tool in AI research and game development. In robotics, it is used for motion planning. In GPS navigation, variants of it run on graphs with millions of nodes. In game AI, it routes characters through dynamic environments. The core algorithm is unchanged from 1968; what has evolved is how the heuristic is computed, how the open set is managed (binary heaps replaced linear scans), and how the technique is extended for hierarchical or weighted search.
References
- Dijkstra, E.W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269–271.
- Hart, P.E., Nilsson, N.J., Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th ed. Pearson. Chapter 3, "Solving Problems by Searching."