A* Pathfinding

A* pathfinding is a shortest-path algorithm that orders its frontier by f(n) = g(n) + h(n): the cost already paid plus a heuristic guess of the remaining cost. With a consistent heuristic, this closed-set A* implementation returns an optimal path while usually expanding fewer cells than Dijkstra's algorithm.

Think of walking through a building with a floor plan in your hand. g is the distance already walked. h is your straight-line sense of how far the exit is. A* is the disciplined version of that instinct: head toward the exit, but keep the receipt for every step you have actually paid for. Pure greed walks into walls. Pure Dijkstra checks too much hallway. A* is the compromise behind game maps, robot floor plans, and route planners - when you can give it an honest lower-bound guess.

The last clause matters. The Overweight preset deliberately lies with h = 4 × Manhattan distance. The goal looks cheap before the cheap detour has been explored, so A* returns the wrong path. That failure is not a footnote; it is the condition under which the whole trick stops being true.

How A* pathfinding works

A* keeps three pieces of state.

g[cell] is the cheapest cost found so far from the start to that cell. came_from[cell] remembers the parent that produced that best cost, so the final path can be reconstructed. The open set is a priority queue ordered by f = g + h, where h estimates the remaining cost to the goal.

The loop is short.

Pop the open cell with the smallest f. If it is already closed, discard the stale heap entry. If it is the goal, stop and reconstruct the path. Otherwise, close it and try its passable neighbors. For each neighbor, compute tentative_g = g[cur] + move_cost. If that beats the neighbor's old g, record the current cell as its parent, lower g, compute the new f, and push a fresh open-set entry.

This implementation never reopens a closed cell, so its optimality guarantee requires a consistent heuristic: h(u) <= cost(u, v) + h(v) on every edge, with h(goal) = 0. Consistency implies admissibility, meaning the heuristic never overestimates the true remaining cost. An admissible but inconsistent heuristic may require reopening closed cells. With consistency, the first time the goal is popped, the path is optimal. At that moment the goal has the smallest f in the open set. Every unfinished route would have to beat that f, and with a consistent lower-bound heuristic such as Manhattan distance here, a later route cannot sneak in under the popped goal cost.

Set h = 0 and A* becomes Dijkstra. Same correctness, less guidance. Inflate h too far and A* starts trusting a bad hunch.

A* pathfinding step by step

Run the default Maze scenario. The grid has 4 rows and 7 columns. Start is r1c0, goal is r1c6, and a wall blocks column 3 in rows 0, 1, and 2. The only gap is at the bottom, so the path must go down, cross the gap, then climb back up.

The trace below follows the returned path, but the animation expands more than those final path cells. That is the point. A* evaluates frontier candidates, closes 15 of the 25 passable cells, and still avoids the broader 23-cell wave Dijkstra produces on the same maze.

1. Seed the open set. g[r1c0] = 0. Manhattan distance from r1c0 to r1c6 is 6, so the first open entry has f = 0 + 6 = 6.
2. Pop r1c0. It has the smallest f, so A* closes it. Its right neighbor r1c1 gets g=1, h=5, f=6. The up/down side cells also enter the open set, but their f values are larger because they move away from the goal row.
3. Pop r1c1, then r1c2. The search keeps following the corridor toward the goal because each cell on that line still has f=6. At r1c2, the wall blocks the direct move into column 3. Now the hint says "go right," but the map says "no."
4. Route around the wall. The best useful route drops through r2c2, then r3c2, crosses the gap at r3c3, and moves to r3c4. Each accepted neighbor writes a new parent arrow and a new g/h/f score.
5. Climb back toward the goal. From r3c4, A* moves through r2c4, r1c4, r1c5, and finally r1c6. The path cost is 10 because the route enters ten cells after the start.
6. Pop the goal. Once r1c6 leaves the open set, its f is tied for best and no open entry has a lower f. Because Manhattan distance is consistent on this grid, the algorithm can stop safely. The reconstructed path is r1c0 -> r1c1 -> r1c2 -> r2c2 -> r3c2 -> r3c3 -> r3c4 -> r2c4 -> r1c4 -> r1c5 -> r1c6.

