NullReferenceException in Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent

dnlbschff · March 26, 2021, 12:39pm

Hi,
I just noticed that a couple of exceptions are coming in through the cloud analytics dashboard for our game. Both of them are “NullReferenceException: Object reference not set to an instance of an object”.
I’ll attach the two call stacks at the bottom.

We are using a couple of NavMeshCut components, one of them attached to the player so that AI won’t try to walk through them, if they block a narrow pathway. So this NavMeshCut moves around a lot and I suspect in some cases, this causes Poly2Tri to fail. However, I’m not sure about this. Is there anything I can try to reduce the chance of this going wrong? Unfortunately, it is not an easy thing to reproduce since we only very rarely get the error in the editor during development (1 or 2 occasions so far in total).

Could I solve the agents’s pathfinding around the player some other way without using NavMeshCut?
Any help would be much appreciated
Thanks!

I’m on unity 2020.2.0f1 and the package version is 4.2.15.

Here’s call stack #1:

Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.EdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle triangle, Pathfinding.Poly2Tri.TriangulationPoint point) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.EdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.DTSweepConstraint edge, Pathfinding.Poly2Tri.AdvancingFrontNode node) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.Sweep (Pathfinding.Poly2Tri.DTSweepContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.Triangulate (Pathfinding.Poly2Tri.DTSweepContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.TriangulationContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.TriangulationAlgorithm algorithm, Pathfinding.Poly2Tri.Triangulatable t) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.Polygon p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Util.TileHandler.CutPoly (Pathfinding.Int3[] verts, System.Int32[] tris, Pathfinding.Int3[] extraShape, Pathfinding.Util.GraphTransform graphTransform, Pathfinding.IntRect tiles, Pathfinding.Util.TileHandler+CutMode mode, System.Int32 perturbate) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
Pathfinding.Util.TileHandler+<>c__DisplayClass41_0.<LoadTile>b__0 (Pathfinding.IWorkItemContext context, System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
AstarPath.PerformBlockingActions (System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
AstarPath.Update () (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)

And here’s the slightly different call stack #2:

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) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.FlipEdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle t, Pathfinding.Poly2Tri.TriangulationPoint p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.EdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.TriangulationPoint ep, Pathfinding.Poly2Tri.TriangulationPoint eq, Pathfinding.Poly2Tri.DelaunayTriangle triangle, Pathfinding.Poly2Tri.TriangulationPoint point) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.EdgeEvent (Pathfinding.Poly2Tri.DTSweepContext tcx, Pathfinding.Poly2Tri.DTSweepConstraint edge, Pathfinding.Poly2Tri.AdvancingFrontNode node) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.Sweep (Pathfinding.Poly2Tri.DTSweepContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.DTSweep.Triangulate (Pathfinding.Poly2Tri.DTSweepContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.TriangulationContext tcx) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.TriangulationAlgorithm algorithm, Pathfinding.Poly2Tri.Triangulatable t) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Poly2Tri.P2T.Triangulate (Pathfinding.Poly2Tri.Polygon p) (at <07aca9e84ffe412bbfb50d0962eb64f2>:0)
Pathfinding.Util.TileHandler.CutPoly (Pathfinding.Int3[] verts, System.Int32[] tris, Pathfinding.Int3[] extraShape, Pathfinding.Util.GraphTransform graphTransform, Pathfinding.IntRect tiles, Pathfinding.Util.TileHandler+CutMode mode, System.Int32 perturbate) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
Pathfinding.Util.TileHandler+<>c__DisplayClass41_0.<LoadTile>b__0 (Pathfinding.IWorkItemContext context, System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
AstarPath.PerformBlockingActions (System.Boolean force) (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)
AstarPath.Update () (at <a06ec6d629b7444ebaeffc0f8bc4c221>:0)

SkirmishModeGames · March 28, 2021, 8:03am

Hey there, I am also getting this error. Mostly get it in a build, but almost never in editor. My team is trying to launch our game in about a month. Our QA lead is reporting this as the highest priority bug with a crash to desktop every time so it would be great to get a fix for this asap. Here’s my almost identical call stack:

Uploading Crash Report
StackOverflowException: The requested operation caused a stack overflow.
  at Pathfinding.Poly2Tri.FixedArray3`1[T].get_Item (System.Int32 index) <0x1f2ca831880 + 0x00008> in <07aca9e84ffe412bbfb50d0962eb64f2>:0 
  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

aron_granberg · March 31, 2021, 9:16am

Hi

Yes this is an annoying bug in a third party library that I haven’t managed to fix

I haven’t seen these exact variants though. At least for @dnlbschff what you could try is to change the try-catch code in the TileHandler.cs script which looks like

try {
	P2T.Triangulate(polygonToTriangulate);
} catch (Poly2Tri.PointOnEdgeException) {
	Debug.LogWarning("PointOnEdgeException, perturbating vertices slightly.\nThis is usually fine. It happens sometimes because of rounding errors. Cutting will be retried a few more times.");
	return CutPoly(verts, tris, extraShape, graphTransform, tiles, mode, perturbate + 1);
}

(which I have to work around another bug in that library)
to also catch NullReferenceExceptions. While not a perfect fix, it might help significantly.

dnlbschff · March 31, 2021, 12:07pm

Hi @aron_granberg,
thanks for the quick reply. Trying that seems like a good idea. I’ll also add cloud diagnostics logging to the error message you log when the recursion level / perturbation count gets too high to see if that’s something that happens a lot in the wild. I won’t have data to compare it with but I’ll have a percentage of users who might have a broken navmesh tile.

I’ll report back once adoption for the new version gets big enough.

SkirmishModeGames · April 1, 2021, 12:55am

Hey @aron_granberg yeah thanks for looking at this. What can I do to fix this? I cannot ship with this bug and my deadline is approaching very quickly. I am using your beta package so I’m not sure how to edit your code while it’s in a package. Is there anything that can be done here to mitigate this issue?

aron_granberg · April 6, 2021, 12:39pm

Hi

Sorry for the late answer.
As a first approach I would copy the package into your project so that you can edit it (there’s https://docs.unity3d.com/Manual/upm-embed.html, Unity sadly does not expose this method via a nice UI, but it should be simple enough to call that method from an editor script).