StackOverflow UpdateRecursiveG

[Gabe]

• A* version: [new System.Version(4, 3, 60);]
• Unity version: [2021.3.45f1]

NOTE: I’ve fixed this issue by updating from 4.3 to 5.2, BUT I have some problems with the update outlined in the last reply if you could please read that, thanks!

Hello, I recently updated my unity version very slightly from 1. 2021.3.5f1 to 2021.3.45f1 for some minor shader updates in a different plugin. I did not change anything in astar project or in my use of the API. Everything seemed fine with it at first, but after testing more I’m now getting a stack overflow issue like this

"System.StackOverflowException: The requested operation caused a stack overflow.\r\n  at (wrapper managed-to-native) System.Object.__icall_wrapper_mono_gc_wbarrier_generic_nostore_internal(intptr)\r\n  at (wrapper write-barrier) System.Object.wbarrier_conc(intptr)\r\n  at Pathfinding.BinaryHeap.DecreaseKey (Pathfinding.BinaryHeap+Tuple node, System.UInt16 index) [0x00083] in C:\\PerforceWorkspaces\\FormationTacticsGame\\Library\\PackageCache\\com.arongranberg.astar@4.3.60\\Core\\Misc\\BinaryHeap.cs:167 \r\n  at Pathfinding.BinaryHeap.Add (Pathfinding.PathNode node) [0x00029] in C:\\PerforceWorkspaces\\FormationTacticsGame\\Library\\PackageCache\\com.arongranberg.astar@4.3.60\\Core\\Misc\\BinaryHeap.cs:137 \r\n  at Pathfinding.GridNode.UpdateRecursiveG (Pathfinding.Path path, Pathfinding.PathNode pathNode, Pathfinding.PathHandler handler) [0x00023] in C:\\PerforceWorkspaces\\FormationTacticsGame\\Library\\PackageCache\\com.arongranberg.astar@4.3.60\\Generators\\NodeClasses\\GridNode.cs:262 \r\n  at Pathfinding.GridNode.UpdateRecursiveG (Pathfinding.Path path, Pathfinding.PathNode pathNode, Pathfinding.PathHandler handler) [0x00086] in C:\\PerforceWorkspaces\\FormationTacticsGame\\Library\\PackageCache\\com.arongranberg.astar@4.3.60\\Generators\\NodeClasses\\GridNode.cs:270 \r\n  at Pathfinding.GridNode.UpdateRecursiveG (Pathfinding.Path path, Pathfinding.PathNode pathNode, Pathfinding.PathHandler handler) [0x00086] in C:\\PerforceWorkspaces\\FormationTacticsGame\\Library\\PackageCache\\com.arongranberg.astar@4.3.60\\Generators\\NodeClasses\\GridNode.cs:270 \r\n  at Pathfinding.GridNode.UpdateRecursiveG (Pathfinding.Path path, Pathfinding.PathNode pathNode, Pathfinding.PathHandler handler) [0x00086] in...

and it just keeps repeating like that, so seemingly some issue in UpdateRecursiveG of GridNode. this in turn calls TerminateReceivers() in CalculatePathsThreaded() of PathProcessor.cs, which means all paths after that fail to start, of course breaking everything after that point. I construct the paths like this (ignore hash in brackets of int just for formatting here):

