Jump point search, or JPS, is an optimization of the A* search algorithm for uniform-cost grids that reduces symmetries in the search by pruning certain nodes based on assumptions about a node's neighbors. This lets the algorithm take long jumps along straight horizontal, vertical and diagonal lines in the grid rather than the small single-step moves ordinary A* considers, preserving A*'s optimality while potentially reducing running time by an order of magnitude.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.