Introduction

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.

Race the Heuristic

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">Green is the start, red is the goal, dark cells are walls. Run each search and watch how many cells it has to <b>open</b>. Both find a shortest path of the same length — A* just opens far fewer cells by aiming at the goal.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Pick a search to run.</div>
<div class="btns">
  <button id="astar" type="button">Run A*</button>
  <button id="bfs" type="button">Run blind search</button>
  <button id="reset" type="button" class="ghost">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; }

// A* vs blind breadth-first search on a grid. Moves are 4-directional (no diagonals), each step costs 1. The heuristic h is the Manhattan distance to the goal, which can never overestimate the true 4-directional distance -> it is ADMISSIBLE, so A* is guaranteed to return a shortest path (Hart, Nilsson & Raphael, 1968).
const W = 15, H = 13;
const START = [1, 6], GOAL = [13, 6];
// A wall with a single gap, forcing both searches around it.
const walls = new Set();
for (let y = 1; y < H - 1; y++) { if (y !== 9) walls.add(7 + ',' + y); }
const key = (x, y) => x + ',' + y;
const isWall = (x, y) => walls.has(key(x, y));
const inBounds = (x, y) => x >= 0 && x < W && y >= 0 && y < H;
const manhattan = (x, y) => Math.abs(x - GOAL[0]) + Math.abs(y - GOAL[1]);
function neighbors(x, y) {
  const out = [];
  for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
    const nx = x + dx, ny = y + dy;
    if (inBounds(nx, ny) && !isWall(nx, ny)) out.push([nx, ny]);
  }
  return out;
}
// Reconstruct the path from a cameFrom map.
function rebuild(cameFrom) {
  const path = []; let cur = key(GOAL[0], GOAL[1]);
  while (cur) { path.push(cur); cur = cameFrom[cur]; }
  return path.reverse();
}
// Breadth-first search: explores in pure distance order, ignoring where the goal is.
function bfs() {
  const startK = key(START[0], START[1]), goalK = key(GOAL[0], GOAL[1]);
  const queue = [START]; const cameFrom = { [startK]: null };
  const opened = new Set([startK]); let expanded = 0;
  while (queue.length) {
    const [x, y] = queue.shift(); expanded++;
    if (key(x, y) === goalK) return { path: rebuild(cameFrom), opened, expanded };
    for (const [nx, ny] of neighbors(x, y)) {
      const k = key(nx, ny);
      if (!opened.has(k)) { opened.add(k); cameFrom[k] = key(x, y); queue.push([nx, ny]); }
    }
  }
  return { path: null, opened, expanded };
}
// A*: expands the cell with the lowest f = g + h first.
function astar() {
  const startK = key(START[0], START[1]), goalK = key(GOAL[0], GOAL[1]);
  const g = { [startK]: 0 }, cameFrom = { [startK]: null };
  const openList = [[manhattan(START[0], START[1]), START]];
  const opened = new Set([startK]); let expanded = 0;
  while (openList.length) {
    // Pick the smallest f (small list, linear scan is fine for a demo).
    let bi = 0; for (let i = 1; i < openList.length; i++) if (openList[i][0] < openList[bi][0]) bi = i;
    const [, [x, y]] = openList.splice(bi, 1)[0]; expanded++;
    if (key(x, y) === goalK) return { path: rebuild(cameFrom), opened, expanded };
    for (const [nx, ny] of neighbors(x, y)) {
      const k = key(nx, ny), tentative = g[key(x, y)] + 1;
      if (!(k in g) || tentative < g[k]) {
        g[k] = tentative; cameFrom[k] = key(x, y); opened.add(k);
        openList.push([tentative + manhattan(nx, ny), [nx, ny]]);
      }
    }
  }
  return { path: null, opened, expanded };
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function render(opened, path) {
  const g = document.getElementById('grid'); g.innerHTML = '';
  const openedS = opened || new Set(); const pathS = new Set(path || []);
  for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) {
    const d = document.createElement('div'); const k = key(x, y); let cls = 'cell';
    if (isWall(x, y)) cls += ' wall';
    else if (openedS.has(k)) cls += ' open';
    if (pathS.has(k)) cls += ' path';
    if (k === key(START[0], START[1])) cls = 'cell start';
    else if (k === key(GOAL[0], GOAL[1])) cls = 'cell goal';
    d.className = cls; g.appendChild(d);
  }
}
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
function show(name, res) {
  render(res.opened, res.path);
  const len = res.path ? res.path.length - 1 : 0;
  setStatus(fmt('%name% opened %cells% cells, found a path of length %length%.', { name: name, cells: res.opened.size, length: len }), 'ok');
  console.log(name, '| opened', res.opened.size, '| path length', len);
}
document.getElementById('astar').addEventListener('click', () => show('A*', astar()));
document.getElementById('bfs').addEventListener('click', () => show('Blind search', bfs()));
document.getElementById('reset').addEventListener('click', () => { render(null, null); setStatus('Pick a search to run.', ''); });
render(null, null);
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/a-star/Content licensed under CC BY-NC 4.0.