Game AI Pro 3

22

Faster A* with Goal Bounding

Steve Rabin and Nathan R. Sturtevant

22.1    Introduction

22.2    Concept

22.3    Runtime

22.4    Precomputation

22.5    Empirical Results

22.6    Similarities to Previous Algorithms

22.7    Conclusion

References

22.1  Introduction

Goal bounding is a pathfinding optimization technique that can speed up A* by roughly eight times on a grid (Rabin and Sturtevant 2016), however, it is applicable to any graph search space, including waypoint graphs or navmeshes (navigation meshes). Goal bounding is not a search algorithm itself, but rather a method to prune the search space, thus radically reducing the number of nodes that need to be considered to find the goal. This is accomplished by preprocessing the search space ...