TileCache for custom NavMesh triangulation?

[rob-myers]

In my use-case I can already construct nice triangulations using triangle-wasm, purely in the XZ plane.

Is there any way to skip Recast's triangulation-generation, and construct tiles from a custom triangulation?

It seems natural to want to control the triangulation, either totally, or to some extent.
But I wonder whether I'm barking up the wrong tree, because I don't find any clear references online.

[isaac-mason]

This issue tracks supporting this in recast-navigation-js, there hasn't been any progress though: #17

I've also done some searching for common wisdom on how this is done with detour, and haven't found much.

Most have worked around this by running their existing navmesh triangles through recast. This isn't ideal but works fine for many cases.

Using a non-recast navmesh with detour is possible, you'd need to construct detour dtNavMeshCreateParams yourself instead of constructing it with recast. Related: https://github.com/isaac-mason/recast-navigation-js/blob/main/packages/recast-navigation-generators/src/generators/generate-solo-nav-mesh.ts#L353

It's not straightforward though, the data that detour requires is fairly coupled to what recast generates. In particular, recast generates & detour works with both a simple polygon mesh representation, and a detailed mesh representation that contains more accurate height data. This article gives a good overview: https://www.unrealdoc.com/p/navigation-mesh

I imagine most people wanting to use an existing navmesh with detour already have the detailed mesh representation. Maybe if it's straightforward to generate the simple polygon mesh representation a generic utility could be added to recast-navigation-js

The current recast-navigation-js bindings also don't make it easy to interact with dtNavMeshCreateParams. We could extend DetourNavMeshBuilder to support building navMeshCreateParams without recast structures, maybe using the Array wrappers. Currently there's only methods that take rcPolyMesh and rcPolyMeshDetail:

// https://github.com/isaac-mason/recast-navigation-js/blob/d3adca721ce1993976d4cc01881a61e76e9ecec3/packages/recast-navigation-wasm/src/Detour.cpp#L3

void DetourNavMeshBuilder::setPolyMeshCreateParams(dtNavMeshCreateParams *navMeshCreateParams, rcPolyMesh *polyMesh)
{
    navMeshCreateParams->verts = polyMesh->verts;
    navMeshCreateParams->vertCount = polyMesh->nverts;
    navMeshCreateParams->polys = polyMesh->polys;
    navMeshCreateParams->polyAreas = polyMesh->areas;
    navMeshCreateParams->polyFlags = polyMesh->flags;
    navMeshCreateParams->polyCount = polyMesh->npolys;
    navMeshCreateParams->nvp = polyMesh->nvp;

    rcVcopy(navMeshCreateParams->bmin, polyMesh->bmin);
    rcVcopy(navMeshCreateParams->bmax, polyMesh->bmax);
}

void DetourNavMeshBuilder::setPolyMeshDetailCreateParams(dtNavMeshCreateParams *navMeshCreateParams, rcPolyMeshDetail *polyMeshDetail)
{
    navMeshCreateParams->detailMeshes = polyMeshDetail->meshes;
    navMeshCreateParams->detailVerts = polyMeshDetail->verts;
    navMeshCreateParams->detailVertsCount = polyMeshDetail->nverts;
    navMeshCreateParams->detailTris = polyMeshDetail->tris;
    navMeshCreateParams->detailTriCount = polyMeshDetail->ntris;
}

[rob-myers]

Thanks for the references.

I originally asked because I wanted certain "doorway polygons" to be present in the recast navmesh.

The image above uses a constrained Delaunay triangulation.
Every "doorway" consists of two triangles forming an axis-aligned rectangle.

The image above uses Recast via your wonderful library, where cs is 0.149 and maxSimplificationError is 0.5. The indicated doorway does not have this property, and I've failed to fix it by tuning the inputs to your function generateTileCache.

Given such doorway polygons I can apply filters to prevent agents from navigating through the locked doors. But it's not super-important since this can be achieved via hierarchical path-finding (e.g. rooms are nodes, doors are edges).

So, maybe I'm asking for something which is too complex and not really justified (yet).

[isaac-mason]

I think I understand your use case now.

Another way you might be able to support this is by assigning custom areas for the doors as part of the recast navmesh generation process. There's an example of marking areas here: https://recast-navigation-js.isaacmason.com/?path=/story/advanced-custom-areas--compute-path

When marking areas as part of the recast navmesh generation process, you are interacting with the compact heightfield - an intermediate structure before the final navmesh polygons. This means the resulting navmesh polygons are affected by areas.

In the below screenshots from the custom areas storybook, the red area is an area I've marked as unwalkable, and the blue area I've marked as "water".

When I mark a box area as "water", the resulting navmesh polygons wrap around the marked area:

[rob-myers]

Thanks a lot, this sounds like just what I need. I'll report back.

[rob-myers]

It worked!

I kept track of where the doorway triangles were in the input triangulation, then marked them using markConvexPolyArea.

Now I can mark the doorways as open/closed, and e.g. avoid agents being pushed through doors by other agents.

[isaac-mason]

Glad to hear you got it working! 🙂

[isaac-mason]

Related google discussion: https://groups.google.com/g/recastnavigation/c/nrYwdskj8E8/m/UjIHXXkvBAAJ