Jump Point Search, in depth: path symmetry, forced neighbours without corner cutting, a tested implementation and when it beats A*

The movement model comes first

JPS is not one algorithm but a family of rule sets, one per movement model, and using the rules for the wrong model gives wrong answers. This article uses the model most games and robots want:

• 8-connected grid, every free cell has the same traversal cost.
• Straight moves cost 1 and diagonal moves cost sqrt(2).
• No corner cutting: a diagonal move from (x, y) to (x+dx, y+dy) is allowed only if both side cells (x+dx, y) and (x, y+dy) are free.
• Heuristic: octile distance max(dx, dy) + (sqrt(2) - 1) * min(dx, dy), which is exact on an empty grid and therefore admissible and consistent.

The 2011 paper used a model that permits some corner-cutting moves; Harabor and Grastien's 2012 'JPS Pathfinding System' paper adapted the method to grids where corner cutting is forbidden. The forced-neighbour tests differ between the two, which is the most common reason a JPS port produces paths that clip walls or misses paths that exist. Decide the model first, write it down next to the code, and make the collision system agree with it.

Pruning: natural and forced neighbours

Suppose the search reached node x from its parent p, moving in direction (dx, dy). Any neighbour n of x that can be reached from p at least as cheaply without passing through x does not need x as a predecessor, so it can be pruned from x's successors. What remains are the natural neighbours (those you reach by continuing the move) and, near obstacles, forced neighbours.

Straight move, for example east (dx = 1). The natural neighbour is the next cell east. The cell above x, (x, y+1), is normally reachable from p by one diagonal step, which costs less than going through x. But if the cell above p, (x-1, y+1), is a wall, that diagonal would cut a corner and is forbidden, so the only short way up is through x. The cell above x is then forced, and so is the cell above-ahead, (x+1, y+1), when the diagonal to it is legal. The same holds below.

Diagonal move, for example north-east. The natural neighbours are east, north, and north-east. In this model a diagonal never has forced neighbours: a cell such as (x-1, y+1) is reachable from p through the free side cell (x-1, y) for a cost of 2, while going through x costs 2 sqrt(2). The arrival diagonal was legal, so the side cells it needed are free, and the cheaper route always exists. Under the corner-cutting model this argument fails, which is why that model has diagonal forced neighbours and this one does not.

Jumping

From each surviving direction, JPS does not step one cell; it jumps, moving repeatedly in that direction until one of three things happens:

1. The next move is illegal (wall, map edge, or a corner cut): return nothing.
2. The current cell is the goal: return it. Forgetting this test makes the scan run straight past the goal.
3. The current cell has a forced neighbour (straight scans), or a straight sub-scan east or north from it finds a jump point (diagonal scans): return the current cell as a jump point.

The diagonal rule is the subtle one. At each diagonal step, JPS launches the two straight scans that the diagonal's natural neighbours would start. If either finds something interesting, the diagonal cell is where an optimal path may turn, so it becomes a jump point. Only jump points are pushed onto the open list, with g increased by the octile distance travelled. Every cell skipped lies on a segment with a symmetric alternative of equal cost, so the search stays optimal under the model's assumptions. Harabor and Grastien give the formal proof.

A tested implementation

The implementation below is complete apart from path reconstruction. can_step encodes the movement model in one place, so the jump and pruning code never tests walls directly for legality.

import heapq, math
SQRT2 = math.sqrt(2)
DIRS = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]

class Grid:
    def __init__(self, w, h, blocked):
        self.w, self.h, self.blocked = w, h, blocked   # set of (x, y)
    def free(self, x, y):
        return 0 <= x < self.w and 0 <= y < self.h and (x, y) not in self.blocked
    def can_step(self, x, y, dx, dy):                  # no corner cutting
        if not self.free(x + dx, y + dy):
            return False
        return dx == 0 or dy == 0 or (self.free(x + dx, y) and self.free(x, y + dy))

def octile(a, b):
    dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])
    return max(dx, dy) + (SQRT2 - 1) * min(dx, dy)

def jump(grid, x, y, dx, dy, goal):
    while True:
        if not grid.can_step(x, y, dx, dy):
            return None
        x, y = x + dx, y + dy
        if (x, y) == goal:
            return (x, y)
        if dx and dy:
            if jump(grid, x, y, dx, 0, goal) or jump(grid, x, y, 0, dy, goal):
                return (x, y)
        elif dx:
            if (grid.free(x, y+1) and not grid.free(x-dx, y+1)) or \
               (grid.free(x, y-1) and not grid.free(x-dx, y-1)):
                return (x, y)
        else:
            if (grid.free(x+1, y) and not grid.free(x+1, y-dy)) or \
               (grid.free(x-1, y) and not grid.free(x-1, y-dy)):
                return (x, y)

def pruned_dirs(grid, node, parent):
    if parent is None:
        return DIRS
    x, y = node
    dx = (x > parent[0]) - (x < parent[0]); dy = (y > parent[1]) - (y < parent[1])
    if dx and dy:
        return [(dx, 0), (0, dy), (dx, dy)]
    out = [(dx, dy)]
    for s in (1, -1):
        if dx and grid.free(x, y+s) and not grid.free(x-dx, y+s):
            out += [(0, s), (dx, s)]
        if dy and grid.free(x+s, y) and not grid.free(x+s, y-dy):
            out += [(s, 0), (s, dy)]
    return out

