When using Temp Obstacles in the Demo I am able to generate a correct path when leveraging a path for individual agents (Test Navmesh).

Crowd Control seems to ignore Temp Obstacles as shown by the path generated below and walks right through it.
Or is there a setting I am misconfiguring for Crowd Control for it to ignore Temp Obstacles?.

Rider keeps telling me that Small Object Heap allocation is high for the DtCrowd.Update method.

This is my usage

Where the Update method is called every 0.3...

On the pictures above the compiler is complaining about 200mb-ish, but I've seen it complaining about almost 800mb. Do you have any idea of what could it be?

I was messing around with the library and wanted to test a larger scene for an RTS example using a default cude in Blender that I scaled to 500x1x500.

I definitely expected a regression in performance but are these allocations correct or is there a known issue with the navmesh generatioon?

I collected some stacktraces of the memory from DotMemory here:
Singles being allocated, mostly from DividePoly.

System.Single[]
  Objects : n/a
  Bytes   : 1603298776

>99.9%  DividePoly • 1.49 GB / 1.49 GB • DotRecast.Recast.RcRasterizations.DividePoly(Single[], Int32, Int32, Int32, Int32, Int32, Int32, Single, Int32)
  >99.9%  RasterizeTri • 1.49 GB / - • DotRecast.Recast.RcRasterizations.RasterizeTri(Single[], Int32, Int32, Int32, Int32, RcHeightfield, RcVec3f, RcVec3f, Single, Single, Single, Int32)
    >99.9%  RasterizeTriangles • 1.49 GB / - • DotRecast.Recast.RcRasterizations.RasterizeTriangles(RcContext, Single[], Int32[], Int32[], Int32, RcHeightfield, Int32)
      >99.9%  BuildSolidHeightfield • 1.49 GB / - • DotRecast.Recast.RcVoxelizations.BuildSolidHeightfield(RcContext, IInputGeomProvider, RcBuilderConfig)
        >99.9%  Build • 1.49 GB / - • DotRecast.Recast.RcBuilder.Build(IInputGeomProvider, RcBuilderConfig)
          >99.9%  BuildRecastResult • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.BuildRecastResult(DemoInputGeomProvider, RcConfig)
            >99.9%  Build • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcPartition, Single, Single, Single, Single, Single, Single, Int32, Int32, Single, Single, Int32, Single, Single, Boolean, Boolean, Boolean)
              >99.9%  Build • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcNavMeshBuildSettings)
                >99.9%  OnNavMeshBuildBegan • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnNavMeshBuildBegan(NavMeshBuildBeganEvent)
                  >99.9%  OnMessage • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnMessage(IRecastDemoMessage)
                    >99.9%  OnWindowUpdate • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnWindowUpdate(Double)
                      >99.9%  <Run>b__0 • 1.49 GB / - • Silk.NET.Windowing.WindowExtensions+<>c__DisplayClass2_0.<Run>b__0()
                        >99.9%  Run • 1.49 GB / - • Silk.NET.Windowing.Internals.ViewImplementationBase.Run(Action)
                          >99.9%  Run • 1.49 GB / - • Silk.NET.Windowing.WindowExtensions.Run(IView)
                            >99.9%  Run • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.Run()
                              >99.9%  StartDemo • 1.49 GB / - • DotRecast.Recast.Demo.Program.StartDemo()
                                >99.9%  Main • 1.49 GB / - • DotRecast.Recast.Demo.Program.Main(String[])
                                  ► >99.9%  [AllThreadsRoot] • 1.49 GB / - • [AllThreadsRoot]

#stacktrace

RcSpans being allocated by AddSpan

