Thought Toys · Computation & information · Exhibit 36

A* pathfinding

Dijkstra floods outward evenly until it happens to reach the goal. A* instead guesses — it favors squares that look closer to the goal — and explores far fewer of them for free. Push that guess too hard, though, and the search can lock in a longer, wrong route before the true shortest one is ever found.

A maze with a start cell on the left and a goal on the right, scattered walls between them. Squares fill in as the search visits them; the final route is drawn in amber, and when it is wrong, the true shortest route is drawn as a dashed cyan line for comparison.

Turn up the guess and watch the search narrow.

↳ your turn — drag the guess dial past 1

What you're seeing

A maze of squares, some blocked. Getting from the start to the goal costs one step per square. Dijkstra (exhibit 26's engine) finds the cheapest route by growing outward from the start in every direction at once, like a ripple — reliable, but it wastes effort exploring squares that lead nowhere near the goal.

A* adds a guess: for every square it's considering, it adds a heuristic — an estimate of the remaining distance, here the straight-line (Manhattan) distance to the goal, and explores the most promising-looking square first. Turn the guess dial to 1 and the search is still provably exact — same answer as Dijkstra — but it visits far fewer squares, because the guess is never overconfident: it can under-promise (a wall might make the true route longer) but never over-promise. That's an admissible heuristic — one that never overestimates the true remaining cost, and it's the whole reason A* can be both fast and correct.

Push the dial past 1 and the guess starts to dominate the cost actually paid so far. On this maze, once it crosses roughly 4, the search convinces itself a longer route is fine because a few of its squares look close to the goal — and by the time the true shortest route would have been found, the search has already locked in the wrong answer and stopped. Hit show the true shortest route to see exactly how much longer the wrong one is.

The rule, exactly. Order the frontier by f(n) = g(n) + w·h(n) — cost-so-far plus w times the estimated remaining cost — and stop as soon as the goal is popped as the best candidate. Verified in node (improve/verify/36-astar.js): at w≤1 this matches an independent breadth-first reference on 263 solvable random mazes, every single time; on the maze shown here, w=1 finds the true shortest route (36 steps) while exploring markedly fewer squares than w=0 (plain Dijkstra); past w=4 the route jumps to 52 steps — a real 44% detour, not a rounding error. Counter-example: on an obstacle-free grid, no weight — however large — ever produces a wrong answer, because the straight-line guess is then exact, with nothing for it to overestimate around. It's the combination of a scaled-up guess and a wall that fools the search, not the weight alone.

Also in Computation & information: Diffie–Hellman key exchange →

All 20 in Computation & information
  1. 101Noise sets a speed limit, not an accuracy limit.
  2. 111Any party of six hides a trio
  3. 120How one bit of ink makes a grey
  4. 125The ambulance that arrives sooner by going slower
  5. 131Every number is a sum of Fibonacci numbers
  6. 23Sorting algorithms
  7. 24PageRank & the random surfer
  8. 25Huffman coding
  9. 26Dijkstra's shortest path
  10. 33The learning-rate cliff
  11. 36A* pathfinding — you are here
  12. 44Diffie–Hellman key exchange
  13. 49Freeze too fast, stay stuck
  14. 56Catch one error, miss the next
  15. 57Why more processors stop helping
  16. 58Why a busy line explodes
  17. 59The set that's only sure when it says no
  18. 60The fit that memorizes instead of learns
  19. 61When the wire breaks, pick one
  20. 82Your computer can't hold one tenth

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 36.