How does the function: physics.overlapsphere work “behind the scenes” so-to-speak?
I’d like to modify it slightly if I could. What I want is for it to work exactly how it does now, but instead of putting every single collider touching or inside the sphere into an array, I’d like it to only put three or four colliders into the array maximum. So essentially I’d simply like to limit how large the array is when it’s built. Is there a way to do this?
I’ve read the script reference a lot, and I know it says it checks against the bounding volumes of the colliders. Does this mean it uses bounding volume functions such as Bounds.Contains(), or others?
You can just ignore any entries in the array past the fourth, or go through the array and build a new one based on whatever criteria you come up with for excluding objects.
Thanks for the reply. The problem is the collection of the entries themselves and the performance (cpu-wise) hit that it causes, so just using the first four entries (for example), is not what I’m after. In addition, building a new one after the first would simply compound the problem. My problem is one of performance with multiple agents using this function in real-time.
The function is excellent for my purposes, but the fact that it collects every single collider in the radius causes my game a massive performance hit while it’s doing this function, even if I stagger the time at which every agent builds the array.
So, my problem is simply performance related. I really need to limit the size of the array that is built the first time.
The use is for enemy unit detection in an rts-style game. Every .8-1.2 seconds, I physics.overlapsphere to build an array of possible enemies, then iterate over that array to find the closest enemy. It usually works pretty well up to about 75 v 75 units. Over this, and the fps drop is noticeable.
I’ve tried detection using triggers, and it usually performs about the same, if not worse. Especially since I need to detect enemies that “stay” within the trigger, and using OnTriggerStay is even more performance heavy than my current implementation. It’s been a few months since I played around with using a “trigger” solution though so I don’t remember exactly why I didn’t like it, but I remember it not performing as well as my current solution.
Put everything into layers, then overlapsphere on the particular layers you care about.
Im not sure on the inner workings of overlapsphere, but you might squeeze more performance out of using a single list that contains all units then just looping through that list when you need a target using vector3.distance to determine if its a valid target
its how I do it.
I noticed there was a bit of a performance hit (small, but still there) in my original method that would create a new list for the results to pass back to the caller. By just passing back the entire list, I am doing the same thing without any new allocations
Those are very good suggestions thank you, but unfortunately I’ve tried them as well. Although I must say, it’s been awhile since I’ve tried all these methods (i’ve been working on a better detection system off and on for the last 7 months honestly lol).
I am currently doing this.
I may have to revisit this/try it again. But I did try keeping a large array “master list” before, but it seemed like the overhead on having 300 units iterate through a 300 unit array every x amount of seconds was very taxing as well. Every unit has to constantly check it’s distance versus every single unit in the game.
Maybe I am missing something with this method though? Are you suggesting what I stated above, in that every unit checks it’s distance vs. every unit in the “master” array?
There’s also a distinct possibility that I’m just not implementing some of these methods correctly, but I have tried them. It’s getting too late now for me to think properly though, so I will come back to this tomorrow. I appreciate all of the suggestions
Then don’t use a ‘master array’, but sort every object’s position into a spacial collection - I quite like the spacial hash for simplicity but you also have quad/oct trees etc. Cost here is updating the position of each unit, but querying is much faster.
How so?
300*300 = 90,000
Say 10 cycles per check.
90,000 *10c = 900kc
Now you’re running this how often… every second? And your CPU is say 2ghz?
900kc/2000000kc = 0.045%
That’s a lot of computation time… less than half of a tenth of a percent!
Should you ever decide to add more units, you can simply make it a Coroutine [spread the calculation over several frames], multithread it [using unused cores] and use smarter collections [see earlier].
Indeed. This may in fact be the key to getting the performance I am after. I have looked at R-trees and Quad/Oct trees before as well. They look like they could solve my problem. I just need to learn how to program them. I spent a couple days trying to find articles/examples in order to learn how to do them (I currenlty use Unityscript), but was not able to even start a rudimentary quad-tree. I really want a teacher on this
So, it could be as simple as I need to learn more.
Only thing I can think of that might be a dead end is the fact that if I have lots of units in a very small space, the amount of overhead on dividing up my game-world into that amount of spacial partitions may be in vain.
I wouldn’t expect the performance of a list-based approach being as bad as you’re experiencing. Did you have the transforms pre-cached, or were you finding them each frame? (Calling .transform on an object does not get a direct reference, it actually does a GetComponent.) Were you testing against distance or square magnitude? (The latter is faster as it replaces costly square root calculations with a relatively cheap multiply.) Were you having units check only against relevant other units, ie: ones on the other team? Also, since you want to test every second or there abouts, are you testing the whole list at the same time or staggering it throughout a whole second?
Also… do you have rigidbodies on all of your moving colliders - even if they’re triggers? The physics system is optimised based on the assumption that static (non-rigidbody) colliders don’t move often, so if you’re moving a bunch of them you’re kind of rubbing it’s fur the wrong way, so to speak.
That said, the basic advice is good. Sticking with the basic array approach, I’d be doing something along the lines of:
var fasterCollection = new SortedList<Vector3, GameObject>();
foreach (var go in gameObjects)
fasterCollection.Add(go.transform.position, go);
/*Now iterate over fasterCollection.*/
I stand corrected, though either way it’s trashing the managed cache.
I’m not sure I understand the context in which you’re suggesting that code snippet be used, though. If I were to take the flat array approach I’d make it as flat as I possibly could.
Basically you need to get the position of every game object once, then do the 90k iterations. I’d go and optimise that further [get rid off the sorted list and simply use an array of a struct, or have two arrays one of V3 and one of GameObject where the index corresponds], but this going to be easier for OP to understand and use.
However, since you brought it up
//option 2
var positions = gos.Select(go => go.transform.position).ToArray(); //Linq
var sqrMaxDist = dist*dist;
for (var goIndex = 0; goIndex < gos.length; goIndex++)
{
var position = positions[goIndex];
for (var posIndex = 0; posIndex < positions.length; posIndex++)
if((position - positions[posIndex]).sqrMagnitude < sqrMaxDistance)
/*Handle Collision between gos[posIndex] and gos[goIndex]*/;
}
This is by no means complete - it’s just a starting point.
For anyone reading and wondering why we do this, instead of just using go.transform.position? The reason is twofold:
Getting go.transform is expensive, and getting transform.position may also be expensive - though I’ve not benchmarked that. This is very important because we’ll be doing a lot of comparisons.
By ‘caching’ the positions in an array, they’ll be in a nice small contiguous array that can fit nicely into CPU caches. Otherwise we’d be accessing data stored all over memory, making hardware caching much harder.
These are relatively simple optimisations to make, that are useful in delaying the need for more complicated systems - e.g. a QuadTree.
