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.