A pathfinding heuristic is not a hunch.

It is a contract.

When A* assigns a node the score

\[f(n) = g(n) + h(n),\]

the first term is evidence and the second term is a promise. \(g(n)\) is the cost already paid to reach the node. \(h(n)\) is an estimate of the cheapest remaining cost to the goal.

If \(h(n)\) never overstates the truth, A* can use it aggressively and still return an optimal path. If \(h(n)\) lies upward, the algorithm may become faster, but the proof is gone. Sometimes the answer is still optimal. Sometimes it is not. The machine will not apologize when the distinction matters.

That is the whole post.

The rest is just making the promise visible.

Dijkstra Refuses to Guess

Dijkstra’s shortest-path algorithm is a beautiful refusal to guess.1 It expands the unsettled node with the smallest known cost from the start. If all edge costs are nonnegative, then when a node is removed from the priority queue, its shortest distance is known.

For a single source and single goal, Dijkstra can feel wasteful. It may expand large regions in directions that are obviously not heading toward the target. But that word, “obviously,” is doing work outside the algorithm.

A* imports that outside information.

Hart, Nilsson, and Raphael’s 1968 paper gave the formal basis for adding a heuristic term to best-first graph search.2 The canonical A* score is:

\[f(n) = g(n) + h(n).\]

Read it as:

best known cost to get here
+ promised lower bound on cost from here to goal

If the promise is valid, a node with \(f(n)\) larger than the best solution candidate cannot secretly lead to a cheaper path. This is what lets A* prune work without changing the answer.

The usual grid-world example uses Manhattan distance:

\[h(n)=|x_n-x_g|+|y_n-y_g|.\]

On a four-neighbor grid where every move costs at least 1, Manhattan distance is a lower bound. Obstacles and swamps can make the true path longer or more expensive. They cannot make it cheaper than walking the coordinate difference.

That is why Manhattan distance is not merely intuitive. It is admissible.

Two Ways for h to Tell the Truth

Two related words matter.

A heuristic is admissible if:

\[h(n) \le h^*(n),\]

where \(h^*(n)\) is the true cheapest cost from \(n\) to the goal.

A heuristic is consistent if every edge \(n \to m\) satisfies:

\[h(n) \le c(n,m) + h(m).\]

Consistency is a triangle inequality. It says the heuristic cannot drop faster than the actual price of taking an edge. On ordinary grids, Manhattan distance with unit lower-bound edge costs is consistent.

Why care about the distinction?

With a consistent heuristic, A* does not need to reopen closed nodes in the usual graph-search form. The priority queue order behaves like Dijkstra on a reweighted graph. With an admissible but inconsistent heuristic, optimality can still be recovered, but implementations must be more careful about reopening nodes when a better route is found.

Dechter and Pearl sharpened the optimality story around A* and best-first search: the strong claims depend on the exact class of algorithms and on the heuristic conditions.3 The folk sentence “A* is optimal” is missing a contract clause.

Pearl’s broader treatment is still worth reading because it frames heuristics as explicit information about a problem, not as magic attached to a search loop.4

Make the Promise Turn Red

The lab below runs a real graph search on a deterministic four-neighbor grid. It computes a Dijkstra baseline for the optimal path, runs A* with the selected heuristic, and audits the heuristic against the true distance-to-goal map.

That last part is important. The red audit panel is not opinion. It computes the true remaining cost from every reachable cell and marks cells where \(h(n)\) is too large.

The maps are small on purpose:

  • swamp: a direct route crosses costly terrain;
  • rooms: walls and doors make the heuristic repeatedly revise its plan;
  • funnel: a map that tempts search toward a narrow wrong-looking route;
  • open: the friendly case where geometric distance is almost all the story.
Start Goal Explored Returned path Costly terrain

Deterministic toy graph. The audit panel computes exact remaining costs by a reverse Dijkstra pass, then compares the selected heuristic to those costs.