DotRecast.Recast.RcSpan
  Objects : n/a
  Bytes   : 890084272

 100%  AddSpan • 848.85 MB / 848.85 MB • DotRecast.Recast.RcRasterizations.AddSpan(RcHeightfield, Int32, Int32, Int32, Int32, Int32, Int32)
   100%  RasterizeTri • 848.85 MB / - • DotRecast.Recast.RcRasterizations.RasterizeTri(Single[], Int32, Int32, Int32, Int32, RcHeightfield, RcVec3f, RcVec3f, Single, Single, Single, Int32)
     100%  RasterizeTriangles • 848.85 MB / - • DotRecast.Recast.RcRasterizations.RasterizeTriangles(RcContext, Single[], Int32[], Int32[], Int32, RcHeightfield, Int32)
       100%  BuildSolidHeightfield • 848.85 MB / - • DotRecast.Recast.RcVoxelizations.BuildSolidHeightfield(RcContext, IInputGeomProvider, RcBuilderConfig)
         100%  Build • 848.85 MB / - • DotRecast.Recast.RcBuilder.Build(IInputGeomProvider, RcBuilderConfig)
           100%  BuildRecastResult • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.BuildRecastResult(DemoInputGeomProvider, RcConfig)
             100%  Build • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcPartition, Single, Single, Single, Single, Single, Single, Int32, Int32, Single, Single, Int32, Single, Single, Boolean, Boolean, Boolean)
               100%  Build • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcNavMeshBuildSettings)
                 100%  OnNavMeshBuildBegan • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnNavMeshBuildBegan(NavMeshBuildBeganEvent)
                   100%  OnMessage • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnMessage(IRecastDemoMessage)
                     100%  OnWindowUpdate • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnWindowUpdate(Double)
                       100%  <Run>b__0 • 848.85 MB / - • Silk.NET.Windowing.WindowExtensions+<>c__DisplayClass2_0.<Run>b__0()
                         100%  Run • 848.85 MB / - • Silk.NET.Windowing.Internals.ViewImplementationBase.Run(Action)
                           100%  Run • 848.85 MB / - • Silk.NET.Windowing.WindowExtensions.Run(IView)
                             100%  Run • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.Run()
                               100%  StartDemo • 848.85 MB / - • DotRecast.Recast.Demo.Program.StartDemo()
                                 100%  Main • 848.85 MB / - • DotRecast.Recast.Demo.Program.Main(String[])
                                  ►  100%  [AllThreadsRoot] • 848.85 MB / - • [AllThreadsRoot]

#stacktrace

There are a couple more that are also allocating a couple hundred MBs but these 2 are by far the most agressive it seems.

Good thing, I have been searching for the C # version online for a long time. Thank you, moderator

First of all thanks for the port.

I refactored to use Vector3 instead of RcVec3f and the performance I had was like 4x faster on DtCrowd.

Parallel also improved a lot.

Why is RcVec3f being used instead?

program = _gl.CreateProgram();
uint vert_shdr = _gl.CreateShader(GLEnum.VertexShader);
_gl.ShaderSource(vert_shdr, vertex_shader);
_gl.CompileShader(vert_shdr);
_gl.GetShader(vert_shdr, GLEnum.CompileStatus, out var status);
if (status != (int)GLEnum.True)
{
throw new InvalidOperationException();
}

Would it even be possible to update the demo to make it more of a tool, in the sense where we could click to select single polygons in our generated navmesh and delete them, and if even possible an option to add or paint in new polygons?

You can post your screenshots here!

I am finally working on integrating this into Stride3d and I am having trouble actually generating the mesh for debugging purposes.

As far as I can tell in your demos for Unity the methods used only require that the vertices are provided as far as I understand it. in the Unity example I see you are generating per poly but in my generated mesh some poly data has more than 3 points depending on the tile.

I didnt realize DrawAAConvexPolygon was for drawing an arrow not the poly mesh.

In the code above you can see one of the polys has 24 verts or 8 Vector3 points. am I just meant to try and make my own indices or is there a way to get that data from the navmesh?

I finally have a mostly working nav mesh result. The main issue seems to be that the navmesh is being generated on the ceiling of the object as seen in the image below.
Each cube in the image represents a point on the nav mesh.

Is there a setting I am missing to have it generate on the opposite Y axis?

So I've got this error: rcBuildContours: Bad outline for region 6, contour simplification is likely too aggressive.

This is how raw vs simplified looks:

So yeah, the simplified polygon is self-intersecting, which is a problem. Looking at the code, however, I see this bit (rcContours.SimplifyContour):

