A* Pathfinding in JavaScript: Heaps and Hierarchies for RTS

Anyone who has ever commanded a swarm of two hundred virtual tanks in a browser-based real-time strategy (RTS) game knows the exact split-second tragedy of a frozen tab. One click to rally your units across a sprawling map, and suddenly your browser engine wheezes, the main thread locks up, and Chrome offers to kill your page.

Vanilla A* pathfinding is clean, elegant, and notoriously brutal on performance when scaled across hundreds of units in JavaScript. If you want silky 60 FPS unit navigation in the browser, you have to ditch naive array sorting and flat tile grids.

Here is how modern indie web developers tame pathfinding overhead using Binary Min-Heaps and *Hierarchical Pathfinding (HPA\)**.

What Is A* Pathfinding in Web RTS Games?

Quick Definition: *A\ (A-Star)** is a graph traversal and path-search algorithm that plots the shortest route between starting and goal nodes. It evaluates nodes using the formula:

>

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

>

- $g(n)$: The actual movement cost from the starting node to node $n$.

- $h(n)$: The estimated heuristic cost from node $n$ to the goal (typically Manhattan or Euclidean distance).

- $f(n)$: The total estimated cost of the path through node $n$.

In browser RTS titles, running a naive A* search means scanning an "open list" of prospective tiles on every single tick. If your open list is a basic JavaScript array, finding the lowest-$f$ tile requires either sorting the array repeatedly with Array.prototype.sort() or running an $O(N)$ linear scan. Multiply that across forty marching harvesters, and your frame budget evaporates.

[Start Tile] ---> Searches Neighbours ---> Evaluates f(n) ---> [Goal Tile]
     |                                          ^
     +--- Naive Array Scan: O(N) operations ----+  <-- Bottleneck!
     +--- Binary Min-Heap:  O(log N) operations +  <-- 60 FPS Win!

Step 1: Replace Flat Arrays with a Binary Min-Heap

The biggest performance sinkhole in novice JavaScript pathfinding is managing the open list. A Binary Min-Heap is a tree-based data structure where the parent node is always smaller than or equal to its children. Storing this heap inside a flat typed array lets you extract the lowest-cost node in $O(\log N)$ time rather than $O(N)$.

Here is a lean, battle-tested binary heap tailored for grid nodes:

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(node) {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const bottom = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = bottom;
      this.sinkDown(0);
    }
    return top;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  bubbleUp(index) {
    const element = this.heap[index];
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      const parent = this.heap[parentIdx];
      if (element.f >= parent.f) break;
      this.heap[index] = parent;
      index = parentIdx;
    }
    this.heap[index] = element;
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swap = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx].f < element.f) {
          swap = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        const rightChild = this.heap[rightChildIdx];
        const compareVal = swap === null ? element.f : this.heap[leftChildIdx].f;
        if (rightChild.f < compareVal) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      index = swap;
    }
    this.heap[index] = element;
  }
}

By swapping an unorganised array for this heap, an open list containing 500 candidate tiles drops its cheapest-node extraction time from hundreds of checks down to around nine operations.

Step 2: Scale Up with Hierarchical Pathfinding (HPA*)

Even with a binary heap, plotting a path across a massive $512 \times 512$ tile grid forces the engine to examine thousands of unnecessary dirt tiles between bases. This is where *Hierarchical Pathfinding for A\ (HPA\)* saves the day.

Instead of searching tile-by-tile across the entire world, HPA* breaks the map into macro-chunks (such as $16 \times 16$ blocks) and pre-computes valid border crossings between them.

How Hierarchical Navigation Executes:

1. Abstract Layer: The pathfinder identifies which chunk the unit is in and which chunk holds the target. It calculates a high-level route between the chunk "entrances".

2. Local Layer: A standard A* search with a min-heap operates strictly inside the unit's immediate chunk to reach the nearest transition node.

3. Lazy Stitching: As the unit crosses chunk borders, the next local leg generates on demand.

If your enemy constructs a defensive turret that blocks a canyon entrance, you only re-bake the transition graph for that specific $16 \times 16$ chunk—never the whole map.

Production Tips for Browser Runtimes

Recent browser engine updates have improved garbage collection, but thrashing memory in an animation frame remains deadly. The developer consensus across WebGL game engines and indie dev communities points to three essential practices:

• Object Pooling: Never construct new { x, y, f, g, h } objects during a tick. Pre-allocate an array of reusable node structures to avoid triggering JavaScript's garbage collector.
• Web Workers: Shift long-distance path planning off the DOM thread. Send the coordinates to a dedicated worker via postMessage, let the worker solve the graph, and stream back an array of tile indices.
• Path Smoothing: Raw grid paths make units move in jagged 45-degree zig-zags. Run a quick raycast string-pulling algorithm (like Theta\*) to connect non-obstructed waypoints, letting units move in clean, natural lines.

Mastering pathfinding is what separates clunky tech demos from responsive, commercial-calibre browser RTS games. Build the heap, split your world into chunks, and your armada will cross the map without dropping a single frame.