patternjavascriptModerate

A* pathfinding uses a heuristic to guide BFS toward the goal faster

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

a stara* pathfindingheuristic searchmanhattan distancegrid pathfindingadmissible heuristic

Problem

Dijkstra explores nodes in all directions equally. For grid pathfinding (games, maps), exploring toward the goal is much more efficient. A* combines actual cost with an estimated cost to goal to prioritize promising paths.

Solution

A* is Dijkstra with an added heuristic h(node) estimating cost to goal. Priority queue key is f = g + h, where g = actual cost from start, h = estimated cost to goal. For grids, Manhattan distance (no diagonals) or Euclidean distance are common admissible heuristics.

Why

An admissible heuristic never overestimates the true cost. This guarantees A finds the optimal path while exploring far fewer nodes than Dijkstra. With a perfect heuristic, A visits only the optimal path nodes.

Gotchas

Heuristic must be admissible (never overestimate) for guaranteed optimality — Euclidean distance is admissible for grid movement
A consistent (monotone) heuristic avoids reopening nodes and is strictly stronger than admissible
For weighted graphs with non-unit costs, g must track actual cost, not hop count

Code Snippets

A* pathfinding on a 2D grid

// A* on a grid (0=open, 1=wall)
function aStar(grid, start, goal) {
  const [gr, gc] = goal;
  const h = (r, c) => Math.abs(r - gr) + Math.abs(c - gc); // Manhattan
  const key = (r, c) => `${r},${c}`;

  const open = new MinHeap(); // [f, g, r, c]
  open.push([h(...start), 0, ...start]);
  const gScore = new Map([[key(...start), 0]]);
  const parent = new Map();

  while (open.size) {
    const [, g, r, c] = open.pop();
    if (r === gr && c === gc) {
      // reconstruct path
      const path = [];
      let cur = key(r, c);
      while (cur) { path.push(cur); cur = parent.get(cur); }
      return path.reverse();
    }
    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 >= grid.length || nc >= grid[0].length || grid[nr][nc]) continue;
      const ng = g + 1;
      const nk = key(nr, nc);
      if (ng < (gScore.get(nk) ?? Infinity)) {
        gScore.set(nk, ng);
        parent.set(nk, key(r, c));
        open.push([ng + h(nr, nc), ng, nr, nc]);
      }
    }
  }
  return null; // no path
}

Context

Game pathfinding, map routing, robot navigation, or any grid/graph search with a known goal

Revisions (0)

No revisions yet.