Combining Bounding Boxes and JPS to Prune Grid Pathfinding
Full Text: 12336-55527-1-PB.pdf
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.
Citation
S. Rabin, N. Sturtevant. "Combining Bounding Boxes and JPS to Prune Grid Pathfinding". National Conference on Artificial Intelligence (AAAI), (ed: Dale Schuurmans, Michael P. Wellman), pp 746-752, March 2016.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Rabin+Sturtevant:AAAI16,
author = {Steve Rabin and Nathan R. Sturtevant},
title = {Combining Bounding Boxes and JPS to Prune Grid Pathfinding},
Editor = {Dale Schuurmans, Michael P. Wellman},
Pages = {746-752},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2016,
}Last Updated: July 05, 2020Submitted by Sabina P
