Question How to improve preformance of 2000 agents targeting on a large map

Hi,
I'm trying to create an RTS game with hundreds if not thousands of agents at once on the field.
This game might hold multiple players that might be enemies or allied with each other.
In summary, this script iterates through a list of agents and finds targets for AI agents based on their faction, enemy tags, and proximity within a specified magnitude. It sets the found targets to be used by the AI agents in their behaviors or actions.

The issue:
is that the performance drops considerably after 200 or so agents are on the field.
I would appreciate any further insights or alternative approaches that could help improve the performance of this target-finding process.

Note:
the agent view distance is 40 and the map is quite large means agents aren't always within a view distance of each other.

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4. public class TargetMasterForAI : MonoBehaviour
5. {
6.     GameMaster master;
7.     private void Start()
8.     {
9.         master = this.GetComponent<GameMaster>();
10.     }
11.     private void FixedUpdate()
12.     {
13.         findTargetToAI();
14.     }
15.  
16.     private void findTargetToAI()
17.     {
18.  
19.         if (master.allAgents.Count > 0)
20.         {
21.             for (int i = 0; i < master.allAgents.Count; i++)
22.             {
23.                 if (master.allAgents[i] != null)
24.                 {
25.                     if (master.allAgents[i].GetComponent<AiTargeting>() != null)
26.                     {
27.                         AiTargeting agentStats = master.allAgents[i].GetComponent<AiTargeting>();
28.                         agentStats.OnStart();
29.                         agentStats.Target = null;
30.                         for (int y = 0; y < master.allAgents.Count; y++)
31.                         {
32.                             if (master.allAgents[y] != master.allAgents[i])
33.                             {
34.                                 if (master.allAgents[y] == null)
35.                                 {
36.                                     continue;
37.                                 }
38.                                 if (master.allAgents[y].tag == master.allAgents[i].tag) //if ally
39.                                 {
40.                                     continue;
41.                                 }
42.                                 for (int x = 0; x < agentStats.myFaction.MyEnemies.Count; x++)//List of all enemy tags
43.                                 {
44.                                     if (master.allAgents[y].tag == agentStats.myFaction.MyEnemies[x])
45.                                     {
46.                                         if (master.allAgents[y].GetComponent<Entity>() != null)
47.                                         {
48.                                             Entity status = master.allAgents[y].GetComponent<Entity>();
49.                                             if (status.CurrentHP > 0)
50.                                             {
51.                                                 float dis = DisCalc(master.allAgents[y], master.allAgents[i].transform.position);
52.                                                 if (dis <= agentStats.magnitude)
53.                                                 {
54.                                                     agentStats.Target = master.allAgents[y].gameObject;
55.                                                 }
56.                                             }
57.                                         }
58.                                     }
59.                                 }
60.                             }
61.                         }
62.                     }
63.                 }
64.             }
65.         }
66.     }
67.     private float DisCalc(GameObject target, Vector3 me)
68.     {
69.         float distance = Vector3.Distance(target.transform.position, me);
70.         return distance;
71.     }
72. }

 

First thing you want to do is the profiler. I had a performance issue with my own AI agents one time. I was convinced it was the pathfinding and wasted a lot of time trying to fix that, but (when I finally used the profiler) it turns out that almost 80% of cpu time was my code writing debugging messages to the console. Totally different than I was expecting.

So see if you can identify more specific areas that are causing your slow-down.

 

Why are you using FixedUpdate()?

 

Some notes:

1. It looks like you are calculating the distances double times. The distance from agent #1 to agent #2 is equal than the distance from agent #2 to #1. But it may be faster to calculate the distance every time instead of doing the hashing for finding the already calculated distance. Has to be profiled to know for sure.
2. Depends on your exact case, but you may use the distance calculation without the mathematical square-root operation. You still get the distances relations between each agent pair. Saves some CPU cycles for each distance calculation.
3. GetComponent results should be cached/stored. Avoid using GetComponent in loops, because the lookup does require some effort.
4. Another approach may be to cache all distances so it can be reused in the next FixedUpdate. And then optimize the loops so only enemy agents which are close to the related agent are considered.
5. Unity is trying to call your findTargetToAI 50 times per second. Does it really have to run that frequently? A possibility is to split up the calculations so only portions of the agents are calculated each FixedUpdate. But you won't have realtime data then and have to work with out-dated data.
6. Another possibility is to use Unity C# Job System to do calculations in another thread and optionally in the background. Similar to 5. you may have to work with out-dated data until you have new results. Also Burst compilation is possible to enhance calculation speed.
7. Edit: Inline the distance calculation so it is not a separate method. When method is called very often this can save some overhead.

 

To begin with, you need a different approach.

You are testing all agents against all agents. This means that the amount of work is the number of agents squared: having 2000 agents means doing the inner loop four million times. All that to find the closest agent within 40 units.

Even a brute-force Physics.OverlapSphereNonAlloc() with radius 40 for each agent with properly set layer masks would be faster.

 

Neto_Kokku is right, checking all agents against all agents is not a good idea if you want a lot of agents.

Right now I have 2 different ideas which would help:
- grid
- blobs

The grid idea is to have a grid on your map and to know which agent is in which cell (several agents can be in the same cell).
It means that each time an agent moves you have to check if he has changed cell and update if necessary.
If your cells size is good, for each agent you will check the agents which are in the 9 cells around the cell the agent is in (8 around + the current cell = 9).
That should drastically reduce the number of checks you will do.

The blob idea is probably more complex to implement but may be more interesting depending on the way you agents are dispersed on the map (the more grouped they are, the better the blob idea will work).
You have to find out which agents are near each other, like a squadron of birds, and update these blobs.
How to do that depends on how they move, and may not be easy, but I'm pretty sure that there's some standard algorithms for that.
When you have that, for each agent you check the distance with other agents in the same blob.
And then you check the distance of the other blobs to see if they can be close enough, in which case you check all their agents.
Basically it's the same as the cells in the grid, except that it's not a fixed grid, so you do not have empty cells and you have a lot less cells (except if you have a lot of lone agents, in which case the grid is a much better idea).


And remember to follow the advice of the others, like caching GetComponent results or checking squared distances instead of distances to avoid computing a square root, all these advice are quite good.