The map is known.
The route is not.

Two algorithms, one line apart

Every search keeps a set of cells it has seen but not yet examined — the frontier, or open set. Take a cell from it, mark it settled, and push its unseen neighbours back on. The entire algorithm is that loop. What you have not specified is which cell to take, and that is not a detail: it is the algorithm. Take the oldest and you get breadth-first search; take the newest and you get depth-first. Same code, same maze, one method call apart.

BFS settles cells in strict order of distance from the start, so the first time it touches the goal it has arrived by a shortest route — the path is optimal, and it is optimal for free. The price is that it settles every cell nearer than the goal, whether or not that cell was ever going in the right direction. DFS pays that price too — it settles about as many cells — and gets nothing for it: the route it returns is whatever corridor it happened to fall down, routinely five to ten times longer than necessary. On a perfect maze — no loops, exactly one route between any two cells — that excess collapses to a few percent, because a tree gives DFS nothing to get wrong. Add loops and it comes straight back.

Now look at the peak frontier readout, which usually says the opposite of what people expect. DFS is supposed to be the memory-cheap one — and here its stack runs ten to fifty times larger than BFS's queue. Both claims are correct about different algorithms. The O(depth) figure describes recursive DFS walking a tree, where the only thing on the stack is the current branch. This is an iterative DFS on a graph, and it pushes every unsettled neighbour on discovery, so each expansion adds up to three entries and removes one. The stack grows to a sizeable fraction of the whole map, and the shape on screen is the reason: those long parallel tendrils are all sitting in memory at once, every one of them a branch point waiting to be unwound.

Not every step costs the same

Breadth-first search counts steps. The moment a step through a swamp costs five times a step down a road, counting steps returns a route that is short and slow. The fix is to stop taking the oldest cell and start taking the cheapest one — the cell whose known cost-from-start g is smallest. That is Dijkstra's algorithm, and it is BFS with a priority queue instead of a plain one.

Drag the marsh cost up and the cheapest route peels away from the straight line and goes the long way round — at some crossover cost the detour becomes worth it, and Dijkstra finds that crossover without being told it exists. Drag it back to 1.0 and the two routes collapse onto each other, because Dijkstra on a uniform-cost graph is exactly BFS. One caveat that matters in practice: this all depends on costs being non-negative. A single negative edge and the whole argument fails — once a cell is settled Dijkstra never revisits it, and a negative edge is precisely a promise that revisiting could have paid.

A good guess is worth a million nodes

Dijkstra spreads in every direction because it knows nothing about where the goal is. But we do know something: on a grid, the straight-line distance to the goal is a free, always-optimistic lower bound on what remains. A* adds it in. Order the frontier not by cost-so-far g but by estimated total trip cost f = g + h, and the search stops spreading like a puddle and starts leaning toward the goal.

Two things are worth staring at. First, going from w = 0 to w = 1 usually cuts the settled count by a large factor while the path cost curve stays perfectly flat — that speed is free, and it is free because the heuristic never overestimates. Second, past w = 1 the settled count keeps falling but the cost curve lifts off the optimum and starts to wander. You are now buying speed with quality, at an exchange rate you do not control. That is not always a bad trade — a game with a hundred units repathing every frame will happily take a 4% longer route for a 10× cheaper search — but it should be a decision, not an accident.

The one rule a heuristic must not break

A* is optimal under exactly one condition: h must never overestimate the true remaining cost. Guess low and you may waste time; guess high and A* can commit to a route and stop looking, because the alternative looked worse than it was. The map below computes the true cost-to-goal for every single cell with a reverse Dijkstra, then paints coral on every cell where your chosen heuristic claims more than that. Coral is not decoration — it is a map of the lies.

Set 8-way movement with the Manhattan heuristic and the map floods with coral. The reason is arithmetic, not bad luck: to reach a cell ten right and ten up, Manhattan says 20, but ten diagonal moves at √2 each cost 14.1. Manhattan overestimates by up to a factor of √2 — which makes it behave exactly like the weighted A* of § 03 with w = 1.41, complete with a path that is slightly, silently wrong. Switch to octile and the coral disappears entirely: octile is the exact distance on an empty 8-way grid, so it is the tightest guess that still never lies. Switch movement to 4-way and Manhattan becomes exact instead. Admissibility is not a property of a heuristic. It is a property of a heuristic and a movement model, together.

Meet in the middle

Here is a saving that costs no heuristic and no accuracy. A uniform search from the start settles roughly everything within distance d — on a plane, an area of about πd². Run two searches instead, one forward from the start and one backward from the goal, and stop when they touch: each only has to reach distance d/2, so together they settle 2 · π(d/2)² = πd²/2. Half the work, same answer. The saving is geometric, and it gets better in higher dimensions.

Try the four maps in order and watch the saving evaporate. On the open field it is close to the predicted half; through rooms it is smaller; on a perfect maze it goes negative — two fronts do more work than one. The disc argument assumed there was area to save, and a maze is a tree: corridors one cell wide, no room to spread, a search that is effectively one-dimensional. In one dimension two searches of length d/2 cover exactly the same ground as one of length d, and the stopping rule then makes each front overshoot slightly past the meeting point. The geometry is the whole saving, so wherever the geometry goes away, so does the benefit.

The other subtlety is knowing when to stop. The two searches meeting is not enough — the first cell they share is rarely on the best route. The correct rule is to keep going until the cheapest cell remaining in the forward queue plus the cheapest remaining in the backward queue is no less than the best joined path found so far; only then is no better join possible. Get that wrong and you have built a fast algorithm that returns nearly-shortest paths, which is a perfectly respectable thing to build as long as you know that is what you did. Combining this with a heuristic is harder still: naïve bidirectional A* can have its two fronts pass each other like ships, and the fixes for it fill papers.

Now you run the numbers

Five problems, each needing one idea from above and arithmetic you can do on paper. Hints reveal one step at a time — try before you peek, then check yourself against the simulators.