The Heuristic That Lets Search Hurry

The A* sketch makes route-finding legible as a contest between two search styles. Draw walls, drag the endpoints, and compare how quickly the blue heuristic-guided frontier converges against the broader orange sweep of Dijkstra's algorithm.

A* is one of those algorithms whose fame comes from practical use, then keeps widening because the idea is so clean. Peter Hart, Nils Nilsson, and Bertram Raphael published it in 1968 during the Stanford Research Institute's Shakey project, where route-finding had to serve a robot that could perceive a room, plan movement, and rearrange simple objects. SRI still describes Shakey as the first mobile robot able to perceive and reason about its surroundings. The historical point matters because A* did not emerge as a toy exercise in graph theory. It came out of a concrete planning problem: how do you search fast enough to move through the world without checking every possible route first.

The answer was to combine accumulated cost with a guess about what remains. That is the whole famous formula, and the sketch turns it into visible behavior. Dijkstra's algorithm expands outward with admirable discipline because it only trusts the cost already paid. A* keeps that cost and adds a heuristic estimate of the remaining distance, so the frontier leans toward the goal from the start. Wikipedia's historical summary still gets the basic distinction right when it describes A* as an extension of Dijkstra guided by heuristics. In practice, that means fewer explored cells whenever the guess is decent. The algorithm is still searching. It is simply searching with directional pressure.

You can see the pressure encoded directly in gallery/astar.html:

function heuristic(a,b){
  return Math.abs(a.r-b.r)+Math.abs(a.c-b.c);
}

fScore[nk]=tentG+(useHeuristic?heuristic(nb,endCell):0);
open.push({r:nb.r,c:nb.c,f:fScore[nk]});

The heuristic here is Manhattan distance, which fits a grid where movement is measured cell by cell. Once that estimate gets added to tentG, the priority queue stops treating every frontier node as equally urgent. Some nodes feel closer to the future than others. The sketch's blue expansion narrows into a directed wedge for exactly that reason. When you flip to compare mode and watch orange Dijkstra cells spill across the map beside it, the conceptual difference becomes visual before it becomes formal.

I like this artifact because it keeps the algorithm honest. It does not romanticize A* as magic. You can draw a maze that forces the search to backtrack, and you can watch diagonal movement complicate the route with corner-cutting checks and weighted steps. Yet the central insight still holds. A heuristic is a disciplined hunch. When the hunch matches the structure of the space, search starts to look less like exhaustive inspection and more like informed movement. That is why A* still sits at the center of game AI, robotics, and teaching demos. It makes intelligence look procedural in the best way, as a matter of paying for what you already know while estimating what the world is likely to demand next.