1. We start with raw vertices, iterate over all pairs and look for changes in either neighbour region id or area border flag, and add them as initial 'seed' vertices in simplified list - this is reasonable.
2. Then we iterate over pairs of simplified vertices, and for each pair see whether error (max distance between simplified edge and raw vertex) is bigger than threshold, if so split the simplified edge - this is reasonable.
3. However, this error check is only done for vertices that are either bordering wall or other area - this is not done for 'interior' vertices (bordering different region with same area). As a result, the error for them can be arbitrarily large, and it can create self intersections. This leads to a misleading error message (it blames aggressive simplification, while in reality all the checks using passed simplification parameters are skipped).

There should be an issue with vertex/tri count i was hardly been able to load the bridge and even the bridge have poor performance.

Windows 11, rtx2060 super.

In original recast nav demo, i can select "Temp obstacles" and create/save tile cache for future using. DotRecast, seems, has not that option in demo, but i see, that working with tile cache is present in the tests. Is DotRecast tile cache reader binary compatible with saved tile cache, generated by original recast? When i try to use reader, it crashes with exception "Could not allocate a tile".

I've been investigating problems with incorrect pathing, e.g.

After some digging, I've found that the root cause is the logic that removes vertices on tile borders while building polymeshes.

There is a parameter that controls the max edge length while tracing contours, it correctly creates 'small' areas:

When later poly mesh is built, it builds a triangulation for each contour. However, there is a piece of code (see RcMeshs.BuildPolyMesh) that marks vertices on the tile borders for removal:

                    if ((cont.verts[v + 3] & RC_BORDER_VERTEX) != 0)
                    {
                        // This vertex should be removed.
                        vflags[indices[j]] = 1;
                    }

As a result, recast creates a huge polygons on tile borders:

Presumably this is done for better tile stitching? However, it creates problems for pathfinding (since the pathfinding considers edge midpoints, it thinks that going 'around' this polygon is 'shorter' than crossing long edge midpoint).

Removing this vertex removal bit fixes the triangulation (and consequently pathfinding), and doesn't seem to break stitching in my limited testing so far:

However, I don't quite understand all implications. I suspect this part is directly ported from recast?

Hi!

I was just searching around to see if anyone had ported Recast/Detour to C# and came upon this project, which is looking great so far.

I just wanted to check if you're planning to publish it on NuGet for easier consumption?

Hi,

I'm playing around with OpenGL and trying to generate a navMesh with DotRecast. I'm a bit stuck because the detail mesh is always null after mesh generation.

I'm using a left hand coord system:

Im generating terrain mesh from a hightmap. The mesh is squared with a length of 800.0f (-400.0f to 400.0f) and a height between 0.0f and 40.0f. It has a grid of 256x256 cells divided into two triangular polygons each.

I'm converting my mesh to a right hand system before I pass it to the Geo provider:

public static class MeshConverter
{
    public static MeshData<VertexPositionNormalTexture, uint> ConvertMeshToRightHandSystem(this MeshData<VertexPositionNormalTexture, uint> meshData)
    {
        var convertedVertices = new VertexPositionNormalTexture[meshData.Vertices.Length];
        for (int i = 0; i < meshData.Vertices.Length; i++)
        {
            var vertex = meshData.Vertices[i];
            // Swap X and Z for position and normal to convert the mesh for Recast
            var newPosition = new Vector3D<float>(vertex.Position.Z, vertex.Position.Y, vertex.Position.X);
            var newNormal = new Vector3D<float>(vertex.Normal.Z, vertex.Normal.Y, vertex.Normal.X);
            convertedVertices[i] = new VertexPositionNormalTexture(newPosition, newNormal, vertex.TexCoords);
        }

        // The order of indices might need to be adjusted to correct the winding order.
        // Since we have swapped axes, the orientation of triangles could be affected.
        // For this specific case (just axis swap), it might not be necessary, but it should be tested.
        var convertedIndices = new uint[meshData.Indices.Length];
        for (int i = 0; i < meshData.Indices.Length; i += 3)
        {
            // Directly copy the indices as no direct impact on winding order is expected
            convertedIndices[i] = meshData.Indices[i];
            convertedIndices[i + 1] = meshData.Indices[i + 1];
            convertedIndices[i + 2] = meshData.Indices[i + 2];
        }

        return new MeshData<VertexPositionNormalTexture, uint>(convertedVertices, convertedIndices);
    }
}

