I’m currently using a grid graph. I was wondering what is the best way to update a graph to account the changes of moving objects, such as the player, the NPCs, AI, etc…
The way I’m doing it is I have all colliding objects update every few seconds by calling the update(at the same time, but only by coincidence) by calling the AstarPath.active.UpdateGraphs(collider.bounds). Unfortunately this is resulting with an FPS dip to around 20FPS whenever the graph updates are called and that’s only with around 50 objects.
So I was wondering how do most games, RTS and RPGs in particular, handle moving objects with their graphs when they have many moving units?
I’m thinking of maybe serially calling all objects that need to be updated from a script that will hold a reference to them. The script will make sure only 1 object (or a small batch of objects) will be updated at a time, and won’t call the UpdateGraphs method to other objects until the current update process is done. But I’m not sure if this will fix the performance issues.
What do you think?
Many RTS games don’t update the graphs for that. SC2 for example uses navmeshes for everything. Either they don’t update the graphs, or the units happen to have the same size as one node, and then the update is really fast. Instead they use different local avoidance algorithms to handle the avoidance of other units. Local avoidance algorithms only give the local minima however, not the global minima (which pathfinding would give), but this is usually not a problem.
One optimization is to only update if the position has changed more than some distance. And to, as you say, chunk the updates to a few large updates. When I have a bunch of units which will do something in regular intervals I use this kind of code:
IEnumerator DoStuff () { while (true) { //DoStuff which takes some time yield return new WaitForSeconds (delayTime * (Random.value+0.5f)); } }
That usually spreads them out nicely.
Thank you for your quick answer! Sorry I didn’t reply sooner!
It’s really funny that you mention SC2, because that’s the exact game I was thinking of when I asked this question, where every map has at least 3948239048 units it! xD
Local obstacle avoidance seems like a bit of a pain to implement, but that’s just from a quick browsing of some articles I saw so far. Normally I’d try to implement it anyway, but after implementing your way with the Wait and the serial updates, I managed to get a stable FPS between 50-60, and that’s with around 700 objects! (if not more)
Sure, they take around 5-10 seconds to update all, but that’s with updating only 1 object at a time, and without the optimization of updating only moving objects, as well without giving priority to certain types of objects, and other optimizations.
If any trouble is encountered in the future, I will think about obstacle avoidance. The thing that’s deterring me the most from it is making the AI movement seem somewhat realistic.
Thank you again for your great answer. 
PS: Local avoidance based on http://gamma.cs.unc.edu/RVO2/ will be included in the next update.
