Static NavMesh Generation
NavMesh Series - Part 2
In Part 1, we explored Recast & Detour, the library used by Unreal Engine for NavMesh generation.
Building upon that foundation, we now delve into the implementation details within Unreal for static NavMesh generation. As a reminder, a static NavMesh does not support runtime modifications to its geometry (in contrast to a dynamic NavMesh).
Topics covered in this article:
Overview of systems and configuration options involved in the generation process.
Code analysis (UE 5.2).
While extensive, this article will not cover dynamic NavMeshes, world partitioning, runtime pathfinding, and other important topics. These areas will be addressed in subsequent posts, giving them the focus they deserve.
For now, let’s focus on static NavMesh generation, from which all future topics will build upon.
Overview
Agents
An agent defines an entity that will navigate a NavMesh.
Navigation data is generated for each agent you configure.
You can configure as many agents as your project requires, each represented by a set of characteristics such as a radius, height and max step height. These properties are used as part of the generation process, such as for eroding walkable areas.
Each agent configuration sets a navigation data type, with RecastNavMesh being the default (hence Part 1 discussing Recast & Detour). Unreal gives you the flexibility of implementing your own type (e.g., navigation data not generated using Recast), though that is outside the scope of this series.
Boundaries
A NavMeshBoundsVolume defines the boundaries where NavMesh data is generated.
By mapping agents to a NavMeshBoundsVolume, we define what navigation data type is generated within its boundaries. A volume can support multiple agents.
Navigation Data
With agents and boundaries defined, the NavMesh generation process is able to generate navigation data.
The process takes into account the intersecting geometry within the defined boundaries, the agent’s generation parameters (e.g., agent radius, height, etc.), and the chosen navigation data type (e.g., Recast library).
For each supported agent, a unique instance of ARecastNavMesh stores the navigation data tailored to their characteristics.
Tiles and Layers
The 3D boundaries of a NavMeshBoundsVolume are made up of tiles of a fixed size, with each tile storing a portion of the navigation data. These tiles are further categorized into layers based on the height range they cover.
This subdivision allows for Unreal to leverage its Task system, a mechanism specifically designed for asynchronous work. This enables concurrent processing of tiles, effectively reducing generation runtime.
Within the Recast library, dtMeshTile represents a tile and holds the polygons and vertices of the NavMesh area they cover. They are stored as a linked list within a parent dtNavMesh.
Resolution
The NavMesh generation process, as explained in Part 1, starts with the generation of a heightmap (used for voxelization), with its cell size assuming a crucial role. All subsequent steps rely on this initial step.
Unreal provides low, default, and high resolution presets for configuring the heightmap’s cell dimensions.
The resolution presets are configured in the project settings and are applied per-tile during the NavMesh generation process.
Resolution selection at runtime is determined by NavModifierVolumes overlapping generation boundaries, e.g., NavMeshBoundsVolume.
The choice of resolution depends on gameplay and performance requirements. Opting for higher resolutions, achieved by using smaller cells, results in more detailed and precise NavMeshes. However, they also lead to increased memory usage, generation time, impacted runtime performance (due to having more data to process), and overfitting (e.g., minor geometry details are considered, yet are not necessarily relevant for navigation).
Code Analysis (UE 5.2)
Class Overview
UNavigationSystemV1
Oversees the entire navigation system within Unreal, including all instances of ARecastNavMesh.
FNavDataConfig
Describes an agent for which NavMesh data can be generated.
Name, radius, height, navigation data type, etc.
Owned by UNavigationSystemV1.
ARecastNavMesh
High-level manager class serving as a bridge between Unreal and the Recast library.
Provides access to generated Recast data, accessible from its owned FPImplRecastNavMesh instance.
Offers utility functions for various navigation-related operations.
ex: GetPolyNeighbors(), GetPolyEdges(), etc.
Owned by UNavigationSystemV1.
FPImplRecastNavMesh
Handles the private implementation details of ARecastNavMesh.
Wraps access to NavMesh data through owned pointers to Recast types (e.g., dtNavMesh, dtMeshTile).
Owned by ARecastNavMesh.
FRecastNavMeshGenerator
Manages the tile-based generation process by overseeing instances of FRecastTileGenerator. It leverages Unreal's Task system to parallelize the execution of all FRecastTileGenerator instances, maximizing performance during the generation process.
Owned by ARecastNavMesh.
FRecastTileGenerator
Responsible for generating navigation data for layered tiles within specific boundaries using the Recast library
Owns an array of FNavMeshTileData, which stores the navigation data for all layered tiles corresponding to the position covered by this generator.
Owned by FRecastNavMeshGenerator.
FNavMeshTileData
Holds the data generated by Recast for a single layered tile.
Owned by FRecastTileGenerator.
dtNavMesh
A low-level Recast type holding a NavMesh’s entire data set, including all layered tiles (e.g., dtMeshTile).
Owned by FPImplRecastNavMesh.
dtMeshTile
A low-level Recast type that stores all the polygons and vertices for a layered tile. It utilizes a header (e.g., dtMeshHeader) to store metadata that uniquely identifies its corresponding tile (e.g., x/y position, layer index, etc.).
Holds a pointer to the next layered tile.
Owned by dtNavMesh.
Logic & Data Flow
Non-essential statements have been excluded from code snippets to highlight only statements that facilitate the comprehension of the static NavMesh generation logic.
Function names remain unchanged and can serve as references to the original code accessible from Epic's Git repository (v5.2).
The goal is not to provide a per-statement analysis of the code, but rather describe the overall logic and data flow.
The (x) syntax references a numbered statement in the code snippet being discussed.
Entry Point
UNavigationSystemV1::Build() serves as the entry point to the generation process.
First, the function checks if there are any ANavMeshBoundsVolume instances with valid boundaries (1). These volumes define areas where NavMesh data will be generated.
If at least one valid boundary exists, SpawnMissingNavigationData() (2) creates an ARecastNavMesh instance per supported agent type. An agent type is considered supported if a ANavMeshBoundsVolume is configured with support for it.
ARecastNavMesh is a high-level manager class that functions as a bridge between Unreal and Recast. To facilitate quick lookup, a mapping is maintained between agent types and their corresponding ARecastNavMesh instance (3).
ARecastNavMesh does not directly interact with the Recast library. Instead, it delegates this responsibility to its unique instance of FRecastNavMeshGenerator, which is constructed by invoking the RebuildAll() function (4, 5).
We’ll cover the EnsureBuildCompletion() function (6) when we discuss FRecastTileGenerator.
FRecastNavMeshGenerator
FRecastNavMeshGenerator is unique to each instance of ARecastNavMesh (7, 8). Its primary purpose is to coordinate the parallelization of agent-specific work for all tiles within the boundaries where NavMesh data should be generated.
Reminder: Each supported agent type has its own dedicated ARecastNavMesh. As FRecastNavMeshGenerator is owned by an instance of ARecastNavMesh, the data produced by the generator is also specific to that particular agent.
The generator’s Init() function (9) configures the properties that will be used during the generation process. It also defines the boundaries within which navigation data will be generated. Finally, it determines the maximum number of Tasks that will execute parallel work.
Following initialization, the RebuildAll() function is invoked (10):
(11) ConstructTiledNavMesh():
Allocates memory for low-level Recast objects (e.g., dtNavMesh, dtMeshTile) to store generated NavMesh data.
These objects will be used by Unreal at runtime to execute navigation-related queries.
(12) MarkNavBoundsDirty():
Creates an FPendingTileElement for each tile requiring NavMesh data generation.
Those instances are stored in the PendingDirtyTiles array.
All that’s left is to run asynchronously the generation of navigation data for all dirty tiles.
Tile Generators
At this stage, all the necessary ARecastNavMesh and FRecastNavMeshGenerator instances have been created, with each generator holding a collection of tiles to process (e.g., PendingDirtyTiles).
The execution flow now returns to the entry point of the generation process, UNavigationSystem::Build(), where EnsureBuildCompletion() is called on each ARecastNavMesh instance (6).
ARecastNavMesh forwards the call to its FRecastNavMeshGenerator, which starts processing its PendingDirtyTiles collection by invoking ProcessTileTasksAndGetUpdatedTiles() (13).
Since there might be more tiles to process than the maximum number of tasks permitted to run in parallel (NumTasksToProcess), this function is invoked as many times as needed until data generation is completed for all tiles.
ProcessTileTasksAndGetUpdatedTiles() creates a unique instance of FRecastTileGenerator per tile requiring generation (14).
FRecastTileGenerator will interface directly with the Recast library.
Each FRecastTileGenerator is then wrapped within an FRecastTileGeneratorTask to handle its asynchronous execution (15).
Launching the task is done through StartBackgroundTask(), with progress monitored by adding an FRunningTileElement entry to the RunningDirtyTiles collection (16). After processing, the corresponding tile entries are removed from PendingDirtyTiles (17).
For debugging purposes, the global variable GNavmeshSynchronousTileGeneration can be set to force synchronous execution of tile generators.
To understand how navigation data is generated by FRecastTileGenerator you can examine its DoWork() function. The code interfaces with the Recast library and largely follows the same steps discussed in Part 1:
Rasterization of geometry triangles into a 3D grid of voxels (e.g., heightfield).
Filtering of generated heightfield and conversion into a compact heightfield.
Creation of a distance field from heightfield data.
Generation of layered data, e.g., rcBuildHeightfieldLayers()
With generation completed, FRecastTileGenerator stores the navigation data of each layered tile within instances of FNavMeshTileData. These are stored in its NavigationData array.
The final step involves FRecastNavMeshGenerator retrieving the content of the NavigationData array from all of its completed FRecastTileGeneratorTask instances. This data is then used to populate the dtNavMesh Recast object previously created in step (11).
The dtNavMesh object will be utilized by Unreal at runtime to execute navigation-related queries.
This article has provided a comprehensive overview of static NavMesh generation in Unreal Engine. We've explored the key components and processes involved, from defining agents, boundaries and resolutions to the coordination of asynchronous tile-based generation using ARecastNavMesh, FRecastNavMeshGenerator and FRecastTileGenerator.
Through detailed code analysis and logic flow, we've gained insight into how Unreal leverages its Task system to efficiently generate navigation data tailored to each agent's characteristics.
While this article focused on static NavMesh generation, it's only the beginning of our journey into Unreal Engine's navigation capabilities.
In the next installment, we will delve into the dynamic NavMesh generation process, where we'll tackle real-time modifications, obstacles, and other dynamic aspects essential for responsive navigation in dynamic game environments.
Lovely article, super helpful to understand Unreal's navmesh generation.
I am also hoping for a part3... I would like to hear more about: "navigation data not generated using Recast" - I wonder if you could include some info on that :)
Very nice. Hope part 3 is in the works :)