Make this algorithm more efficient

Unity Engine
1

Hi there,

I’ve written a small algorithm to get the closest object of a certain type.
My current algorithm is as follows:

        Vector3 pos = this.transform.position;

        float minDistance = 30f;
        float closest = Mathf.Infinity;

        if (pool.explored.Count == 0)
        {
            closest = minDistance;
        }
        else
        {
            var e = pool.explored.GetEnumerator();
            while (e.MoveNext())
            {
                float d = (e.Current.position - pos).sqrMagnitude;
                if (d < closest)
                {
                    closest = d;
                }
            }
        }

Where pool.explored is a HashSet that stores Transforms.

The only issue is, this is an exponential time complexity and makes the game suffer pretty badly.

This code is called every frame, (it sort of needs to be every frame as units have differing speeds, as such, a timer would not work. Unless you can suggest a way this is possible).

Each time that closest is less than minDistance it instantiates a new GameObject which will also be added to pool.explored.

You can probably see how this could get progressively more laggy.

Does anyone have any suggestions as to a potential solution to this?

If any more information is required then do let me know.

Thanks.

2
1 Like
3

Okay, I took some inspiration from this.

I decided to use a collider to check for the nearest ones and loop over those ones instead of every single one on the map.

Thanks for your help.

4

The easiest appraoch would be to call Physics.OverlapSphere to find neighbors within region, and take it from there.

If you really want to do this by hand, you’ll need to code some sort of manual space partitioning scheme. For example OctTree would do.
Objects, whiel moving would need to register their position in the tree, and when you need to find nearest, you first check your current “cell”, if there’s no object of this time, you go “one level up” and try bigger cell, and so on, till you reach top of the world. This is a rough idea that will need some fine tuning, of course.

5

unitys cullinggroup can be also used to collect nearby objects, example here: