Pathfinding Over Streaming Terrain: Intrinsic Detail In Navigation Mesh Generation
By: James Stewart
Supervisor: Anton Ephanov
Masters of Interactive Technology degree conferred March 23, 2007
Thesis / Project completed: March 21, 2007

Game developers working with next-generation hardware face two technical challenges: leveraging the power of multicore architectures and shoehorning the massive content demands of AAA titles into the limited RAM available on modern consoles. How developers address these challenges has implications for all subsystems within an application, especially the control logic of the game itself. Simulation programmers can no longer assume that an asset will be available in system memory at the time a script invokes its use; next-generation titles will have to page geometry, sound, and other resources rapidly in and out of memory to present the rich virtual worlds consumers have come to expect, while remaining synchronized with numerous threads handling other aspects of the game.

A particular version of this problem is pathfinding. AI must still move entities from point A to point B, but now it is possible that point B is not available in system memory, but must be paged from storage media such as a hard drive or optical media.

This thesis describes a method to generate high-fidelity paths over a terrain of any size. The key to this approach is the Restricted Quadtree Triangulation (RQT), which provides the minimal representation of a height map given an object-space error metric. RQT is ideal for navigation meshes because it represents low-frequency regions (flat plains, for example) with the fewest needed vertices while preserving detail in high-frequency terrain.

At runtime, path generation determines a preliminary routine over a high-tolerance (high error) representation of the entire terrain, then refines the initial path in subsequent frames by paging low-tolerance navigation meshes for terrain chunks in the order they occur along the path. Crucial details—a narrow valley through an otherwise impassible mountain iv range, for example—are omitted by naïve simplifications (like increasing sample stride) but preserved by RQT.

This approach is less complex than various schemes to stitch streaming data, avoids backtracking during path refinement and works transparently alongside other methods of navigation mesh simplification. This strategy for pathfinding scales to any number of available threads, and is capable of generating paths for large numbers of entities.

Key Terms: Navigation Mesh Generation, Mesh Refinement, Restricted Quadtree Triangulation, Streaming Terrain, Pathfinding.

Download entire thesis (.pdf)