The JPS pathfinding system in 3D

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


The ability to quickly compute shortest paths in 3D grids is a technological enabler for several applications such as pipe routing and computer video games. The main challenge is how to deal with the many symmetric permutations of each shortest path. We tackle this problem by adapting Jump Point Search (JPS), a well-known symmetry breaking technique developed for fast pathfinding in 2D grids. We give a rigorous reformulation of the JPS pathfinding system into 3D and we prove that our new algorithm, JPS-3D, is optimality preserving. We also develop a novel method for limiting scan depth during jump operations, which can further reduce search time. Experimental results show significant improvements versus online A* search and previous attempts at generalising JPS. We demonstrate that searching with adaptive scan limits can yield additional speedups of over an order of magnitude.
Original languageEnglish
Title of host publicationProceedings of the International Symposium on Combinatorial Search
EditorsLukás Chrpa, Alessandro Saetti
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages8
ISBN (Electronic)1577358732
Publication statusPublished - 2022
EventInternational Symposium on Combinatorial Search 2022 - Vienna, Austria
Duration: 21 Jul 202223 Jul 2022
Conference number: 15th

Publication series

NameFifteenth InternationalSymposium on Combinatorial Search
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)


ConferenceInternational Symposium on Combinatorial Search 2022
Abbreviated titleSOCS 2022
Internet address


  • Bounding And Pruning Techniques
  • Symmetry Handling

Cite this