Pathfinding at Scale: Jump Point Search (JPS) & Hierarchical A* (HPA*) Algorithms

The Anatomy of Standard A* Grid Bottlenecks

Standard A* determines the shortest path between start node $S$ and goal node $G$ by evaluating the cost function $f(n) = g(n) + h(n)$, where $g(n)$ is the exact movement cost from the start to node $n$, and $h(n)$ is an admissible heuristic (such as Euclidean or Octile distance) estimating the cost from $n$ to the goal.

While mathematically elegant, standard A* exhibits severe degradation on uniform-cost 2D grids (such as tilemaps in RTS, RPG, and survival titles):

• Combinatorial Path Symmetry: In open terrain devoid of obstacles, there exist thousands of permutations of horizontal, vertical, and diagonal steps that yield the exact same optimal distance. Standard A* explores every permutation, fanning out into a massive circular frontier.
• Priority Queue Heap Thrashing: Every expanded grid neighbor must be pushed into a binary min-heap (the Open Set). As the Open Set grows to thousands of nodes, each insertion and deletion incurs $O(log N)$ heap reorganizations, introducing substantial CPU cache misses.
• JavaScript Garbage Collection Overhead: Instantiating dynamic node objects ({ x, y, g, h, f, parent }) for thousands of grid cells during every path request triggers continuous garbage collection pauses in the browser runtime.

Jump Point Search (JPS): Exploiting Grid Symmetries

Developed by Daniel Harabor and Alban Grastien, Jump Point Search (JPS) is an algorithm specifically designed for uniform 2D grid pathfinding. JPS retains the exact optimal shortest-path guarantees of A* while delivering 10x to 30x faster execution speeds.

JPS achieves this through neighbor pruning rules. Instead of placing every adjacent tile into the Open Set, JPS shoots directional rays along straight (horizontal/vertical) and diagonal lines, skipping empty intermediate nodes. It stops and registers a node into the Open Set only when it discovers a Jump Point.

// Recursive horizontal/vertical jump evaluation
private jump(x: number, y: number, px: number, py: number): [number, number] | null {
  const dx = x - px;
  const dy = y - py;

  if (!this.isWalkable(x, y)) return null;
  if (x === this.goalX && y === this.goalY) return [x, y];

  // Diagonal movement check
  if (dx !== 0 && dy !== 0) {
    // Check for forced neighbors along diagonal
    if ((this.isWalkable(x - dx, y + dy) && !this.isWalkable(x - dx, y)) ||
        (this.isWalkable(x + dx, y - dy) && !this.isWalkable(x, y - dy))) {
      return [x, y];
    }
    // Check if horizontal or vertical recursions find jump points
    if (this.jump(x + dx, y, x, y) !== null || this.jump(x, y + dy, x, y) !== null) {
      return [x, y];
    }
  } else {
    // Horizontal / Vertical straight movement check
    if (dx !== 0) {
      if ((this.isWalkable(x + dx, y + 1) && !this.isWalkable(x, y + 1)) ||
          (this.isWalkable(x + dx, y - 1) && !this.isWalkable(x, y - 1))) {
        return [x, y];
      }
    } else if (dy !== 0) {
      if ((this.isWalkable(x + 1, y + dy) && !this.isWalkable(x + 1, y)) ||
          (this.isWalkable(x - 1, y + dy) && !this.isWalkable(x - 1, y))) {
        return [x, y];
      }
    }
  }

  return this.jump(x + dx, y + dy, x, y);
}

Understanding Forced Neighbors

A forced neighbor occurs when an obstacle blocks what would otherwise be a shorter straight trajectory, forcing an entity to pivot around a corner.

Consider an entity travelling east from $(x-1, y)$ to $(x, y)$. If the tile directly north $(x, y-1)$ is an obstacle, but the tile north-east $(x+1, y-1)$ is walkable, the entity cannot cut through the obstacle. Node $(x+1, y-1)$ is classified as a forced neighbor of $(x, y)$. When JPS detects this condition during its ray march, it halts the jump, registers $(x, y)$ as a jump point, and adds it to the A* priority queue.

Hierarchical Pathfinding (HPA*): Macro-Cluster Abstraction

While JPS is phenomenal for local and medium-range navigation, querying routes across colossal maps (e.g. 4,096x4,096 open-world tilemaps) causes any single-layer grid algorithm to degrade. Hierarchical Pathfinding for A* (HPA*) solves this through multi-tier spatial abstraction:

1. Map Partitioning: The global grid is divided into fixed-size macro-clusters (typically 16x16 or 32x32 sectors).
2. Border Node Discovery: Adjacent clusters share border boundaries. Contiguous walkable openings between clusters are identified and condensed into entry/exit nodes.
3. Abstract Graph Construction: Offline during level load, the engine calculates shortest intra-cluster paths between all entrance nodes within each sector, building an abstract macro-graph.
4. Two-Level Query Execution: When a path is requested, the start and goal positions are temporarily linked to their local cluster entrance nodes. A high-level A* search solves the macro-path through the abstract graph in under 1 millisecond. The entity then streams fine-grained local paths sector-by-sector as it travels.

Multi-Threaded Pathfinding via Web Workers

To preserve an uncompromised 60 FPS main render loop, pathfinding must never execute synchronously on the JavaScript main thread. Production web game engines deploy dedicated Pathfinding Web Workers.

Using SharedArrayBuffer or transferable ArrayBuffer instances, the static collision grid is shared with worker threads with zero serialization latency. When units issue movement commands, a compact job request ({ jobId, startX, startY, goalX, goalY }) is dispatched to the worker pool. Workers process the JPS or HPA* algorithms on dedicated background CPU cores and return the finalized array of jump-point waypoints via structured message channels.

Comparative Architectural Matrix: 2D Pathfinding Algorithms

Comparing performance and capabilities across pathfinding methodologies:

Conclusion

Scaling pathfinding in browser games demands moving beyond naive textbook algorithms. Combining Jump Point Search for symmetrical grid pruning, Hierarchical A* for macro-cluster routing, and Web Workers for background thread execution empowers web games to simulate complex, multi-agent AI ecosystems without compromising the visual fluidity of the 60 FPS HTML5 Canvas pipeline.