def jps(grid, start, goal):
    g, parent = {start: 0.0}, {start: None}
    openq, closed = [(octile(start, goal), 0.0, start)], set()
    while openq:
        _, gc, n = heapq.heappop(openq)
        if n in closed:
            continue
        closed.add(n)
        if n == goal:
            return gc, parent
        for dx, dy in pruned_dirs(grid, n, parent[n]):
            j = jump(grid, n[0], n[1], dx, dy, goal)
            if j is not None and gc + octile(n, j) < g.get(j, math.inf):
                g[j], parent[j] = gc + octile(n, j), n
                heapq.heappush(openq, (g[j] + octile(j, goal), g[j], j))
    return None, parent

Diagonal jumps call straight jumps, but straight jumps never recurse, so the recursion depth is at most two regardless of map size. A forced direction such as (dx, s) is simply rejected by can_step when its corner is blocked, which keeps the pruning code free of special cases.

Measured: correctness, expansions and scanning cost

Correctness first. On 1,998 random grids from 2 by 2 to 14 by 14, with 0 to 35 percent walls and random start and goal, the JPS cost matched plain A* on the same movement model in every case, including all the unreachable ones. That validates this rule set for this model only; a corner-cutting variant needs its own cross-check.

Then cost. Each map is 256 by 256, searched corner to corner. 'Expansions' counts nodes popped from the open list, and 'cells scanned' counts every cell a jump stepped onto, including the straight sub-scans of diagonal jumps.

All path costs agreed with A* (for example 374.784 on the rooms map). The table shows the honest shape of the trade. On the rooms map, the structure JPS was built for, the open list shrank 158-fold and time halved. On noisy random maps nearly every cell is next to a wall, so jump points are everywhere and expansions only halve. On the empty map, A* with a perfect heuristic walks the diagonal in 256 expansions, while JPS's diagonal jump launches two straight scans to the map edge at every step and touches 65,535 cells. Fewer queue operations is not the same as less work; the work moves into scanning. These are single runs of pure Python on a set-based grid, so read them as ratios. Compiled implementations scan bit-packed rows and the balance shifts strongly toward JPS.

From jump points to a path

The parent map links jump points, not cells. To produce a walkable path, walk back from the goal and interpolate between consecutive jump points; each segment is a straight or diagonal line, so stepping by the sign of the difference reproduces it. The result is optimal under the octile model but has the characteristic grid look: long straight runs joined by 45-degree turns. If agents can move at any angle, post-process with line-of-sight smoothing or use an any-angle planner such as the one in the Theta* article; note that smoothing changes the cost model, so the result is no longer the octile optimum.

Block scanning and JPS+

Harabor and Grastien's ICAPS 2014 paper, 'Improving Jump Point Search', reported three kinds of improvement: scanning blocks of cells at once rather than one cell at a time, an offline preprocessing step that identifies jump points in advance, and stronger pruning rules that skip more nodes. The preprocessing family is usually called JPS+: for every cell and direction it stores how far the next jump point or wall is, turning each jump into a table lookup. The trade is memory proportional to eight values per cell and a rebuild whenever the map changes, so JPS+ suits static maps and plain JPS suits maps that change at runtime.

Operational guidance

• Use JPS only on uniform-cost grids. The symmetry argument needs every free cell to cost the same. With weighted terrain (mud, roads), two orderings of the same moves no longer cost the same, and pruning discards optimal paths. Use A* or Dijkstra there, as covered in the A* pathfinding article.
• Pack the grid. Store walls as bit rows and find the next wall or forced neighbour with word-level operations; this is what turns the scanning cost in the table into an advantage.
• Keep the movement model in one function and share it with collision and steering code, so the planner never produces a move the agent cannot execute.
• Precompute only when the map is static. For maps that change, invalidate or rebuild JPS+ tables per region, or stay with online JPS; for maps that change during a single plan, consider replanning algorithms such as the one in the D* article.
• Bound the work per frame. Cap expansions or scanned cells per tick in games, and keep the open list and g map between ticks if you resume the search.

Failure modes

• Rules for the wrong movement model: corner-cutting forced-neighbour tests on a no-corner-cutting map return paths through diagonal gaps the agent cannot take.
• No goal test inside the jump: the scan runs past the goal and the search reports a longer path or none.
• Weighted cells: silently suboptimal paths, with no error.
• Assuming fewer expansions means faster: on open maps with a naive scan, the empty-grid row above is the counterexample.
• Stale JPS+ tables after a door closes: paths through walls.
• Start or goal inside a wall or outside the map: validate inputs before searching, since the jump code treats them as ordinary cells.

Trade-offs

What to do next

1. Run the implementation and an A* baseline on your own maps and confirm equal costs before trusting any speed numbers.
2. Write your movement model next to can_step and check that your collision code makes the same corner-cutting decision.
3. Instrument both expansions and cells scanned; decide on scanned cells and wall time, not expansions alone.
4. Replace the set-based grid with bit rows and remeasure the empty-map case.
5. If your maps are static and queried often, prototype JPS+ distance tables and measure their memory against your budget.
6. Add path interpolation and, if agents move at any angle, compare smoothed JPS paths with Theta*.