Search Unity

Get n nearest objects without using colliders.

Discussion in 'Scripting' started by Dextozz, May 23, 2019.

  1. Dextozz

    Dextozz

    Joined:
    Apr 8, 2018
    Posts:
    112
    I have a few hundred game objects in the scene and I need to get n closes objects to my source. I am not using colliders so Vector3.Distance() is all that comes to mind. I've thought about creating an array/list of items and then sorting it but that would be inefficient because this operation needs to repeat every 0.5 seconds (or something similarly short so that the user doesn't notice any delay).
     
  2. sylon

    sylon

    Joined:
    Mar 5, 2017
    Posts:
    242
    Dextozz likes this.
  3. Dextozz

    Dextozz

    Joined:
    Apr 8, 2018
    Posts:
    112
    Thanks, @sylon , I'll look into that. By a weird stroke of luck, this showed up:
    Code (CSharp):
    1. using System.Linq;
    2.  
    3.  
    4.  
    5. //get 3 closest characters (to referencePos)
    6.  
    7. var nClosest = myTransforms.OrderBy(t=>(t.position - referencePos).sqrMagnitude)
    8.  
    9.                            .Take(3)   //or use .FirstOrDefault();  if you need just one
    10.  
    11.                            .ToArray();
    Thanks to this thread: https://forum.unity.com/threads/clean-est-way-to-find-nearest-object-of-many-c.44315/

    I'll reply back if this actually solves anything.
     
  4. Boz0r

    Boz0r

    Joined:
    Feb 27, 2014
    Posts:
    342
    If you're going the Vector3.Distance() route, use Vector3.sqrMagnitude() instead. The square root of Distance is very expensive.

    EDIT: Beaten by this much.
     
    SparrowsNest and Dextozz like this.
  5. sylon

    sylon

    Joined:
    Mar 5, 2017
    Posts:
    242
    Yes, you'll need something like that as well.
    This will however loop through all your transforms.
    The CullingGroup API can help you do a quick filter and make the list smaller.
     
  6. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,385
    Did you actually tried sphere cast?
    Did you profiled it, to validate your concerns?

    Other alternative, is to create own spatial mapping. Some of them are quadtree and octtree. Then you can test for nearest objects in a tree.
     
  7. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,148
    To simplify things you may keeping Dictionary<Vector3, GameObject> map; In this map store your objects with rounded coordinates. For example,rounded to 10. When you need to find objects closer than 20 meters, you need to round your coorditanes and check distance with only few neighbor boxes.
    You may have multiple nested such indexes when you have really huge amount of objects.
     
  8. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,385
    You would need iterate somewhere through every object, to put into such dictionary.
    And remember to remove from previous key.
    And what if you want search nearest objects, of next 1000 objects.
    Meaning storing 1000 such dictionaries :)
     
  9. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,148
    No, I don't need to iterate through all objects. Moving objects may register their changes themselves atm they change coordinates. Remove/Add, yes. If finding appopriate bucket in dictionary will ever become performance problem, you may switch your storage to 3d array.

    What? No, you never need multiple dictionaries. You probably misunderstood the concept. You need only 1 for 1 scene. Core idea behind this is to split 3d space to cubes containg multiple objects. Say you have level 1000x1000x10 meters with 1 000 000 objects. If they're distrubuted equally, then you may split your scene into 100x100x1 cubes and there will be about 1 000 000 / (100 * 100) = 100 object inside each cube. Now, if you searching object in relatively small radius, you don't need to check distance between you and 999 999 other objects, only few hundreds in your and adjanced cubes, depending on search radius.
     
  10. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,385
    @palex-nx ah ok, I see what you meant now.
    3D array is optional however, while 1D array is more than enough, for such case. Just need index offset.
     
  11. Boz0r

    Boz0r

    Joined:
    Feb 27, 2014
    Posts:
    342
    Dextozz likes this.
  12. Dextozz

    Dextozz

    Joined:
    Apr 8, 2018
    Posts:
    112
    Culling group API (as suggested by @sylon) managed to give me a list of objects I need. Vector3.sqrMagnitude() (as suggested by @Boz0r) was fine, but it was being called way to often in my project, so it needed replacement. Thanks for the help and here's the link to a script that helped with culling groups a lot. (Since documentation is useless as it contains almost no info).

    http://tsubakit1.hateblo.jp/entry/2016/01/07/233000
    (just auto-translate it with google)
     
  13. xVergilx

    xVergilx

    Joined:
    Dec 22, 2014
    Posts:
    1,899
    Its funny how you're suggesting optimizations while dude does delegate allocation + ToArray() allocation.

    sqrMagnitude is a good advice though.

    Extra: Avoid linq if you do not know what does alloc and what doesn't.
    Otherwise you'll end up scratching your head in a question why does your game stutters like hell.