NavMesh Traverse Links

NAVMESH TRAVERSE LINKS

Click here for a video demo of the tool

After reverse engineering the navmesh system for the engine powering Apex Legends and Titanfall 2, several new challenges showed up. One of them being the file sizes; the levels of Apex Legends are incredibly large, and the navmeshes have to be static. Another issue is that NPC's could not jump from isolated polygon islands.

To address these problems, the following has to be done:

Convert the Recast C++ demo project into an actual navmesh editor.
Implement an algorithm to link various polygon islands together with custom traverse link portals.
Implement an algorithm to mark various polygon islands reachable/unreachable for the Detour runtime.
Implement an algorithm that prunes all unused polygons and associated data from the navmesh tile.

Since we are currently working on a custom Radiant level editor, I had to keep the demo code separated from the navmesh library. The algorithm has to be implemented as such it could be easily implemented into our new Radiant level editor once it becomes usable, along with the rest of the heavily modified Recast library.

To start, I had to address 2 issues in the Recast & Detour library, the first one being that many math functions were duplicated across Recast and Detour (Recast being the navmesh generator, Detour being the game's runtime). Many of these math functions were also missing from the Recast library, which I was intending to use. Instead of copying these over, I have decided to move everything into a shared math library instead and exposed it to both libraries, and deduplicate existing ones. This ensures maximum code portability while also reducing the chance of potential bugs or regressions.

The second issue is that the demo project was using a custom imgui implementation that simply did not scale towards my needs for turning it into an editor. As such, I've completely replaced the old ui library with Dear ImGui.

AUTOMATIC GENERATION

Traverse links are portals that allow the NPC to jump or climb from 2 isolated polygons. Each link has its own type (represented by color). The type dictates the traverse animation; a human or titan can only climb and jump on short walls, while a drone could fly, use rocket boosters, jump 50 meters in the air, etc.. Therefore, the length of each link plays an important role to decide what traverse type the portal gets!

Since its unrealistic to manually place traverse links in a map that spans 2 kilometers in each direction, an automated solution has to be made. The idea is to go over each tile, iterate over each polygon in the tile, and take the polygon's detail mesh. From the detail mesh, we take the boundary sub-edge and start looking for nearby polygons to link to using the same process.

The source code for the algorithm can be found in this GitHub link

Some additional details regarding the algorithm:

When connecting to neighboring tiles, the algorithm favors the tile facing the sub-edge normal.
For the best results, the initial linking should be limited to internal polygons first.

To avoid having game specific code in the library, while also making it very easy to implement in our future Radiant level editor, I made the following struct that can be found in this GitHub link. All the programmer has to do is provide the parameters to the library with an already built navmesh tile, the rest happens automatically!

The order of portal establishment by user defined callbacks:

getTraverseType gets called with details about the potential link (edge vectors, slope angles, etc), a callback (currently implemented like this) returns the best suitable traverse type for this link. If the callback returns DT_NULL_TRAVERSE_TYPE, no link will be established. The algorithm will continue to the next edge.
findPolyLink gets called to check if we already linked these 2 polygons together with the same traverse type. If we did, but not with the provided traverse type, a pointer to the bitfield containing all established traverse types between the 2 polygons gets returned.
traverseLinkInLOS gets called to check if there is nothing blocking the path, this gets performed last as this performs intersection tests with the map's geometry and is slow. Once we can use the game's BVH4 collision system, it will be significantly faster. All we have to do is swap the callback!
addPolyLink gets called if we haven't linked anything between these 2 polygons before. If we did, we instead set the traverse type bit index in the bitfield that was provided by the former call to findPolyLink.

After establishing this code separation, I created a fine tuner in the editor that allowed one of our level designers to find the best values. Fine tuning the algorithm was a tedious process! But once we had the best values, it worked very well and consistently across all maps for Titanfall 2 and Apex Legends.

In the image above, both humans and drones can traverse the red links. The animation is determined by the game engine. Green however can only be traversed by drones and uses yet a different set of animations, in this case it's either the rocket booster or a high vertical jump. The fine tuner made this possible without having to change any code.

RUNTIME OPTIMIZATIONS

The last challenge is optimizing the generated navmesh files. For maps in Titanfall 2, this isn't really a huge problem as the maps are generally small, but Apex Legends is a whole different story. The image above shows a freshly generated navmesh for the map Worlds Edge, which is one of the largest maps in Apex Legends. The navmesh file was 273mb, which simply is too large. We also have to take into consideration that the game loads 5 different types of the navmesh, a detailed one for small entities, up to a much less detailed one for large entities such as titans.

By default, the Recast navigation library does not provide any utilities to optimize away unused polygons and its associated data, as this operation is rather involving. It only allows for removing complete tiles, but a tile can contain linked and unlinked polygons, so this wasn't sufficient for our use case.

The goal was to get the navmesh to at least 180mb to ensure maximum performance and minimum memory usage for the dedicated servers.

After spending a week into the problem, I wrote a function that rebuilds an entire navmesh tile and fixes all external and internal references to the remapped polygons. The way this works is by having the user either place a probe in the world or click on a polygon island that they wish to keep. The editor will traverse every polygon through their link references and marks all unselected polygons as dead. If a tile only consists of unlinked polygons, the tile will be marked with a special user ID and will be removed completely instead.

The source code of this function can be found in this GitHub link.

After placing the probe and running the prune selection tool, we can see the entire selected region highlighed. The traverse link stage was very useful as we can now select the entire region we want to keep with a single probe. Due to the line-of-sight checks before establishing links between various islands, we essentially prune out everything clipped inside geometry, or that was otherwise inaccessible by the NPC's in the game.

After running the new tool, we can see a significant amount of noise reduction; only reachable polygons are kept. The navmesh's file size has been reduced to 107mb while being functionally identical, far beyond my initial goal.

With that being done, there was one more issue left. By default, the Detour navmesh query system is made to always generate a path to the goal polygon, even if there is a clear separation between the 2 islands with no means of traversing the gap. This can be computationally heavy given the game can have many NPC's at once.

On top of this, since we have traverse links with various types, it's possible a certain isolated polygon is reachable for a drone, but not a human. This is generally solved with a query filter, but this still requires going over the linked list. In order to solve this problem while maintaining maximum performance, we have to group each polygon island with a unique group identifier. This is done by traversing each polygon in a tile and skipping the traverse portals or off-mesh connections we made earlier.

In the above image, I added a new render mode that visualizes polygon groups by color. There is also an option to display the group id's as text.

Anyways, now that we have the polygon islands grouped, all we have to do is create separate static tables for the human and drone NPC, with bit cells that correspond to each polygon island. The idea is to take both islands, check for any traverse link that connects the 2, and based on the traverse type mask that is provided by the editor (which is a copy of the mask used by the query filter in the runtime to filter out any links we don't want to use during pathing), and set the bit for the goal polygon island in the current island's bitcell if all conditions are met.

This allows us to perform a very cheap check before we decide to run the navmesh query logic: