Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Efficient way to scan surrounding with OverlapSphere with large number of objects

Discussion in 'Physics' started by jiri-vyc, Oct 13, 2021.

  1. jiri-vyc

    jiri-vyc

    Joined:
    Feb 18, 2014
    Posts:
    6
    Hello,

    I am working on a personal ant colony simulation project and I am struggling with performance.

    I have a bunch of agents (ants) in the scene and I need each of them individually to scan their surrounding in some area. For now I am using Physics.OverlapSphere to get the objects around them. The problem is I need to get the type of the object there is and perform some action based on the type and their count.

    For that I haven't found another way than to call .GetComponent() on the Collider. As you may already guess, this is really inefficient, since I'm calling this in every Update of each Ant and the possible Collider objects are all other ants in the scene, as well as different pheromones dropped on the ground (which there are order of magnitude more of than ants), so there are thousands of interactions and GetComponent calls each frame.

    I have tried moving the "Scan" out from Update into a Coroutine which is triggered on random intervals instead of every Update, which helped, but not a lot.

    I have also improved the performance a bit by using LayerMasks for the OverlapSphere, but it's again negligible.

    I'm aiming to have thousands of ants in the scene, and the framerate drops to unacceptable levels even with 100+ now. The scene is pretty much empty otherwise.

    I have also considered moving to Dots/ECS, but I found out that the Physics can be triggered from the main thread only anyway, so I'm not sure that would be of much help. Is this correct assumption?

    Any suggestions? Even outside of the box ones are welcome. I am even failing to grasp how Unity handles 1000+ (MonoBehaviour) agents in the scene in general.

    Another thing I considered is to move all the "non-ant" object to a "virtual" plane (some structure like 2D array) and do the scanning by coordinates there by hand with some hand-made algorithm (like quad-tree) but it seems like a lot of work for questionable results (doubtful I could make it more efficient than Unity's built-in Physics library functions).

    PS: I am sure the culprit of the performance is where I say, see the profiler snippet:

    (EditorLoop is 32%+, 10% is Camera.Render)

    PPS: I tried at answers, but got no response
     
  2. Peeling

    Peeling

    Joined:
    Nov 10, 2013
    Posts:
    442
    You're thinking along the right lines by moving to a custom data structure. Having written something similar myself in the past, here's what I would do:

    1, Create a dedicated internally-linked Presence class

    Less scary than it sounds. It looks like this:

    Code (CSharp):
    1. public class Presence
    2. {
    3.  
    4.     // Back-references to useful components for quick access
    5.     public GameObject obj;
    6.     public Ant ant;
    7.     public Pheromone pheromone;
    8.  
    9.     // Internal ring links.
    10.     public Presence next;
    11.     public Presence prev;
    12.  
    13.     public Presence()
    14.     {
    15.         // Give ourselves a hug!
    16.         next = this;
    17.         prev = this;
    18.  
    19.         // Note: prev and next are ALWAYS valid, never null.
    20.         // That saves a whole lot of null checks!
    21.         // Manipulating rings is branchless, unlike linked lists.
    22.     }
    23.  
    24.     public void Disconnect()
    25.     {
    26.         next.prev = prev;
    27.         prev.next = next;
    28.         next = this;
    29.         prev = this;
    30.     }
    31.  
    32.     public void InsertAfter(Presence other)
    33.     {
    34.         // Disconnect from where we are...
    35.         next.prev = prev;
    36.         prev.next = next;
    37.         // ...and insert in our new location
    38.         next = other.next;
    39.         prev = other;
    40.         next.prev = this;
    41.         prev.next = this;
    42.     }
    43.  
    44. }
    This Presence class serves as a handy reference for all the different types of component there might be on an object in your game world. If you like, you can add a 'type' enum for quick identification and filtering.

    Why is the class internally linked? Because it makes updating a world map a breeze:

    2. Create a PresenceMap singleton

    This is also pretty straightforward:

    Code (CSharp):
    1.  
    2. public class PresenceMap : MonoBehaviour
    3. {
    4.     public static PresenceMap inst;
    5.  
    6.     public Vector2 minBound;
    7.     public Vector2 maxBound;
    8.     public float resolution;  // Set this to the range at which you're interested in sensing objects.
    9.  
    10.     Presence[,] map;
    11.  
    12.     int maxCellX;
    13.     int maxCellY;
    14.  
    15.     List<Presence> neighbours = new List<Presence>();
    16.  
    17.     private void Awake()
    18.     {
    19.         inst = this;
    20.  
    21.         int dimx = (int)((maxBound.x - minBound.x) / resolution);
    22.         int dimy = (int)((maxBound.y - minBound.y) / resolution);
    23.         map = new Presence[dimx, dimy];
    24.         maxCellX = dimx - 1;
    25.         maxCellY = dimy - 1;
    26.  
    27.         // Seed the array with blank roots to make relocation of presences easy.
    28.         for (int x = 0; x < dimx; ++x)
    29.         {
    30.             for (int y = 0; y < dimy; ++y)
    31.             {
    32.                 map[x, y] = new Presence();
    33.             }
    34.         }
    35.     }
    36.  
    37.     //Call when you create or move a presence to keep its location up to date.
    38.     // Note: There's no need to inform the PresenceMap when you remove or destroy
    39.     // a Presence. Just call Disconnect on the Presence.
    40.     public void UpdatePresence(Presence p)
    41.     {
    42.         Vector2 presencePos = p.trans.position;
    43.         Vector2 mapPos = (presencePos - minBound) / resolution;
    44.  
    45.         int cellX = Mathf.Clamp((int)mapPos.x, 0, maxCellX);
    46.         int cellY = Mathf.Clamp((int)mapPos.y, 0, maxCellY);
    47.  
    48.         p.InsertAfter(map[cellX, cellY]);
    49.     }
    50.  
    51.     //Build a list of neighbours based on the nearest four cells
    52.     //NOTE: Re-uses a single list to avoid garbage. DO NOT RETAIN RESULT!
    53.     public List<Presence> GetNeighbours(Presence p)
    54.     {
    55.         neighbours.Clear();
    56.  
    57.         // Assumes the x/y plane is the relevant one; adapt accordingly.
    58.         Vector2 presencePos = p.trans.position;
    59.         Vector2 mapPos = (presencePos - minBound) / resolution;
    60.  
    61.         int cellX = Mathf.Clamp((int)(mapPos.x + 0.5f), 1, maxCellX);
    62.         int cellY = Mathf.Clamp((int)(mapPos.y + 0.5f), 1, maxCellY);
    63.  
    64.         AddNeighbours(map[cellX - 1, cellY - 1]);
    65.         AddNeighbours(map[cellX, cellY - 1]);
    66.         AddNeighbours(map[cellX - 1, cellY]);
    67.         AddNeighbours(map[cellX, cellY]);
    68.  
    69.         return neighbours;
    70.     }
    71.  
    72.     void AddNeighbours(Presence root)
    73.     {
    74.         Presence iter = root.next;
    75.         while (iter != root)
    76.         {
    77.             neighbours.Add(iter);
    78.             iter = iter.next;
    79.         }
    80.     }
    81. }
    3. Profit!

    Anything you want to have a presence in the game, give it a Presence!

    Hook up the trans/Ant/Pheromone back-references as appropriate.

    Call PresenceMap.inst.UpdatePresence(myPresence) when you add or move the presence (so for static stuff you can just add it once and leave it).

    Call myPresence.Disconnect() to remove it from the map (eg when the object it wraps is destroyed)

    To check your surroundings, just call GetNeighbours and do a quick square-distance check on each if you want more accuracy (or add a variation of GetNeighbours that takes a range and does that for you during AddNeighbour)

    If you need to gather neighbours in a radius bigger than the resolution of the map, it's not hard to add a version of GetNeighbours that takes a range and gathers from a square of cells around the specified Presence.

    Once you have your neighbours, you can either use a type enum or check which of the back-references (to Ant or Pheromone) are non-null, and off you go. No GetComponent, no physics overlap, no garbage generated.

    You can make Presence a monobehaviour in its own right, but that means spawning the big 2D array of roots actually in the scene. On the positive side, it gives you something you can inspect at runtime, and you can always tuck the root array away under a deactivated gameobject so that Unity doesn't process them. It's up to you. If you don't make Presence a monobehaviour, your Ant and Pheromone classes can just create and hold onto one themselves, and you'll save some processing time on the static ones.

    If you give Presence its own Vector2 position, you can remove its dependence on Transform and allow non-monobehaviour classes to be present in the map too. Whether that's useful is up to you.

    You should find this makes a pretty big difference to the speed of your interaction-checking. You can probably remove colliders/triggers entirely from stuff like pheromones. While Unity's physics are indeed very fast and efficient, manual overlap checks almost certainly bypass important optimisations, especially those that rely on frame-to-frame coherency. A bucketing system like this one, tailored to the range of influence that you need and involving no garbage collection, no scene-gathering, no interrogation of collider properties - it's going to be at least two, more likely three orders of magnitude quicker, and that's without considering the saving from GetComponent.

    If different objects have greatly different radii of influence:

    Consider supporting multiple layers of map within the PresenceManager, each with a different resolution, and having UpdatePresence() take a parameter to indicate which layer the presence should be pushed into. Then GetNeighbours can work through each layer internally to return an overall list of neighbours. Layers with a smaller resolution will return neighbours from a smaller area, and layers with a larger resolution from a larger area, so you don't end up pulling in lots and lots of unwanted short-range results just because you need to check for longer-range ones.

    Good luck!

    NB: These classes ought to compile as-is (bar the Ant and Pheromone stuff) but I wrote them from scratch for this post so they might be (dons sunglasses) buggy.
     
    Last edited: Oct 14, 2021
    jiri-vyc likes this.
  3. jiri-vyc

    jiri-vyc

    Joined:
    Feb 18, 2014
    Posts:
    6
    Thanks a lot @Peeling !

    That's certainly quite some reading, but I will give it a try and get back to you. Much appreciated.

    Sticking with Physics and overlaps would be much simpler, but for such use case I more and more realize it's probably just unsuitable and something like you suggested is needed.
     
  4. Peeling

    Peeling

    Joined:
    Nov 10, 2013
    Posts:
    442
    It's not really much more work. Drop those two scripts into your project and:
    1. Add the PresenceMap script to an object in your scene and set up the bounds and resolution. For instance, if your ants need to detect other ants and pheromones within 1m, set the resolution to 1.
    2. Replace the 'Ant' and 'Pheromone' fields with whatever you want to be able to access when you scan the local area
    3. In your Ant and Pheremone monobehaviours, add a Presence field and 'new' it on Start(), filling in the trans/Ant/Pheromone/whatever field to point back at 'this'
    4. I'm guessing Pheromones don't move around, so just call PresenceMap.inst.UpdatePresence(myPresence) in Start() as well.
    5. In your Ant update, call PresenceMap.inst.UpdatePresence(myPresence)
    6. When you want to scan the area around your ant, call PresenceMap.inst.GetNeighbours(myPresence) and iterate through the list you get back, just the way you're iterating over the colliders you get back from an overlap check. (Incidentally, GetNeighbours doesn't filter out the Presence that made the request, so watch out for that)
    Example:

    Code (CSharp):
    1. class Ant : MonoBehaviour
    2. {
    3.  
    4.     Presence myPresence;
    5.  
    6.     private void Start()
    7.     {
    8.         myPresence = new Presence();
    9.         myPresence.ant = this;
    10.     }
    11.  
    12.     private void Update()
    13.     {
    14.         PresenceMap.inst.UpdatePresence(myPresence);
    15.  
    16.         List<Presence> nearby = PresenceMap.inst.GetNeighbours(myPresence);
    17.         foreach (Presence p in nearby)
    18.         {
    19.             if (p.ant != null)
    20.             {
    21.                 //it's an ant!
    22.             }
    23.             if (p.pheromone != null)
    24.             {
    25.                 //it's a pheromone!
    26.             }
    27.         }
    28.     }
    29.  
    30. }
    31.  
    32.  
    33. public class Pheromone : MonoBehaviour
    34. {
    35.  
    36.     Presence myPresence;
    37.  
    38.     private void Start()
    39.     {
    40.         myPresence = new Presence();
    41.         myPresence.pheromone = this;
    42.         PresenceMap.inst.UpdatePresence(myPresence);
    43.     }
    44.  
    45. }
    46.  
    At that point, you're more or less where you are now, except that you've got direct access to the pheromones or ants you've scanned for without using GetComponent and only 1/1000th of the time has gone by :)
     
    Last edited: Oct 14, 2021
    jiri-vyc likes this.
  5. Peeling

    Peeling

    Joined:
    Nov 10, 2013
    Posts:
    442
    Was intrigued to know just how much difference this might make, so I incorporated these scripts into a little testbed of 1000 randomly distributed ants and 10000 randomly distributed pheromones.

    First, I just ran the scene with nothing in the ant Update function (bar setting a value to zero to ensure an update would actually occur, to get a baseline for script timing

    That baseline turned out to be 0.25ms for scripts and 0.0ms for physics.

    Next, I added in Physics.OverlapCollider calls. That raised the script time to 1.86ms and the physics time to 3.52ms, so gathering nearby colliders takes an (impressively low!) 5.13ms

    Since Unity also offers a non-allocating version of Physics.OverlapCollider, I switched to that. Oddly, that turned out to be consistently slower, with a similar physics time of 3.5-3.6ms but a script time of 2.2ms. However, it did all but eliminate garbage generation.

    Before doing anything with the results of gathering nearby colliders, I implemented the Presence scripts and ran an identical test. Physics time dropped to 0ms and script time was around 2.1ms. In other words, performing the entire gathering operation via Presence was faster than the non-physics part of calling Physics.OverlapCollider.

    To summarise so far:

    Physics.OverlapCollider: 5.13ms
    Physics.OverlapColliderNonAlloc: 5.7ms (but no garbage)
    Presence : 2.1ms

    Saving 3-3.5ms is not to be sniffed at, but I was super impressed with the efficiency of OverlapCollider in general.

    However, I wasn't yet actually doing anything with the gathered results, so I did some more testing and found where the real bottleneck lies!

    In the Presence version, I had direct access to the Ant and Pheromone components via backreferences from the Presence list. Using that to count how many ants and pheromones were nearby raised the script time to 3.0ms

    Then I went back to the OverlapCollider version and tried using GetComponent to do the same job. The difference was just about noticeable:

    upload_2021-10-15_14-4-46.png

    Using GetComponent raised the script time to 46ms, and generated a ton of garbage too.

    Conclusion...

    Physics.OverlapSphere itself is a perfectly reasonable method of gathering neighbours. Yes, it can be improved upon, but it's impressively efficient (although why the non-allocating version would be slower is a bit of a mystery)

    GetComponent, on the other hand, is a completely unreasonable way of gettng information about a neighbour, taking between eight and twenty times longer than gathering the colliders in the first place. Unfortunately, we're stuck with it...

    ...OR ARE WE???

    You know what's fast? Really fast? A Dictionary.

    As a final test, I created a hybrid system. I gave Presence a static dictionary like this:

    static Dictionary<Collider,Presence> lookUp = new Dictionary<Collider,Presence>()


    Each ant and pheromone, on Start, uses their Collider component to add their Presence to the dictionary.

    Now, instead of using GetComponent on each collider gathered by Physics.OverlapSphere, I can do this:

    Code (CSharp):
    1.  for (int i = 0; i < neighbourCount; ++i)
    2.                 {
    3.                     if (Presence.lookup.TryGetValue(cache[i], out Presence p))
    4.                     {
    5.                         if (p.ant != null) ++nearbyAnts;
    6.                         if (p.pheromone != null) ++nearbyPheromones;
    7.                     }
    8.                 }
    Here's what happened in the profiler:

    upload_2021-10-15_14-28-24.png

    Script time dropped to 5.9ms. Factoring in the physics time, it's still 7ms slower than a full Presence implementation, but having a dictionary of colliders with which to access a Presence and its back-references, rather than using GetComponent, saved 38ms.

    I can't believe I never thought of that before!
     
    jiri-vyc likes this.
  6. jiri-vyc

    jiri-vyc

    Joined:
    Feb 18, 2014
    Posts:
    6
    Thank you for the detailed responses and for the time you put into this! It's incredible.

    Same here! I knew the GetComponent is the worst offender, but the simple idea of getting rid of it and replacing by a Dictionary never occurred to me.

    I tried it (and kept the basic OverlapSphere) and it significantly improved. Still not orders of magnitude though. I am encountering a problem with already +- 300 ants, when they clump up over each other and over the common paths of Pheromones (then each OverlapSphere is hitting 200+ Colliders and even with the fast Dictionary access it's slow).

    I also switched to the non-alloc version of OverlapSphere and it was actually also noticeable difference for the better. I am using an object pool for the Pheromones and capping the OverlapSphere by 100 Colliders (doesn't make sense to precisely get all of them if the area is that saturated anyway).

    I am still hitting the performance ceiling though. Just simple operation on the Pheromone (get its intensity) is more than enough to slow down my program down to 15 FPS when, as I said, they're all clumped up over each other and it gets called 10000+ per (albeit async) update.

    I'm also hitting another problem, and that is reliably measuring the performance. All my Ants move by random (if not following Pheromone trail) and I cannot replicate the exact same conditions/behavior to directly compare results of my changes (even when using seed/Random.initState). The biggest problem is I think the async updates (using Coroutines) together with random decisions I'm using throughout the program.

    I still haven't got around to (and probably still will have to) using your custom Presence approach instead of the OverlapSphere.

    But looking at the real-life results, I think Unity is just simply not suited for these kinds of simulations with its lack of easy async processing.
     
    Last edited: Oct 18, 2021
  7. Peeling

    Peeling

    Joined:
    Nov 10, 2013
    Posts:
    442
    Final thought: you could probably shave off a bit more time by exposing the values you most often interrogate in the Presence class itself rather than via a back-reference, since that data will already be in the processor's cache after assembling the list of Presences in the first place.
     
  8. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,333
    Saying the game engine isn't suitable is wrong TBH. Stuff like this is possible using C#, Jobs and Burst without any internal changes. It sounds more like trying to brute-force everything single threaded isn't suited to what you're doing.

    Quite simply, a full physics engine isn't always best suited to all tasks. If you're doing large-scale neighbourhood searching (such as things you need when doing large-scale Boids sim) then you might want to consider alternate approaches (similar to what was suggested above) such as integrating you own Spatial Acceleration Structures such as quad-tree, kD-Tree etc. Even keeping them as particles (points) and using simply distance tests would be quicker as compared to using physics to check spheres against all the different types of things in the scene.

    Of course, I do not know what other aspects of 3D physics you actually require and integrated it'd need to be with your neighbourhood searching stuff etc.

    It sounds like you're be better off with DOTS Physics TBH.
     
  9. jiri-vyc

    jiri-vyc

    Joined:
    Feb 18, 2014
    Posts:
    6
    Yes, you're right. I've phrased it wrong and this was more close to what I meant. I should've added "...the way I'm using it".

    I was looking for relatively simple built-in-physics-using solution, since this is just a prototype/playground project (most probably) without any future, and was wondering if it's possible.

    Using custom structure and for example quad-tree search is something I considered, as well as using DOTS, but decided against it at the time. Gonna take a look at the DOTS Physics, that is something I haven't researched before.

    Thanks for the answers!