Improving jump point search

Daniel Harabor, Alban Grastien

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

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
Duration: 21 Jun 201426 Jun 2014
Conference number: 24
http://icaps14.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2014
Abbreviated titleICAPS 2014
CountryUnited States
CityPortsmouth
Period21/06/1426/06/14
Internet address

Cite this

Harabor, D., & Grastien, A. (2014). Improving jump point search. In S. Chien, & A. Fern (Eds.), Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (pp. 128-135). Palo Alto California USA: Association for the Advancement of Artificial Intelligence (AAAI).
Harabor, Daniel ; Grastien, Alban. / Improving jump point search. Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. editor / Steve Chien ; Alan Fern. Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2014. pp. 128-135
@inproceedings{659d7c40a27c4760834da1989d41520a,
title = "Improving jump point search",
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.",
author = "Daniel Harabor and Alban Grastien",
year = "2014",
language = "English",
isbn = "9781577356608",
pages = "128--135",
editor = "Steve Chien and Alan Fern",
booktitle = "Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States",

}

Harabor, D & Grastien, A 2014, Improving jump point search. in S Chien & A Fern (eds), Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto California USA, pp. 128-135, International Conference on Automated Planning and Scheduling 2014, Portsmouth, United States, 21/06/14.

Improving jump point search. / Harabor, Daniel; Grastien, Alban.

Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. ed. / Steve Chien; Alan Fern. Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2014. p. 128-135.

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

TY - GEN

T1 - Improving jump point search

AU - Harabor, Daniel

AU - Grastien, Alban

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84933042641&partnerID=8YFLogxK

M3 - Conference Paper

SN - 9781577356608

SP - 128

EP - 135

BT - Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling

A2 - Chien, Steve

A2 - Fern, Alan

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto California USA

ER -

Harabor D, Grastien A. Improving jump point search. In Chien S, Fern A, editors, Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. Palo Alto California USA: Association for the Advancement of Artificial Intelligence (AAAI). 2014. p. 128-135