A node in a RecastGraph contained a connection to a destroyed TriangleMeshNode

  • A* version: 5.4.6
  • Unity version: 6000.3.15f1

Hi, we’re currently having an issue where, on extremely rare occasions, we get an error that results in a hard crash. We’ve only seen it in builds (Has occurred twice that I know of) and I have not found any to find any way replicating the error.

First we get:

[Exception] System.InvalidOperationException: A node in a RecastGraph contained a connection to a destroyed TriangleMeshNode.
  at Pathfinding.HierarchicalGraph+JobRecalculateComponents+<>c.<FindHierarchicalNodeChildren>b__13_0 (Pathfinding.GraphNode neighbour, Pathfinding.HierarchicalGraph+JobRecalculateComponents+Context& context) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:410
  at UnityEngine.InputSystem.Utilities.NamedValue.set_value (UnityEngine.InputSystem.Utilities.PrimitiveValue value) [0x00000] in ./Library/PackageCache/com.unity.inputsystem@21a28c3a6c83/InputSystem/Utilities/NamedValue.cs:22
  at Pathfinding.HierarchicalGraph+JobRecalculateComponents.FindHierarchicalNodeChildren (Pathfinding.HierarchicalGraph hGraph, System.Int32 hierarchicalNode, Pathfinding.GraphNode startNode) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:427
  at Pathfinding.HierarchicalGraph+JobRecalculateComponents.Execute () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:524
  at Pathfinding.HierarchicalGraph.RecalculateIfNecessary () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:554
  at Pathfinding.WorkItemProcessor.EnsureValidFloodFill () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:315
  at Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force, System.Boolean sendEvents) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:411
  at AstarPath.PerformBlockingActions (System.Boolean force) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:932
  at AstarPath.Update () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:910
  at UnityEngine.Logger.LogException (System.Exception exception, UnityEngine.Object context)
  at UnityEngine.Debug.CallOverridenDebugHandler (System.Exception exception, UnityEngine.Object obj)
  at Pathfinding.HierarchicalGraph.RecalculateIfNecessary () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:554
  at Pathfinding.WorkItemProcessor.EnsureValidFloodFill () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:315
  at Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force, System.Boolean sendEvents) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:411
  at AstarPath.PerformBlockingActions (System.Boolean force) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:932
  at AstarPath.Update () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:910

Which is then followed by

