Improving jump point search

Daniel Harabor, Alban Grastien

    Research output: Contribution to journalConference articlepeer-review

    89 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
    Pages (from-to)128-135
    Number of pages8
    JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
    Volume2014-January
    Issue numberJanuary
    Publication statusPublished - 2014
    Event24th International Conference on Automated Planning and Scheduling, ICAPS 2014 - Portsmouth, United States
    Duration: 21 Jun 201426 Jun 2014

    Fingerprint

    Dive into the research topics of 'Improving jump point search'. Together they form a unique fingerprint.

    Cite this