And afterwards I try to generate the nav mesh:

        var meshInRightHandSystem = mesh.ConvertMeshToRightHandSystem();
        float[] vertexArray = meshInRightHandSystem.Vertices.SelectMany(v => new[] { v.Position.X, v.Position.Y, v.Position.Z }).ToArray();
        int[] indexArray = meshInRightHandSystem.Indices.Select(i => (int)i).ToArray();

       var geomProvider = new DemoInputGeomProvider(vertexArray, indexArray);
        
        var partitionType = RcPartition.WATERSHED;
        float tileSize = 800 / 256; // Die Größe eines Tiles, basierend auf der Größe deines Terrains und der Anzahl der Tiles
        float cellSize = tileSize / 2; // Wie detailliert jedes Voxel sein sollte, kleinere Werte führen zu detaillierteren NavMeshes
        float cellHeight = 0.2f; // Die Höhe jedes Voxels, kleinere Werte führen zu einem detaillierteren NavMesh
        float agentHeight = 2.0f; // Die Höhe des Agenten, der das NavMesh nutzen wird
        float agentRadius = 0.6f; // Der Radius des Agenten, der das NavMesh nutzen wird
        float agentMaxClimb = 0.9f; // Die maximale Steigung, die der Agent überwinden kann
        float agentMaxSlope = 45.0f; // Der maximale Neigungswinkel, den der Agent noch begehen kann
        int regionMinSize = 8; // Die minimale Größe einer Region, die noch als begehbar betrachtet wird (in Voxeln)
        int regionMergeSize = 20; // Die minimale Größe von Regionen, die zusammengeführt werden sollen (in Voxeln)
        float edgeMaxLen = 12.0f; // Die maximale Länge der Kanten des NavMeshes (längere Kanten werden aufgeteilt)
        float edgeMaxError = 1.3f; // Der maximale Fehler von Kantenverläufen im NavMesh
        int vertsPerPoly = 6; // Die maximale Anzahl von Vertices pro Polygon
        float detailSampleDist = 6.0f; // Der Abstand für die Detail-Mesh-Sampling, größer als 0 aktiviert das Detail-Mesh
        float detailSampleMaxError = 1.0f; // Der maximale Sampling-Fehler für das Detail-Mesh
        
        RcConfig recastConfig = new RcConfig(
            true,
            (int)tileSize,
            (int)tileSize,
            borderSize: 0,
            partitionType,
            cellSize,
            cellHeight,
            agentMaxSlope,
            agentHeight,
            agentRadius,
            agentMaxClimb,
            regionMinSize,
            regionMergeSize,
            edgeMaxLen,
            edgeMaxError,
            vertsPerPoly,
            detailSampleDist,
            detailSampleMaxError,
            true,
            true,
            true,
            SampleAreaModifications.SAMPLE_AREAMOD_GROUND,
            true);
        var recastBuilderConfig = new RcBuilderConfig(recastConfig, geomProvider.GetMeshBoundsMin(), geomProvider.GetMeshBoundsMax());

        RcBuilder rcBuilder = new RcBuilder();
        RcBuilderResult rcResult = rcBuilder.Build(geomProvider, recastBuilderConfig);
        RcPolyMesh polyMesh = rcResult.GetMesh();
        for (int i = 0; i < polyMesh.npolys; ++i)
        {
            polyMesh.flags[i] = 1;
        }

        RcPolyMeshDetail polyMeshDetail = rcResult.GetMeshDetail();

The poly mesh detail is always null. What I am doing wrong?

Hey, first I want to thank you for the great job you are doing, you even converted the demo tool!

I would like to know if you have any parameters related to performance with the original or did you not perform any yet?

There is a another project too, for performance reasons the guy decided to keep pointers (unsafe) and others things, but it's no longer an active project.

https://github.com/ryancheung/RecastSharp/tree/main

Cheers!

