ABSTRACT
This chapter introduces the goal-bounding concept, walk through the runtime code, and then show the necessary preprocessing steps. For games that meet the constraints, goal bounding can speed up pathfinding dramatically—by nearly an order of magnitude. Not only can goal bounding be applied to any search algorithm on any type of search space, it can also be applied with other optimizations, such as hierarchical pathfinding, overestimating the heuristic, or open list optimizations. Goal bounding is a pathfinding optimization technique that can speed up A* by roughly eight times on a grid, however, it is applicable to any graph search space, including waypoint graphs or navmeshes. The chapter discusses experimental data that shows the effective speed-up to a standard A* implementation. For A* with goal bounding to work, it is assumed that every node edge has a precomputed bounding box containing all nodes that can be reached optimally through that edge.
