iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Pathfinding (A*)

By · Reviewed & last updated · Part of Game Development Tutorial

A* (A-star) finds the shortest path from start to goal on a graph by combining the distance walked (g) with a heuristic estimate to the goal (h). Done right it is exact and dramatically faster than Dijkstra; done wrong (a non-admissible heuristic) it returns suboptimal paths. For 2D grids the heuristic is Manhattan distance (no diagonals) or octile (with diagonals).

A* on a tile grid with a min-heap and reconstruction

EXAMPLE
// A* on a 2D grid. Tiles: 0 = walkable, 1 = wall.
// Start and goal are [row, col].

function astar(grid, start, goal) {
  const rows = grid.length, cols = grid[0].length;
  const key = (r, c) => r * cols + c;

  // Octile heuristic: optimal on grids with 8 neighbours (cost 1 ortho, √2 diag).
  const h = (r, c) => {
    const dr = Math.abs(r - goal[0]), dc = Math.abs(c - goal[1]);
    return Math.max(dr, dc) + (Math.SQRT2 - 1) * Math.min(dr, dc);
  };

  const open = new MinHeap((a, b) => a.f - b.f);
  const gScore = new Map();
  const came = new Map();

  gScore.set(key(...start), 0);
  open.push({ r: start[0], c: start[1], f: h(...start) });

  const NEIGHBOURS = [
    [-1, 0, 1],  [1, 0, 1],  [0, -1, 1],  [0, 1, 1],
    [-1, -1, Math.SQRT2], [-1, 1, Math.SQRT2],
    [ 1, -1, Math.SQRT2], [ 1, 1, Math.SQRT2],
  ];

  while (open.size) {
    const cur = open.pop();
    if (cur.r === goal[0] && cur.c === goal[1]) {
      // reconstruct
      const path = [[cur.r, cur.c]];
      let k = key(cur.r, cur.c);
      while (came.has(k)) {
        const prev = came.get(k);
        path.unshift([prev.r, prev.c]);
        k = key(prev.r, prev.c);
      }
      return path;
    }

    for (const [dr, dc, cost] of NEIGHBOURS) {
      const nr = cur.r + dr, nc = cur.c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (grid[nr][nc] === 1) continue;
      // Block corner cutting through walls when moving diagonally
      if (dr && dc && (grid[cur.r][nc] === 1 || grid[nr][cur.c] === 1)) continue;

      const tentative = (gScore.get(key(cur.r, cur.c)) ?? Infinity) + cost;
      const nKey = key(nr, nc);
      if (tentative < (gScore.get(nKey) ?? Infinity)) {
        came.set(nKey, { r: cur.r, c: cur.c });
        gScore.set(nKey, tentative);
        open.push({ r: nr, c: nc, f: tentative + h(nr, nc) });
      }
    }
  }
  return null;   // unreachable
}

// Tiny binary heap
class MinHeap {
  constructor(cmp) { this.a = []; this.cmp = cmp; }
  get size() { return this.a.length; }
  push(x) {
    this.a.push(x);
    for (let i = this.a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (this.cmp(this.a[i], this.a[p]) < 0) {
        [this.a[i], this.a[p]] = [this.a[p], this.a[i]]; i = p;
      } else break;
    }
  }
  pop() {
    const top = this.a[0], last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < this.a.length && this.cmp(this.a[l], this.a[s]) < 0) s = l;
        if (r < this.a.length && this.cmp(this.a[r], this.a[s]) < 0) s = r;
        if (s === i) break;
        [this.a[i], this.a[s]] = [this.a[s], this.a[i]]; i = s;
      }
    }
    return top;
  }
}

// Usage
const grid = [
  [0,0,0,1,0],
  [1,1,0,1,0],
  [0,0,0,0,0],
  [0,1,1,1,0],
  [0,0,0,0,0],
];
console.log(astar(grid, [0, 0], [4, 4]));

Why it matters

Get the heuristic admissible (never overestimates the true cost) and your A* is exact; get it consistent (monotonic with edge cost) and you can skip the closed-set check, which is a nice constant-factor win. Manhattan, Euclidean, and Octile all qualify for grids — invented per-game heuristics often do not, and silently return wonky paths.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// A* on a grid. f(n) = g(n) + h(n).
// h() is the heuristic — Manhattan distance for 4-direction, Chebyshev for 8.
Try it Yourself »

Exercise

Pathfinding algorithm with f(n) = g(n) + h(n).

Discussion

Loading…