Overview
JPS4+ is a tile-based Burst 2D Pathfinding solution tailored for 2D grid-based movement and pathing. It includes A* (4 and 8-connected grids) and JPS4 (4-connected grids) with horizontal/vertical canoncial ordering.
What is JPS4?
Jump Point Search Pathfinding in 4-connected Grids (2025 Johannes Baum) Find it here
JPS4 builds upon the Jump Point Search (JPS8) algorithm, originally designed for 8-connected environments. To achieve efficient pathfinding on 4-connected grids, JPS4 employs a canonical ordering and a successor function that enable online graph pruning. This reduces the search space by minimizing unnecessary node expansions.
The core concept of JPS4 as well as JPS8 lies in the utilization of jump points. Strategically placed at obstacle corners, jump points prevent the search from overlooking crucial sections of the state space. They essentially reinitialize the canonical ordering, allowing exploration beyond obstacles. This mechanism ensures JPS4 finds optimal paths even in complex environments.
This stands out from other 2D pathing solutions because it implements Jump Point Search Pathfinding in 4-connected Grids (Johannes Baum 2025) For dense maps, JPS4 can give >50x improvement v.s. A* by reducing the search space to remove unnecessary node expansions.
Resources
Algorithms
- JPS4 Algorithm
- A* Algorithm
Samples
-
A simple 2D scene with a small example grid and pathfinding agent.
-
A 2D maze generator to showcase how jump points and canonical ordering works with JPS4. We'll cover debugging tools to visualize the JPS4 algorithm.
-
An example to showcase tile-based movement and and 3D colliders for the grid.
-
A full implementation of a synced world controller to showcase multi-threaded path scheduling on a static and dynamic grid with adaptive targets (closest targets).
-
Showcases external generation of a large grid from a thresholded image.