Jump point search

In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, jump point search (JPS) 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 (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.

Future work

Although jump point search is limited to uniform cost grids and homogeneously sized agents, the authors are placing future research into applying JPS with existing grid-based speed-up techniques such as hierarchical grids.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1294613544 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.