A* Pathfinding

How A* works

For each node n, A* tracks two values:

• g(n) — the actual cost from the start to n along the best known path.
• h(n) — the heuristic estimate of the remaining cost from n to the goal.

The total estimated cost through n is f(n) = g(n) + h(n). A* maintains a min-priority queue keyed on f-values and repeatedly extracts the node with the smallest f. Just like Dijkstra, but with the heuristic biasing the order of expansion toward the goal.

The algorithm:

1. Initialize: g(start) = 0, push start onto the open queue.
2. Pop the lowest-f node n. If n is the goal, reconstruct the path and return.
3. For each neighbor v of n: compute tentative g(v) = g(n) + cost(n, v). If this is better than v's known g, update g(v), set parent(v) = n, and push v onto the queue.
4. Repeat from 2 until the queue is empty (no path) or the goal is reached.

Heuristic quality determines performance

The "informedness" of the heuristic determines how much faster A* is than Dijkstra:

Heuristic	Property	A* behavior
h(n) = 0	Admissible (trivially)	Reduces to Dijkstra — explores in concentric rings
h(n) = 0.5 × true cost	Admissible	Slightly biased toward goal, expands ~50% as many nodes
h(n) = true cost	Admissible (perfect)	Expands only optimal-path nodes
h(n) > true cost (overestimating)	Inadmissible	May find suboptimal path; faster but wrong
h(n) = -1 × true cost	Anti-admissible (degenerate)	Expands away from the goal — pathological

The closer h(n) gets to the true remaining cost without exceeding it, the fewer nodes A* expands. Designing good heuristics is its own subfield — domain knowledge often produces orders-of-magnitude speedups.

Grid pathfinding heuristics

Movement allowed	Edge cost	Heuristic	Formula
4-directional (N/S/E/W)	1 per step	Manhattan	|dx| + |dy|
8-directional	1 per step (incl. diag)	Chebyshev	max(|dx|, |dy|)
8-directional	1 cardinal, √2 diagonal	Octile	max + (√2 − 1) × min
Free 2D	Distance	Euclidean	√(dx² + dy²)
Free 2D, but on a sphere	Great-circle distance	Haversine	2r·arcsin(√(...))

Using the wrong heuristic for the movement model breaks admissibility. If you allow diagonal moves on a grid but use Manhattan distance, the heuristic overestimates and A* may miss the optimal diagonal-heavy path.

When to use A*

• Game pathfinding. The most common use. A* with Manhattan or octile distance on tile-based maps gives instant pathfinding for thousands of units.
• Robot motion planning. Sample-based motion planning often uses A* on a discretized configuration space, with heuristics derived from straight-line distance.
• Word ladders and puzzle solving. Rubik's cube, sliding puzzles, n-queens — when the state space is huge but you can estimate "how far from solved." A* with pattern-database heuristics solves Rubik's cube in seconds.
• GPS navigation with traffic data. Edge weights are travel times. Heuristic is straight-line travel time at maximum speed (admissible: real travel time can never be less). A* explores far fewer roads than full Dijkstra on continent-scale graphs.

JavaScript implementation (grid pathfinding)

function aStar(grid, start, goal) {
  const [sr, sc] = start, [gr, gc] = goal;
  const rows = grid.length, cols = grid[0].length;
  const key = (r, c) => r * cols + c;
  const heuristic = (r, c) => Math.abs(r - gr) + Math.abs(c - gc); // Manhattan

  const open = new MinHeap(); // see heap article
  open.push([heuristic(sr, sc), 0, sr, sc]); // [f, g, r, c]

  const gScore = new Map([[key(sr, sc), 0]]);
  const cameFrom = new Map();

  while (open.size()) {
    const [f, g, r, c] = open.pop();
    if (r === gr && c === gc) {
      // Reconstruct path
      const path = [[r, c]];
      let k = key(r, c);
      while (cameFrom.has(k)) {
        const [pr, pc] = cameFrom.get(k);
        path.unshift([pr, pc]);
        k = key(pr, pc);
      }
      return path;
    }
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (grid[nr][nc] === 1) continue; // 1 = obstacle
      const tentativeG = g + 1;
      const nk = key(nr, nc);
      if (tentativeG < (gScore.get(nk) ?? Infinity)) {
        gScore.set(nk, tentativeG);
        cameFrom.set(nk, [r, c]);
        open.push([tentativeG + heuristic(nr, nc), tentativeG, nr, nc]);
      }
    }
  }
  return null; // no path
}

Python implementation

import heapq

def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    gr, gc = goal
    h = lambda r, c: abs(r - gr) + abs(c - gc)  # Manhattan

    open_heap = [(h(sr, sc), 0, sr, sc)]  # (f, g, r, c)
    g_score = {(sr, sc): 0}
    came_from = {}

    while open_heap:
        f, g, r, c = heapq.heappop(open_heap)
        if (r, c) == (gr, gc):
            path = [(r, c)]
            while (r, c) in came_from:
                r, c = came_from[(r, c)]
                path.append((r, c))
            return path[::-1]
        for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols): continue
            if grid[nr][nc] == 1: continue
            tg = g + 1
            if tg < g_score.get((nr, nc), float('inf')):
                g_score[(nr, nc)] = tg
                came_from[(nr, nc)] = (r, c)
                heapq.heappush(open_heap, (tg + h(nr, nc), tg, nr, nc))
    return None

Common bugs and edge cases

• Inadmissible heuristic. The most common bug — using Manhattan when diagonals are allowed, using Euclidean when grid-only movement is allowed. The algorithm runs and returns a path, just not the shortest.
• Forgetting to update parents on a better path. If a node v is reached via a shorter path later, you must update parent(v) — otherwise path reconstruction returns a non-optimal route. The tentativeG < gScore.get(v) check is what gates this.
• Re-expanding closed nodes when h is inconsistent. With an inconsistent (but admissible) heuristic, A* may need to re-open closed nodes to maintain optimality. Using a "closed set" that prohibits re-expansion silently produces suboptimal paths. Use a consistent heuristic or skip the closed set.
• Stale heap entries. When a node's g is improved, you push a new entry — the old one is stale. Skip it on pop with if g > gScore.get(node): continue. Forgetting this leads to processing the same node multiple times.
• Tie-breaking that flips path choice between runs. Two paths with equal f-value tie in the heap. Order of expansion depends on heap implementation. Add a deterministic tiebreaker (insertion counter, prefer smaller h) for reproducible paths.