Clean(est) way to find nearest object of many (C#)

_Adriaan_1 · March 22, 2010, 8:25pm

Imagine a field with many, many enemies. And you have a key to shoot the nearest target. Well, that is almost my game.

I can think of a couple ways to find out which enemy is the nearest, but I am afraid none of these is going to be able to go through 50+ enemies without decreasing the performance dramatically.

Can anyone with experience with this suggest me a way, please?

First one to hint me receives a cookie!

tomvds · March 22, 2010, 9:59pm

The easiest way first. That is

Transform GetClosestEnemy(Transform[] enemies)
{
    Transform tMin = null;
    float minDist = Mathf.Infinity;
    Vector3 currentPos = transform.position;
    foreach (Transform t in enemies)
    {
        float dist = Vector3.Distance(t.position, currentPos);
        if (dist < minDist)
        {
            tMin = t;
            minDist = dist;
        }
    }
    return tMin;
}

Attach this untested function on a script on your player object. The function should then calculate the closest enemy to the player from an array of all enemies.

It is the most straightforward, unoptimized way of doing it, but I doubt that with numbers within the 100 range, it would have any noticeable overhead.

I don’t think you should complicate matters if this approach works. However, if I’m wrong (oO), there is many ways to improve it later on ;).

_Adriaan_1 · March 23, 2010, 8:57am

Nice!
As promised.

edwardrowe · August 7, 2014, 2:15pm

For anyone who arrives here through a Google search, the presented answer by tomvcds is good, but should definitely be optimized by comparing distance squared instead of straight distance. It adds no complexity to the code and is more efficient, since it avoids the expensive square root operation that happens under the hood by doing “Vector3.Distance”.

For example - Say you have 3 objects, A, B, and C, and a source. You want to know which one is closest to the source. Let’s say A is 2m away, B is 3m away, and C is 4m away. Instead of doing the distance test and getting 2, 3, and 4, you can instead get the value in distance squared, which would be 4, 9, and 16, respectively. Distance squared still maintains their order by proximity, it’s just that the values increase exponentially instead of linearly.

Here is the code:

    Transform GetClosestEnemy (Transform[] enemies)
    {
        Transform bestTarget = null;
        float closestDistanceSqr = Mathf.Infinity;
        Vector3 currentPosition = transform.position;
        foreach(Transform potentialTarget in enemies)
        {
            Vector3 directionToTarget = potentialTarget.position - currentPosition;
            float dSqrToTarget = directionToTarget.sqrMagnitude;
            if(dSqrToTarget < closestDistanceSqr)
            {
                closestDistanceSqr = dSqrToTarget;
                bestTarget = potentialTarget;
            }
        }
     
        return bestTarget;
    }

*Edited to add an example.

Kokumo · August 7, 2014, 2:37pm

In order to improve the code, you could use a Physic.SphereCast -at a set interval- to detect enemies inside of a certain range (or use a SphereCollider); this will give you a shorter list of enemies (and the list will be shorten if you take in a count only a few layer).

edwardrowe is right about using straight distance.

I corrected “SphereCollider” which I mispelled.

Josepht45 · October 30, 2014, 9:10pm

Does anyone know how I could take the bestTarget and make it change position to a gameobject?

HeavyArmor · December 4, 2015, 5:47am

Thank you Kokumo!

Iknow21 · March 3, 2016, 4:56am

hey guys.
I i felt like sharing this code. Its not perfect but I hope it helps somebody.

usingUnityEngine;
usingUnityEditor;
usingSystem.Collections;
usingSystem.Collections.Generic;
usingSystem.Linq;

