Get n nearest objects without using colliders.

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).

 

You could use the CullingGroup API as a base for creating your list.
https://docs.unity3d.com/Manual/CullingGroupAPI.html

 

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.​

 

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.

 

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.

 

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.

 

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.

 

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

 

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.

 

@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.

 

If you want to learn more about that sort of thing, search for Space Partitioning/Subdivision. It's really neat.

https://slideplayer.com/slide/9290852/

 

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)

 

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.