ABSTRACT
This chapter introduces the goal-bounding concept, moves through the runtime code, and then shows the necessary preprocessing steps. It discusses experimental data that shows the effective speed-up to a standard A* implementation. Goal bounding has three constraints that limit whether it is appropriate to use in the game: map constraint, memory constraint, and precomputation constraint. The other primary constraint is that goal bounding requires extra memory at runtime for the precomputed data. The name goal bounding comes from the core concept. Goal bounding can be similarly applied to navmeshes. 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. Precomputation consists of computing a bounding box for every edge of every node. At its core, goal bounding is an approximation of the Floyd–Warshall all-pairs shortest paths algorithm.