publicclasscurious : MonoBehaviour {

publicfloatMoveStep = 10.0f;

floatDist = 0.0f;
floatDisT = 0.0f;

boolm_bIsMoving;

Vector3Position;
Vector3dir;
Vector3mVec;

privateVector3velocity = Vector3.zero;

floatfTimer = 2.0f;
floatfrealtime;
floattimeSU;

privatefloatspeed = 1.5f;
GameObjectobject2;
publicGameObjectobject1;

publicList objects1 = newList();

publicfloatforce ;

privateVector3pos;
privatefloatrandom;
floatRad;

intsizeOfList;

publicfloatmin = 0.0F;
publicfloatmax = 0.0F;

voidStart()
{

force = (Dist / Time.deltaTime) * random;
random = Random.Range (min, max);

objects1 = GameObject.FindGameObjectsWithTag (“audio”).ToList();

mVec = this.gameObject.transform.position;
m_bIsMoving = false;

pos = transform.position;
FindTarget();
}

voidOnTriggerExit(ColliderCol)
{
if (Col.gameObject.tag == “Ground_Smoke”) {
objects1 = GameObject.FindGameObjectsWithTag (“audio”).ToList();
inti = 1;
objects1.Sort();
Debug.Log(objects1*);*
m_bIsMoving = false;
}
}
voidOnTriggerEnter(Colliderother)
{
if (other.gameObject.CompareTag(“audio”))
{
sizeOfList = objects1.Count -1;
intrad = Random.Range(0,sizeOfList);
object1 = objects1[rad];
objects1.Remove(other.gameObject);
FindTarget();
}
if (other.gameObject.CompareTag(“Ground_Smoke”)) {
m_bIsMoving = true;
}
}
voidUpdate()
{
intrads = Random.Range(1,objects1.Count);
intt = objects1.Count - rads ;
object2= objects1[t];
print(object2);
floatangle = 0.0F;
floatvel = 1;
floattimeSpent = 1;
Rad = Random.Range (1F,2F);
timeSU = Time.fixedTime * Rad;
floatfollowDistance = 1.0F;
mVec = this.gameObject.transform.position;
this.gameObject.transform.position = mVec;
if( this.gameObject.transform.position != Position)
{
for(inti=1; i>objects1.Count; i++)
{
dir = objects1*.gameObject.transform.position - this.gameObject.transform.position;*
dir = dir.normalized - newVector3(random * 1, random * 1, random * 1);
GetComponent().AddRelativeForce(dir * force);
Debug.Log(objects1*);*
}
if (object1 != null)
{
Dist = Vector3.Distance(this.gameObject.transform.position, object2.gameObject.transform.position);
Vector3TargetPosition = object1.transform.position;
floatmove;
move = Dist - Time.deltaTime;
this.gameObject.transform.position = Vector3.MoveTowards(this.gameObject.transform.position, TargetPosition, (MoveStep * (move)));
}
if (Dist > 10){
DisT = Vector3.Distance(this.gameObject.transform.position, object2.gameObject.transform.position);
Debug.Log(Dist);
timeSpent = DisT * 0.0001F;
angle = timeSpent / Time.deltaTime;
print(angle);
this.gameObject.transform.RotateAround(object1.transform.position, Vector3.up, angle);
}
}
m_bIsMoving = true;
}
voidFindTarget()
{
floatlowestDist = Mathf.Infinity;
for(inti=1; i<objects1.Count; i++)
{
floatdist = Vector3.Distance(objects1*.transform.position, transform.position);*
if (dist<lowestDist)
{
sizeOfList = objects1.Count -1;
intrad = Random.Range(1,sizeOfList);
object1 = objects1[rad];
lowestDist = dist;
}
//object1 = objects1*;*
FindTarget();
//sortedOrder.FirstOrDefault();
}
objects1 = GameObject.FindGameObjectsWithTag (“audio”).ToList();
FindTarget();
}
publicboolisMoving()
{
returnm_bIsMoving;
}
}

stratos_kakalis · June 11, 2016, 6:34am

tomvds:

The easiest way first. That is

Transform GetClosestEnemy(Transform[] enemies)
{
    Transform tMin = null;
    float minDist = Mathf.Infinity;
    Vector3 currentPos = transform.position;
    foreach (Transform t in enemies)
    {
        float dist = Vector3.Distance(t.position, currentPos);
        if (dist < minDist)
        {
            tMin = t;
            minDist = dist;
        }
    }
    return tMin;
}

Just saying that if you are calling this as a function (as i did :p) everyframe you will have to move the variable minDist outside of it so it doesnt re-set its value to infinity all the time.Only if you place this code into a function though hopefully this will save some frustration it took me a good 30 mins to understand where the problem was

stratos_kakalis · June 11, 2016, 6:42am

I just noticed this only works in my case where i want to find the closest gameobject and not recalculate again. If you want something like the first goal you would have to find a way to reset minDist but not every frame

stratos_kakalis · June 11, 2016, 6:47am

