Hi, I’m wondering if anyone who has experience with a large number of actors in a scene has any suggestions on a fast and efficient target selection system.
The best I have been able to come up with looks something like this:
targetList = GameObject.FindGameObjectsWithTag(targetTag);
if (targetList.Length > 0)
{
foreach (GameObject targetTemp in targetList)
{
if (!target)
{
target = targetTemp;
}
else
{
if (Vector3.Distance(target.transform.position, transform.position) > Vector3.Distance(targetTemp.transform.position, transform.position))
{
target = targetTemp;
}
}
}
But that implementation runs into major framerate issues when there are a large number of actors in the scene. And yes, I have the targeting set up in a coroutine that waits between a half a second and three seconds per update, depending on the unit.
For clarification a large number of actors would be 26 moving entities and 21 static turrets, all using the same targeting procedure (although the moving entities are governed by implementing AngryAnt’s Behave.)
I would like to be able to have up to 75-100 actors on the screen at any given time (I know thats a hefty goal when I’m focusing on android and IOS…), I’m planning on grouping the moving actors into groups of 4-10 and having them share a target assignment controller, but I don’t feel that would be an appropriate solution when dealing with turrets(as some of the turrets are on a moving actor, to allow it to fire on multiple enemies at once, if they are chained to the same target assignment controller, it would seem that they would lose their effectiveness as they would target the same enemy at all times.
I know that was long-winded, but I would appreciate any thoughts on how to improve this.
Thanks
There a plenty of simple algorithmic optimizations you can apply.
This line is what’s hurting you:
if (Vector3.Distance(target.transform.position, transform.position) > Vector3.Distance(targetTemp.transform.position, transform.position))
Firstly “target.transform.position” has already been calculated so you don’t need to calculate it a second time, you should just store it the first time:
distanceTemp = Vector3.Distance(targetTemp.transform.position, transform.position);
if (distance > distanceTemp)
{
target = targetTemp;
distance = distanceTemp;
}
This has not only halved the number of calculations it has also made the code easier to read 
Secondly you can compare distance squared and save yourself from doing a square root.
Note: if a < b then (a*a) < (b*b)
distanceSqrdTemp = (targetTemp.transform.position - transform.position).sqrMagnitude;
if (distanceSqrd > distanceSqrdTemp)
{
target = targetTemp;
distanceSqrd = distanceSqrdTemp;
}
This should be noticably faster and do exactly the same thing. The primary thing to consider with this kind of algorithm is that it is NxN (foreach AI and foreach possible target). This is known as O(N^2) using O notation, ‘order n squared’
These kinds of operations can become very expensive very quickly if one of the dimensions of N becomes large, in other words lots of AIs or lots of targets.
Something to consider when calling a function like this is how often does the AI need to look for targets. It probably works if it’s every frame but you could probably get away with doing it less frequently. For example if you only call this function one in every 5 frames, it will only cost you 20% of the CPU hit and the difference for the player is probably not noticable. This is known as time slicing, ideally you would process 20% of the AIs per frame. That way it is smoothed out and you don’t get frame drops.
My first thought is to just put a SphereCollider trigger around each turret and sort through the objects that enter the collider. But if you get a lot of objects on one turret, then instead of just searching like you’re currently doing you could do something a little more sophisticated. You only need the closest object, and the objects are probably moving in a fairly coherent fashion. The simplest thing that comes to mind is a priority queue. Since everything is moving, you need a way to update the priorities with low cost. You can use a diminishing series of ranges from the turret and only update the distance when the moving entity crosses the threshold from one range to the next. A heap implemented using an Array or List is best. You should be able to find one on the internet. You need one priority queue per turret.
But if you have lots of turrets, then all those priority queues can get expensive. The problem you’re describing is called “all nearest neighbors” and is most efficiently solved using a spatial data structure such as a k-d tree. k-d trees aren’t easy to update dynamically, but with everything moving you could just rebuild it every frame.
Be sure to benchmark as you go because it is easy for this stuff to go awry. Data structures is an area where it can be useful to take off your OOP hat.