Game Dev Mechanics: A* Pathfinding — How It Works

A* Pathfinding: The Algorithm Powering Every Smart NPC

In any game with intelligent character movement, whether a strategy unit routing around terrain, a stealth enemy circling to flank, or hundreds of RTS soldiers crossing a battlefield, you are almost certainly watching A* (pronounced "A-star") in action. The algorithm is provably optimal and fast enough for real-time use, which is why it has been the standard in game pathfinding for decades.

In this article we will break down exactly how A* works, implement it from scratch in JavaScript, understand when and why it outperforms other approaches, and explore how modern games extend the algorithm to handle 3D navigation meshes, dynamic obstacles, and massive open worlds.

The Problem: Finding the Shortest Path

Pathfinding begins with a graph, a set of nodes (positions) connected by edges (possible movements). In most 2D games this is a tile grid where each cell is a node and edges connect adjacent cells. In 3D games it is often a navigation mesh (navmesh), where triangles form the walkable surface.

The naive approach, enumerating every possible path and picking the shortest, is computationally hopeless. For a modest 30×20 grid the search space is astronomically large. We need something smarter.

Before A*, the standard was Dijkstra's algorithm, which finds the shortest path by exploring all nodes in order of cumulative distance from the start. It is correct but expands outward in all directions equally, with no concept of "the goal is over there." A* adds one insight: a reasonable guess about how far away the goal is can dramatically reduce the nodes we need to explore.

The Core Formula: $f(n) = g(n) + h(n)$

A* assigns a priority score to every node it considers, as the sum of two values:

• $g(n)$ — The exact cost from the start to node $n$, accumulated as we explore.
• $h(n)$ — The heuristic estimate of the cost from $n$ to the goal. An educated guess, not the true value.

$$f(n) = g(n) + h(n)$$

A* always expands the node with the lowest $f$ score next. By including $h(n)$, it preferentially explores nodes that are both cheap to reach and close to the goal:

• $h(n) = 0$ always → degenerates into Dijkstra's algorithm. Correct but slow.
• $g(n)$ ignored → Greedy Best-First Search. Fast but not guaranteed optimal.
• A* balances both: it finds shortest paths while exploring far fewer nodes than Dijkstra's.

Choosing the Right Heuristic

The heuristic $h(n)$ must be admissible: it must never overestimate the true cost to the goal. An admissible heuristic is always optimistic. For grid-based movement:

Manhattan Distance (4-directional grids)

$$h(n) = |n_x - goal_x| + |n_y - goal_y|$$

The sum of absolute horizontal and vertical differences. Since you must travel at least this many steps, it never overestimates. Perfect for up/down/left/right movement with uniform cost.

Chebyshev Distance (8-directional, equal costs)

$$h(n) = \max(|n_x - goal_x|,\; |n_y - goal_y|)$$

The maximum of the absolute differences. Tight and efficient for 8-directional movement where diagonal moves cost the same as cardinal moves.

Octile Distance (8-directional, diagonal costs $\sqrt{2}$)

Let $dx = |n_x - goal_x|$ and $dy = |n_y - goal_y|$:

$$h(n) = (dx + dy) + (\sqrt{2} - 2) \cdot \min(dx,\, dy)$$

This exactly equals the minimum possible movement cost when diagonal moves cost $\sqrt{2}$ and cardinal moves cost $1$, making it a perfect admissible heuristic for this very common movement model.

The Algorithm, Step by Step

A* maintains an open set (nodes discovered but not yet fully evaluated) and a closed set (nodes already evaluated). Here is the complete logic:

function aStar(grid, start, end) {
  const openSet = new MinHeap();   // ordered by f score
  const gScore  = new Map();       // cost from start to each node
  const cameFrom = new Map();      // for path reconstruction

  gScore.set(start, 0);
  openSet.push(start, heuristic(start, end));

  while (!openSet.isEmpty()) {
    const current = openSet.pop();  // lowest-f node

    if (current === end) {
      return reconstructPath(cameFrom, end);
    }

    for (const { node: neighbor, cost } of getNeighbors(current, grid)) {
      const tentativeG = gScore.get(current) + cost;

      if (tentativeG < (gScore.get(neighbor) ?? Infinity)) {
        cameFrom.set(neighbor, current);
        gScore.set(neighbor, tentativeG);
        const f = tentativeG + heuristic(neighbor, end);
        openSet.pushOrUpdate(neighbor, f);
      }
    }
  }

  return null; // no path exists
}

