skip to main content
10.1145/3274856.3274883acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicaitConference Proceedingsconference-collections
short-paper

Modification of JPS+ Algorithm for Optimal Pathfinding on Uniform-Cost Grids

Published: 01 November 2018 Publication History

Abstract

Pathfinding is a widespread task in many domains, including computer games, robotics and road maps. This paper describes the work of JPS+ algorithm and puts forward its modifications allowing to reduce pathfinding time. We propose to use a visibility graph to modify the map pre-processing logic at the stage of Primary Jump Points calculation. The paper also puts forward modifications in the shortest path algorithm solved for two points: the logic of Target Jump Points work and Primary Jump Points filtering has been altered to deal with obstacles. We propose an open-source software solution that accommodates the modifications.

References

[1]
A. Botea, J.A. Baier, D. Harabor, and C. Hernández. 2013. Moving target search with compressed path databases. ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling (2013), 288--292.
[2]
Xiao Cui and Hao Shi. 2011. A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security 11 (2011), 125--130.
[3]
D. Harabor and A. Grastien. 2014. Improving jump point search. Proceedings International Conference on Automated Planning and Scheduling, ICAPS 2014-January (2014), 128--135.
[4]
S. Rabin. 2013. Game AI Pro: Collected Wisdom of Game AI Professionals. Taylor & Francis. 598 pages.
[5]
S. Rabin. 2017. Game AI Pro 3: Collected Wisdom of Game AI Professionals. CRC Press. 514 pages.
[6]
T. Uras, S. Koenig, and C. Hernández. 2013. Subgoal graphs for optimal pathfinding in eight-neighbor grids. ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling(2013), 224--232.

Cited By

View all
  • (2023)Improved JPS+ Path Planning Algorithm Based on Hexagonal Grid MapProceedings of 2022 International Conference on Autonomous Unmanned Systems (ICAUS 2022)10.1007/978-981-99-0479-2_267(2885-2896)Online publication date: 10-Mar-2023
  • (2022)An optimization algorithm for path generated by Jump point search2022 IEEE International Conference on Mechatronics and Automation (ICMA)10.1109/ICMA54519.2022.9856042(1574-1580)Online publication date: 7-Aug-2022

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
ICAIT'2018: Proceedings of the 3rd International Conference on Applications in Information Technology
November 2018
171 pages
ISBN:9781450365161
DOI:10.1145/3274856
© 2018 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

In-Cooperation

  • University of Aizu: University of Aizu

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2018

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. A*
  2. JPS
  3. JPS+
  4. grid
  5. pathfinding

Qualifiers

  • Short-paper
  • Research
  • Refereed limited

Funding Sources

Conference

ICAIT'2018

Acceptance Rates

ICAIT'2018 Paper Acceptance Rate 33 of 56 submissions, 59%;
Overall Acceptance Rate 122 of 207 submissions, 59%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Improved JPS+ Path Planning Algorithm Based on Hexagonal Grid MapProceedings of 2022 International Conference on Autonomous Unmanned Systems (ICAUS 2022)10.1007/978-981-99-0479-2_267(2885-2896)Online publication date: 10-Mar-2023
  • (2022)An optimization algorithm for path generated by Jump point search2022 IEEE International Conference on Mechatronics and Automation (ICMA)10.1109/ICMA54519.2022.9856042(1574-1580)Online publication date: 7-Aug-2022

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media