Jump point search

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 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]

References[edit]

  1. ^ a b D. Harabor; A. Grastien (2011). "Online Graph Pruning for Pathfinding on Grid Maps". 25th National Conference on Artificial Intelligence. AAAI. 
  2. ^ Witmer, Nathan (5 May 2013). "Jump Point Search Explained". zerowidth positive lookahead. Retrieved 9 March 2014.