Jesus count me wrong AGAIN this is the last post i promice :P.I was curious so i run a little test to see what would actually fix it and as weird as i seems to me updating minDist in the update method/function is exactly what makes it work.My guess is it calculates first which object is closest to the player and then resets the value to Mathf.Infinity hope i didnt cause any trouble and that i actually helped

IgorAherne · July 1, 2017, 12:26pm

Dude, 50 monsters is nothing. Just use linq and let it use n*log(n) time complexity

using System.Linq;

//get 3 closest characters (to referencePos)
var nClosest = myTransforms.OrderBy(t=>(t.position - referencePos).sqrMagnitude)
                           .Take(3)   //or use .FirstOrDefault();  if you need just one
                           .ToArray();

Otherwise, you need to look into octrees/kd trees

mjonasz · January 10, 2018, 6:56pm

edwardrowe:

For anyone who arrives here through a Google search, the presented answer by tomvcds is good, but should definitely be optimized by comparing distance squared instead of straight distance. It adds no complexity to the code and is more efficient, since it avoids the expensive square root operation that happens under the hood by doing “Vector3.Distance”.

For example - Say you have 3 objects, A, B, and C, and a source. You want to know which one is closest to the source. Let’s say A is 2m away, B is 3m away, and C is 4m away. Instead of doing the distance test and getting 2, 3, and 4, you can instead get the value in distance squared, which would be 4, 9, and 16, respectively. Distance squared still maintains their order by proximity, it’s just that the values increase exponentially instead of linearly.

Here is the code:
    Transform GetClosestEnemy (Transform[] enemies)
    {
        Transform bestTarget = null;
        float closestDistanceSqr = Mathf.Infinity;
        Vector3 currentPosition = transform.position;
        foreach(Transform potentialTarget in enemies)
        {
            Vector3 directionToTarget = potentialTarget.position - currentPosition;
            float dSqrToTarget = directionToTarget.sqrMagnitude;
            if(dSqrToTarget < closestDistanceSqr)
            {
                closestDistanceSqr = dSqrToTarget;
                bestTarget = potentialTarget;
            }
        }
    
        return bestTarget;
    }
*Edited to add an example.

How would you select from enemies with a specific tag?

Transform GetClosestEnemy (Transform[ ] enemies)
{
Transform bestTarget = null;
float closestDistanceSqr = Mathf.Infinity;
Vector3 currentPosition = transform.position;
foreach(Transform potentialTarget in enemies)
{
Vector3 directionToTarget = potentialTarget.position - currentPosition;
float dSqrToTarget = directionToTarget.sqrMagnitude;
if(dSqrToTarget < closestDistanceSqr)
{
closestDistanceSqr = dSqrToTarget;
bestTarget = potentialTarget;
}
}
return bestTarget;
}

WarmedxMints_1 · January 10, 2018, 11:24pm

Simple pass just the gameobjects with that tag into the array parameter.

mjonasz · January 11, 2018, 6:35pm

Thanks! Next step is to make the NPC move away from the “bestTarget”.
I tried this:

Vector3 direction = bestTarget.transform.position - transform.position;
this.transform.Translate(0, 0, Time.deltaTime * speed);

But it doesn’t do anything.

