Interactive demo
Jump Point Search
Jump point search (JPS), by Daniel Harabor and Alban Grastien (2011), makes A* much faster on grids where every step costs the same. Most cells of an open grid can be skipped, because many paths of equal length lead to them.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. The faint cells were only looked at while jumping; just the jump points (light teal) enter the open list. Compare the expanded cells with A*. Mud is ignored, so with mud the path may not be the cheapest.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Jump point search always moves diagonally too.
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Looked at while jumping
- Expanded right now
- Path
Properties
Optimal
Conditionally
Finds the shortest path on grids where every step costs the same. Mud breaks that assumption.
Weighted cells
No
Assumes uniform costs, so the mud is ignored while searching.
Heuristic
Yes
As in A*, with the octile distance by default.
Any angle
No
Straight and diagonal runs between the jump points.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search this page | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. Pruning neighbors
Coming from a direction, most neighbors of a cell can be reached at the same cost without passing through it. JPS only follows the natural directions (straight on, or the parts of a diagonal) and forced neighbors that a wall would otherwise make unreachable.
2. Jumping
Instead of adding every cell to the open list, JPS runs along a direction until it hits a wall, the goal or a cell with a forced neighbor: a jump point. Diagonal runs check both straight directions at every step.
3. Without cutting corners
In this demo, paths may not squeeze past the corner of a wall. That changes which neighbors are forced: only straight runs stop at jump points of their own, diagonal runs stop where a straight run finds one.
Credits
- Daniel Harabor's article Jump Point Search on the method from “Online Graph Pruning for Pathfinding on Grid Maps” by Daniel Harabor and Alban Grastien (AAAI 2011).
- The jumping rules for paths that do not cut corners follow PathFinding.js by Xueqiao Xu (MIT license).