var p = ABPath.Construct(startPosition, endPosition, OnPathComplete);
int[#] tagPenalties = new int[32];
Pathfinding.GraphNode nodeEndPosition = AstarPath.active.GetNearest(endPos).node;
tagPenalties[3] = …
ApplyMovementPathSettings(p, tagPenalties);
AstarPath.StartPath(p);

if(Application.isPlaying){AstarPath.BlockUntilCalculated(p);}

and where:

public void OnPathComplete(Pathfinding.Path path)
{
ABPath abPath = path as ABPath;
…

I did not change gameplay code or astar code or increase the number of paths calculated or anything like that. The stack trace in visual studio and at the exception e doesn’t go back far enough to which path was called to help me isolate which unit started it, as it’s multithreaded i guess? Could some settings need to be updated? Is this version of Unity not compatible with this version of AStar?

Thanks for any help.

[Gabe]

as a further update, i’m getting warnings saying:

Very high penalty applied. Are you sure negative values haven't underflowed?
Penalty values this high could with long paths cause overflows and in some cases infinity loops because of that.
Penalty value applied: 4294957296
UnityEngine.Debug:LogWarning (object)
Pathfinding.GraphNode:set_Penalty (uint) (at Library/PackageCache/com.arongranberg.astar@4.3.60/Core/Nodes/GraphNode.cs:231)
Pathfinding.Jobs.Grid.JobAssignNodeData:Execute (int,int) (at Library/PackageCache/com.arongranberg.astar@4.3.60/Generators/Utilities/GridGraphJobs.cs:912)
Pathfinding.Jobs.JobParallelForBatchedExtensions/ParallelForBatchJobStruct`1<Pathfinding.Jobs.Grid.JobAssignNodeData>:Execute (Pathfinding.Jobs.Grid.JobAssignNodeData&,intptr,intptr,Unity.Jobs.LowLevel.Unsafe.JobRanges&,int) (at Library/PackageCache/com.arongranberg.astar@4.3.60/Utilities/IJobParallelForBatched.cs:42)

If that helps? I do apply penalties of 15,000, 30,000, or 90,000 as the case may be for different ground types, but those did not cause issues before. The penalty it says is 4294957296 which is ofc 2^32 so probably max int32 but why would that be applied all the sudden?

[Gabe]

looking at where the warning is thrown, it’s in GridGraphJobs.cs Execute() method on line 912 where it applies the penalty:

node.Penalty = nodePenalties[dataIndex];

where in this case dataIndex is 991, but starting at 909 the penalties all go from 0 to 4294957296, and it seems that max int penalty is in random places in the array of 1681 entries in nodePenalties.

In GridGenerator.cs where nodePenalties is initialized like

// Assign the data to the nodes (in parallel for performance)
// Note that it is essential that the nodes have earlier been dirtied, otherwise they might be dirtied in parallel which
// will cause all kinds of thread safety issues.
var job2 = new JobAssignNodeData {
				nodesHandle = nodesHandle,
				graphIndex = graphIndex,
				nodePositions = nodePositions,
				nodePenalties = nodePenalties,

you can see that comment about nodes being dirtied? is that the issue? they are not initialized somewhere else to 0? Why would this all the sudden start happening? like reused before released by another thread? NodePenalties is itself:

nodePenalties = dependencyTracker.NewNativeArray<uint>(numNodes, allocationMethod, NativeArrayOptions.UninitializedMemory);

which I guess is set here:

public void SetDefaultPenalties (uint initialPenalty) {
	nodePenalties.MemSet(initialPenalty).Schedule(dependencyTracker);
}

but I guess that is not being called? or not in time? Am I just somehow calling too many paths in a short period of time? But why would this all the sudden start happening after being fine for a year?

[Gabe]

And maybe a relevant question, but I am on version 4.3.60, should i update it? what is the highest I should update it to with unity version 2021.3.45f1?

I have it installed via the scoped registry option by editing the manifest.json in yourProject /Packages/manifest.json. Given that’s the case, I don’t have to delete the existing folder, right? I’m a bit confused by the instructions which say:

ie only delete the project folder if you installed before without the package manager, but does it mean with instead of without? I installed without the package manager, so instead with the scoped registry via manifest.json, and so I don’t have a project folder to delete, only the PackageCache entry in the Library folder.

If I were to update, all I’d need to do is edit the version number in manifest.json and then I will be prompted by the scoped registry popup? What version number should I choose for 2021.3.45f1? I do have a custom ailerp script btw if that’s important.

[Gabe]

A further note here, I see that there are some other, much older threads discussing something similar, although without (public) solutions:

Overflowing graphs, penalty set too high, no new paths will be created

Hi, I’ve been having some trouble trying to figure out what might be causing some errors I am getting during runtime. I just upgraded A* to the most current version, and am seeing a few warnings and errors that I didn’t see prior to the upgrade. 1st… After a few minutes and 30 or so units are on the grid I see warnings telling me that there are high penalties set… As far as I can tell, there are no penalties set anywhere. 2nd… I receive a warning telling me that no new paths will be created,…

"Very high penalty applied"

I’m getting similar errors including StackOverflowException and “very high penalty applied” when using Alternative Path script updating the grid graph using a Graph Update Object. I’ve even reduced the Alternative Path penalty to 10 and I’m still getting the error. Is there something that I should be doing if I update the graph? Is there a way to reset penalties on the graph to zero?

PointGraph + AIPath + RVO + AlternativePath = Crash

Hey all, As stated in the subject I have a PointGraph+AIPath+RVO setup and it’s working the way I would like it. I’m trying to add an AlternativePath modifier to my agents and it’s crashing essentially randomly. Which is a shame because when it’s not crashing it’s doing almost exactly what I want. Some info: This scene has 15 agents to test with. I need to support upwards of 50. The agents are repathing every 0.25 or 0.5 seconds depending on which they are. Editor.log is giving me thi…

It would make sense as a multithreading issue as one of those posts mentioned that the issue would go away if you set thread count in the pathfinding settings to 1. IE one thread starts using that native array of tag penalties before another is finished with it and you end up with max int penalties applied, or something like that.

I am not using AlternativePath script as far as I know, as some of those threads mention, only a custom ai lerp script.

One reply there mentioned just editing the GraphNode.Penalty property setter to just throw a warning but otherwise edit on Setting the Penalty to a normal number if it is > 0xFFFFF, which I guess would work but not really fix the underlying issue. Does a newer version of astar address this one way or the other?

Thanks!

[Gabe]

NOTE: I upgraded to latest and that resolved the stack overflow exception on my scripts so I don’t end up with crashes anymore, however the “very high penalty applied…” warning is still getting spammed. I suspect this may still be causing problems if the penalty values are not being reset?

I am also left with another issue that may be related:

I am carving the navmesh manually around combats in my game so other units nav around them, but now that functionality has stopped working. By carving I mean applying a penalty, not making unwalkable. The code looks like:

public void ActivateCombatMeshCarver(bool activate)
{
GraphUpdateScene GUS = unitCombatMeshCarverObject.GetComponent<GraphUpdateScene>();
    GraphUpdateScene GUS2 = unitCombatMeshCarverInteriorObject.GetComponent<GraphUpdateScene>();

    if(activate)
    {
        unitCombatMeshCarverObject.transform.position = _formation.Line.GetMidpoint();
        unitCombatMeshCarverObject.transform.rotation = transform.rotation;
        unitCombatMeshCarverObject.GetComponent<BoxCollider>().size = Universals.u.combatBoxSizeWalkPenalty;
        GUS.penaltyDelta = Universals.u.combatBoxWalkPenalty;

        GUS.Apply();

        unitCombatMeshCarverInteriorObject.transform.position = _formation.Line.GetMidpoint();
        unitCombatMeshCarverInteriorObject.transform.rotation = transform.rotation;
        unitCombatMeshCarverInteriorObject.GetComponent<BoxCollider>().size = Universals.u.combatBoxInteriorSizeWalkPenalty;
        GUS2.penaltyDelta = Universals.u.combatBoxWalkInteriorPenalty;
        GUS2.Apply();
    }
    else
    {
        GUS.penaltyDelta = -Universals.u.combatBoxWalkPenalty;
        GUS.Apply();
        unitCombatMeshCarverObject.transform.position = new Vector3(0, 100, 0);

        GUS2.penaltyDelta = -Universals.u.combatBoxWalkInteriorPenalty;
        GUS2.Apply();
        unitCombatMeshCarverInteriorObject.transform.position = new Vector3(0, 100, 0);
    }
}

so basically it was carving around the size of a box collider that is placed around a unit (like a formation of men in this case) where they are in combat, and then removes the penalty and goes away when the combat is over. This worked before, but now appears to have no effect on navigation penalties. Is there some change to the API for this now? Do I need a newer version of Unity? I have experimented with delaying the apply with a coroutine after moving the box into place, and it will sometimes erratically carve and sometimes not, but it needs to do it consistently otherwise the map is left with random carved bits after combats are resolved, because I’m turning it on and off as the combat start/end or shift back and forth.

Thanks

EDIT: to add some detail, here’s the graphupdatescene component of the above collider in editor in play mode as it’s instantiated in code:

and here it is in the scene view, you can see it overlapping the navmesh, ie you can see the box around the combat where the penalty should be applied:

and you can see here I do a test graphupdatescene object over on the right that I just put into the scene with apply on start and scan and a penalty delta and it works, but the dynamic ones i spawn myself around combats that don’t apply on start or scan, but manually call apply when combats start, which you can see on the left where the green debugs are, there’s no penalty applied.

so in the general case of putting a graph update scene collider in the scene in editor it will work and show the penalty, but if it’s calling apply from script it doesn’t work. Is there something new I need to do to Apply() the graphupdatescene from the script? I’ve experimented with changing convex and erosion settings but it did not change anything. I tried batchGraphUpdates as well but it made no difference. Is there another setting on the astarpath component or grid graph itself that should change?

Also notable, with further testing I can see that the “Very high penatly applied…” warning from GraphNOde.cs line 303 only starts getting thrown after a graphupdatescene is successfully applied (just happens at end of combats now, never on begin or during them when its supposed to, and is supposed to turn off not on after a combat), so something about the apply is like setting off random max int32 penalties. Does astarpath 5.x require unity 2022+ and not unity 2021?

[Gabe]

Further update for anyone reading this: The cause of the issue is that, for performance reasons related to something else, I incidentally had turned off Auto Sync Transforms in ProjectSettings → Physics, so colliders like the one used for the graph update scene were not syncing to transform changes until the next tick. Not normally a huge deal, BUT if you do something like the above GraphUpdateScene.Apply() on the line right after updating the transform of the object and you don’t auto sync transforms then the collider used as the bounds wont be at the right position for the update until just after apply has already run. So, the solution is either to turn auto sync transforms back on if you can, or in my case the better solution was to manually call Physics.SyncTransforms(); right after the transform updates but right before the call to GraphUpdateScene.Apply(), so like:

GraphUpdateScene GUS = unitCombatMeshCarverObject.GetComponent<GraphUpdateScene>();
unitCombatMeshCarverObject.transform.position = _formation.Line.GetMidpoint();
unitCombatMeshCarverObject.transform.rotation = transform.rotation;
unitCombatMeshCarverObject.GetComponent<BoxCollider>().size = Universals.u.combatBoxSizeWalkPenalty;
GUS.penaltyDelta = Universals.u.combatBoxWalkPenalty;

Physics.SyncTransforms();
GUS.Apply();

where unitCombatMeshCarverObject is the game object/transform I instantiated from a prefab at start that contains the box collider and the GraphUpdateScene component and that is placed down where a combat starts.

Arguably, a better solution is to manually change the box colliders location and bounds and not depend on the movement of its transform, but actually I’m not 100% sure how to do that the way I wanted.

Also note that with this change the warning spamming about “very high penalty applied…” went away, I suspect because the turning off of the box still worked, as it was already in place before the apply in that case, but in that case rather than bringing the penalty from 10k back down to zero, it was bringing it from 0 into -10k as the initial apply had not worked, and negative penalties are not permitted (i guess its a uint32 not int32, so no negative values, so trying to do negative messes up wherever it’s reset and makes it max uint32 and sets off all the other issues). Maybe the place where that warning is thrown or somewhere before it should say “you tried to apply a negative penalty to a node whose magnitude is higher than the current penalty thus resulting in a net negative penalty which is not permitted” and then just set it to 0 min penalty rather than trying to force set a net negative penalty. Like maybe change this:

set {
	if (value > 0xFFFFFF)
		Debug.LogWarning("Very high penalty applied. Are you sure negative values haven't underflowed?\n" +
			"Penalty values this high could with long paths cause overflows and in some cases infinity loops because of that.\n" +
			"Penalty value applied: "+value);
	penalty = value;
}

to either not change penalty at all if value > 0xFFFFFF, or to set incoming value and thus penalty to 0 in that case?

[Gabe]

As an additional note in case it helps anyone in the future, because the GraphUpdateScene uses the colliders AABB bounds, it doesn’t rotate with the transform, so if you are going to rotate the relevant box collider’s transform dynamically in the scene for node updates, you can set the GUS object’s points (and min bounds height if needed) like so:

GUS2.points = GetColliderTopVertexPositions(unitCombatMeshCarverInteriorObject);
GUS2.minBoundsHeight = 40f;

where GetColliderTopVertexPositions (assuming you use a box collider) looks like:

public Vector3[] GetColliderTopVertexPositions (GameObject obj)
{
    BoxCollider b = obj.GetComponent<BoxCollider>(); GameObject called obj
    Vector3[] vertices = new Vector3[4];
    vertices[0] = b.center + new Vector3(-b.size.x, -b.size.y, -b.size.z) * 0.5f;
    vertices[1] = b.center + new Vector3(b.size.x, -b.size.y, -b.size.z) * 0.5f;
    vertices[2] = b.center + new Vector3(b.size.x, -b.size.y, b.size.z) * 0.5f;
    vertices[3] = b.center + new Vector3(-b.size.x, -b.size.y, b.size.z) * 0.5f;

    return vertices;
}

note it’s getting 4 not all 8 as you just need the top or bottom of the box, then you project up and down with the minBoundsHeight

[tealtxgr]

Hey there, thanks for the detailed thread! If I’m following correctly, your original issue was solved by updating Astar, and the resulting issue was solved using SyncTransforms(), correct? Were there any other complications you were having I might’ve missed?

[Gabe]

yes! thanks, although one additional thing to mention is the confusion over whether the UPM installation guide has a typo, ie this part:

I did not delete any astarpath project folder as I did not have one as I had only ever installed it via the scoped registry not via the package manager. So, should it say with or without in that 1. step?

[Gabe]

I actually do have an additional question. I am getting this error:

generally after ending playmode, but I don’t PathfindingTag anywhere myself. Is this an error being thrown from the astar code? It does not give a locations as you see on the bottom.

[tealtxgr]

I’m pretty sure it should say ‘without’ as it does already, yes. If you haven’t done so already when you updated to 5.2 I’d fully delete and reinstall the package, being sure to backup your custom AILerp script. That may also help with the PathfindingTag error. That class is a part of Astar, yes, but I don’t know whether Unity itself or Astar is throwing that.

[Gabe]

ok, but what I’m confused about is if I install from the scoped registry I don’t have an astarpath project folder.

[aron_granberg]

But if you install it using a scoped registry, then you are using the package manager, and point 1 does not apply to you (because of the “without using the package manager” part). Editing the manifest.json file counts as using the package manager. The package manager is essentially just a UI for editing the manifest.json file.

[Gabe]

so…what do I do? Do I still need to delete a folder somewhere? sorry just a bit confused I can’t find this folder.

[aron_granberg]

No. You installed it using the package manager, so you do not have to delete anything.

[Gabe]

ok thanks! 13 characters etc…