NavMeshCut Compare Function

General Navmesh graph
1
  • A* version: 5.2.5
  • Unity version: 2022.3.54f1

BUG:
InvalidOperationException: System.InvalidOperationException: Comparison function is incorrect. Compare(a, b) when a and b are different values should not return the same value as Compare(b, a).
This Exception was thrown from a function compiled with Burst, which has limited exception support.
0x00007fffaff7c7ae (0ae88993e460fa38157630d718e7091) burst_Abort_Trampoline
0x00007fffaff583ba (0ae88993e460fa38157630d718e7091) Pathfinding.NavmeshCutJobs.ConvexHull (at F:/Unity/ProjectTitan/Library/PackageCache/com.unity.burst@1.8.18/.Runtime/Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:1089)
0x00007fffaff576c9 (0ae88993e460fa38157630d718e7091) Pathfinding.NavmeshCutJobs.BoxConvexHullXZ (at F:/Unity/ProjectTitan/Library/PackageCache/com.unity.burst@1.8.18/.Runtime/Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:996)
0x00007fffaff560a5 (0ae88993e460fa38157630d718e7091) Pathfinding.NavmeshCutJobs.JobCalculateContour.Execute (at F:/Unity/ProjectTitan/Library/PackageCache/com.unity.burst@1.8.18/.Runtime/Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:810)
0x00007fffaff553a9 (0ae88993e460fa38157630d718e7091) 75ae4786f05f2725e8712bff663ac500
0x00000242474f7ee8 (Mono JIT Code) (wrapper managed-to-native) Pathfinding.NavmeshCutJobs/Pathfinding.CalculateContour_000008BF$BurstDirectCall:wrapper_native_indirect_00000243453120D8 (intptr&,Pathfinding.NavmeshCutJobs/JobCalculateContour&)
0x00000242474f7be3 (Mono JIT Code) Pathfinding.NavmeshCutJobs/Pathfinding.CalculateContour_000008BF$BurstDirectCall:Invoke (Pathfinding.NavmeshCutJobs/JobCalculateContour&)
0x00000242474f6e6b (Mono JIT Code) Pathfinding.NavmeshCutJobs:CalculateContour (Pathfinding.NavmeshCutJobs/JobCalculateContour&) (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:654)
0x00000242474f6953 (Mono JIT Code) Pathfinding.NavmeshCut:GetContourBurst (Unity.Collections.LowLevel.Unsafe.UnsafeList1<Unity.Mathematics.float2>*,Unity.Collections.LowLevel.Unsafe.UnsafeList 1<Pathfinding.NavmeshCut/ContourBurst>*,UnityEngine.Matrix4x4,single) (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:529)
0x00000242474f4eeb (Mono JIT Code) Pathfinding.NavmeshCut:GetContour (System.Collections.Generic.List1<Pathfinding.NavmeshCut/Contour>,UnityEngine.Matrix4x4,single) (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:469) 0x00000242474f3cf3 (Mono JIT Code) Pathfinding.NavmeshCut:GetBounds (Pathfinding.Util.GraphTransform,single) (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshCut.cs:394) 0x0000024247b95203 (Mono JIT Code) Pathfinding.Graphs.Navmesh.NavmeshUpdates:ScheduleTileUpdates () (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshUpdates.cs:444) 0x00000241cb08e493 (Mono JIT Code) Pathfinding.Graphs.Navmesh.NavmeshUpdates:Update () (at ./Packages/com.arongranberg.astar/Navmesh/NavmeshUpdates.cs:368) 0x00000241cb08e23b (Mono JIT Code) AstarPath:Update () (at ./Packages/com.arongranberg.astar/Core/AstarPath.cs:853) 0x00000242477bb8d8 (Mono JIT Code) (wrapper runtime-invoke) object:runtime_invoke_void__this__ (object,intptr,intptr,intptr) 0x00007fffc7084c7e (mono-2.0-bdwgc) mono_jit_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/mini/mini-runtime.c:3445) 0x00007fffc6fbd284 (mono-2.0-bdwgc) do_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/metadata/object.c:3068) 0x00007fffc6fbd3fc (mono-2.0-bdwgc) mono_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/metadata/object.c:3115) 0x00007ff64f5194f4 (Unity) scripting_method_invoke 0x00007ff64f4f5f64 (Unity) ScriptingInvocation::Invoke 0x00007ff64f4dd6e4 (Unity) MonoBehaviour::CallMethodIfAvailable 0x00007ff64f4dd80a (Unity) MonoBehaviour::CallUpdateMethod 0x00007ff64ef6ee2b (Unity) BaseBehaviourManager::CommonUpdate<BehaviourManager> 0x00007ff64ef761aa (Unity) BehaviourManager::Update 0x00007ff64f1abeed (Unity) InitPlayerLoopCallbacks’::`2’::UpdateScriptRunBehaviourUpdateRegistrator::Forward
0x00007ff64f18b7bc (Unity) ExecutePlayerLoop
0x00007ff64f18b930 (Unity) ExecutePlayerLoop
0x00007ff64f191ee5 (Unity) PlayerLoop

  • Other BUG is (a,a) must return 0/equals.

This BUG can fix by:
public int Compare(float2 lhs, float2 rhs)
{
if (lhs.Equals(rhs)) return 0;
if (lhs.GetHashCode() == rhs.GetHashCode()) return 0;

// cross product of (lhs - origin) and (rhs - origin)
var a = lhs - origin;
var b = rhs - origin;
var cross = a.x * b.y - a.y * b.x;
if (cross == 0)
{
    var la = math.lengthsq(a);
    var lb = math.lengthsq(b);
    if (la < lb) return 1;
    else if (la > lb) return -1;

    var fa = a.x + a.y;
    var fb = b.x + b.y;
    if (fa < fb) return 1;
    else if (fa > fb) return -1;

    if (a.x < b.x) return 1;
    else if (a.x > b.x) return -1;

    if (a.y < b.y) return 1;
    else if (a.y > b.y) return -1;

    return 0;

    //return la < lb ? 1 : (lb < la ? -1 : 0);
}
else
{
    return cross < 0 ? 1 : -1;
}

}

2

Hi

Thanks. It did indeed miss the case where a == -b.
However, the original code should definitely handle lhs == rhs and return 0.

I’ll include a fix in the next update:

struct AngleComparator : IComparer<float2> {
	public float2 origin;
	public int Compare (float2 lhs, float2 rhs) {
		// cross product of (lhs - origin) and (rhs - origin)
		var a = lhs - origin;
		var b = rhs - origin;
		var cross = a.x*b.y - a.y*b.x;

		if (Unity.Burst.CompilerServices.Hint.Unlikely(cross == 0)) {
			var la = math.lengthsq(a);
			var lb = math.lengthsq(b);

			if (la < lb) return 1;
			else if (la > lb) return -1;

			// At this point, either lhs == rhs, or lhs == -rhs
			// Sort first by x, then by y
			if (a.x < b.x) return 1;
			else if (a.x > b.x) return -1;

			if (a.y < b.y) return 1;
			else if (a.y > b.y) return -1;

			return 0;
		} else {
			return cross < 0 ? 1 : -1;
		}
	}
}