Search Unity

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

Discussion in 'Scripting' started by _Adriaan, Mar 22, 2010.

  1. _Adriaan

    _Adriaan

    Joined:
    Nov 12, 2009
    Posts:
    425
    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!
     
  2. tomvds

    tomvds

    Joined:
    Oct 10, 2008
    Posts:
    1,028
    The easiest way first. That is
    Code (csharp):
    1. Transform GetClosestEnemy(Transform[] enemies)
    2. {
    3.     Transform tMin = null;
    4.     float minDist = Mathf.Infinity;
    5.     Vector3 currentPos = transform.position;
    6.     foreach (Transform t in enemies)
    7.     {
    8.         float dist = Vector3.Distance(t.position, currentPos);
    9.         if (dist < minDist)
    10.         {
    11.             tMin = t;
    12.             minDist = dist;
    13.         }
    14.     }
    15.     return tMin;
    16. }
    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 ;).
     
    dappledore, shavemadox and jacupiri like this.
  3. _Adriaan

    _Adriaan

    Joined:
    Nov 12, 2009
    Posts:
    425
    Nice!
    As promised.

     
  4. edwardrowe

    edwardrowe

    Joined:
    Feb 11, 2014
    Posts:
    35
    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:

    Code (CSharp):
    1.     Transform GetClosestEnemy (Transform[] enemies)
    2.     {
    3.         Transform bestTarget = null;
    4.         float closestDistanceSqr = Mathf.Infinity;
    5.         Vector3 currentPosition = transform.position;
    6.         foreach(Transform potentialTarget in enemies)
    7.         {
    8.             Vector3 directionToTarget = potentialTarget.position - currentPosition;
    9.             float dSqrToTarget = directionToTarget.sqrMagnitude;
    10.             if(dSqrToTarget < closestDistanceSqr)
    11.             {
    12.                 closestDistanceSqr = dSqrToTarget;
    13.                 bestTarget = potentialTarget;
    14.             }
    15.         }
    16.      
    17.         return bestTarget;
    18.     }
    *Edited to add an example.
     
    Last edited: Aug 7, 2014
  5. Kokumo

    Kokumo

    Joined:
    Jul 23, 2010
    Posts:
    416
    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.
     
    Last edited: Aug 7, 2014
  6. Josepht45

    Josepht45

    Joined:
    Oct 20, 2014
    Posts:
    12
    Does anyone know how I could take the bestTarget and make it change position to a gameobject?
     
  7. HeavyArmor

    HeavyArmor

    Joined:
    May 14, 2014
    Posts:
    2

    Thank you Kokumo!
     
  8. Iknow21

    Iknow21

    Joined:
    Oct 31, 2015
    Posts:
    2
    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<GameObject> objects1 = newList<GameObject>();

    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<Rigidbody>().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;
    }

    }
     
  9. stratos_kakalis

    stratos_kakalis

    Joined:
    Mar 8, 2016
    Posts:
    4
    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 :p
     
  10. stratos_kakalis

    stratos_kakalis

    Joined:
    Mar 8, 2016
    Posts:
    4
    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
     
  11. stratos_kakalis

    stratos_kakalis

    Joined:
    Mar 8, 2016
    Posts:
    4
    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 :p
     
  12. IgorAherne

    IgorAherne

    Joined:
    May 15, 2013
    Posts:
    344
    Dude, 50 monsters is nothing. Just use linq and let it use n*log(n) time complexity

    Code (CSharp):
    1. using System.Linq;
    2.  
    3. //get 3 closest characters (to referencePos)
    4. var nClosest = myTransforms.OrderBy(t=>(t.position - referencePos).sqrMagnitude)
    5.                            .Take(3)   //or use .FirstOrDefault();  if you need just one
    6.                            .ToArray();
    Otherwise, you need to look into octrees/kd trees
     
    Last edited: Jul 1, 2017
    ionside, Ne0mega, Ruslanas33 and 9 others like this.
  13. mjonasz

    mjonasz

    Joined:
    Sep 7, 2017
    Posts:
    5



    How would you select from enemies with a specific tag?
    1. Transform GetClosestEnemy (Transform[] enemies)
    2. {
    3. Transform bestTarget = null;
    4. float closestDistanceSqr = Mathf.Infinity;
    5. Vector3 currentPosition = transform.position;
    6. foreach(Transform potentialTarget in enemies)
    7. {
    8. Vector3 directionToTarget = potentialTarget.position - currentPosition;
    9. float dSqrToTarget = directionToTarget.sqrMagnitude;
    10. if(dSqrToTarget < closestDistanceSqr)
    11. {
    12. closestDistanceSqr = dSqrToTarget;
    13. bestTarget = potentialTarget;
    14. }
    15. }
    16. return bestTarget;
    17. }
     
  14. WarmedxMints

    WarmedxMints

    Joined:
    Feb 6, 2017
    Posts:
    755
    Simple pass just the gameobjects with that tag into the array parameter.
     
    mjonasz likes this.
  15. mjonasz

    mjonasz

    Joined:
    Sep 7, 2017
    Posts:
    5
    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;
    }
     
    Last edited: Jan 12, 2018
  16. tarikkoenig

    tarikkoenig

    Joined:
    Sep 5, 2018
    Posts:
    6
    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:

    Code (CSharp):
    1. using System.Collections;
    2. using System.Collections.Generic;
    3. using UnityEngine;
    4. using System;
    5.  
    6. public class AmrDistance : MonoBehaviour {
    7.  
    8.     public double coordinate;
    9.  
    10.     Transform GetClosestEnemy(Transform[] enemies)
    11.     {
    12.         enemies = GameObject.FindGameObjectsWithTag(Finish);
    13.     }  
    14.    
    15.     void FixedUpdate()
    16.     {
    17.             for (int i = 0; i < enemies.Length; i++)
    18.             {
    19.                 Transform bestTarget = null;
    20.                 float closestDistanceSqr = Mathf.infinity;
    21.                 Vector2 currentPosition = transform.position;
    22.                 foreach (Transform potentialTarget in enemies)
    23.                 {
    24.                     Vector2 directionToTarget = potentialTarget.position - currentPosition;
    25.                     float dSqrToTarget = directionToTarget.sqrMagnitude;
    26.                     if (dSqrToTarget < closestDistanceSqr)
    27.                     {
    28.                         closestDistanceSqr = dSqrToTarget;
    29.                         bestTarget = potentialTarget;
    30.                     }
    31.                 }
    32.                 return bestTarget;
    33.             }
    34.     }
    35. }
    36.    
    but i feel like this was completely wrong :D
     
  17. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,822
    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.
     
    Joe-Censored likes this.
  18. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    5,741
  19. tarikkoenig

    tarikkoenig

    Joined:
    Sep 5, 2018
    Posts:
    6
    i have found a solution thanks to @lordofduct great help. Maybe this will help anyone like me:

     
    Marcos-Elias likes this.
  20. krupps

    krupps

    Joined:
    Oct 17, 2017
    Posts:
    43
    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.

    Code (CSharp):
    1.  Collider[] colliders = Physics.OverlapSphere(center, radius);
    2. Collider nearestCollider = null;
    3. float minSqrDistance = Mathf.Infinity;
    4. for (int i = 0; i < colliders.Length; i++)
    5. {
    6.      float sqrDistanceToCenter = (center - colliders[i].transform.position).sqrMagnitude;
    7.      if (sqrDistanceToCenter < minSqrDistance)
    8.      {
    9.          minSqrDistance = sqrDistanceToCenter;
    10.          nearestCollider = colliders[i];
    11.      }
    12. }
     
  21. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,822
    Yes, if you had colliders on all your objects that you care about.

    Of course you would have to filter out any colliders you didn't intend to check (layers, tags, component on the object, whatever).
     
  22. eovento

    eovento

    Joined:
    Feb 22, 2018
    Posts:
    26
    It's not as common to find a thread with such productive replies. Thank you, _Adriaan for initiating this one, and everybody else for such amazing answers on such an important and useful topic! There are many threads on the subject, but this one here is gold! :)