Hitting the maximum allowed hierarchical node count

Feature Requests
1
  • A* version: 5.3.8
  • Unity version: 6000.0.41f1

First of all, thank you for this package. It has saved us a significant amount of time by allowing us to overcome the limitations of Unity’s built-in pathfinding system without needing to reimplement everything from scratch. We truly appreciate it.

We’re using a Recast graph and streaming tiles with ‘ReplaceTiles’ to support our large open-world scene (4x4 km). Recently, however, we’ve started encountering some exceptions in the editor from A*, such as the two shown below:

AssertionException: Assertion failure. Values are equal.
Expected: -2 != -2
UnityEngine.Assertions.Assert.Fail (System.String message, System.String userMessage) (at <2431722e3e3e41d78b6718bb39ab9111>:0)
UnityEngine.Assertions.Assert.AreNotEqual[T] (T expected, T actual, System.String message, System.Collections.Generic.IEqualityComparer`1[T] comparer) (at <2431722e3e3e41d78b6718bb39ab9111>:0)
UnityEngine.Assertions.Assert.AreNotEqual[T] (T expected, T actual, System.String message) (at <2431722e3e3e41d78b6718bb39ab9111>:0)
UnityEngine.Assertions.Assert.AreNotEqual (System.Int32 expected, System.Int32 actual) (at <2431722e3e3e41d78b6718bb39ab9111>:0)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.FindHierarchicalNodeChildren (Pathfinding.HierarchicalGraph hGraph, System.Int32 hierarchicalNode, Pathfinding.GraphNode startNode) (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:425)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.Execute () (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:510)
Unity.Jobs.IJobExtensions+JobStruct`1[T].Execute (T& data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, Unity.Jobs.LowLevel.Unsafe.JobRanges& ranges, System.Int32 jobIndex) (at <2431722e3e3e41d78b6718bb39ab9111>:0)

IndexOutOfRangeException: Invalid allocation -2
Pathfinding.Collections.SlabAllocator`1[T].GetSpan (System.Int32 allocatedIndex) (at ./Packages/com.arongranberg.astar/Core/Collections/SlabAllocator.cs:112)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.RemoveHierarchicalNode (Pathfinding.HierarchicalGraph hGraph, System.Int32 hierarchicalNode, System.Boolean removeAdjacentSmallNodes) (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:276)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.Execute () (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:480)
Unity.Jobs.IJobExtensions+JobStruct`1[T].Execute (T& data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, Unity.Jobs.LowLevel.Unsafe.JobRanges& ranges, System.Int32 jobIndex) (at <2431722e3e3e41d78b6718bb39ab9111>:0)

In builds, the issue also leads to crashes, which can vary in nature.

After some investigation, I discovered that our scene had become quite fragmented, with many disjointed areas. As a result, we exceeded the limit of hierarchical nodes, which is capped at 131,072 (17 bits). It took me a while to track this down. It would be very helpful for others if A* could notify users when this limit is exceeded and optionally provide a way to increase the maximum node count.

Thanks in advance!

2

I’ll go ahead and tag @aron_granberg on this suggestion- thanks for posting this :slight_smile:

3

Thanks!

I’ll add a nicer error message for this.

I’ll not add a method to increase the max count, though, since if you are reaching that ceiling, then you really should be working on reducing that fragmentation instead. It’s a ridiculous number of hierarchical nodes.

4

Fair enough. I’m currently working on minimizing the number of navmesh islets on my end, not just to stay within the limit, but also to improve performance, as the high number of nodes is slowing down graph updates (HierarchicalGraph.FloodFill time scales linearly with the number of nodes).

Thanks a lot!