Fastest Graph/Path for large numbers of simple agents?

I have a large number (about 10k) of agents moving in formations well with the standard AILerp on a grid graph, but I am looking just to optimize it as much as possible. All I am doing right now is setting their destination on their AILerp component. Each formation (~500 men) gets its own path directly, and the individual men just follow along with their formation position offset using the lerp. My questions are for how to optimize those individual AILerp movers:

  1. what optimizations can I do to the AILerp component to make it as fast and barebones as possible? I don’t need very high fidelity, just to look ok from 100 feet or so. I made a custom AILerp that gets rid of some checks like remainingdistance, interpolatepathswitches, canmove, 2D/Y forward mode, and so on that I either don’t need or always want on, and i set the y rotation to 0 so they are always upright, but is there anything in the core MovementUpdate() I can optimize?

  2. I have the seeker component start/end point snapping set to “closest on node surface” (without which they don’t stay on the surface correctly) but are there some optimizations there to make it as barebones as possible?

  3. I have a simple smooth modifier with max segment length 10, uniform length, simple smooth option, 2 iterations, and .5 strength. Are there optimized selections there, or things I can remove from that modifier? What about just going without it?

  4. and finally for the graph type itself, what would be the most efficient one to move huge numbers of simple ai-lerping agents across? I only need one graph, and it does not need to update at runtime or be cut. I don’t even have obstacles or avoidance, just terrain that goes up and down. I have the pro version and am on the beta. Is there a fastest graph type? Maybe recast? and what are optimized settings for it?

thanks for any help!

Not a whole lot. To optimize it further you probably have to use burst, and that will require a larger rewrite.

Going without the modifier will make path calculations faster. If you use the profiler you may see a section called “Calling Path Callbacks” which is mostly due to modifiers.

Recast will be faster than a grid graph. Though, you will need the funnel modifier then. Pathfinding time is essentially proportional to the number of nodes searched, so if the graph has larger nodes then it will be faster to search.
You may not get as good paths with a recast graph, though. Depending on what your game needs.

thank you for the reply! I need a kind of undulating, rolling hills terrain, with no or few obstacles, and looking around at other threads and experimenting it seems like recast is not great for that as there are very few points of reference and you kind of just need to use a grid graph.

callbacks don’t seem bad in the profiler. anything I should try to do about the seeker instead? maybe that is not very heavy performance wise though, although i’m not sure what to look for for it.

I’ll look into using burst on movement update. RVO is done like that in the pro beta? Just burst and not ECS more generally? Or can that be a way to speed up calculations separate from iterating over entities?

Just burst, yes. I don’t want to add a dependency on entities.

I’d say use the profiler and check for anything that looks slow. In terms of movement scripts, AIPath is a bit faster than RichAI, and AILerp is also faster (but that one only works for some types of games).

Take a look at Optimization - A* Pathfinding Project

a few questions now actually that I’m coming back to try and optimize this more. The profiler says the main burden for me is in the location/rotation update of AILerp. How might a rewrite of that using Burst/Jobs potentially look? Is that something you’ve started on or have some ideas about? What file is your RVO using burst in? Would it be able to use the new ECS Transforms?

Also, why do I need the funnel modifier for the recast graph? The simple smooth modifier seems to be working?

I’ve enabled multithreading, turned off logging and such. There are no character controllers or much of anything else on the individual entities.
By larger nodes = faster to search, do you mean the tile size? Or what settings on the recast graph (i have pro) would improve performance of huge numbers of ailerp navigating objects?



If you want, you could try out the new FollowerEntity movement script which is now available in the beta.
It uses ECS and scales much better to multiple cores.
It does way more than the previous movement scripts, though. So handling 10k agents is still a bit of a tall order for it. The AILerp script is still significantly simpler and probably more performant, even though it runs in the main thread. So while this might not be for you, it might be interesting for you to look at nontheless.