ExtendedSource checked

Jump Point Search

Speeds up grid pathfinding by skipping over symmetric intermediate nodes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: Grid Pathfinding
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: JPS

Overview

Jump Point Search prunes uniform-cost grid moves and jumps to forced decision points while preserving optimal paths.

Core Concepts

path costgrid frontierheuristic scoringobjective functiongrid pathfindingroute costfrontier expansionpath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E)

Average

O(E)

Worst

O(E)

Space

O(V)

When to Use

Use Jump Point Search when you need to skip straight-line grid nodes.
Use it for game grid navigation with inputs like uniform-cost grid.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the Grid Pathfinding tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when the required output is not shortest grid path.

What It Does

Skips straight-line grid nodes
Keeps forced neighbors that affect path choices

Use Cases

Game grid navigation
Fast A* on uniform grids
Tile map pathfinding

Inputs

Uniform-cost grid
Start and goal

Outputs

Shortest grid path
No-path result

Key Formulas (1)

Jump stop rule

stop jumping if node is goal or node has a forced neighbor

stop jumping if node is goal or node has a forced neighbor

Identifies the grid cells that must be kept because they may change the optimal path.

Pseudocode

1.Run A* over jump points
2.From each node, jump in allowed directions
3.Stop a jump at obstacles, goal, or forced neighbors
4.Add jump points to the open set
5.Reconstruct the path from parents

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Jump Point Search: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Uniform-cost grid; Start and goal.
Use this step as the implementation spine: Run A* over jump points.
Then preserve the next state change: From each node, jump in allowed directions.
Store predecessor links if the final path is needed, not just the final distance.

Common Pitfalls

Jump Point Search assumes regular grids with uniform movement costs.
Treating a visited node as final before its best known cost is actually settled.
Returning shortest grid path without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show long grid jumps replacing many single-cell expansions.

Step 1 of 5: Run A* over jump points

grid-jumps

Notes

Jump Point Search operates in O(E) time and O(V) space within the Grid Pathfinding family. Key governing relation: stop jumping if node is goal or node has a forced neighbor. Often compared with A* Search and Lee Algorithm.