Jump Point Search
Jump Point Search (JPS) is an optimization of the A* search algorithm tailored for uniform-cost grid graphs. By systematically eliminating symmetric path alternatives and identifying forced neighbors, JPS leaps over large swaths of redundant grid nodes, drastically reducing node expansions while maintaining mathematical optimality.
HOW-TO IMPLEMENT & CONFIGURE
- Modern runtime supporting high-performance memory manipulation (e.g., C++17, Rust, or modern JS)
- Standard template libraries for priority queues and dynamic arrays
- A uniform-cost grid representation where cells are explicitly walkable or blocked
Step 1
Initialize the 2D grid structure, defining discrete costs for orthogonal and diagonal movements. Allocate memory for the open set priority queue, closed set bitsets, and distance maps.
struct GridNode {
int x, y;
double g, h, f;
GridNode* parent;
};
class JumpPointSearch {
int width, height;
std::vector<bool> obstacles;
public:
JumpPointSearch(int w, int h) : width(w), height(h), obstacles(w * h, false) {}
bool isWalkable(int x, int y) const {
if (x < 0 || x >= width || y < 0 || y >= height) return false;
return !obstacles[y * width + x];
}
};Step 2
Implement the core recursive or iterative pruning rules. Detect forced neighbors which occur when an obstacle blocks an alternate optimal path, dictating where a jump point must be declared.
std::pair<int, int> jump(int x, int y, int dx, int dy) {
int nx = x + dx;
int ny = y + dy;
if (!isWalkable(nx, ny)) return {-1, -1};
if (nx == goalX && ny == goalY) return {nx, ny};
// Check for forced neighbors
if (dx != 0 && dy != 0) {
if ((isWalkable(nx - dx, ny + dy) && !isWalkable(nx - dx, ny)) ||
(isWalkable(nx + dx, ny - dy) && !isWalkable(x, ny - dy))) {
return {nx, ny};
}
// Recursively search orthogonal directions if diagonal
if (jump(nx, ny, dx, 0).first != -1 || jump(nx, ny, 0, dy).first != -1) {
return {nx, ny};
}
} else {
if (dx != 0) {
if ((isWalkable(nx, ny + 1) && !isWalkable(nx - dx, ny + 1)) ||
(isWalkable(nx, ny - 1) && !isWalkable(nx - dx, ny - 1))) {
return {nx, ny};
}
} else {
if ((isWalkable(nx + 1, ny) && !isWalkable(nx + 1, ny - dy)) ||
(isWalkable(nx - 1, ny) && !isWalkable(nx - 1, ny - dy))) {
return {nx, ny};
}
}
}
return jump(nx, ny, dx, dy);
}Step 3
Benchmark JPS against standard A* using randomized maps with varying obstacle densities (10% to 40%). Assert that generated path lengths are mathematically identical while node expansions decrease by orders of magnitude.
// Pseudocode verification assert
void verifyJPSvsAStar(Point start, Point goal) {
auto pathAStar = runAStar(start, goal);
auto pathJPS = runJPS(start, goal);
assert(pathAStar.totalCost == pathJPS.totalCost);
assert(jpsNodeExpansions < astarNodeExpansions);
}Step 4
Handle scenarios with tight corridors, diagonal corner-cutting restrictions, and memory bounds overflow by utilizing flat memory buffers instead of pointer-heavy graphs.
// Ensure diagonal movement respects corner cutting rules
bool canCutCorner(int x, int y, int dx, int dy) {
return isWalkable(x + dx, y) && isWalkable(x, y + dy);
}Mathematical Formulation & Symmetry Breaking
Standard A* treats uniform grids as regular graphs where every node expansion considers all neighbors. In unweighted uniform grids, this leads to massive path symmetry: multiple paths of identical weight are explored simultaneously. Jump Point Search resolves this by pruning symmetric paths through natural neighbors and forced neighbors. A node x has a forced neighbor if the standard traversal rules would force an optimal path to branch uniquely past an obstacle.
Forced Neighbors and Jump Points
A forced neighbor is defined relative to a parent direction. For instance, moving horizontally with dx=1, if the cell (x, y+1) is walkable but (x-1, y+1) is blocked, then (x, y+1) is a forced neighbor. When a jump point search encounters a node with a forced neighbor, or when it reaches the target, it stops and marks that node as a jump point, pushing it onto the open set priority queue.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Harabor, D., & Grastien, A. (2011). Online Graph Pruning for Pathfinding on Uniform Grids. AAAI Conference on Artificial Intelligence.
- Harabor, D., & Grastien, A. (2014). The JPSPathfinder Algorithm. NICTA and Australian National University.