I'm in the memory profiler today checking in on my program and was surprised by the number of objects that DotRecast is creating and keeping live for what might be considered a relatively small scene -

Here you'll notice we have 500k live instances of RcSpan -

Is there any change we can make to DotRecast or our usage to reduce the object count footprint here? Maybe a different internal representation or perhaps a posteri pruning? Or perhaps there's a reference from the mesh construction process I can let go of? I currently keep a reference to RcBuilderResult so I can draw the above debug lines. Should I not hold on to that? If so, would there be a better way to draw debug info for the nav mesh than using RcBuilderResult? If not, can I prune RcBuilderResult somehow?

Since we're dealing with realtime games, we'd like to keep the GC sweep phase as cheap as possible.

Lastly, here's the related issue I filed locally -

bryanedds/Nu#774

Thank you for your greatly helpful project - it has already saved us tremendous amounts of time and effort!

Hi, I want to use DotRecast in a test project I am building, but purely on my (dotnet, C#) server. I am using Unity as my GameEngine and now I was wondering if there is an example project to export the data from Unity and import it into DotRecast.

What I have:

• I can export the vertices and indices from my Unity NavMesh (serialize to JSON)
• I can import that data on the server (deserialize the JSON)

What I need help with:

• How do I initialize DotRecast with this data so that I can: Sample Height and get a path?

This causes the entire list to be copied over. It's pretty slow, if we going to do this every game cycle.

if (s.Count == TIMING_SAMPLES)
{
    s.RemoveAt(0);
}

This is Linq call and will cause memory allocation. Would be nice to avoid that, especially in a code that supposed to measure performance.

_executionTimings[name] = (long)s.Average();

I would replace List with some sort of cyclic buffer to avoid removing elements and replace Linq query with foreach cycle or even SIMD.

So when creating a convex volume, it will crash the program if you accidentally only give 3 points for the volume, is this intended behavior, and if so could if instead just catch the exception instead of crash the program? P.S. I made a new issue for this so it can be closed when acted on, separate from our ongoing discussion

my code like this:
var indexs = new List<int>(){ 7, 0, 1, 2, 3, 4, 6, 7, 1, 2, 4, 5, 5, 6, 1, 1, 2, 5}; var verts = new List<float>(){17307.352, -13128.241, 4000, 17307.352, 5071.7583, 4000, -8892.649, 5071.7583, 4000, -8892.649, -8428.24, 4000, -4592.6494, -8428.24, 4000, -4592.6494, -928.24164, 4000, 8307.351, -928.24164, 4000, 8307.351, -13128.241, 4000, 17307.352, -13128.241, 4000 }; SimpleInputGeomProvider geomProvider = new(verts, indexs); RcVec3f bmin = geomProvider.GetMeshBoundsMin(); RcVec3f bmax = geomProvider.GetMeshBoundsMax(); RcContext m_ctx = new(); RcConfig cfg = new( RcPartition.WATERSHED, m_cellSize, m_cellHeight, m_agentMaxSlope, m_agentHeight, m_agentRadius, m_agentMaxClimb, m_regionMinSize, m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError, m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError, true, true, true, new RcAreaModification(0x2, 0x07), true); RcBuilderConfig bcfg = new(cfg, bmin, bmax); RcBuilder rcBuilder = new(); RcBuilderResult rcResult = rcBuilder.Build(geomProvider, bcfg);
it throws System.ArgumentException:“'0' cannot be greater than -1.”
I don't know how it caused it？

on a 4k screen its really hard to read as the ui doesnt scale, can you please make it scale or the very least put in a 4k ui option

Hey!

I've been using this mainly with Unity and it seems the X axis is inverted in comparison to Unity's coordinates. I have to do something like this every time I sent the position to my clients:

public static SVector3 toSVector3(this RcVec3f v, RcVec3f mapSize) => new() { X = mapSize.X - v.X, Y = v.Y, Z = v.Z };

Is there any way you can think of to invert this so we can avoid these conversions?

Hey,

Are there any examples for Unity 3D? What projects are really needed for Unity? And to generate navmesh use unity itself to generate?

Cheers!