Jump point search
|Graph and tree
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, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors. 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.
- D. Harabor; A. Grastien (2011). "Online Graph Pruning for Pathfinding on Grid Maps". 25th National Conference on Artificial Intelligence. AAAI.
- Witmer, Nathan (5 May 2013). "Jump Point Search Explained". zerowidth positive lookahead. Retrieved 9 March 2014.
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|