Wait, What?
A* can be perfectly correct and still spend most of its time proving that hundreds of equivalent grid moves are unnecessary.
Jump Point Search (JPS) is a pathfinding technique for uniform-cost grid maps that keeps the optimality of A* while pruning large families of symmetric paths. The key idea is not “jump farther because long moves are cheaper.” It is “skip intermediate states whose expansion would tell us nothing new.” That makes JPS a powerful lesson in symmetry, search invariants, admissible heuristics and the difference between reducing the search space and changing the problem.
Quick Answer
Learn JPS through A* foundations → grid-path symmetry → natural neighbours → forced neighbours → the jump operation → jump-point expansion → optimality reasoning → movement-model edge cases → implementation and benchmarking. Do not start with an optimized JPS+ implementation. Start by proving to yourself which intermediate grid nodes can be skipped without removing every optimal route.
1. Begin With the Job JPS Actually Owns
JPS is not a replacement for graph search in general. It is a symmetry-breaking acceleration for pathfinding on grids with regular local movement costs. On an open grid, there are often many different sequences of horizontal, vertical and diagonal moves with exactly the same cost. A* may expand multiple states representing these equivalent choices. JPS prunes many of them and keeps only strategically important turning or constraint points.
This is why the Learning Hall boundary matters: D* Lite owns incremental replanning when edge costs change, Theta* owns any-angle parent rewiring, and JPS owns online symmetry pruning in regular grid search.
2. Rebuild A* Before You Add JPS
A* evaluates a node n using f(n)=g(n)+h(n), where g is the cost already paid and h estimates the remaining cost. With an admissible heuristic, A* can return an optimal path. JPS does not replace this priority rule. It changes which successors are generated.
A learner should be able to trace a small A* search first: open set, closed set, parent pointers, g-values and heuristic values. Only then does the JPS pruning logic have a stable foundation.
3. See the Symmetry
Imagine moving east through an empty corridor. From each intermediate cell, A* can consider moves that correspond to path permutations with the same cost. If nothing in the local geometry distinguishes those cells, expanding all of them is redundant. JPS collapses the repeated decision chain into a single directional scan until something important happens.
The professional mental model is: JPS compresses sequences of search decisions, not physical distance. Every skipped cell still exists in the path geometry; it is simply not used as a branching search state.
4. Natural Neighbours Versus Forced Neighbours
When a node is reached from a parent, some successors are natural continuations of the direction of travel. Others become necessary because obstacles block the symmetric alternatives. These are commonly called forced neighbours.
A forced neighbour is the local evidence that says, “If you prune this direction, you may remove an optimal route.” This is the core invariant behind JPS. The exact pattern depends on whether movement is four-connected or eight-connected and on whether diagonal corner-cutting is permitted.
5. The Jump Operation
Instead of returning the immediately adjacent cell as a successor, the jump routine repeatedly advances in one direction. It stops when one of several things happens:
- the next position is blocked or outside the map;
- the goal is reached;
- a forced neighbour appears, making the current position a jump point;
- for diagonal travel, a recursive straight-direction check discovers a jump point that makes the current diagonal position relevant.
jump(x, direction):
y = step(x, direction)
if y is blocked: return NONE
if y is goal: return y
if y has a forced neighbour: return y
if direction is diagonal:
if jump(y, horizontal_part(direction)) exists: return y
if jump(y, vertical_part(direction)) exists: return y
return jump(y, direction)The pseudocode is intentionally conceptual. Real implementations must make movement legality and corner rules explicit.
6. Work One Corridor by Hand
Draw a 12×8 grid. Put the start near the left edge and the goal near the right. Leave the first half open, then add a wall that forces a turn through a gap. Trace ordinary A*: mark every expanded cell. Then trace JPS. In the open region, JPS should jump across long stretches without expanding every intermediate cell. Near the wall and gap, forced neighbours create jump points and the search regains the local detail it needs.
This trace teaches the most important idea: pruning is aggressive in symmetric space and conservative near structural constraints.
7. Why Optimality Can Survive the Pruning
Harabor and Grastien’s JPS work proves that, under the intended grid assumptions, the pruning rules preserve at least one optimal representative from each family of symmetric paths. JPS therefore reduces redundant expansions without changing the shortest-path objective.
A good learner proof is not “the paper says it works.” It is: identify two equal-cost path permutations, show why one can be removed, then identify an obstacle configuration where a forced neighbour prevents unsafe pruning.
8. Movement Rules Are Part of the Algorithm
Many JPS bugs are actually model-definition bugs. Before coding, decide:
- four-way or eight-way movement;
- cost of diagonal moves;
- whether moving diagonally past blocked orthogonal cells is legal;
- how map boundaries behave;
- which heuristic matches the movement metric.
For eight-connected grids with unit orthogonal cost and √2 diagonal cost, octile distance is a common admissible heuristic. If the movement model changes, pruning rules and heuristics may need to change too.
9. Complexity: Do Not Promise a Magic Big-O
JPS often reduces node expansions dramatically on uniform grids, sometimes by an order of magnitude or more in benchmark settings, but its advantage depends on map structure, obstacle density, implementation and movement rules. The worst case can still require substantial search. Professional analysis therefore tracks expanded states, generated successors, jump-scan work, priority-queue operations and wall-clock time.
10. JPS+, Precomputation and Engineering Trade-Offs
Later JPS work introduced stronger online pruning and JPS+ style preprocessing. Precomputation can reduce repeated scan work on static maps, but it adds memory and update cost. In a changing map, a lighter online JPS may be easier to maintain. The engineering question is therefore not “which version is fastest in isolation?” but “which version matches map volatility, memory budget and query volume?”
11. How to Learn It Efficiently
Use a Predict–Run–Investigate–Modify–Make progression. First predict which cells ordinary A* will expand. Run the baseline. Investigate where symmetric expansions occur. Modify successor generation to prune obvious natural-neighbour redundancy. Only then implement the full jump logic. Parsons-style reconstruction tasks can help novices focus on ordering the pruning steps before writing the whole routine from scratch.
Common Failure States
- Calling every long stride a “jump point” even when no stopping condition is met.
- Applying eight-connected forced-neighbour rules to a four-connected grid.
- Allowing diagonal corner cutting accidentally.
- Using a heuristic inconsistent with the movement costs.
- Skipping parent reconstruction across jumped cells.
- Benchmarking JPS against a poorly implemented baseline A* and drawing exaggerated conclusions.
- Treating a static-map optimization as automatically appropriate for frequently changing maps.
Practice Ladder
- Beginner: trace A* on a 10×10 empty grid and mark equivalent path permutations.
- Foundation: classify natural and forced neighbours for several obstacle patterns.
- Intermediate: implement a jump routine and reconstruct all skipped cells in the returned path.
- Advanced: compare four-connected and eight-connected rules and prove which pruning steps stay valid.
- Professional: benchmark A*, JPS and a preprocessed JPS variant across open maps, mazes, game maps and changing-obstacle scenarios.
Learning Hall Boundary
This article owns JPS as a grid-specific symmetry-pruning acceleration for optimal A* search. It does not replace the existing A*/shortest-path foundations, D* Lite replanning, Theta* any-angle pathfinding, RRT motion planning or general network-routing material.
Evidence Boundary
The core reference is Daniel Harabor and Alban Grastien, “Online Graph Pruning for Pathfinding on Grid Maps,” AAAI 2011, which introduces the jump-point strategy, proves optimality under its grid assumptions and reports major reductions in search effort. Their later “Improving Jump Point Search,” ICAPS 2014, develops stronger online and offline optimizations, and the JPS Pathfinding System work describes competition-oriented variants including JPS+.
Professional rule: you understand JPS when you can explain exactly why a skipped cell cannot be the only gateway to an optimal path—and exactly which obstacle patterns force the search to stop skipping.
