Recursive AI

Build a 2D navmesh from polygon obstacles in C#

OnePath is a free, open-source pathfinding library for .NET from Recursive AI. MIT or Apache-2.0, no native dependencies.

A navigation mesh divides walkable space into connected polygons. Obstacle holes leave space the character cannot enter.

Terminal
dotnet add package RecursiveAI.OnePath

Requires .NET 10 (net10.0); .NET 9 and earlier aren’t supported.

C#
using RecursiveAI.OneMath;
using RecursiveAI.OnePath;
using RecursiveAI.OnePath.Mesh.Build2D;
 
var outline = new Outline(
    new Vector2D[] { new(0,0), new(20,0),
        new(20,12), new(0,12) },
    new[] { new Vector2D[] {
        new(8,4), new(12,4),
        new(12,8), new(8,8) } });
var mesh = NavMesh.Build2D(new[] { outline });
var route = mesh.FindPath(
    new(2,0,6), new(18,0,6));
Console.WriteLine($"Route: {route.Status}");
Text
Route: Found

Unzip the example, then dotnet run.

The full program

The floor and obstacle coordinates are defined below. The program queries a path, tests the direct line, saves and reloads the mesh, and checks that each returned segment stays on the mesh.

C#
using RecursiveAI.OneMath;
using RecursiveAI.OnePath;
using RecursiveAI.OnePath.Mesh.Build2D;
 
var outline = new Outline(
    new Vector2D[] { new(0,0), new(20,0), new(20,12), new(0,12) },
    new[] { new Vector2D[] { new(8,4), new(12,4), new(12,8), new(8,8) } });
var mesh = NavMesh.Build2D(new[] { outline });
var route = mesh.FindPath(new(2,0,6), new(18,0,6));
Console.WriteLine($"Route: {route.Status}");
foreach (var point in route.Points)
    Console.WriteLine(point.Position);
Console.WriteLine($"Direct line blocked: {mesh.Raycast(new(2,0,6), new(18,0,6), out _)}");
var loaded = NavMesh.Load(mesh.Save());
Console.WriteLine($"Loaded route: {loaded.FindPath(new(2,0,6), new(18,0,6)).Status}");
bool clear = true;
for (int i = 1; i < route.Points.Count; i++)
    clear &= !mesh.Raycast(route.Points[i-1].Position, route.Points[i].Position, out _);
Console.WriteLine($"Route segments clear: {clear}");

dotnet run prints:

Text
Route: Found
(2, 0, 6)
(7.79296875, 0, 3.400390625)
(12.20703125, 0, 3.400390625)
(18, 0, 6)
Direct line blocked: True
Loaded route: Found
Route segments clear: True

Invalid coordinates throw ArgumentOutOfRangeException; when routing does not succeed, inspect route.Status before consuming the points.

Variations

Build for a smaller character. Replace the Build2D line in the full program; Small uses radius 0.3 instead of 0.6.

C#
var mesh = NavMesh.Build2D(new[] { outline },
    NavSettings.Small);
Text
Route: Found
(2, 0, 6)
(7.896484375, 0, 3.7001953125)
(12.103515625, 0, 3.7001953125)
(18, 0, 6)
Direct line blocked: True
Loaded route: Found
Route segments clear: True

The short answer

Pass an Outline containing the floor boundary and obstacle rings to NavMesh.Build2D. Each obstacle is a hole in that outline, not another walkable outline. The builder resolves the region, shrinks it by the configured radius, partitions it into convex polygons and assembles a tiled navigation mesh. Query that mesh with FindPath using world-space positions.

The example’s floor runs from (0, 0) to (20, 12); the obstacle runs from (8, 4) to (12, 8). The geometry plane maps to world X/Z, so a 2D point (2, 6) becomes a query point (2, 0, 6). World Y stays at FloorY. This is a flat-floor build, not a reconstruction of ramps or stacked floors from 3D geometry.

How to generate a navmesh?

Start with the area a character may occupy. Put its outside ring and every hole into one Outline. Rings close automatically from the last vertex to the first; they need at least three vertices. Ring orientation does not decide whether an area is a hole: the outline uses the even-odd fill rule. Separate outlines are unioned, so passing an obstacle as a second outline would add walkable space instead of removing it.

For a separately authored obstacle region, the other supported route is Region.Difference: resolve the walkable region and the obstacle region with the same snap grid, subtract the obstacle, and pass the resulting region to Build2D. The geometry rules are in the 2D geometry documentation.

Set the character radius before building. OnePath’s default radius is 0.6 world units. The build shrinks the walkable region, including the outside floor edge, so the character’s center stays away from obstacles and ledges. A passage that disappears during shrinking is not traversable for that character size. Build a separate mesh for another radius rather than assuming a route for a small character also fits a large one.

How does navmesh work?

The mesh represents walkable space with connected convex polygons. A route can bend around an obstacle without visiting every cell of a rectangular grid. In this example, the direct ray hits the removed area, but the path goes below it. The program also raycasts each returned segment and repeats the query after saving and loading the mesh. These checks describe this particular floor, not arbitrary input geometry.

Coordinates are snapped before geometry operations. Input coordinates must be finite and within ±2^21; SnapBits fixes the grid spacing at 2 raised to minus that value. Features thinner than the unit can disappear. When you let Build2D resolve outlines, the default chooses a snap grid compatible with CellSize. When you supply an already-resolved Region, its unit must be at least CellSize / 256; a finer region is rejected rather than silently losing distinct vertices in the mesh format. See the tile and rounding rules.

Self-intersecting, touching and duplicate-point input rings are legal under the documented fill rule. The resolved region removes crossing and overlapping boundaries before triangulation. That does not rescue an incorrectly modeled floor: a hole outside the boundary, an unintended overlap or a narrow corridor rounded away still changes the walkable area. Inspect the returned status and the route positions for the scene you actually intend to build.

All onepath recipes