Jump point search
In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning,[1] 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.[2]
Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude.[1]
History[edit]
Harabor and Grastien's original publication provides algorithms for neighbor pruning and identifying successors.[1] The original algorithm for neighbor 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.[3] This paper also presents an algorithm for pre-processing a grid in order to minimize online search times.
A number of further optimizations were published by the authors in 2014.[4] 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[edit]
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.[4][5]
References[edit]
- ^ a b c D. Harabor; A. Grastien (2011). Online Graph Pruning for Pathfinding on Grid Maps (PDF). 25th National Conference on Artificial Intelligence. AAAI.
- ^ Witmer, Nathan (5 May 2013). "Jump Point Search Explained". zerowidth positive lookahead. Archived from the original on 2014-03-10. Retrieved 10 March 2014.
- ^ D. Harabor; A. Grastien (2012). The JPS Pathfinding System. 26th National Conference on Artificial Intelligence. AAAI. Archived from the original on 2020-11-09. Retrieved 2015-07-11.
- ^ a b Harabor, Daniel; Grastien, Alban. "Improving Jump Point Search" (PDF). Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Retrieved 11 July 2015.
- ^ Adi Botea; Martin Muller (2004). "Near Optimal Hierarchical Path-Finding" (PDF). University of Alberta. University of Alberta.