Faster Grid Pathfinding with Approximate Bounding Boxes
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 29-35
DOI: 10.1609/socs.v19i1.43070 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Mark Carlson und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Grid-based path planning is an important application used widely in computer games and robotics. One of the fastest current approaches to optimal grid-based path planning, JPS+BB+, relies on extensive pre-computation to compute, for each jump point node, pruning bounding boxes containing all points reachable optimally by leaving the node in each direction. With this, the search for a shortest path is almost direct, only rarely considering more than one leaving direction at each node. But the pre-computation is expensive, requiring a full Dijkstra search from each jump point node to every other node in the graph. For the largest grid maps, this may require over 8 hours. In this paper we explore how to speed up this pre-computation, at the expense of a decrease in the accuracy of the bounding boxes created. We show we can improve pre-computation time by up to two orders of magnitude while only increasing average search time by at most 60% but often less than 10%. The faster bounding box computation can also be used to compute bounding boxes for every node in the map, decreasing average search time by up to 20% with typically only a 10% increase in pre-processing time.
Zitieren
APA
Carlson, M., Harabor, D. D., & Stuckey, P. J. (2026). Faster Grid Pathfinding with Approximate Bounding Boxes. Proceedings of the International Symposium on Combinatorial Search, 19(1), 29-35. https://doi.org/10.1609/socs.v19i1.43070
Vancouver
Carlson M, Harabor DD, Stuckey PJ. Faster Grid Pathfinding with Approximate Bounding Boxes. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):29-35. doi:10.1609/socs.v19i1.43070
BibTeX
@article{Carlson2026,
author = {Carlson, Mark and Harabor, Daniel D. and Stuckey, Peter J.},
title = {Faster Grid Pathfinding with Approximate Bounding Boxes},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {29--35},
doi = {10.1609/socs.v19i1.43070}
}
EUVIMED