Combining Bounding Boxes and JPS to Prune Grid 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.
Cite
Text
Rabin and Sturtevant. "Combining Bounding Boxes and JPS to Prune Grid Pathfinding." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10076Markdown
[Rabin and Sturtevant. "Combining Bounding Boxes and JPS to Prune Grid Pathfinding." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/rabin2016aaai-combining/) doi:10.1609/AAAI.V30I1.10076BibTeX
@inproceedings{rabin2016aaai-combining,
title = {{Combining Bounding Boxes and JPS to Prune Grid Pathfinding}},
author = {Rabin, Steve and Sturtevant, Nathan R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {746-752},
doi = {10.1609/AAAI.V30I1.10076},
url = {https://mlanthology.org/aaai/2016/rabin2016aaai-combining/}
}