Principle:CARLA simulator Carla Pedestrian Navigation Mesh
| Knowledge Sources | |
|---|---|
| Domains | Navigation Mesh, Pedestrian Simulation |
| Last Updated | 2026-02-15 00:00 GMT |
Overview
A navigation mesh (NavMesh) is a polygonal representation of the walkable surfaces in a 3D environment, used to compute paths for pedestrian agents and to sample valid spawn locations on sidewalks and other navigable areas.
Description
In driving simulation, pedestrians must walk on sidewalks, cross streets at crosswalks, and navigate around obstacles like lampposts, benches, and parked vehicles. A navigation mesh provides the spatial data structure that enables this behavior.
A NavMesh is constructed by analyzing the 3D geometry of the simulation environment and generating a simplified polygon mesh that represents all surfaces a pedestrian can walk on. This mesh excludes roads (unless at crosswalks), building interiors, water, and elevated surfaces that are not accessible by walking.
The NavMesh serves two primary purposes:
- Pathfinding -- Given a start and goal position, a pathfinding algorithm (typically A* on the NavMesh polygons, followed by path smoothing via a string-pulling algorithm) computes a collision-free walking path.
- Random Location Sampling -- By selecting a random point on the NavMesh surface, the system can generate valid pedestrian spawn locations that are guaranteed to be on walkable surfaces (sidewalks, plazas, crosswalks).
CARLA uses the Recast/Detour library (developed by Mikko Mononen), which is the industry-standard NavMesh solution used in game engines including Unreal Engine and Unity. Recast handles NavMesh generation (voxelization of geometry, region partitioning, contour tracing, polygon mesh creation), while Detour handles runtime pathfinding queries.
The NavMesh is generated offline (at map build time) through the following stages:
- Voxelization -- The 3D environment geometry is rasterized into a regular grid of voxels (3D pixels). Each voxel is marked as solid or empty.
- Walkable Surface Detection -- Voxels with a surface slope below a configurable maximum (typically 45 degrees) are marked as walkable. Surfaces too close to overhead geometry (low clearance) are excluded.
- Region Partitioning -- Connected groups of walkable voxels are partitioned into non-overlapping regions using watershed or monotone partitioning.
- Contour Tracing -- The boundary of each region is traced to create simplified contour polygons.
- Polygon Mesh Generation -- Contours are triangulated into convex polygons, forming the final NavMesh. Adjacent polygons store connectivity information for pathfinding.
Usage
The navigation mesh is used when you need to:
- Spawn pedestrians at random but valid sidewalk locations
- Compute walking paths for pedestrian AI controllers
- Ensure pedestrians do not walk through walls, into traffic lanes (except at crosswalks), or into other non-walkable areas
- Support crowd simulation with many simultaneous pedestrian agents
Theoretical Basis
Recast/Detour Architecture
Recast (Offline - NavMesh Generation):
Input: 3D triangle mesh of the environment
Step 1: Voxelize into heightfield (cell_size, cell_height)
Step 2: Filter walkable surfaces (agent_height, agent_radius, max_slope)
Step 3: Partition into regions (watershed algorithm)
Step 4: Trace contours and simplify
Step 5: Build polygon mesh with adjacency graph
Output: NavMesh binary file (.bin)
Detour (Runtime - Pathfinding):
Input: NavMesh + start_position + goal_position
Step 1: Find nearest polygon to start and goal positions
Step 2: A* search on polygon adjacency graph
Step 3: String-pulling (funnel algorithm) to produce smooth path
Output: List of waypoints forming the walking path
To sample a random location on the NavMesh, the algorithm:
- Select a random polygon from the mesh, weighted by polygon area (larger polygons are more likely to be selected)
- Generate a random point within the selected polygon using barycentric coordinates
function random_point_on_navmesh(navmesh):
total_area = sum(polygon.area for polygon in navmesh.polygons)
r = random_uniform(0, total_area)
cumulative = 0
for polygon in navmesh.polygons:
cumulative += polygon.area
if cumulative >= r:
# Generate random point in this polygon using barycentric coords
u, v = random_uniform(0,1), random_uniform(0,1)
if u + v > 1:
u, v = 1 - u, 1 - v
point = (1-u-v)*polygon.v0 + u*polygon.v1 + v*polygon.v2
return point
Crowd Simulation Integration
Detour includes a DetourCrowd module that manages multiple agents on the NavMesh simultaneously. It handles:
- Local avoidance -- Agents steer around each other using velocity obstacles (VO) or reciprocal velocity obstacles (RVO)
- Corridor following -- Each agent maintains a corridor (sequence of NavMesh polygons) representing its current path, which is dynamically updated
- Separation -- A minimum distance is maintained between agents to prevent overlapping
The crowd simulation operates in the following loop per tick:
For each simulation tick:
For each agent in crowd:
1. Update agent's position on the NavMesh
2. Check if current corridor is still valid
3. If goal reached or corridor invalid, replan path
4. Compute desired velocity toward next corridor waypoint
5. Apply local avoidance against nearby agents
6. Integrate velocity to update position