Try four moves.

The default starts slightly over the proof line on purpose. With Manhattan distance weighted at 1.20, the swamp map still returns the optimal cost 39.0, but it expands only 109 cells instead of Dijkstra’s 706 and the audit shows a maximum overstatement of 8.6. The answer is fine here. The proof is no longer doing the work.

First, set Heuristic weight to 0.00. This is Dijkstra. The heuristic audit is green because \(h=0\) never overstates anything, but the search does not know where the goal is.

Second, set Heuristic weight to 1.00 with Manhattan distance. The path cost should match the Dijkstra optimum, while the explored region usually shrinks. This is the classic A* bargain: less work, same answer, because the heuristic is a lower bound.

Third, set Swamp cost to 3.0 and Heuristic weight to about 1.80 on the swamp map. The audit panel turns red and the path gap can become positive. The search is not broken. You changed the algorithm into a weighted best-first policy whose speed is no longer backed by the optimality proof.

Fourth, try bad beacon. This heuristic rewards a tempting region of the map. It is useful as a cartoon of a learned or hand-tuned heuristic that has a local bias. The search may still succeed, but the audit shows where the promise is no longer a theorem.

Games Sometimes Buy the Lie On Purpose

In a game, “optimal” is not always the product requirement.

If a unit needs to move this frame, a slightly longer path found quickly may be better than a perfect path found too late. This is why weighted A*, greedy best-first search, hierarchical pathfinding, flow fields, navigation meshes, jump-point pruning, and cache reuse all show up in practice.

The point is not that inadmissible heuristics are bad. The point is that they are a different contract.

With admissible A*, the claim is:

if a path exists, the returned path has minimum cost

With weighted A*, the claim is closer to:

we are spending optimality margin to reduce search work

That may be a perfectly rational trade. But it should be instrumented as a trade. Track the cost gap on representative maps. Track expansions and latency. Track failure modes near costly terrain, doors, one-way edges, dynamic obstacles, and congestion. If the heuristic is learned, audit it against exact solutions on small instances.

The lab’s red panel is the small-instance audit.

Heuristic Belongs in the Spec

It is tempting to think of a heuristic as a performance detail.

It is not.

The heuristic states what the algorithm is allowed to ignore. A zero heuristic ignores nothing and searches broadly. A strong admissible heuristic ignores regions that cannot beat the current best path. A lying heuristic may ignore regions that actually contain the cheaper route.

This is why the implementation details matter:

  • Is the graph weighted or unweighted?
  • Are diagonal moves allowed?
  • Are terrain costs lower-bounded by the unit used in the heuristic?
  • Is the heuristic consistent, or can closed nodes need reopening?
  • Does the algorithm stop when the goal is popped, or does it continue to prove a bound?
  • Are tie breakers changing only work, or also behavior under an inadmissible heuristic?

None of these are aesthetic choices. They are proof obligations.

The Bill So Far and the Bill Ahead

Think of Dijkstra as expanding a circle of known cost from the start.

Think of A* as bending that circle toward the goal using a lower-bound estimate.

Think of weighted A* as pulling the circle with a stronger magnet. It may reach the goal faster. It may also pull past the cheaper detour.

The clean version is:

g is what you have paid
h is what you promise remains
f is the cheapest total bill this route can still claim

When the promise is honest, A* can be both directed and exact. When the promise is overconfident, it can still be useful, but it has become policy rather than proof.

That is the small discipline behind a lot of pathfinding work:

do not ask whether the heuristic is smart
ask what it is allowed to promise

  1. Edsger W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, 1959. DOI record: Springer. ↩

  2. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 1968. ↩

  3. Rina Dechter and Judea Pearl, [“Generalized Best-First Search Strategies and the Optimality of A”](https://ics.uci.edu/~dechter/publications/r0.pdf), *Journal of the ACM, 1985. ↩

  4. Judea Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984. A scanned copy is available from UAB. ↩