Combining Bounding Boxes and JPS to Prune Grid Pathfinding

Authors

  • Steve Rabin DigiPin Institute of Technology
  • Nathan Sturtevant University of Denver

DOI:

https://doi.org/10.1609/aaai.v30i1.10076

Keywords:

heuristic search, jump point search, grids, pathfinding

Abstract

Pathfinding is a common task across many domains and platforms, whether in games, robotics, or road maps. Given the breadth of domains, there are also a wide variety of representations used for pathfinding, and there are many techniques which have been shown to improve performance. In the last few years, the state-of-the-art in grid-based pathfinding has been significantly improved with domain-specific techniques such as Jump Point Search (JPS), Subgoal Graphs, and Compressed Path Databases. In this paper we look at a specific implementation of the general idea of Geometric Containers, showing that, while it is effective on grid maps, when combined with JPS+ it provides state-of-the-art performance.

Downloads

Published

2016-02-21

How to Cite

Rabin, S., & Sturtevant, N. (2016). Combining Bounding Boxes and JPS to Prune Grid Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10076

Issue

Section

Technical Papers: Heuristic Search and Optimization