Navmeshes in the Source Engine

In 2013 I implemented Recast/Detour into the source engine for Zeitgeist (a game that has never seen the light of day), replacing the Nodegraph for NPC navigation.

Recast/Detour comes with a demo program that already works fine as a standalone toolset. I just needed to extend the demo with my own code to import BSP maps (including displacements) and collision meshes of all static objects (prop_static). The navigation mesh could then be generated from the imported geometry and exported into a file.

For improved NPC locomotion I additionally replaced the hacky Half-Life 2 collision avoidance code with Optimal Reciprocal Collision Avoidance. You can find more info on that in this post.

Overall the changes resulted in a smoother, more natural navigation, and easier authoring. One extra benefit was that NPCs could be restricted from going to areas outside of the navmesh (like falling into the underground tracks, see the images below). Previously, this kind of walkable-area-restriction had to be done using invisible NPC-only collision geometry. With better collision avoidance, NPCs also didn’t clog up bottlenecks nearly as often.

The London-Underground map you can see in the images also featured a system I created where NPCs would enter the map, walk to an idle spot, wait for the train to arrive, enter the train, assume their idle animations and get despawned as soon as the train left the station.