Recast & Detour
NavMesh Series - Part 1
Other articles in the series:
A navigation mesh (NavMesh) is a set of interconnected polygons that are generated through an analysis of the environment. They represent the walkable surfaces.
The NavMesh serves as a guiding tool for AI-controlled entities, allowing them to navigate the game world while avoiding obstacles. It provides spatial information about the environment, such as the type of walkable surfaces, height and elevation data, and other relevant attributes.
This information can be used by AI systems to make informed decisions, such as determining the nearest cover location or planning optimal paths.
Unreal Engine supports two types of NavMeshes:
Global (also known as Unified)
World-Partitioned (experimental as of UE 5.2)
The topic of world partitioning will be tackled in a follow-up article.
A Global NavMesh fully covers an area, it is not divided into smaller parts (i.e.: partitioned).
In order to reduce memory usage and improve performance, the polygons that make up the NavMesh are grouped together to form tiles, which provide additional granular control over which polygons are loaded or unloaded at runtime based on the proximity of the player or AI agents.
The quantity of tiles and polygons generated is determined by several factors, including the dimensions of the covered area, the complexity of the environment, and the generation configuration.
Before delving deeper into the NavMesh generation process within Unreal Engine (a topic for the next article), it is essential to grasp the inner workings of the library on which it relies: Recast & Detour.
The Recast & Detour library shipping with UE had modifications made to it.
We will be covering “vanilla” v1.6.0 of Recast (latest version as of this writing).
The next article will discuss the modifications made by Epic, as well as how the library is integrated within UE.
Recast & Detour
Generating a NavMesh in Unreal creates an actor of type ARecastNavMesh. The Recast prefix originates from Epic’s use of the Recast & Detour open source library.
The library is made up of two toolsets: Recast, which handles the generation of the NavMesh, and Detour for pathfinding using the data generated with Recast.
The Recast generation pipeline consists of several steps. Initially, triangles within the NavMesh's generation boundaries are classified as walkable or non-walkable based on their slope, with the maximum slope angle being adjustable.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/Recast.cpp
/* ========================================================================
Triangle Categorization (i.e.: walkable or not)
======================================================================== */
void rcMarkWalkableTriangles(rcContext* context,
const float walkableSlopeAngle,
const float* verts, const int numVerts,
const int* tris, const int numTris,
unsigned char* triAreaIDs)
{
(...)
const float walkableThr = cosf(walkableSlopeAngle / 180.0f * RC_PI);
float norm[3];
for (int i = 0; i < numTris; ++i)
{
const int* tri = &tris[i * 3];
calcTriNormal(&verts[tri[0] * 3], &verts[tri[1] * 3], &verts[tri[2] * 3], norm);
// Check if the face is walkable.
if (norm[1] > walkableThr)
{
triAreaIDs[i] = RC_WALKABLE_AREA;
}
}
}The triangles are converted (rasterized) into a 3D grid of voxels. This 3D grid, known as a heightfield, represents the environment by capturing both the ground surface and other structures or objects within it.
A heightfield is composed of cells, which are square units on the XZ plane. The dimensions of a cell can be configured. The smaller the cell, the higher the resolution of the heightfield.
As we iterate over all cells, we determine their overlap with the triangles making up the environment’s mesh - this overlap represents obstructed space. This is accomplished by taking a cell on the XZ plane and projecting it upwards. Anything that overlaps does so for a certain Y range. This range is used to create spans, representing the height variations where obstructions exist within the cells.
A cell contains [0, X] spans.
Based on the slope of the triangles overlapping with the cells, spans are marked as walkable or non-walkable.
The elevation data from the spans, along with the position of the cells on the XZ plane, enables the construction of the 3D grid of voxels, accurately representing the terrain and obstacles within the environment.
Spans represent the height variations where obstructions exist within a heightfield cell.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastRasterization.cpp
bool rcRasterizeTriangles(...)
{
// Invokes rasterizeTri()
}
static bool rasterizeTri(...)
{
// Invokes dividePoly() and addSpan()
}
static void dividePoly(...)
{
}
static bool addSpan(...)
{
}The heightfield is subjected to a series of filtering operations which aim to refine its data, removing any artifacts or noise, as well as enhance its accuracy.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastFilter.cpp
void rcFilterLowHangingWalkableObstacles(...)
{
// If an unwalkable span has a walkable span directly under it, and the
// height difference (climb) between them is under a configured threshold,
// the unwalkable span is marked as walkable.
}
void rcFilterLedgeSpans(...)
{
// Marks spans as unwalkable if close to a ledge or on a steep slope.
}
void rcFilterWalkableLowHeightSpans(...)
{
// Remove walkable flag from spans which do not have enough
// space above them for the agent to stand there.
}Next, the heightfield undergoes a conversion process to become a compact heightfield, aimed at optimizing processing speed. As part of this optimization, the dynamically allocated memory used by the non-compact heightfield is reorganized into blocks of sequential memory.
By arranging the data to fit in blocks of memory that the computer's processor can retrieve at once from main memory (i.e.: cache lines), cache locality is improved. Improved locality reduces the occurrence of cache misses, where data needs to be fetched from main memory because it is not found in the CPU's caches (L1/L2/L3). This results in faster memory access times and overall improved performance, as the CPU spends less time waiting for data from main memory.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/Recast.cpp
bool rcBuildCompactHeightfield(...)
{
}Walkable areas are then eroded based on a walkable radius config. This ensures that the data takes into account the physical constraints of the entities that will eventually make use of the NavMesh. A larger walkable radius is used to accommodate larger entities, ensuring they have enough room to navigate the environment.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastArea.cpp
bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf)
{
// Any spans that are closer to a boundary or obstruction than the
// specified radius are marked as unwalkable.
}With filtering complete, a distance field is created from the heightfield data.
The algorithm operates in two passes. In the first pass, it traverses the heightfield from the top left to the bottom right, calculating the walkable distance for each spans of a cell. The value is determined by considering the number of neighboring spans that are walkable. To ensure complete coverage, the process is repeated in a second pass, this time traversing the heightfield from the bottom right to the top left.
The distances are then “blurred” to smooth the transitions between values.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastRegion.cpp
bool rcBuildDistanceField(...)
{
}
static unsigned short* boxBlur(...)
{
}The heightfield is then partitioned into regions. Recast offers three different partitioning algorithms: Watershed, Monotone and Layer. Only Watershed relies on the previously described distance field. For all algorithms, the goal is to create simple regions by grouping cells based on their walkable property and environment connectivity.
Each algorithm has it’s advantages and disadvantages, detailing them is outside the scope of this article.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastRegion.cpp
bool rcBuildRegions(...)
{
}
bool rcBuildRegionsMonotone(...)
{
}
bool rcBuildLayerRegions(...)
{
}Next, contours are extracted from the regions by identifying boundaries.
// Source: https://github.com/recastnavigation/recastnavigation
// File: Recast/Source/RecastRegion.cpp
bool rcBuildContours(...)
{
}Finally, polygons are generated from the contours to form the NavMesh.
We’ve covered quite a few things today and while certain details were briefly mentioned, we will delve further into them in the next post, which will focus on how Unreal Engine leverages the Recast library. This upcoming article will provide a more comprehensive exploration of the topic.
I hope you found this post informative, and I look forward to sharing more insights in the next installment.
Well described and informative post! Looking forward to the next.