Jump Point Search (JPS) and Four Optimized Variants for High‑Performance Pathfinding

This article introduces the Jump Point Search (JPS) algorithm, originally proposed in 2011, and four derived optimizations (JPS‑Bit, JPS‑BitPrune, JPS‑BitPre, and JPS‑BitPrunePre). The author, Wang Jie, a backend engineer at Tencent TEG, demonstrates that the optimized versions can be up to 273× faster than classic A* on a 200‑grid test case.

Experimental results show the total search time for 10,000 runs on a 200‑grid scenario:

A*: ~2.6074×10¹¹ ns

Basic JPS: ~1.7037×10¹⁰ ns

JPS‑Bit: ~3.2364×10⁹ ns

JPS‑BitPrune: ~2.3703×10⁹ ns

JPS‑BitPre: ~2.0043×10⁹ ns

JPS‑BitPrunePre: ~9.5434×10⁸ ns

These correspond to average per‑search latencies of 1.7 ms, 0.32 ms, 0.23 ms, 0.02 ms, and 0.095 ms respectively, yielding speed‑ups of 15×, 81×, 110×, 130×, and 273× over A*.

Algorithm Basics

JPS retains the A* framework but reduces successor generation by jumping over unnecessary nodes. Key concepts include:

Forced neighbour : a neighbour that becomes reachable only because a blocked cell forces a detour.

Jump point : a node that is either the start/goal, has a forced neighbour, or satisfies a diagonal‑move condition.

Three rules govern jump‑point expansion:

If both straight and diagonal moves are possible, search straight directions first.

When moving straight, prune neighbours that can be reached via a shorter path that bypasses the current node.

When moving diagonally, apply analogous pruning.

Four Optimizations

1. JPS‑Bit : Uses bit‑wise operations to locate obstacles quickly. Example code:

int leadingZeros = __builtin_clz(B); // find first obstacle position

2. JPS‑BitPrune : Adds pruning of intermediate jump points to avoid redundant node expansions. After pruning, missing intermediate points are re‑inserted as “corner” points using the following logic:

if (dx == dy) // diagonal reachable
    addCorner = nullptr;
else
    addCorner = moveAlongDiagonal(min(dx, dy));

3. JPS‑BitPre : Pre‑processes each grid cell to store the maximum reachable steps in all eight directions (the so‑called JPS+). This eliminates per‑step direction scans.

4. Space‑for‑Time Trade‑off : Implements the open set as a binary heap and stores node metadata (id, G/F values, parent pointer, expanded flag, heap index) in a compact 12‑byte structure. A two‑level matrix (coarse 20×20 blocks → fine 100×100 sub‑blocks) reduces memory usage while keeping O(1) lookup for open/closed sets.

Multithreading Support

To avoid contention, per‑thread data such as the matrix of node pointers is declared thread_local . This ensures each search thread works on its own copy, preventing race conditions when marking nodes as expanded.

Memory Management

Two memory pools are employed: one for jump‑point objects (≈800 entries, ~9.6 KB) and another for the 100×100 sub‑matrix blocks (≈0.04 MB). This design keeps total memory under 4 MB even with 16 concurrent threads.

Path Post‑Processing

After JPS returns a sequence of jump points, a linear‑time “shortcut” pass removes unnecessary intermediate points by checking straight‑line reachability between non‑adjacent nodes, reducing visual jitter in games.

GPPC Competition Analysis

The Grid‑Based Path Planning Competition (GPPC) provides a benchmark suite of game maps (StarCraft, Dragon Age 2, Dragon Age Origins) and synthetic maps (maze, random, rooms). Over 347 868 path‑finding queries, JPS ranks among the Pareto‑optimal algorithms, especially in the “Avg Sub‑Opt” (average sub‑optimality) and storage metrics.

Tables summarise map statistics, competition metrics (total time, average time, 20‑step time, max segment time, average path length, sub‑optimality, solved/unsolved counts, RAM usage, storage size, preprocessing time), and the relative performance of 22 competing algorithms.

Overall, the article demonstrates that with bit‑wise acceleration, pruning, preprocessing, and careful memory layout, JPS can achieve orders‑of‑magnitude speed‑ups over A* while remaining lightweight enough for real‑time game servers.