A* Search

Imagine standing in a maze and needing the shortest way out. One option is to flood outward in every direction at once, checking each new square in turn until you stumble onto the exit. That works — it is exactly what Dijkstra's algorithm and breadth-first search do — but it wastes enormous effort exploring squares that point away from the goal.

Now suppose you also have a compass and roughly know where the exit lies. You would naturally favor steps that head toward it. That single extra hint is the whole idea behind A* (pronounced "A-star").

A* keeps a running tally of two numbers for every square it considers: the cost to reach it so far, plus an estimate of the cost still remaining to the goal. It always expands the square with the smallest total. The estimate — the heuristic — turns aimless flooding into a search that leans toward the answer.

Below is a grid with a start (green), a goal (red) and a wall of obstacles. Press Run A* to watch the guided search expand cells, and Run blind search to see breadth-first search flood the grid instead. Both find a shortest path of the same length — but look at how many cells each one had to open.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{pick_search}}</div>
<div class="btns">
  <button id="astar" type="button">{{btn_astar}}</button>
  <button id="bfs" type="button">{{btn_bfs}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: repeat(15, 26px); gap: 2px; margin: .4rem 0; }
.cell { width: 26px; height: 26px; border-radius: 4px; background: #eef2f6; transition: background .12s; }
.cell.wall { background: #36404a; }
.cell.open { background: #bcd5ef; }
.cell.path { background: #f4c542; }
.cell.start { background: #2a9d4a; }
.cell.goal { background: #e63946; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

That gap is the heuristic at work. Blind search treats every direction as equally promising; A* uses its estimate of remaining distance to push toward the goal first. Crucially, both return a path of identical length — A* is faster without sacrificing optimality, as long as its estimate never overpromises.

What makes A* trustworthy is a theorem, not a hope.

• The score it minimizes. For each cell A* tracks f = g + h, where g is the real cost already paid to get there and h is the heuristic's estimate of what remains. It always expands the cell with the smallest f.
• Admissibility. The heuristic is admissible if it never overestimates the true remaining cost. A straight-line distance, for example, can never exceed the real walking distance around obstacles, so it is admissible.
• The guarantee (proven, 1968). Peter Hart, Nils Nilsson and Bertram Raphael proved that with an admissible heuristic, A* always returns a shortest path. With a slightly stronger property called consistency, it also never needs to re-open a cell — making it as efficient as any algorithm could be given the same heuristic.
• Two familiar extremes. Set h = 0 and A* never guesses — it becomes plain Dijkstra, optimal but slow. Make h a perfect oracle and A* walks straight to the goal. Real heuristics live in between: the better the estimate, the fewer cells opened.

So A* is not a gamble. Unlike the NP-complete problems where no fast exact method is known, finding a shortest path in a graph is firmly an easy (polynomial-time) problem — and A* is the practical, provably optimal way to solve it.

"Find the cheapest path through an enormous space" describes a surprising number of real problems, and A* is the workhorse for most of them:

• Maps and navigation: routing engines use A* and its variants to find driving directions in road networks with millions of intersections.
• Video games: a character crossing a level toward you is almost always running A* on a navigation grid or mesh.
• Robotics: a vacuum or warehouse robot plans collision-free routes by searching a grid of its surroundings.
• Puzzles and planning: sliding-tile puzzles, Rubik's-cube solvers and logistics planners frame their states as a graph and let A* find the shortest solution.

The unifying trick is always the heuristic — a cheap, never-overestimating guess. Pick a good one and A* explores a tiny sliver of the space. Closely related searches show up in shortest paths and route-finding problems like the traveling salesman.

A* captures a deep and practical lesson: a good guess, used carefully, can make a hard-looking search dramatically cheaper without giving up correctness. The whole method rests on one humble promise — never overestimate the distance still to go — and from that single rule comes a proof that the path it returns is always the shortest.

That is why, more than half a century after Hart, Nilsson and Raphael described it in 1968, A* still steers the cars on your map, the enemies in your games and the robots on warehouse floors. Sometimes the smartest thing an algorithm can do is have a sensible hunch — and know exactly how much to trust it.