Crashes killing Unity When using Navmesh Cuts with Recast

General Recast graph
#1

Crashes killing Unity (happens to both Editor and compiled version)
When using many Navmesh Cuts (about 200)
on a Recast Graph

StackOverflowException: The requested operation caused a stack overflow.
at Pathfinding.Poly2Tri.FixedArray3`1[T].IndexOf (T value) [0x00007] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DelaunayTriangle.IndexOf (Pathfinding.Poly2Tri.TriangulationPoint p) [0x00000] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DelaunayTriangle.PointCWFrom (Pathfinding.Poly2Tri.TriangulationPoint point) [0x00000] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DelaunayTriangle.OppositePoint (Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) [0x00000] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DTSweep.FlipScanEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle flipTriangle, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) [0x0000a] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) [0x00115] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DTSweep.FlipScanEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle flipTriangle, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) [0x00066] in <07aca9e84ffe412bbfb50d0962eb64f2>:0
at Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) [0x00115] in <07aca9e84ffe412bbfb50d0962eb64f2>:0

at Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force) [0x000f3] in <64e167c5a01a4cfb962c6b689ad034e2>:0
at AstarPath.PerformBlockingActions (System.Boolean force) [0x0002b] in <64e167c5a01a4cfb962c6b689ad034e2>:0
at AstarPath.FlushWorkItems () [0x00014] in <64e167c5a01a4cfb962c6b689ad034e2>:0
at AstarPath+d__141.MoveNext () [0x002ec] in <64e167c5a01a4cfb962c6b689ad034e2>:0
at AstarPath.Scan (Pathfinding.NavGraph[] graphsToScan) [0x00030] in <64e167c5a01a4cfb962c6b689ad034e2>:0

Crash in Build - Poly2Tri
Stack overflow with FlipScanEdgeEvent
Stack overflow with FlipScanEdgeEvent
Crash in Build - Poly2Tri
#2

Looks like this is an edge case.

My specific scenario is that I’m using a maze generator to create walls. Each Wall prefab has a box shape NavMeshCut on it.
The wall prefabs are all 6 X 6 in size (X , Z) sizes as height is irrelevant.
In any wall segment the wall prefabs will be placed right next to each other. Which means that the navmesh cut polygons of two adjacent cuts will have overlapping vertices.

To get around this issue all I did was to inflate the navmesh cut on each prefab by 0.1f
Now the crash does not happen at all.

So in summary if two NavMesh cuts have overlapping vertices. And there are many navmesh cuts with this scenario we end up with the stack overflow crash in Pathfinding.Poly2Tri

If we ensure that no two NavMesh cuts have overlapping vertices then the crash never happens.

#3

Note: I am training ML Agents which means millions upon millions of iterations using multiple concurrent sessions.

So with the overlapping NavMesh Cuts. Running 8 instances in parallel at Timescale of 25X
I get one crash every minute or so.

With zero overlapping NavMesh Cuts. Running 8 instances in parallel at Timescale of 25X
After 1 hour I have zero crashes.

#4

Hi

Ah, yeah, that is sadly a known bug in the Poly2Tri library that I’m using. I’ve been trying to mitigate it several times and even tried writing my own triangulation library, but I’ve only had partial success so far.
I’d recommend inflating the prefabs like you mention. That will give you the most robust solution.
Sorry about the trouble this has caused you.

#5

All Good Aron

Maybe just add it to the docs as a known issue. The workaround is pretty straight forward.

Cheers
Tikiri
1 Like