computePath of straight line is detouring to hit steiner-points

[OdinvonDoom]

The problem:

Shown in the image is the output of Recast generateSoloNavMesh()... getDebugNavMesh(). The triangulation seems fine (if not a little needlessly heavy across some edges, but I'll presume it's necessary), but the issue comes when I try t navigate nearby one of these steiner-points using the output of navmeshQuery.computePath, and for some reason the path funneling is not going through all the triangles, but detouring to the point.

Background:

I'm making a 2D game, and trying to adapt Recast for it, given it's high regard and inadequacies of other navigation libraries, but I'm having a lot of trouble due to lacking sufficient usage guides/documentation, so I'm likely doing something wrong.

I've built a boundary polygon in the "Tiled" 2D map creation program, clipping off some outer edges and inner holes using "js-angusj-clipper", then triangulating the result with "poly2tri".

The resulting set of triangles, I manually convert to 3D, y-axis-up, right-handed space, and into the requisite flat arrays of positions and indices as required by Recast's generateSoloNavMesh, getting the result seen above from there.

Of course, given the amount of adaptation being done, I'm likely doing something wrong, but I can't find much to go off unless I happened to be using Three.js, which I am not.

Likely point of failure:

1. The "Delaunay" triangulation of "Poli2Tri" likely does not produce the same sort of polygonal divisions (size/structure) that would be found in a Three.js mesh, resulting in bad input?
2. The navmesh holes being worked out of the positions and indices ahead of calling generateSoloNavMesh is perhaps a problem? Though I really have not seen anywhere else how to define a "hole" in Recast.
3. My initial efforts to use generateSoloNavMesh failed on the entire map, so I tried filtering to just the first few triangles, and found success to only a given point (13 tris = success, 14 = failure), later realizing that the more I increased the cellSize, the more triangles could successfully complete generateSoloNavMesh, so now without truly understanding why, I "successfully" create the navmesh with navMeshGeneratorConfig: cs: 1.5.

I'm truly trying to read everything I can to understand how Recast works and why I'm having these troubles, but I just can't find anything truly explanatory for direct usage not involving Three.js or some other major engine.

I can maybe convert my map polygon to Three's ShapeGeometry if that will help with Recast compatibility, but I really have no clue what might be the problem.

[isaac-mason]

Hey @OdinvonDoom! Apologies for the late reply.

I should call out that while some have probably had success using recast for 2d games, it's not the most optimal tool for 2d use cases. The way recast constructs navigation meshes has unnecessary complexity and overhead for 2d inputs.

Perhaps a simpler library like nav2d could better serve your needs, see:

• https://github.com/frapa/nav2d
• Recommended way to implement "holes" in navmesh? frapa/nav2d#29

---

If you choose to proceed with using recast for your use case, I would suggest as a next step visualising the navigation mesh build process intermediates to see if any input / build process issues become more obvious with intermediates.

Some quick things you could try:

• try constructing a tiled navmesh instead of a solo nav mesh
• try increasing the max simplification error parameter
• try decreasing the max edge length parameter

The github issues and google discussions on the main recastnavigation repo are a good place to look for existing similar issues, you may find some more information there:

• https://github.com/recastnavigation/recastnavigation
• https://groups.google.com/g/recastnavigation (although unfortunately it's being spammed at the moment :( the old discussions are still a gold mine)

---

I can maybe convert my map polygon to Three's ShapeGeometry if that will help with Recast compatibility, but I really have no clue what might be the problem.

The core of recast-navigation-js is entirely agnostic to three.js. The only requirements for input are the below:

The input positions and indices should adhere to OpenGL conventions:

• Use the right-handed coordinate system
• Indices should be in counter-clockwise winding order
• The positions and indices arguments should be flat arrays of numbers

---

If you are able to post a minimal reproduction, myself or another library user may be able to take a look at your issue 🙂

[rob-myers]

I'm also using Recast-Detour to generate a 2D navigation mesh, although the environment is 3D.
I definitely want to use Recast-Detour because of the crowd navigation feature.
I've also encountered these damn Steiner points (see pic), although they don't always cause unnatural navigation.

Here's a couple of things I'm intending to try:

1. Scale up nav-mesh, use larger cs, then scale back down.

   Might be nonsense, but I'll try it anyways.

2. Do not create TiledMesh "all-at-once" i.e. create it section by section (my maps are made of many geomorphs).

   There should fewer constraints, potentially leading to a better navmesh.

[rob-myers]

So, "Steiner points" are additional points not present in the input polygon for a triangulation algorithm.
Usually they're intended to improve the quality of the triangulation.

But for navigation meshes and path-planning, such additional points can:
(a) change the "approximated" length of paths during A*,
(b) change the string-pulled path.

I've seen crowd agents in Recast-Detour where these "changes" produce bad nav paths,
e.g. two sides of two triangles (sharing a vertex), rather than a direct path.
This can happen at start/end or midway (a kind of wobble).

However, "bad nav paths" seem to correspond to "bad triangulations" e.g. long thin triangles and nodes with high degree.

For example a TileCacheGeneratorConfig with cs: 0.1 and unspecified tileSize yields the triangulation below. If you head for the bottom-right door the string-pull aligns with the long edge the agent is right next to, causing a (somewhat) unnatural turn at that node of high degree.

But this problem disappears when we add tileSize: 10 to TileCacheGeneratorConfig, despite the large number of Steiner points:

The above triangulation is more uniform. It seems to correspond to the underlying tiles of edge length 0.1 * 10. In closing, we probably shouldn't be trying to avoid Steiner points. If our particular choice of parameters yields a "bad triangulation" then we should probably use smaller smaller tileSize until it starts looking better.

I wish I could be more precise, but it's not really possible without a deeper knowledge of the code-base.

[rob-myers]

Finally, such Steiner points are also visible in the default example at:

https://navmesh.isaacmason.com/editor

when you choose poly mesh detail in the debug drawer options.