A* Pathfinding Algorithm —
From Theory to JavaScript

1. The Shortest-Path Problem

Given a graph G = (V, E) where each edge (u, v) has a non-negative cost w(u,v), find the minimum-cost path from a start node s to a goal node g.

For game grids the graph is implicit: cells are nodes, orthogonal/diagonal neighbours are edges with cost 1 (or √2 for diagonals). Obstacles are simply absent edges. The same A* code works on explicit graphs (road networks, metro maps) by providing a neighbour list instead of a grid lookup.

2. The A* Algorithm

A* assigns each node n a priority score:

The algorithm maintains two sets:

• Open set (priority queue) — discovered nodes not yet fully evaluated, ordered by f.
• Closed set — nodes already evaluated; we will never need to revisit them (for admissible h).

At each step A* pops the node with the lowest f from the open set, expands its neighbours, and for each neighbour computes a candidate g = g(current) + w(current, neighbour). If this is better than any previously known path to that neighbour, update and enqueue it.

Visual trace on a 5×5 grid

S = Start (0,0), G = Goal (4,4), walls in grey. Numbers in cells show the f-score. Blue = closed (already expanded), green = open (in queue), orange = final path.

3. Heuristic Functions

A heuristic h(n) is admissible if h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost from n to the goal. Admissibility guarantees A* finds the optimal path. A consistent (monotone) heuristic also satisfies h(n) ≤ w(n,n') + h(n') for every edge — this means the f-value never decreases along a path, simplifying the closed-set logic.

4. JavaScript Implementation

The following implementation works on a flat array grid where grid[y * width + x] is true for walkable cells. It returns the optimal path as an array of {x, y} objects, or null if no path exists.

// MinHeap — simple binary heap keyed on .f
class MinHeap {
  constructor() { this.data = []; }
  push(node) {
    this.data.push(node);
    this._bubbleUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._siftDown(0); }
    return top;
  }
  get size() { return this.data.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p].f <= this.data[i].f) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l].f < this.data[min].f) min = l;
      if (r < n && this.data[r].f < this.data[min].f) min = r;
      if (min === i) break;
      [this.data[min], this.data[i]] = [this.data[i], this.data[min]];
      i = min;
    }
  }
}

// Octile distance heuristic (8-directional, diagonal cost = √2)
function octile(ax, ay, bx, by) {
  const dx = Math.abs(ax - bx), dy = Math.abs(ay - by);
  return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy);
}

/**
 * @param {boolean[]} grid  - flat array, true = walkable
 * @param {number}    width - grid width
 * @param {{x,y}}     start
 * @param {{x,y}}     goal
 * @param {boolean}   [diag=true] - allow diagonal movement
 * @returns {{x,y}[]|null}
 */
function aStar(grid, width, start, goal, diag = true) {
  const height = grid.length / width;
  const key = (x, y) => y * width + x;

  const gScore = new Float32Array(grid.length).fill(Infinity);
  const cameFrom = new Int32Array(grid.length).fill(-1);
  const closed  = new Uint8Array(grid.length);

  const heap = new MinHeap();
  const sk = key(start.x, start.y);
  gScore[sk] = 0;
  heap.push({ x: start.x, y: start.y, f: octile(start.x, start.y, goal.x, goal.y) });

  const dirs = diag
    ? [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]
    : [[0,-1],[-1,0],[1,0],[0,1]];

  while (heap.size) {
    const cur = heap.pop();
    if (cur.x === goal.x && cur.y === goal.y) return reconstruct(cameFrom, width, key(cur.x, cur.y));
    const ck = key(cur.x, cur.y);
    if (closed[ck]) continue;
    closed[ck] = 1;
    for (const [dx, dy] of dirs) {
      const nx = cur.x + dx, ny = cur.y + dy;
      if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
      const nk = key(nx, ny);
      if (!grid[nk] || closed[nk]) continue;
      const moveCost = (dx !== 0 && dy !== 0) ? Math.SQRT2 : 1;
      const tentG = gScore[ck] + moveCost;
      if (tentG < gScore[nk]) {
        gScore[nk] = tentG;
        cameFrom[nk] = ck;
        heap.push({ x: nx, y: ny, f: tentG + octile(nx, ny, goal.x, goal.y) });
      }
    }
  }
  return null; // no path
}

function reconstruct(cameFrom, width, goalKey) {
  const path = [];
  let k = goalKey;
  while (k !== -1) {
    path.push({ x: k % width, y: Math.floor(k / width) });
    k = cameFrom[k];
  }
  return path.reverse();
}

5. Priority Queue & Tie-Breaking

The efficiency of A* depends entirely on the priority queue. A binary min-heap gives O(log N) push and pop. For very large grids, a Fibonacci heap gives amortised O(1) decrease-key but is rarely worth the implementation complexity in practice.

Tie-breaking is crucial for performance. When many nodes share the same f-score, A* explores them in arbitrary order. Adding a small cross-product tie-breaker (prefer nodes whose current direction aligns with the start→goal vector) reduces explored nodes by 30–50% on open terrain:

// Nudge f slightly toward the straight-line corridor
function hTieBreak(nx, ny, gx, gy, sx, sy) {
  const dx1 = nx - gx, dy1 = ny - gy;
  const dx2 = sx - gx, dy2 = sy - gy;
  const cross = Math.abs(dx1*dy2 - dx2*dy1);
  return octile(nx, ny, gx, gy) + cross * 0.001;
}

6. Dijkstra, BFS and Weighted A*

A* is a generalisation. Setting h to different values recovers well-known algorithms:

In game AI, Hierarchical Pathfinding A* (HPA*) builds a two-level hierarchy: cluster-level abstract graph + within-cluster paths. Long-range queries run on the small abstract graph; fine paths are only computed near the agent. This is how RTS games handle hundreds of units on 512×512 maps in real time.

Jump Point Search (JPS) exploits uniformly-weighted grid symmetry: it skips redundant symmetric paths and jumps to "interesting" nodes, reducing explored nodes by 10–40× compared to plain A* on open grids with no preprocessing.

7. Complexity & Practical Notes

• Time complexity: O(b^d) in the worst case where b = branching factor, d = depth. With a perfect heuristic (h = h*) only nodes on the optimal path are expanded.
• Space complexity: O(b^d) — the open set can hold exponentially many nodes. Memory-bounded variants (SMA*, RBFS) limit this at the cost of re-expansion.
• Admissibility vs. Consistency: Consistency (monotonicity) implies admissibility and means each node is expanded at most once. Always prefer consistent heuristics.
• Dynamic graphs: D* Lite (dynamic A*) efficiently re-plans when edge weights change (e.g. new obstacles discovered by a robot sensor). It propagates changes backward from the goal rather than replanning from scratch.
• Precomputed tables: Pattern Databases (PDB) precompute h for subproblems, giving tighter lower bounds. Widely used in puzzle solving (15-puzzle, Rubik's cube).

Related Content