function jumpPointSearch(grid: Grid, start: Cell, goal: Cell) {const open = new MinHeap<Cell>([start]), distance = new Map([[start, 0]]), parent = new Map();
while (open.size > 0) {const current = open.pop(); // lowest distance + heuristic
if (current === goal) return rebuild(parent, current);
for (const direction of directionsFrom(current, parent.get(current))) {const point = jump(grid, current, direction, goal);
if (point === null) continue;
const candidate = distance.get(current)! + manhattan(current, point);
if (candidate >= (distance.get(point) ?? Infinity)) continue;
distance.set(point, candidate); parent.set(point, current);
open.push(point, candidate + manhattan(point, goal));
}
}
}
function jump(grid: Grid, from: Cell, direction: Direction, goal: Cell): Cell | null {const next = step(from, direction);
if (!walkable(grid, next)) return null;
if (next === goal || hasForcedNeighbor(grid, next, direction)) return next;
if (isVertical(direction)) for (const side of [LEFT, RIGHT]) if (jump(grid, next, side, goal)) return next;
return jump(grid, next, direction, goal);
}
Start at (12, 1), goal at (5, 42). Instead of expanding every neighbour, JPS jumps along straight runs until something interesting.
Understanding Jump point search
The idea
On a uniform grid most of A*'s work is pointless: a cell in the middle of an open corridor has exactly one sensible successor, the next cell along. Jump point search keeps A*'s open set and heuristic, but instead of pushing every neighbour it jumps along a straight run and pushes only the cell where something changes: the goal, or a wall that forces a turn.
Those cells are the jump points. Scanning a run costs a few cheap array reads, while each pushed cell costs a heap operation, so JPS expands ten to a hundred times fewer nodes than A* and returns the same optimal path. It needs no preprocessing and no extra memory, only a uniform-cost grid.
The four stages
Complexity
Versus its siblings
Pseudocode
JPS(start, goal)
A* over jump points: open ← {start}pop the jump point with the lowest g + h; if it is the goal, rebuild the path
for each allowed direction: point ← JUMP(current, direction)
if point exists and g(current) + distance < g(point): update, push point
JUMP(cell, direction): step once; stop at a wall (nothing), at the goal or at a forced turn (jump point); on a vertical run also try both sideways jumps; else keep going
When to use
Pitfalls
History
Daniel Harabor and Alban Grastien presented jump point search in 2011 for 8-connected grids, and it became the reference for online grid pathfinding within a few years. JPS+ in 2014 precomputes the jump distances for another order of magnitude when the map is static.