function reconstructPath(cameFrom, current) {
  const path = [];
  while (cameFrom.has(current)) {
    path.unshift(current);
    current = cameFrom.get(current);
  }
  path.unshift(current); // include start
  return path;
}

A Complete JavaScript Implementation

Here is a practical, self-contained implementation for a tile grid supporting 8-directional movement:

class MinHeap {
  constructor() { this.data = []; }
  get size() { return this.data.length; }
  push(f, key) {
    this.data.push([f, key]);
    this._up(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._down(0); }
    return top;
  }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p][0] <= this.data[i][0]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.data.length;
    while (true) {
      let s = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l][0] < this.data[s][0]) s = l;
      if (r < n && this.data[r][0] < this.data[s][0]) s = r;
      if (s === i) break;
      [this.data[i], this.data[s]] = [this.data[s], this.data[i]];
      i = s;
    }
  }
}

// grid: 2D array where 0 = walkable, 1 = wall
function findPath(grid, sr, sc, er, ec) {
  const ROWS = grid.length, COLS = grid[0].length;
  const N    = ROWS * COLS;
  const key  = (r, c) => r * COLS + c;

  const g       = new Float32Array(N).fill(Infinity);
  const from    = new Int32Array(N).fill(-1);
  const closed  = new Uint8Array(N);
  const heap    = new MinHeap();

  // 4 cardinal + 4 diagonal directions with costs
  const DIRS = [
    [-1,0,1],[1,0,1],[0,-1,1],[0,1,1],
    [-1,-1,1.414],[-1,1,1.414],[1,-1,1.414],[1,1,1.414]
  ];
  const h = (r, c) => Math.abs(r - er) + Math.abs(c - ec);

  const sk = key(sr, sc);
  g[sk] = 0;
  heap.push(h(sr, sc), sk);

  while (heap.size > 0) {
    const [, ck] = heap.pop();
    if (closed[ck]) continue;
    closed[ck] = 1;

    const cr = Math.floor(ck / COLS), cc = ck % COLS;
    if (cr === er && cc === ec) {
      // Reconstruct path
      const path = [];
      let cur = ck;
      while (cur !== -1) {
        path.push({ r: Math.floor(cur/COLS), c: cur%COLS });
        cur = from[cur];
      }
      return path.reverse();
    }

    for (const [dr, dc, cost] of DIRS) {
      const nr = cr+dr, nc = cc+dc;
      if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
      if (grid[nr][nc] === 1) continue;
      const nk = key(nr, nc);
      if (closed[nk]) continue;
      const tg = g[ck] + cost;
      if (tg < g[nk]) {
        from[nk] = ck;
        g[nk]    = tg;
        heap.push(tg + h(nr, nc), nk);
      }
    }
  }
  return null; // unreachable
}

Why the Priority Queue Is Critical

The open set data structure determines A*'s real-world performance. At every step we need the node with the lowest $f$ score:

• Sorted array: $O(n)$ insertion. Fine for tiny grids (under ~100 nodes).
• Binary min-heap: $O(\log n)$ insertion and removal. The standard choice for most games.
• Bucket queue: Near-$O(1)$ when costs are small integers and bounded. Used in some high-performance tile-grid engines.
• Fibonacci heap: Theoretically $O(1)$ amortized decrease-key, but high constant factors make it slower in practice.

For game grids up to roughly 50,000 cells a binary min-heap is excellent. For larger worlds, hierarchical approaches become necessary (see below).

Real-World Game Examples

The Sims series routes characters through homes and neighborhoods using A* on a grid, augmented with cost maps that make crowded or narrow corridors more expensive. This causes Sims to prefer wider, more natural-feeling routes rather than always picking the geometrically shortest path.

