pathing over wireframe
Pathfinding Over Terrain
Direct 3D, Win32
REQUIREMENTS: DirectX August 2006 SDK or later.

Over my last two terms at Guildhall, I developed a pathfinding solution for streaming terrain. How does a game entity (such as an enemy solider) get from point A to point B when B isn't in system memory? With content demands increasing, the small amount of RAM available even on next-gen consoles forces developers to load assets only when they are needed, creating new challenges for how game logic interacts with those assets. I thought pathfinding over a terrain too large to fit into memory was an interesting version of this problem.

My solution was to adapt the level-of-detail concept to pathfinding. A representation of the terrain known in the literature as the “Restricted Quadtree Triangulation” (RQT) allows for lower frequency regions to be represented with less data (flat plains for example). Even the lowest level of detail maintains a high-fidelity representation of difficult terrain. By referencing a low level of detail model of the entire terrain, it is possible to create a “good enough” path to get the moving entity started and then refine the path over subsequent frames as space for higher levels of detail become available in the streaming cache.

I need huge terrains for my thesis, so I wrote MFB, which generates random terrain of arbitrary size using the faultline method. Users can tweak synthesis variables via an ini file. It is included as well.




Image 1: Path over large LOD terrain.



Image 2: Effect of multiple smoothing passes during terrain synthesis.


Image 3: Entity (near lower left) follows a path across the terrain marked by the saturated line.


Image 4: Restricted Quadtree Triangulation (RQT) terrain refinement. Top image is a 2D boolean array marking needed vertices for a given error tolerance. The bottom image shows the resulting index buffer.


Image 5: Demo allows user to view entity's progress from extreme vantages.




Back to Main Page