[Exception] System.IndexOutOfRangeException: Index was outside the bounds of the array.
  at Pathfinding.HierarchicalGraph+JobRecalculateComponents.RemoveHierarchicalNode (Pathfinding.HierarchicalGraph hGraph, System.Int32 hierarchicalNode, System.Boolean removeAdjacentSmallNodes) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:322
  at Pathfinding.HierarchicalGraph+JobRecalculateComponents.Execute () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:492
  at Pathfinding.HierarchicalGraph.RecalculateIfNecessary () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:554
  at Pathfinding.WorkItemProcessor.EnsureValidFloodFill () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:315
  at Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force, System.Boolean sendEvents) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:411
  at AstarPath.PerformBlockingActions (System.Boolean force) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:932
  at AstarPath.Update () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:910
  at UnityEngine.Logger.LogException (System.Exception exception, UnityEngine.Object context)
  at UnityEngine.Debug.CallOverridenDebugHandler (System.Exception exception, UnityEngine.Object obj)
  at Pathfinding.HierarchicalGraph.RecalculateIfNecessary () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Pathfinding/HierarchicalGraph.cs:554
  at Pathfinding.WorkItemProcessor.EnsureValidFloodFill () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:315
  at Pathfinding.WorkItemProcessor.ProcessWorkItems (System.Boolean force, System.Boolean sendEvents) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/Misc/WorkItemProcessor.cs:411
  at AstarPath.PerformBlockingActions (System.Boolean force) [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:932
  at AstarPath.Update () [0x00000] in ./Library/PackageCache/com.arongranberg.astar@85d89969624b/Core/AstarPath.cs:910

I’ve looked through our code and can’t see anything obvious that would lead to a destroyed TriangleMeshNode, we don’t create or destroy any connections manually, but we do recalculate the graph occasionally using AStarPath.UpdateGraphs. We also have a large number of NavCuts in our scene, though we use our own NavCut scripts that overrides RequiresUpdate for performance reasons.

Any thoughts or help on this would be appreciated. I’ve seen similar errors in other posts, but can’t find any confirmed cause for this issue.

Do you think this is likely where it’s coming from? Are you able to run a version of your game where it’s just…running indefinitely in a scenario where it will crash from updating its graphs? (Does it require player input? And if so, can you rig it to automatically simulate that?)

Then if you can get it to crash you can try running it indefinitely a few times to crash, and a few times to without updating your graphs. Would help a lot on this side of the river. Let me know if that’s doable :victory_hand:

In the game, the player can build and destroy structures, which means we have to update the A* navmesh at runtime. We think the issue is happening somewhere during these graph updates, although we haven’t been able to reliably reproduce it by repeating the same actions. We may be able to write something to automate this to test, though it will likely be a few weeks before I can dig into that.

For now, we’re using a sanitiser script which seems to prevent the error spam and crash after the initial TriangleMeshNode error. It essentially just cleans up any destroyed nodes and makes any connections that had them as dirty.

I see. I think the best action for now is to keep an eye on if that sanitizer script is helping- especially if it’s able to log anything it finds that may be of help. Whatever you find from that/an automated test if you find the space to do that would be great as well! I’ll keep my ears open for it :+1:

Hi, we finally got some time to do some testing and I think we’ve got a lead on what causes this. The issue seemingly comes from one-way links being created and I believe this could to be caused by ‘AStarMath.SqrDistanceSegmentSegment’ returning 2 different values depending on the order that the segments are passed.

A step-by-step of what I believe it happening:

1. Node A’s tile (X) is rebuilt. TryConnect(X, Y) calls ConnectTiles(X, Y), this order gives the correct value in SqrDistanceSegmentSegment. Links are added between Node A and Node B
2. Node B’s tile (Y) is rebuilt. Node B’s triangle hasn’t changed, so PrepareNodeRecycling reuses B and strips B’s links to other tiles (NavmeshBase.cs:1008-1020). The B→A connection is gone, but nothing touches Node A, so the A→B connection stays stays.
3. The batch-end reconnect runs. This time TryConnect(Y, X) calls ConnectTiles(Y, X), which puts B’s edge first, in this order SqrDistanceSegmentSegment gives the wrong value. This value is larger than maxTileConnectionEdgeDistance*maxTileConnectionEdgeDistance, neither link is added, so B→A isn’t restored either.

At the end, A→B is left over from step 1 and B→A was removed in step 2 and never added back, leaving us with a 1 way connection.

Here is a test script I’ve created the show this issue in SqrDistanceSegmentSegment

using Pathfinding;
using UnityEditor;
using UnityEngine;

public static class SqrDistanceSegmentSegmentRepro
{
	[MenuItem("Tools/A* Repro/SqrDistanceSegmentSegment order")]
	public static void Run()
	{
		// Graph-space Int3 values taken from a real failing tile border
		Vector3 a1 = new Vector3(244.800f, 52.570f, 178.950f);
		Vector3 a2 = new Vector3(244.800f, 52.543f, 178.399f);
		Vector3 b1 = new Vector3(244.800f, 52.541f, 178.399f);
		Vector3 b2 = new Vector3(244.800f, 52.559f, 178.800f);

		float ab = VectorMath.SqrDistanceSegmentSegment(a1, a2, b1, b2);
		float ba = VectorMath.SqrDistanceSegmentSegment(b1, b2, a1, a2);

		Debug.Log($"(A, B) = {ab:R}\n(B, A) = {ba:R}");
	}
}

When this tool is run, the output is:

‘(A, B) = 0.304337442
(B, A) = 3.987576E-06’

The difference in these values appears to come from this section of ‘SqrDistanceSegmentSegment’

// finally do the division to get sc and tc
sc = (Math.Abs(sN) < 0.00001f ? 0.0 : sN / sD);
tc = (Math.Abs(tN) < 0.00001f ? 0.0 : tN / tD);

If I replace the absolute threshold with a guard on the divisor like:

sc = sD > 0.0 ? sN / sD : 0.0;
tc = tD > 0.0 ? tN / tD : 0.0;

the output becomes:

(A, B) = 3.98757447E-06
(B, A) = 3.987576E-06

As a temporary work around we have a Sanitizer that catches when one-way connections are created and remove them, which seems to stop the error from appearing.

Let me know what you think and if this sounds like a likely cause for this issue.

Cheers.

1 Like

Amazing find, thanks for sending it our way! I’ll tag Aron on this to take a look at.

1 Like