OnTriggerEnter()/Exit() with list vs. Physics.overlapSphere()

Hello,

I'm toying with a tower defense game concept and am debating between two solutions to a tower knowing what enemies are in range at a given time. Consider a simple projectile tower which shoots every x seconds. After x seconds since last fire, the tower can simply call Physics.OverlapSphere(tower.pos, tower.fireRadius, Enemy.getEnemyLayer()) and choose an appropriate target from the returned list. Another solution would be to use OnTriggerEnter to add the enemy to a List of enemies, and then OnTriggerExit to remove that enemy. I see the following advantages and disadvantages:

Pros/Cons
OnTrigger solution:
(PRO) Tower knows exactly how many enemies are in range at every frame, and never has to "poll" for how many there are since the list is updated as soon as the enemy enters or leaves.

(CON) On the same token, a list takes extra memory for storing references to the enemies in range. Also, removal is an O(n) operation on the size of the list.

OverlapSphere solution:
1. (PRO) Extremely simple to use. Whenever we want to know enemies in range, such as for firing a projectile or doing an area damage, just call this O(#TotalEnemies) function. Don't need an accessory List on each Tower to keep track of enemies, since this function is all that's needed.

(CON) On the down side, this function takes time to call and may need more calls depending on how often the tower needs to know enemies in range (Fast attacking towers). Also perhaps a concern on this method creating garbage?

What do you guys think? Is one particularly worse for performance/garbage creation? Keeping a list takes O(inRange) space and O(inRange) time for removal, and overLapSphere takes O(totalEnemies) time and O(numEnemies) temporary space (In the form of a returned array of colliders). It seems that perhaps the trigger solution is better in terms of complexity (unless all enemies are in range of a tower... numEnemies == numInRange), and also better in garbage creation since we're not discarding overlapSphere's return value every call when we're done with it, but it's a little messier than overlapSphere.

 

Sounds like you understand the basics of this issue:

Triggers

• Can be flakey / unusable depending on how complex your physics are.
• More state to handle, leading to more complex code.

OverlapSphere

• Along with Raycast, are the only two truly reliable pieces of Unity physics.
• Less state, simpler code.
• Causes allocations.

The extra memory used for state in a competent trigger setup is meaningless. Allocations are not.

That said, my code uses OverlapSphere and other allocating physics operations because there's simply no other reliable way. It would be pretty simple for UT to enhance the API so we could avoid those allocations, but... yeah. You can search for the threads talking about that if you're interested.

(In your situation, it sounds like triggers would be a far better choice.)

 

Thanks Smooth P for your reply, I appreciated your advice and experience. I've decided to use Triggers for this particular application based on my points and your points. I wanted to ask, though, what is your reasoning for choosing overlapSphere over Trigger for complex physics? Doesn't overlapSphere only use bounding volumes of colliders as opposed to the collider itself?

 

For moving volumes, I use CharacterController.Move(), which uses AFAIK uses raycasts and overlaps under the hood. This unfortunately allocates on collisions as for some reason ControllerColliderHit is a reference type.

When using OverlapSphere() directly, I generally do a bit of raycasting to improve the accuracy of any hits. I don't use OverlapSphere for every frame stuff as it allocates an empty array even where there aren't hits. Why it doesn't reuse a shared, empty array is a mystery, and people have been asking for an API enhancement that lets you pass in a List<> or whatnot to fill for ages.

I use these things because my game is a networked FPS with rewind/replay physics, and I need immediate collision results as well as the ability to do a variable number of physics steps between Update()s. Also, Unity physics tend to fall apart when things are moving "fast", which people have various workarounds for. But I doubt speed would be an issue for a tower defense game.

 

please support http://feedback.unity3d.com/suggestions/garbage-free-physics

@Smooth P thank you, insightful

 

Looks like they implemented a NonAlloc version recently! http://docs.unity3d.com/ScriptReference/Physics.OverlapSphereNonAlloc.html

 

oooo

https://twitter.com/anthonyyakovlev/status/631858779282350080

looks to be a 5.3+ thing

 

Have tried to use OverlapSphereNonAlloc and find it always returns 0 found ... though it doesn't allocate any memory in the process or I'm just using it wrong ...

 

had same issue as @lodendsg not sure if i'm doing something wrong or if there is an issue. 5.3.1

 

@lodendsg @JBR games I have the same issue. Any news?

 

Are you guys sending in an array that's big enough?

If the Collider-array you're sending in is of size x, OverlapSphereNonAlloc will fill it with up to x colliders, and return a value of up to x. So if you're sending in an array of size 0, you'll never get any results.

The non-alloc part is that it's not allocating a new array, you're giving the array it needs to fill. The array you're supplying won't be resized for you (that would be bad form).

The intended use is something like:

Code (CSharp):

1. public class TestOverlapSphere : MonoBehaviour {
2.  
3.     private Collider[] overlapResults;
4.  
5.     private void Start() {
6.         overlapResults = new Collider[10];
7.     }
8.  
9.     void Update() {
10.         if (Input.GetKeyDown(KeyCode.Space)) {
11.             int numFound = Physics.OverlapSphereNonAlloc(transform.position, 5f, overlapResults);
12.  
13.             for (int i = 0; i < numFound; i++) {
14.                 Debug.Log("Found collider: " + overlapResults[i]);
15.             }
16.         }
17.     }
18. }

Note that the method does not clear the remaining space in the array. This means that if you're using an array of size 10, and find 10 elements on one check and 3 elements on the next check, there will still be 10 colliders after the second check - so the return value is meant to inform you about what elements in the array are from the last check.

 

Its very possible i forgot to set the size...
is going to piss me off if that's the case haha

 

@Baste yes size was the problem, thanks!