Performance Optimisation with 100's of AI

I'm currently working on a simulation/management game that relies on lots of AI agents, after prototyping it this week I'm currently working out how to make each AI take far less resources per frame so I can push the numbers up as currently 1000 ai will bring the game down to 40fps on a 7700k.

The biggest issues seem to be from each AI doing a lot of Vector3.distance checking and GC on the functions they use when spawning. When a AI spawns it grabs all objects in the scene it needs and stores them in a gameobject array, then it will check if it is close to the ai target to call functions as needed.

The ideas I have to reduce perf cost is to try using object pooling to reduce load on spawning and destroying AIs, using set ints for my for loops as I suspect a lot of GC is it throwing away memory used for storing the values made and try using timers to reduce function calls per frame.

Is there any other things I should consider using to reduce cpu load per AI, as I have a rather powerful cpu and I want to get the game working well on lower end systems with more AI.

 

The main thing would be to use Threading.
What is this method that's called when they spawn? Perhaps that could be optimised?

What does the profiler say? (Make sure to turn on Deep Profiling)

 

Vector3.distance uses a square root, that takes a LOT to calculate (something like 200x your average Mathf function).

If you can, use Vector3.SqrtMagnitude as much as you can, that one is pretty much free compared to distance.

If you can't, there are some ways to optimize square root calculations.

 

Yeah it seems using Vector3.SqrtMagnitude is the way to go, just out of curiosity, what does remainingdistance with ai use perf wise?

 

No idea how expensive that function is, because the code inside it isn't open source, but it probably uses a square root somewhere in it, so I would avoid it if you can.


Btw here is a formula that I "Invented" ( prob someone already invented it before me, but I found out it works by myself ), so it lets you calculate distance without using a square root, but the drwaback is that you can only calculate it in 2d.

Code (CSharp):

1.             float arg = -Mathf.Atan2(y, x);
2.             float distance = x * Mathf.Cos(arg) - y * Mathf.Sin(arg);
3.  
4.             return distance;

 

Use the profiler. I suspect you'll find that GC eats up far more than Mathf.Sqrt, and pooling should help a lot. But every little thing helps, so you might as well use SqrtMagnitude, too.

Instead of threading, it's probably better to simply do less work. If you're checking in Update(), do you really need to check every ~60 frames? Or is one check per second sufficient? If so, this will give you an instant ~60x performance boost.

 

Instead of storing the objects in an array why not use either a quadtree or an octree, that way you can cut down the number of distance checks, by a fair amount.

 

Do you really need to update all 100 AIs every frame? You could spread them out across multiple frames.

 

"Grabs all objects in the Scene it needs" looks suspect. How does it do that exactly? If it's doing a search of the entire hierarchy (many GameObject API calls do this internally) that could be most of your problem right there. Since you have 1000 AIs your Hierarchy is probably large too. Here's what I would do. 2 main things.

If it needs to grab all of 3 different game objects types, have each of those game objects register themselves during onEnable into a list in a static gameTracker script (and remove themselves from that list in onDisable). Then just have the AIs ask for those lists from the gameTracker when they spawn (yes Definitely use pooling always). No hierarchy searching. If you know in advance the capacity of each list, set it to that when you new it up so it doesn't have to keep growing, which causes GC and is slow.

Also, make a queue in an AIManager class to process the AI logic so that you don't even have an Update (or LateUpdate or FixedUpdate) method in your AI scripts at all. Because even a single if statement in an Update method times 1000 can singlehandedly kill your frame rate. Again, have the AI's register themselves into the queue during OnEnable and remove during OnDisable.

In that queue, process a set max number of AI's "Update" methods and adjust it until you get the performance you need and can live with each one only updating every X frames. Yes you will need to put each AI updated back into the end of the queue so it keeps doing it. This second trick works wonders for performance.

 

https://docs.unity3d.com/ScriptReference/Vector3-sqrMagnitude.html

The whole point of that function is to avoid the square root. Instead you do a comparison against the square of the distance to match the squared magnitude returned, so it's replacing the square root with a multiply.

sqrt ((x_2-x_1)^2+ (y_2-y_1)^2+ (z_2-z_1)^2) < distance

becomes

((x_2-x_1)^2+ (y_2-y_1)^2+ (z_2-z_1)^2) < distance^2

and assuming x_1, y_1, z_1 are all 0 for the origin, I suspect the sqrMagnitude function is basically

return (x^2 + y^2 + z^2)

 

A quad-tree has been mentioned already, that is a great way to optimize those distance checks.

There's another way too that will perform only slightly worse, but is far simpler to implement called "Spatial Hashing".
It's basically just having a 2D array of "cells", and every frame you add each AI agent to the correct cell, then when you want to find all nearby agents, you just have to check the center cell + all 8 neighbours.
Its basically a quad-tree with no nesting.

If you are really just limited by just the distance checks, then that will let you deal with tens of thousands of agents with no fps drops. (And you're paying with some memory + work to program that)-

I've seen free implementations on for quad-trees as well as spatial hashing grids for unity on github.