NavMesh Generation

The foundational step where the generator analyzes a 3D scene's geometry to identify surfaces an agent can traverse. This involves filtering polygons based on criteria like slope angle, step height, and surface normal. For example, a slope exceeding 45 degrees or a vertical gap taller than 0.3 meters would be marked as non-walkable. The algorithm typically starts from a designated agent 'seed' position and floods across connected, compliant faces.

Raw 3D geometry is tessellated into a set of convex polygons (usually triangles or monotone polygons) that form the mesh. This process simplifies complex concave geometry into a graph of navigable nodes. Key algorithms include:

• Recursive Subdivision: Splits large polygons along chosen axes.
• Monotone Partitioning: Creates long, thin polygons optimal for corridor-like spaces.
• Heightfield Voxelization: Converts the scene into a 2.5D grid, then extracts a surface mesh, common for terrains. The goal is to balance polygon count for pathfinding speed against navigation precision.

NavMesh generation is not one-size-fits-all; it is parameterized by the physical characteristics of the navigating agent. Critical parameters include:

• Agent Radius: Defines how close an agent can get to walls and obstacles, influencing mesh erosion.
• Agent Height: Determines the clearance required under overhangs and ceilings.
• Max Climb Height: The tallest step the agent can ascend.
• Max Slope Angle: The steepest incline the agent can traverse. These parameters are baked into the mesh, creating agent-specific navigation data.

The system must correctly process dynamic and static obstacles. Static obstacles (e.g., large buildings, permanent walls) are carved out of the base walkable area during generation. Exclusion volumes are user-defined 3D regions that explicitly forbid mesh generation, useful for marking hazardous areas. For dynamic obstacles (e.g., moving crates), the base NavMesh remains intact, but runtime navigation queries use local avoidance or a local grid to steer around them.

Beyond binary walkability, NavMeshes support semantic labeling of polygonal regions with different traversal costs and capabilities. Common area types include:

• Walkable: Standard cost.
• Not Walkable: Impassable.
• Jump: A link between disconnected meshes.
• Water: High cost, swim-only area.
• Door: Interactive link. Pathfinding algorithms like A* use these costs to find the optimal, not just the shortest, path, preferring roads over rough terrain, for instance.

These are manually or procedurally defined connections that allow agents to traverse gaps not represented by contiguous walkable polygons. They are essential for modeling actions like:

• Jumping across a chasm.
• Climbing a ladder or rope.
• Teleporting through a door or portal. An Off-Mesh Link is defined by two endpoints (3D points) and is treated as a special edge in the navigation graph. They bridge the gap between continuous surface navigation and discrete, scripted movement actions.

Dynamic obstacle avoidance enables AI agents to navigate around moving objects or changes in the environment that are not represented in the static NavMesh.

• Local Grids: A fine-grained 2D grid layered over the NavMesh where dynamic obstacles are marked as blocked, forcing local path replanning.
• NavMesh Links & Off-Mesh Connections: Predefined connections (e.g., for jumping over a gap or opening a door) that agents can use. Can be enabled/disabled dynamically.
• Runtime NavMesh Modifiers: Volumes that can carve holes or add walkable areas to the NavMesh at runtime, allowing for destructible environments or player-built structures.