Optimization using boundary lookup jump point search

Jason Traish, James Tulip, Wayne Moore

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

Cache based path finding algorithms lose much of their advantage in dynamic environments where fast online search algorithms are required. Jump Point Search (JPS) is such a fast algorithm. It works by eliminating most map nodes from evaluation during path expansion. Boundary Lookup Jump Point Search (BL-JPS) is a modification that improves the speed of JPS. BL-JPS records the positions of obstacle boundaries and uses these via direct lookup to eliminate much of the iteration involved in searching for jump points in the JPS algorithm. Two sets of experiments are presented, demonstrating the effects of BL-JPS in both static and dynamic environments. The effects of different approaches to cache rebuilding for JPS+ in dynamic environments are also evaluated. Results show that BL-JPS is generally much faster than JPS. It is slower than JPS+ in static environments, but in dynamic environments, BL-JPS outperforms JPS+ for a single search. When multiple paths are searched, the effects of cache rebuilding gradually dominate the effects of search speed, resulting in JPS+ again becoming faster. However, combining JPS+ with BL-JPS provides a very fast path finding algorithm (BL-JPS+) that outperforms JPS+ over a range of map types and numbers of paths searched.
Original languageEnglish
Pages (from-to)268-277
Number of pages10
JournalIEEE Transactions on Computational Intelligence and AI in Games
Volume8
Issue number3
Early online dateApr 2015
DOIs
Publication statusPublished - Sept 2016

Fingerprint

Dive into the research topics of 'Optimization using boundary lookup jump point search'. Together they form a unique fingerprint.

Cite this