Grid & robotics pathfinding

Jump Point Search (JPS)

A turbocharged A* that skips over boring empty cells on grids.

Interactive demo coming soon — read the theory below

The idea

Jump Point Search (JPS) is a speed-up for A* that only works on uniform-cost grids (every step costs the same). Instead of examining every single empty cell, it "jumps" in a straight line over long runs of open space and only stops at special cells called jump points, where the path might need to turn. Because it skips all the equivalent, symmetric detours between two points, it expands far fewer nodes than plain A* while still returning the exact same optimal (shortest) path.

How it works

Start exactly like A*: keep a priority queue (OPEN) of cells to explore, ordered by estimated total path cost, and begin at the start cell.
Pop the most promising cell from OPEN. From it, instead of adding its immediate neighbours, 'jump' outward in each allowed direction (horizontal, vertical, and diagonal).
While jumping in a direction, keep sliding cell by cell over empty space without adding any of those cells to OPEN.
Stop jumping and declare the current cell a 'jump point' if it is the goal, OR if it has a 'forced neighbour' - a spot where an obstacle nearby means the optimal path could be forced to turn here.
For diagonal jumps, before each diagonal step also probe horizontally and vertically; if either of those probes finds a jump point, the diagonal cell counts as a jump point too.
Add only the discovered jump points to OPEN (with their real distance from the current cell as cost), skipping everything in between.
Repeat: pop the best cell, jump again, until you pop the goal - then reconstruct the path by following parent links, filling in the straight-line segments between jump points.
If OPEN empties before reaching the goal, no path exists.

OPEN, CLOSED & the data structures

Same core state as A*: an OPEN priority queue keyed by f = g + h (g = cost so far, h = heuristic estimate to goal, typically octile distance on a grid); a CLOSED set of already-expanded cells; and a parent/came-from map for each jump point to rebuild the path. The extra ingredient is a directional 'jump' routine that scans the grid and the concept of forced neighbours derived from obstacle placement. It needs read access to the grid itself to check which cells are blocked.

Pseudocode

function JPS(grid, start, goal):
    OPEN = priority queue ordered by f = g + h
    push start with g=0, f=h(start, goal)
    while OPEN not empty:
        current = pop lowest-f cell from OPEN
        if current == goal: return reconstruct_path(current)
        add current to CLOSED
        for each direction d from current (pruned by parent):
            jp = jump(current, d, goal)          # slide until a jump point
            if jp is null or jp in CLOSED: continue
            g_new = g[current] + dist(current, jp)
            if jp not in OPEN or g_new < g[jp]:
                g[jp] = g_new
                parent[jp] = current
                push jp with f = g_new + h(jp, goal)
    return failure                                # OPEN empty, no path

function jump(cell, d, goal):
    n = step(cell, d)                             # one move in direction d
    if n is off-grid or blocked: return null
    if n == goal: return n
    if n has a forced neighbour: return n         # obstacle forces a turn
    if d is diagonal:                             # probe the two straight axes
        for each straight sub-direction s of d:
            if jump(n, s, goal) is not null: return n
    return jump(n, d, goal)                       # keep sliding same direction

At a glance

Complete?Yes - complete. Like A*, if a path exists JPS is guaranteed to find one, because the jumping only skips cells that are provably not needed; it never discards a route the goal actually depends on. If it exhausts OPEN, there genuinely is no path.

Optimal?Yes - optimal. With an admissible heuristic (e.g. octile distance) JPS returns a shortest path, exactly the same cost as A* would. It only prunes symmetric alternatives that are equal in length, so it never sacrifices path quality for speed.

TimeWorst case still exponential like A* in general, but in practice dramatically faster: it expands far fewer nodes because whole runs of empty cells are skipped. Each jump can scan up to O(grid width/height) cells, but this scanning is cheap and node-queue overhead - usually the real bottleneck - drops sharply.

SpaceO(number of jump points stored), which is typically much smaller than A*'s OPEN/CLOSED sets on open maps. On maze-like maps the savings shrink because there are more forced turns. No preprocessing of the map is required (unlike JPS+).

👍 When to use it

You need shortest paths on a 2D grid where every move costs the same (uniform-cost), like tile-based game maps.
The map has lots of open space - long corridors and rooms - where plain A* wastes time crawling cell by cell.
You want A*-quality optimal paths but noticeably faster, without changing the answer.
You can accept only 4- or 8-directional movement (grid moves), not arbitrary angles.

⚠️ Watch out for

Only valid on uniform-cost grids with grid-based movement. Weighted terrain (mud costs more than road), non-grid graphs, or any-angle movement break its assumptions.
The real subtlety is the 'forced neighbour' rules - getting them wrong quietly returns wrong or non-optimal paths. Follow a reference implementation carefully.
Speed-up depends heavily on the map: huge on open maps, much smaller on dense mazes where turns are frequent.
It still uses a heuristic - the heuristic must match the movement model (octile distance for 8-directional grids) to stay optimal.
Standard JPS assumes a static map; if obstacles change, cached jumps can become stale. (The JPS+ variant precomputes jumps but then needs the map to stay fixed.)