Improving jump point search

Daniel Harabor, Alban Grastien

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

50 Citations (Scopus)

Abstract

We give online and offline optimisation techniques to improve the performance of Jump Point Search (JPS): a recent and very effective symmetry-breaking algorithm that speeds up pathfinding in computer games. First, we give a new and more efficient procedure for online symmetry breaking by manipulating "blocks" of nodes at a single time rather than individual nodes. Second, we give a new offline pre-processing technique that can identify jump points apriori in order to further speed up pathfinding search. Third, we enhance the pruning rules of JPS, allowing it to ignore many nodes that must otherwise be expanded. On three benchmark domains taken from real computer games we show that our enhancements can improve JPS performance by anywhere from several factors to over one order of magnitude. We also compare our approaches with SUB: a very recent state-of-the-art offline pathfinding algorithm. We show that our improvements are competitive with this approach and often faster.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling
EditorsSteve Chien, Alan Fern
Place of PublicationPalo Alto California USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages128-135
Number of pages8
ISBN (Print)9781577356608
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2014 - Sheraton Harborside Hotel, Portsmouth, United States of America
Duration: 21 Jun 201426 Jun 2014
Conference number: 24th
http://icaps14.icaps-conference.org/
https://dl.acm.org/doi/book/10.5555/2683899 (Proceedings)

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2014
Abbreviated titleICAPS 2014
Country/TerritoryUnited States of America
CityPortsmouth
Period21/06/1426/06/14
Internet address

Cite this