I took the Example2 of the 2 moving cubes that uses the DynamicGridObstacles.
Also, I changed the grid in the A* object to reflect what I have in my game.
I set up :
The NodeSize to 1
The with and depth to 500 to cover all the area.
I pressed Scan to recompute the graph.
This is a typical grid I have in my game.
I pressed play with the Unity Profiler to ON.
The Updategraph takes around 7ms when the script (DynamicGridObstacles) calls the UpdateGraph when they move far enough to call the UpdateGraph.
While it plays, I delete one of the cube, we`re now at 4ms…
Any way to bring that closer to < 1ms ?
Or any other tricks so the pathfind ignores those node without updating the graph but by applying kind of meta data on those nodes to skip them like if they were cut ?
In my game, I have dynamic objects that spawns at random places. When they spawn I want to update that area once and when they die, re-update to bring back how it was. My objects are not moving over time, but appears and disappears.
Any way to achieve that ? I have hundreds of those objects and around 5 to 10 per frames spawning and despawning. It consumes around 70ms per frame by recomputing the graph in my game (layered graph). I cannot ship with that, I need your help to find another trick…
First thing. Batch graph updates to reduce the flood fill overhead: A* Inspector -> Settings -> “Limit graph updates”, “Max Update Frequency”.
If that doesn’t help enough:
What you could do is disable flood filling as that is usually the limiting factor in large worlds.
(I am also working on very interesting feature which will reduce that cost to nearly zero in most cases (not all though), but that’s for later).
In the AstarPath.cs script, put a ‘return;’ at the start of the FloodFill method.
This will make pathfinding go really slow if there is no possible path from the start to the end of the path, but in your game those requests might never happen or your world might be completely connected.
It is a bit odd though that those updates seem to scale linearly with the number of obstacles, I would have expected otherwise since the flood fill cost is usually what takes up most of the time. If the above does nothing then if you could post a more detailed screenshot from the unity profiler that would be great.
Also. Potentially it could be better with a recast graph and navmesh cutting if you do not need to add any new walkable surfaces during runtime. This video shows that quite a lot of obstacles can be handled with that method: http://arongranberg.com/astar/docs/class_pathfinding_1_1_navmesh_cut.php
First thing. Batch graph updates to reduce the flood fill overhead: Astar Inspector → Settings → “Limit graph updates”, “Max Update Frequency”.<
I put 0.5 seconds as MaxUpdate, even 1 seconds, Delaying doesn`t really solve the issue, the update still takes time, I even get behind by a couple of seconds if I have a lot of objects. But I understand the suggestion and I could use it for another topic!
In the AstarPath.cs script, put a ‘return;’ at the start of the FloodFill method.
Ah. So there are some important things here. First: erosion takes a lot of time. That is reasonable, erosion is pretty slow, so if you want higher performance you should disable it.
Removing erosion made the sample2 go to 4ms instead of 7ms, indeed it went down a bit.
But when we update with bounds, I find it strange we need to go through all nodes…There are surely some reasons.
Multiple smaller grids won’t help anything (still same number of nodes to be updated) and it also usually leads to annoying edge cases.
The main thing is the resolution of the graph.
You can also test and see if you can simplify the physics checks (grid graph settings). E.g change collider type from capsule to sphere or ray.
If your objects are not overlapping and always have some margin between each other then you can set the “walkable” field directly instead of using physics, that will reduce the time quite a lot (40-50% would be my guess).
See A* Pathfinding Project
I will make sure the nodes are not too small or not too big.
I will definitely look at the Walkability and I think it’s the answer I needed from the start.
I will change the capsules to spheres I can manage that.
As for the walkability:
Do you have any samples using a walkability change (How could I change the Sample2 to do that with the moving cubes, I will remove the animation from them ) ?
We have Dynamic Grid Obstacle script for the recompute by bounds, is there a script that changes the walkability by bounds too ?
