Stack overflow with FlipScanEdgeEvent

General
#1

Using astarpathfindingproject_master_pro_dev_4_3_34_f1547300

Happened on a certain complex level with lots of Pathfinding.NavmeshCut

Unloading 0 unused Assets to reduce memory usage. Loaded Objects now: 979814.
Total: 727.164100 ms (FindLiveObjects: 61.925000 ms CreateObjectMapping: 70.235500 ms MarkObjects: 593.740200 ms  DeleteObjects: 1.262500 ms)

Unloading 4 Unused Serialized files (Serialized files now loaded: 12)
Meshes on fortpole_b (2) fortpole_b (2) not readable so cannot be destroyed at runtime. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Mesh is not readable: fortpole_b (2) 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)


Unloading 2 unused Assets to reduce memory usage. Loaded Objects now: 980293.
Total: 734.373000 ms (FindLiveObjects: 54.228200 ms CreateObjectMapping: 90.583600 ms MarkObjects: 588.292600 ms  DeleteObjects: 1.267900 ms)

Unloading 0 Unused Serialized files (Serialized files now loaded: 12)
Meshes on wagons_logs_pine_trunkup07 (10) wagons_logs_pine_trunkup07 (10) not readable so cannot be destroyed at runtime. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Mesh is not readable: wagons_logs_pine_trunkup07 (10) 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)


Unloading 0 unused Assets to reduce memory usage. Loaded Objects now: 980325.
Total: 744.331200 ms (FindLiveObjects: 55.813300 ms CreateObjectMapping: 96.251200 ms MarkObjects: 591.046600 ms  DeleteObjects: 1.219300 ms)

Meshes on PM_Cage_2_2_Base_MA_BS PM_Cage_2_2_Base_MA_BS not readable so cannot be destroyed at runtime. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Mesh is not readable: PM_Cage_2_2_Base_MA_BS 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Meshes on _armamentexportv1_weapon_brutal_iron_waraxe _armamentexportv1_weapon_brutal_iron_waraxe not readable so cannot be destroyed at runtime. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Mesh is not readable: _armamentexportv1_weapon_brutal_iron_waraxe 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

KeyNotFoundException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

PointOnEdgeException, perturbating vertices slightly.
This is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times. 
(Filename: C:\buildslave\unity\build\Runtime/Export/Debug/Debug.bindings.h Line: 35)

Uploading Crash Report
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.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.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.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.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.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.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.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.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.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.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

This continues on in the log for another 1000 lines

#2

This error seems to have started after a change I made 13 days ago. Previously I had useRotationAndScale off. I have always used NavmeshCut.MeshType.Rectangle.

void UpdateNavmeshCut(NavmeshCutAndCollider navmeshCutAndCollider)
    {
        Bounds colliderBounds = Utility_Common.GetColliderBounds(navmeshCutAndCollider.collider);
        Vector3 localSpaceCenter = Utility_Common.GetColliderCenter(navmeshCutAndCollider.collider);
        if (localSpaceCenter == Vector3.zero)
            localSpaceCenter = navmeshCutAndCollider.collider.transform.InverseTransformPoint(colliderBounds.center);

        navmeshCutAndCollider.navmeshCut.rectangleSize = new Vector2(colliderBounds.size.x, colliderBounds.size.z);
        navmeshCutAndCollider.navmeshCut.height = colliderBounds.size.y + .1f;
        navmeshCutAndCollider.navmeshCut.center = localSpaceCenter;
        // 10/3/2020: Without useRotationAndScale everything is axis aligned, ruining pathfinding in LinearMission1
        navmeshCutAndCollider.navmeshCut.useRotationAndScale = true;

        float characterRadius = .6f;
        // https://forum.arongranberg.com/t/navmeshcut-does-not-account-for-character-radius/9451
        if (AstarPath.active != null)
        {
            AstarPath astarPath = AstarPath.active;

            for (int graphIndex = 0; graphIndex < astarPath.graphs.Length; graphIndex++)
            {
                Pathfinding.RecastGraph recastGraph = astarPath.graphs[graphIndex] as Pathfinding.RecastGraph;
                if (recastGraph != null)
                {
                    characterRadius = recastGraph.characterRadius;
                    break;
                }
            }
        }

        if (characterRadius > PathReachableCache.pathReachableGameplayTarget * .9f)
            characterRadius = PathReachableCache.pathReachableGameplayTarget * .9f;

        // 10/3/2020: Reduced from characterRadius * 2.0f to characterRadius as visually I can see this makes the cuts unnecessarily large
        navmeshCutAndCollider.navmeshCut.rectangleSize.x += characterRadius;
        navmeshCutAndCollider.navmeshCut.rectangleSize.y += characterRadius;
    }
Can't type in values to Grid graph
#3

I tried reducing in TileHandler.cs if (perturbate > 10) but it continued to crash 2/3 attempts in a randomly generated dungeon. Most likely whatever caused the crash just didn’t come up in the random number generator that 1 time.

I then changed navmeshCut.useRotationAndScale = false; and no other code. After that, it did not crash after 4 attempts. In addition, “KeyNotFoundException, perturbating vertices slightly” was no longer in the log through any of the 4 attempts.

I hope this is fixed. I can change to LayeredGridGraph for all but my large exterior terrain scenes but I’d prefer not to.

#4

Bleh, that library really causes problems. I can’t fix this properly because it’s deep down in a 3rd party library. But I think this is caused by navmesh cuts that are perfectly adjacent (i.e. their edges and/or corners coincide). One simple solution for that is to increase the size of all navmesh cuts by a small amount so that the edges no longer coincide.

#5

This isn’t a solution. I am generating my cuts at runtime and you can see from my pasted code I am already increasing the size of all cuts by the character radius, so basically I’m already doing what you said to do and then some.

It seems to me that the issue is caused by perturbate. I think there’s a math problem, or otherwise problem introduced by perturbate. As I said it doesn’t happen unless use useRotationAndScale .

#6

I think we may be experiencing the same crash (posted about it a few days after this thread originally, hadn’t seen this one Crash in Build - Poly2Tri - General / Recast graph - Support Forum (arongranberg.com) )

For us, it also seems to happen when multiple nav mesh cuts get enabled but it doesn’t occur consistently. However, the crashes are occuring often enough to be a concern… we can’t have our games crashing (and getting angry users) because of a faulty plugin, I hope you’ll investigate further @aron_granberg !

#7

The issue is very replicatable with or without Rich AI.

Turning off navmesh updates with:
AstarPath.active.navmeshUpdates.updateInterval = -1f;

I’ve posted the details of what I encountered here:

#8

Disabling navmesh updates hides the issue which confirms its in the navmesh update system.

AstarPath.active.navmeshUpdates.updateInterval = -1f;
and the issue is hidden. Of course the navmesh cuts do nothing
However if I call AstarPath.active.navmeshUpdates.ForceUpdate(); at any point after this even once. Then the game will eventually crash.
I am not using RichAI or AIPath. I’m only using Seeker.StartPath
In order to get a path

Also the shape of the navmesh cuts makes no difference. I am using box shaped cuts anyway.

#9

I posted more details in Crashes killing Unity When using Navmesh Cuts with Recast

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.