Faster Grid Pathfinding with Approximate Bounding Boxes

Abstract

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.