Jump point search

In computer science, Jump Point Search (JPS) is an optimization to the A* search algorithm pathfinding algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers.

Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude.

History

Harabor and Grastien's original publication provides algorithms for neighbour pruning and identifying successors. The original algorithm for neighbour pruning allowed corner-cutting to occur, which meant the algorithm could only be used for moving agents with zero width; limiting its application to either real-life agents (e.g. robotics) or simulations (e.g. many games).

The authors presented modified pruning rules for applications where corner-cutting is not allowed the following year. This paper also presents an algorithm for pre-processing a grid in order to minimise online search times.

A number of further optimisations were published by the authors in 2014. These optimizations include exploring columns or rows of nodes instead of individual nodes, pre-computing "jumps" on the grid, and stronger pruning rules.

Future Work

Although Jump point search is limited to uniform cost grids and homogeneously sized agents, the authors are placing future research into applying JPS with existing grid-based speed-up techniques such as Hierarchical grids.