Search Unity

  1. Unity 6 Preview is now available. To find out what's new, have a look at our Unity 6 Preview blog post.
    Dismiss Notice
  2. Unity is excited to announce that we will be collaborating with TheXPlace for a summer game jam from June 13 - June 19. Learn more.
    Dismiss Notice

OverlapSphere efficiency?

Discussion in 'Editor & General Support' started by Marble, Oct 23, 2007.

  1. Marble

    Marble

    Joined:
    Aug 29, 2005
    Posts:
    1,271
    I am making an AI that needs to know about nearby objects. I would like to avoid using a trigger because it will become part of a compound collider if I add it to my NPC's hierarchy. Could OverlapSphere could realistically be used every frame (or a few times per second) on 10 or 15 different AI objects?

    Maybe there's a better way?

    Thanks.
     
  2. jeremyace

    jeremyace

    Joined:
    Oct 12, 2005
    Posts:
    1,661
    This would be interesting to know.

    AFAIK, Overlap Sphere actually is a basic distance check loop against all registered RBs. That would mean it's speed would be cut the more RBs you have in the scene, unless they are partitioned or something like that.

    Would be good to know for sure.

    -Jeremy
     
  3. jeremyace

    jeremyace

    Joined:
    Oct 12, 2005
    Posts:
    1,661
    Also, for your AI, I'd just recommend maintaining a list of all _AI_ objects in the scene/area, and doing a distance check against all of those. No matter what, it would prob end up faster than using OverlapSphere.

    -Jeremy
     
  4. Marble

    Marble

    Joined:
    Aug 29, 2005
    Posts:
    1,271
    Yeah, that's the way it works right now, but I recently added an asteroid belt into my scene (this is a space game), meaning that if I want the AI to avoid or shoot at asteroids I'll have to get distances to each of them. Since there are over a hundred of them in the scene, this seemed impractical.

    If OverlapSphere is just a check against rigidbodies, though, it would be just as bad.
     
  5. thylaxene

    thylaxene

    Joined:
    Oct 10, 2005
    Posts:
    716
    not sure if this is helpful. but I have found that Tags used in conjunction with FindGameObjectsWithTag to be a godsend when programming AIs in Unity. Basically returns an array that you can then step through using a for loop looking for information that you need, classes, etc. This approach works very well for waypointing, comparing distances, picking targets etc.

    sorry if I just explained how to suck eggs then. :wink:

    Cheers.
     
  6. Marble

    Marble

    Joined:
    Aug 29, 2005
    Posts:
    1,271
    Ha, no problem. Believe it or not, I didn't know much about sucking eggs before now. :)

    As for efficiency, it would be nice if I could just use a trigger and somehow exempt it from the compound collider. I'm thinking for now I will use an unparented trigger for feeding the AI info and update its position manually. It will look ugly in the hierarchy, but will be far better than measuring tons of distances.

    I'd love to hear of a better idea, though. :D
     
  7. Bampf

    Bampf

    Joined:
    Oct 21, 2005
    Posts:
    369
    Mathematically, finding the nearest of a few hundred spheres really shouldn't take long at all. Not sure what kind of overhead Unity will put on that, but I suspect you won't even notice the operation. Not saying you should do it every frame. Happily, there's no reason the AI can't concentrate on one target for a while before finding a new one.

    I would try it with a simple brute force search, no optimization. If it's slow, then rewrite it.

    Do the asteroids move? If not, you could set up some arrays that point to the asteroids within a particular (small) area. The AI would only have to look at the asteroids near the ship. You might get some uncertain AI behavior right at the boundaries between the areas; this is solvable by using overlapping areas or by having the AI check adjacent areas too, but it's likely that noone will even notice.
     
  8. tz

    tz

    Joined:
    Oct 13, 2007
    Posts:
    91
    Does Unity not support an octree for this sort of thing? Typically in game engines, an object with a collision bound will register itself with the appropriate level of the octree nodes it intersects with at the end of its update... this allows your checking object to simply look at all the hierarchical nodes it participates in and reduces the number of specific collision tests only to members of those nodes.

    Pretty sure the overlap tracker in the engine I use at work already uses this optimization as a general feature, and wouldn't be surprised if Unity does as well.

    P.S. If it becomes a problem, and this optimization is not native to Unity, you might find that partitioning the world into octants and storing a structure of these partitions, and then having your asteroids simply put a pointer to themselves inside the smallest octant their collision bound fits entirely inside might prove to help a lot.

    Since your octants will be axis aligned in the world, and you're simply sphere testing, the intersection check is very fast.

    Tz
     
  9. Daniel_Brauer

    Daniel_Brauer

    Unity Technologies

    Joined:
    Aug 11, 2006
    Posts:
    3,355
    1. Don't optimize code that isn't slow.
    2. Code you haven't written can't be slow.
    3. How you check occlusion/distances is probably not a big part of your AI.

    -> Write the AI first, and then if it is slow, optimize it.
     
  10. Talzor

    Talzor

    Joined:
    May 30, 2006
    Posts:
    197
    1. Listen to Muriac

    2. Use Physics.Overlap (P.O). We used P.O sphere for obstacle avoidance in GC:p (~20-30 checks against ~60-80 colliders each frame), as well as in our current productions.
    P.O is quite fast since PhysX already does an extremly efficient partitioning (or something...) of the scene.

    (Note that P.O checks against colliders, not RigidBodies.)
     
  11. Marble

    Marble

    Joined:
    Aug 29, 2005
    Posts:
    1,271
    K, thanks for the help fellas.
     
  12. tz

    tz

    Joined:
    Oct 13, 2007
    Posts:
    91
    I'm actually doing this in a prototype I'm trying as a way to demo Unity, and in case you missed it, the OverlapSphere() function within the physics class accepts a layer mask. In case there are other colliders in the scene you want to filter out, you may want to consider this as a further optimization.

    In my case, I'm not actually physically bumping into the colliders, so I may be able to leverage some frame coherency by splitting my colliders into several layers, and only checking each layer once ever few frames each to balance the workload.

    (as was mentioned, don't waste time optimizing things that don't need it, but in my case, I'm pretty certain I'm going to need it)

    Good luck!

    Tz
     
  13. s-m-k

    s-m-k

    Joined:
    Oct 26, 2013
    Posts:
    16
    It certainly can unless it means "code that I haven't written yet".
     
    Last edited: Dec 3, 2015
  14. pointcache

    pointcache

    Joined:
    Sep 22, 2012
    Posts:
    579
    5k objects doing V3.distance = 7ms
    5k objects found by overlap sphere each frame = 1.31 ms
    so if you dont need to know the distance but need to know if the object is IN RANGE use overlap.
    Distance checks are costly, directly computing distance should be used very sparsely and substituted
    in most cases with clever tricks.

    The bad side of overlap is that it returns an array, which generates tons of garbage, so also careful with that.