Switch to Overweight and the failure is sharper: A* reports the direct top-row path with cost 13, even though the bottom detour costs 6. The inflated heuristic made the goal look safe too early. In that final comparison, red numbers are the costs A* actually recorded before it stopped; green opt numbers are the oracle's true cumulative cost on the cheaper route.

A* vs Dijkstra: fewer expanded cells

On the default maze, A* and Dijkstra return the same path cost: 10. The difference is work. A* closes 15 of the 25 passable cells. Dijkstra, which is the same loop with h=0, closes 23.

That is not a different asymptotic bound. Both algorithms still use a priority queue and have the same worst-case shape. The heuristic changes the order of attention. Manhattan distance keeps pulling the frontier toward the goal, while g still forces the detour when the wall blocks the corridor. Dijkstra has no direction, so it spreads like a cost wave until the goal finally reaches the front.

This is the practical reason people reach for A*: maps, games, robot grids, and route planners often have a cheap lower bound on remaining distance. If you can write a heuristic that never lies high, A* lets you spend the same correctness proof on less search.

Time and space complexity

Here V is the number of cells or graph nodes, and E is the number of edges. In a four-neighbor grid, E is at most about 4V, so people often describe grid A* as O(V log V) with a binary heap.

The bound matches Dijkstra because the data structure is the same: push frontier entries, pop the smallest key, and relax edges. The heuristic does not change the worst-case complexity. It changes which cells tend to be popped before the goal. Use this A* implementation when you have a cheap consistent heuristic. Use Dijkstra when you do not. Use neither slogan without checking the costs you actually care about.

Edge cases: when A* has no hint or the hint lies

• No heuristic. h=0 is valid. It is just Dijkstra's algorithm, so it keeps optimality and loses direction.
• Blocked maps. If the open set empties before the goal is popped, no path exists. This lesson's presets all have a path, but the code returns (None, INF) for that case.
• Ties in f. Many grid cells can share the same score. This trace breaks ties by smaller h, then by row and column, so playback is deterministic.
• Weighted terrain. Movement cost belongs in g, not h. The Overweight preset uses terrain costs to show that paying attention to real cost matters.
• Inadmissible heuristics. If h can overestimate, popping the goal is no longer proof. The Overweight preset is the counterexample.
• Stale heap entries. When a cheaper route improves an open cell's g, the lazy heap pushes a second entry instead of editing the first. The Detour preset stages exactly this: one cell is reached at cost 4, improved to cost 2, and the superseded entry pops later only to be skipped.

Common mistakes in A* pathfinding

1. Treating A like greedy best-first search.* Greedy search ranks only by h. A* ranks by g + h, so a cell that is visually closer to the goal can still lose if it has already cost too much.
2. Using a heuristic that overestimates. The common slogan is "A* is optimal," but the missing clause is "with a consistent heuristic for this no-reopening implementation." Inflate Manhattan distance and the proof breaks.
3. Marking cells closed when you push them. A cell is not settled when it enters the open set. A cheaper route may still arrive before it is popped. Close on pop, not on push.
4. Forgetting stale heap entries. A plain binary heap does not decrease a key in place. The usual lazy version pushes a new entry and discards the old one when it pops later. Watch the Detour preset: the skipped pop near the end is that discard happening.
5. Counting pixels as cost. The algorithm does not care how far two cells are drawn on screen. It adds movement costs from the grid or graph; the canvas layout is just a picture of that state.

A Note on Simplification

The open set is drawn as a fully sorted strip so the priority rule is readable at a glance. A real binary heap only guarantees the minimum entry is popped next; the rest of the heap is not sorted like a parade. The grid also uses four-neighbor movement, fixed presets, and small integer costs. This is an explainer for the A* invariant, not a production pathfinding engine with diagonal movement, dynamic obstacles, terrain smoothing, or game-specific tie-breaking.