Minecraft uses A* for all mob pathfinding, assigning different movement costs to block types: water is slow, lava is forbidden, ladders have special handling. The varying costs mean pure Manhattan distance is not quite admissible, so Minecraft tunes its heuristic weight for good performance over strict optimality.

Dragon Age: Origins was one of the first mainstream RPGs to use navmesh pathfinding. A* runs on the graph of polygon portals in the navmesh, and the raw path is then smoothed with a funnel algorithm to produce straight-line movement within each polygon rather than zig-zagging from centroid to centroid.

StarCraft II uses flow fields for large army movement, but individual unit pathfinding and strategic AI still rely on A* as a core component. Influence maps layered on top of the pathfinding graph allow units to prefer tactically safer routes.

Advanced Techniques and Variants

Weighted A* ($WA^*$)

Multiply the heuristic by a weight $w > 1$:

$$f(n) = g(n) + w \cdot h(n)$$

This produces faster but potentially suboptimal paths. The result is guaranteed no worse than $w$ times optimal. In games where "good enough, fast" beats "perfect but slow," $WA^*$ with $w \approx 1.1$–$2.0$ is extremely practical and nearly indistinguishable to players.

Hierarchical Pathfinding (HPA*)

For large maps, precompute a high-level graph of "entrance" connections between sectors. A* first runs on this coarse graph, then fills in low-level paths within each sector on demand. Path time drops from $O(N)$ for the full map to roughly $O(K)$ where $K$ is the number of sectors, a significant improvement for open-world games.

Jump Point Search (JPS)

An optimization for uniform-cost grids that can speed up A* by 10–40× with no change to the output path. JPS prunes symmetric paths by identifying jump points where the search direction must change, skipping directly to them and ignoring all intermediate nodes. It requires a uniform-cost grid but is very fast for that case.

D* Lite

A dynamic variant that efficiently re-plans when the environment changes, doors opening, new obstacles appearing, terrain revealed by fog of war. Rather than restarting from scratch, D* Lite propagates updates backward through the already-computed path graph, changing only what the new information invalidates. It is the right choice for any game where pathfinding must respond to a changing world.

Pathfinding on Navigation Meshes

Grid-based A* works well for 2D games but struggles in 3D environments with complex geometry. Modern 3D engines (Unity, Unreal, Godot) represent walkable surfaces as navigation meshes, convex polygon decompositions of the floor. A* runs on the dual graph of the navmesh (nodes = polygon centers or shared edges, edges = polygon adjacency). The raw A* path is then refined with the Simple Stupid Funnel Algorithm (SSFA) or similar string-pulling techniques to produce smooth, straight-line segments through the polygon corridor rather than a zig-zag between centers.

Both Unity's NavMesh system and Unreal Engine's Recast/Detour library are built on this combination, making navmesh A* the industry standard for 3D game pathfinding.

Practical Integration Tips

• Spread over frames. For large searches, timeslice the algorithm across multiple frames using a coroutine or callback. Spending more than ~1ms per frame on pathfinding causes visible hitches.
• Queue and prioritize requests. With many agents, maintain a request queue and process the N highest-priority requests per frame, prioritizing agents closest to the camera or currently visible.
• Path smoothing. Raw A* paths on grids zigzag diagonally. Apply string-pulling (iteratively raycast-shortcutting the path) to produce natural, straight-line routes.
• Local avoidance separately. Use A* for global route finding and a local avoidance algorithm like RVO/ORCA for real-time collision avoidance between moving agents. Mixing the two into one global re-plan every frame is prohibitively expensive.
• Cache paths aggressively. Two agents traveling the same start-to-end route can share a cached path. Invalidate only when the grid changes in a way that intersects the cached route.

A* has stayed relevant because the theory is sound and the performance holds up in practice. Whether you are building a tower defense game or an open-world RPG with hundreds of agents, understanding A* thoroughly lets you tune and extend it for your specific constraints and build NPCs that navigate convincingly.