Transform GetClosestEnemy(Transform[ ] enemies)
{
enemies = GameObject.FindGameObjectsWithTag(targetTag);
{
for (int i = 0; i < enemies.Length; i++)
{
Transform bestTarget = null;
float closestDistanceSqr = Mathf.Infinity;
Vector3 currentPosition = transform.position;
foreach (Transform potentialTarget in enemies)
{
Vector3 directionToTarget = potentialTarget.position - currentPosition;
float dSqrToTarget = directionToTarget.sqrMagnitude;
if (dSqrToTarget < closestDistanceSqr)
{
closestDistanceSqr = dSqrToTarget;
bestTarget = potentialTarget;
}
}
return bestTarget;
}

tarikkoenig · October 22, 2018, 4:22pm

can you explain a little more detailed? are we talking about the array parameter “enemies” after transform[ ]?
what does that first line do anyway?

could you upload the full code? i don’t know what to put into the FixedUpdate() void. i tried to apply your advice to the second code from @edwardrowe :

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

public class AmrDistance : MonoBehaviour {

    public double coordinate;

    Transform GetClosestEnemy(Transform[] enemies)
    {
        enemies = GameObject.FindGameObjectsWithTag(Finish);
    }   
   
    void FixedUpdate()
    {
            for (int i = 0; i < enemies.Length; i++)
            {
                Transform bestTarget = null;
                float closestDistanceSqr = Mathf.infinity;
                Vector2 currentPosition = transform.position;
                foreach (Transform potentialTarget in enemies)
                {
                    Vector2 directionToTarget = potentialTarget.position - currentPosition;
                    float dSqrToTarget = directionToTarget.sqrMagnitude;
                    if (dSqrToTarget < closestDistanceSqr)
                    {
                        closestDistanceSqr = dSqrToTarget;
                        bestTarget = potentialTarget;
                    }
                }
                return bestTarget;
            }
    }
}

but i feel like this was completely wrong

lordofduct · October 22, 2018, 8:02pm

Probably not since the 2 posts you quoted are from last year, and over 2 years ago respectively.

Heck this thread is 8 years old.

…

What are you attempting to do?

Describe your problem, maybe we can help you.

mgear · October 31, 2018, 7:35am

since this is high in the google search for nearest objects,
just found out that can use this to get nearby objects fast Unity - Manual: CullingGroup API

*Added test project: Find Nearby Objects using CullingGroup « Unity Coding – Unity3D

tarikkoenig · November 21, 2018, 9:59am

i have found a solution thanks to @lordofduct great help. Maybe this will help anyone like me:

"":

FindGameObjectsWithTag is both slow and creates an array every time it’s called. This can be an issue.

What I’d do instead is create an ‘Enemy’ script that had a collection for accessing any that currently exist. I do this frequently with what I call a ‘MultitonPool’. I wrote a custom one which can be seen here with some querying checks and the sort:
https://github.com/lordofduct/spacepuppy-unity-framework-3.0/blob/master/SpacepuppyUnityFramework/Collections/MultitonPool.cs

And here is an example of using it. I’m also implementing an Octree for fast spacial tracking, but I haven’t finished it, and I don’t need it currently:
https://github.com/lordofduct/spacepuppy-unity-framework-3.0/blob/master/SPSensors/Sensors/Visual/VisualAspect.cs

This all my be overkill for you though…

So a trimmed down version can be accomplished with a simple ‘HashSet’ like so:
using UnityEngine;
using System.Collections.Generic;

public class Enemy : MonoBehaviour
{

    public readonly static HashSet<Enemy> Pool = new HashSet<Enemy>();

    private void OnEnable()
    {
        Enemy.Pool.Add(this);
    }

    private void OnDisable()
    {
        Enemy.Pool.Remove(this);
    }



    public static Enemy FindClosestEnemy(Vector3 pos)
    {
        Enemy result = null;
        float dist = float.PositiveInfinity;
        var e = Enemy.Pool.GetEnumerator();
        while(e.MoveNext())
        {
            float d = (e.Current.transform.position - pos).sqrMagnitude;
            if(d < dist)
            {
                result = e.Current;
                dist = d;
            }
        }
        return result;
    }

}
You just slap this ‘Enemy’ script on any GameObject that is an enemy… rather than tagging it.

Then you can just call the static method ‘FindClosestEnemy’ from anywhere passing along the position you want to find near to. You’d call that method from FixedUpdate… something like this:
void FixedUpdate()
{
     var nearestEnemy = Enemy.FindClosestEnemy(transform.position);
     //do stuff with that enemy
}
Note I use a ‘HashSet’ because as a collection it forces uniqueness (so no repeat entries), and it has a fast insert for large collections. And if you have a lot of enemies, you’re going to have a large collection.

krupps · February 13, 2019, 7:01pm

I could be wrong, But I would just use a sphere collider and on Trigeer/Collision Stay use this: I’ll test it tonight but it finds other colliders within your collider.

 Collider[] colliders = Physics.OverlapSphere(center, radius);
Collider nearestCollider = null;
float minSqrDistance = Mathf.Infinity;
for (int i = 0; i < colliders.Length; i++)
{
     float sqrDistanceToCenter = (center - colliders[i].transform.position).sqrMagnitude;
     if (sqrDistanceToCenter < minSqrDistance)
     {
         minSqrDistance = sqrDistanceToCenter;
         nearestCollider = colliders[i];
     }
}