In computer science, jump point search 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,[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]
Description edit
The jump point search algorithm focuses on discovering jump points. A jump point represents a potential change of direction in the optimal path from the origin to a goal point.
Applicability edit
The jump point search algorithm is applicable to search problems that can be defined as a grid with the following characteristics:
- The problem graph must be represented as a grid consisting of square units.
- The movement cost must be uniform across the entire grid.
- Movement is constrained to eight directions: the four cardinal directions and the four diagonal directions.
These constraints are satisfied most obviously by using a grid to represent 2-dimensional space.
Assumptions edit
Given the above constraints jump point search can make the following simplifying assumptions when searching:
- The lowest-cost path between any two points on the grid is represented by the geometrically shortest path.
- It is only necessary to investigate a single path through any region of path symmetry.
- If the goal is reachable through a direct line of travel then no lower-cost path to the goal will exist.
Neighbour Pruning edit
Neighbour pruning rules are determined by the direction of travel and the presence of obstructions around a cell. Each cell has one natural neighbour, which exists when no obstructions are present. These diagrams illustrate the natural neighbours for both cardinal and diagonal directions.
Two different pruning rules have been published for cardinal travel when obstructions are present. One rule applies when corner-cutting is allowed[1]. Another pruning rule applies when corner-cutting is not permitted[3].
History edit
Harabor and Grastien's original publication provides algorithms for neighbour pruning and identifying successors[1]. 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; preventing 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 minimise online search times.
A number of further optimisations were published by the authors in 2014[4].
All the published modifications and optimisations preserve A* optimality.
References edit
- ^ a b c d 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. Retrieved 9 March 2014.
- ^ a b D. Harabor; A. Grastien (2012). The JPS Pathfinding System. 26th National Conference on Artificial Intelligence. AAAI.
- ^ Harabor, Daniel; Grastien, Alban. "Improving Jump Point Search" (PDF). Australian National University College of Engineering and Computer Science. Association for the Advancement of Arti- ficial Intelligence (www.aaai.org). Retrieved 11 July 2015.
Category:Game artificial intelligence Category:Graph algorithms Category:Search algorithms
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |