1 Answers
In computer science, jump point search is an optimization to the A* search 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 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.
6 views
Answered