Does JPS replace A* completely?

It is commonly used as a successor-generation and pruning strategy within an A*-style search framework.

Does uniform-cost mean diagonal and straight moves must cost the same?

Not in the original model: straight moves cost 1 and diagonal moves cost square root of 2. Uniformity concerns consistent terrain costs under that movement model.

Can JPS still do redundant work?

Yes. Repeated scans and other behavior motivate later research and variants.

AI Glossary / Graphs and symbolic AI / Advanced

Jump point search

Definition

Jump point search, or JPS, is a pathfinding technique that reduces redundant search on suitable grid maps. It exploits equivalent routes and generates selected jump-point successors instead of expanding every intermediate grid cell as a separate search node.

What it means

An open grid often contains several equally good paths that differ only in the order of their moves. Exploring every such alternative can waste effort. JPS uses the direction from which a node was reached and nearby obstacles to remove unnecessary alternatives while preserving an optimal route under its movement assumptions.

The word jump describes a search shortcut, not physical movement through walls. A jump represents a sequence of valid grid moves whose accumulated cost still counts.

The original method concerns undirected, uniform-terrain grids with specified straight and diagonal movement costs. Its guarantees should not be transferred automatically to arbitrary graphs, varying terrain costs or a different diagonal-collision rule. Jump point search is also unrelated to jump search for sorted arrays.

How it works

JPS changes successor generation within a heuristic search such as A*. Neighbor-pruning rules remove moves whose relevant alternatives are redundant, given the incoming direction. Obstacles can create forced neighbors that must remain because the usual equivalent route is blocked.

The search scans along retained directions until it reaches a goal, a qualifying jump point or a condition that ends that direction. Diagonal scanning also checks appropriate straight directions as part of identifying necessary successors. The successor's cost includes the entire valid segment.

Once a route through jump points is found, its segments can be expanded into ordinary adjacent-cell moves. The search may inspect many cells during scans even when it expands relatively few nodes. Therefore, expansion count and total computational work are different measurements.

Three practical examples

A grid-navigation experiment compares ordinary A* with JPS on the same obstacle map and movement rules.
A game-pathfinding prototype uses jump-point successors to avoid representing every step of a long unobstructed run in the search frontier.
A performance review counts both expanded nodes and scanned cells to identify when successor-generation work limits the benefit.

Think of it this way

Think of route instructions that say continue along this clear corridor to the next meaningful turning point instead of listing each floor tile. The tiles still exist and must be traversable.

The analogy explains segment-based search. JPS uses formal pruning rules based on grid symmetry; it cannot safely skip arbitrary intersections simply because they look unimportant.

Worked example

Preserving distance while compressing search steps

Assume an obstacle-free portion of an eight-connected grid. Straight moves cost 1 and diagonal moves cost the square root of 2. From start (0, 0) to goal (4, 2), a shortest route uses two northeast diagonal moves and two east moves.

Its cost is 2 times square root of 2 plus 2, approximately 4.828. There are six arrangements of those four moves because choosing which two positions contain the diagonal moves gives six possibilities. In the obstacle-free region, each arrangement reaches the same endpoint with the same cost.

JPS exploits this kind of symmetry to avoid separately exploring all equivalent move orderings. This illustration explains the redundancy; it is not a full trace of the algorithm's direction-dependent successor rules.

For a simpler segment, consider start (0, 0) and goal (4, 0) in an open row. A rightward jump can identify the goal as a successor with segment cost 4. The intermediate cells (1, 0), (2, 0) and (3, 0) are not ordinary expanded search nodes along that segment, but the scan still checks traversability and the eventual route still contains four unit moves.

If cell (2, 0) becomes blocked, that straight segment is invalid. The algorithm must stop that scan and consider other permitted routes; it cannot preserve the cost-4 shortcut by jumping over the obstacle. Terrain-dependent costs would also require a method whose pruning rules account for them.

Illustrative case study

The fictional Birch Navigation team tests JPS on a uniform grid. A demonstration shows fewer expanded nodes than its ordinary A* baseline, but some maps still take substantial time.

Reviewers add a count of scanned cells and inspect repeated scans in large open regions. They also confirm that the baseline and JPS implementation use the same diagonal movement and obstacle rules, so path-cost comparisons are meaningful.

Before extending the map with terrain penalties, Birch revisits the algorithm's assumptions instead of treating the change as a harmless data edit. This fictional case illustrates benchmarking and scope control.

Common misconceptions and mistakes

A jump can cross an obstacle. It represents valid intermediate moves and must respect traversability.
Fewer expanded nodes necessarily means proportionally faster execution. Scanning and other overhead still consume time.
All forms of grid movement share the same pruning rules. Direction, cost and collision conventions matter.
JPS finds a continuous straight-line shortcut through arbitrary geometry. It optimizes paths within the specified grid movement model.

Business use

JPS is relevant when evaluating pathfinding on regular grids with compatible cost assumptions. Benchmark representative maps and queries because structure and implementation affect performance.

Check path validity and cost as well as runtime. A returned sequence of jump points must reconstruct into permitted adjacent moves, including around corners. Distinguish the original online method from later variants that use preprocessing or different pruning strategies. Claims about memory or preprocessing should name the variant being evaluated, and a historical research speedup should not be presented as a guarantee for a new application.

Check your understanding

Why is a jump from (0, 0) to (4, 0) still cost 4 in the worked example?

Answer: It represents four unit-cost grid moves. Compressing the search representation does not remove their traversal cost.

Related terms

Admissible heuristic
Jump search
A* search
grid map
path symmetry
forced neighbor
successor generation
path reconstruction

Learn next

Draw the six move orderings from (0, 0) to (4, 2). Place one obstacle on a cell visited by only some of them, then identify which routes remain valid. Explain why obstacle-aware pruning needs more than the open-grid symmetry argument.

Sources

Harabor and Grastien define the original pruning rules and movement assumptions: https://pathfinding.ai/pdf/harabor-grastien-aaai11.pdf

Their JPS system paper summarizes the search mechanism: https://harabor.net/data/papers/harabor-grastien-socs12.pdf

Later primary research examines redundant work: https://arxiv.org/abs/2306.15928

The coordinates, move counts and Birch Navigation case are original illustrations. The original movement assumptions remain essential.

Previous: Judgment sample Next: Jump search