I’ve been manually changing obstacles / penalties (without colliders) by overriding RecalculateCell like so:
public override void RecalculateCell(int x, int z, bool resetPenalties = true, bool resetTags = true)
{
var node = nodes[z * width + x];
// Set the node's initial position with a y-offset of zero
node.position = GraphPointToWorld(x, z, 0);
float moveModifier = MySpecialIndependentGridClass[x, z].MoveModifier;
bool walkable;
uint penalty;
if (moveModifier <= 0f)
{
walkable = false;
penalty = 5000u;
}
else
{
walkable = true;
float tileSpeedToPenalty = 5000f;
// 1.2 MoveModifier --> .833 --> .833 * tileSpeedToPenalty : lower is LESS penalty b/c faster movement
// 0.8 MoveModifier --> 1.25 --> 1.25 * tileSpeedToPenalty : larger is MORE penalty b/c slower movement
penalty = (uint)((1f / moveModifier) * tileSpeedToPenalty);
}
node.Penalty = penalty;
node.Walkable = walkable;
}
This has the advantage that I can easily call
AstarPath.active.UpdateGraphs(boundsToUpdate)
But it’s also true that I have a parallel grid structure (MySpecialIndependentGridClass): I know the exact grid graph nodes that need to change, so using bounds is a little wasteful. Another disadvantage - the one I’m more concerned about - is that whenever I want to change a penalty UpdateGraphs will cause a rescan, and I don’t need that kind of fidelity when only changing penalties. I want my obstacle changes to respect my graphUpdateBatchingInterval, but if only updating penalties I don’t want to process those until there’s something more important to do. Grass-to-mud pathing penalization can be delayed for some time.
Should I not be overriding RecalculateCell and instead directly change nodes through AddWorkItem? AddWorkItem respects the graphUpdateBatchingInterval, correct? To limit updates for penalties, do I need to queue these myself or is there some way to say that a WorkItem is very low priority?
If you know the exact nodes that you want to change, then using AddWorkItem would be ideal. It would most definitely be the fastest approach.
AddWorkItem does however not use the graphUpdateBatchingInterval, however that field is primarily there to avoid having to recalculate the connected components of the graph unnecessarily often (as that is a heavy operation), but setting penalties does not require the connected components to be calculated anyway.
After some more investigation, my problem isn’t the updating, but using penalties whatsoever. I had assumed that the source of a fairly massive performance regression was updating more often, but as best as I understand it it’s from searching many, many more nodes due to penalties. I went from being able to support literally 1000s of agents repathing frequently to a few hundred before paths became unable to complete before a repath request. Do you have any advice on how to limit the performance cost of using penalties in particular beyond general stuff like turning repathing down? More generally, are there alternative ways to get similar behavior (preferentially pathing to faster roads / avoiding slow mud)?
Edit: shifting the typical penalty way down (5000 --> 150) results in fewer nodes searched, so that’s what I’ll do. Large differences between node penalties seems to result in much more searching.
For AddWorkItem, I’ve implemented by own batching.
Yeah, large penalties will make it search a lot more nodes because the shortest path could change a lot.
There is https://arongranberg.com/astar/docs/heuristicopt.html which would help, but unfortunately it requires a large pre-processing step which makes it less suitable when you are doing frequent graph updates.
Those heuristic optimizations work for penalties? I had looked at those docs before and had assumed it was just obstacles. That’s good to know if so.
I have a game where the player can pause, and a lot of processing power is freed up then, and even dropping whole frames isn’t noticeable. I could just have the heuristic run then, right? Or must the heuristic update right after other graph updates because, for example, an obstacle placed on one of the pivot points would be very bad?
It does work for penalties yes. It does not work for tags however.
The important part is that the preprocessing step has to run whenever penalties are reduced or obstacles are removed. However it does not necessarily need to run whenever penalties are increased or obstacles are added (it will just not be as good at improving the search performance, but the paths will still be optimal).
Currently the system is configured to recalculate this whenever a GraphUpdateObject has been applied. You might be able to change this if you want.