Search Unity

  1. We are migrating the Unity Forums to Unity Discussions by the end of July. Read our announcement for more information and let us know if you have any questions.
    Dismiss Notice
  2. Dismiss Notice

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:
    481
    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 ;).
     
  3. _Adriaan

    _Adriaan

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

     
    Lightning_26 and RelayRay like this.
  4. edwardrowe

    edwardrowe

    Joined:
    Feb 11, 2014
    Posts:
    53
    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:
    13
    Does anyone know how I could take the bestTarget and make it change position to a gameobject?
     
    AdenJ and decadeee like this.
  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
     
    mysticvalleycsa likes this.
  12. IgorAherne

    IgorAherne

    Joined:
    May 15, 2013
    Posts:
    393
    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
  13. mjonasz

    mjonasz

    Joined:
    Sep 7, 2017
    Posts:
    12



    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:
    1,035
    Simple pass just the gameobjects with that tag into the array parameter.
     
    mjonasz likes this.
  15. mjonasz

    mjonasz

    Joined:
    Sep 7, 2017
    Posts:
    12
    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:
    8,599
    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:
    9,553
    Last edited: Feb 14, 2023
  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:

     
  20. krupps

    krupps

    Joined:
    Oct 17, 2017
    Posts:
    159
    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. }
     
    CoolCosmos likes this.
  21. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,599
    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:
    38
    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! :)
     
  23. useralpha

    useralpha

    Joined:
    Jun 19, 2017
    Posts:
    8
    I have a similar situation, but with one complication: I need to find the closest several ships. I have a list that contains all possible enemies (which cannot be edited, so a copy would need to be made for changes). I want to find, say the closest 4 enemies to a certain position (another enemy). I also have a list of enemies to exclude, which should just mean another if statement, and a max range, so I don't really need to check anything outside that range, if that helps somehow. So something maybe along the lines of
    Code (CSharp):
    1. public List<Transform> FindClosest(List<Transform> exclude, int numToFind, float range){ }
    Thanks!

    Edit: the list of enemies to search through is defined elsewhere in the same script.

    Edit 2: I think that I can solve the problem by just running through the list several times and adding to the exclude list. This probably isn't the best way, so let me know if there is a better way, but I think this should work for my needs.
     
    Last edited: Jun 22, 2020
  24. Please always open a new thread for your own question.
    Please show us what you have tried so far and where is it not working?

    If you want generalization:
    - you failed to mentioned how many objects you're talking about, potentially. Because if they are just a couple dozens, you can iterate through the array of ships once, store the four closest along the way and that's it.
    - if you are talking about arbitrary number or high number, eventually you will need to build an octree and partition the space: https://www.gamasutra.com/view/feature/131625/octree_partitioning_techniques.php
     
    mysticvalleycsa likes this.
  25. mysticvalleycsa

    mysticvalleycsa

    Joined:
    Sep 22, 2020
    Posts:
    14
    Please for the love of all that is holy, put this in code format so people can skip it. I haven't even read it yet but I was following another conversation.
     
    Popcane, shasaur_unity and CptAWatts like this.
  26. New_Game_Ideas

    New_Game_Ideas

    Joined:
    Jul 17, 2021
    Posts:
    4
    I think it will be more appropriate take the absolute value instead of taking squares. If I remember right it can be done by ".Abs".
     
  27. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,599
    absolute value of what?

    Distance/magnitude is always positive regardless.

    The square here is because distance/magnitude requires a squareroot, so by using the square magnitude (basically the calculation of magnitude just before you square root it), which saves you that calculation yet still gives you the compartive distance test.
     
    Bunny83 likes this.
  28. Ghosthowl

    Ghosthowl

    Joined:
    Feb 2, 2014
    Posts:
    233
    While on the subject of optimization, you should use a for loop instead of a foreach due to foreaches speed and garbage allocation. You can see some testing here.

    The edited version of this would be:

    Code (CSharp):
    1.     Transform GetClosestEnemy(Transform[] enemies)
    2.     {
    3.         Transform bestTarget = null;
    4.         float closestDistanceSqr = Mathf.Infinity;
    5.         Vector3 currentPosition = transform.position;
    6.         for (int i = 0; i < enemies.Length; i++)
    7.         {
    8.             Vector3 directionToTarget = enemies[i].position - currentPosition;
    9.             float dSqrToTarget = directionToTarget.sqrMagnitude;
    10.             if(dSqrToTarget < closestDistanceSqr)
    11.             {
    12.                 closestDistanceSqr = dSqrToTarget;
    13.                 bestTarget = enemies[i];
    14.             }
    15.         }
    16.    
    17.         return bestTarget;
    18.     }
     
  29. krupps

    krupps

    Joined:
    Oct 17, 2017
    Posts:
    159
    If he was creating/destroying objects. He's not, so this is by reference which both are equally just as fast. When a Foreach is modifying local variables the For is only .01% faster.

    Using a Foreach is more readable and easier to maintain. GC is only an issue with creating 10,000+ objects in a few seconds. As long as your disposing correctly.

    GetClosestEnemy is more of a concern. It's just looks bad, seems like a ray is needed.
     
    shasaur_unity likes this.
  30. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    2,098
    There is also a "spatial hash" techniques.
     
  31. StevenAtkinson82

    StevenAtkinson82

    Joined:
    Feb 29, 2020
    Posts:
    17
    Im struggling with how i pass my game objects with tag into the function can anyone help ?
    Like i have an array of gameobjects but it says
    " Argument 1: cannot convert from 'UnityEngine.GameObject[]' to 'UnityEngine.Transform[]' "
     
    Last edited: Dec 4, 2021
  32. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,696
    Why are you hijacking this thread? Please create your own threads if you have a problem.
     
  33. StevenAtkinson82

    StevenAtkinson82

    Joined:
    Feb 29, 2020
    Posts:
    17
    I wasnt trying to hijack the thread my question was relating to the stuff already posted,
    I had put the function posted above

    Code (CSharp):
    1. Code (CSharp):
    2.     Transform GetClosestEnemy(Transform[] enemies)
    3.     {
    4.         Transform bestTarget = null;
    5.         float closestDistanceSqr = Mathf.Infinity;
    6.         Vector3 currentPosition = transform.position;
    7.         for (int i = 0; i < enemies.Length; i++)
    8.         {
    9.             Vector3 directionToTarget = enemies[i].position - currentPosition;
    10.             float dSqrToTarget = directionToTarget.sqrMagnitude;
    11.             if(dSqrToTarget < closestDistanceSqr)
    12.             {
    13.                 closestDistanceSqr = dSqrToTarget;
    14.                 bestTarget = enemies[i];
    15.             }
    16.         }
    17.  
    18.         return bestTarget;
    19.     }
    But I cant figure out how to pass my array of gameobjects through it and need assistance

    Im sorry I maybe should have explained myself better my apologies
     
    Raro- likes this.
  34. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,696
    " Argument 1: cannot convert from 'UnityEngine.GameObject[]' to 'UnityEngine.Transform[]' "
    But your post isn't about the subject, it's about you not knowing C# well and thus not understanding the difference between a GameObject array and a Transform array (two completely different types). The error is telling you everything you need to know. You're passing a GameObject array to a piece of code you posted where the first argument is NOT an array of GameObject but an array of Transforms.

    Not understanding this is fine but it isn't the subject of this thread.
     
    Dieter_Dagger likes this.
  35. StevenAtkinson82

    StevenAtkinson82

    Joined:
    Feb 29, 2020
    Posts:
    17
    I am aware they are two different things im trying to figure how i get the transforms of my array of gameobjects so i can pass it through the code thats what i need help with
     
    Raro- likes this.
  36. kdgalla

    kdgalla

    Joined:
    Mar 15, 2013
    Posts:
    4,703
    Create an array of Transforms that is the same size as your array of GameObjects array. Loop through your GameObjects array and assign each of your GameObject's transforms to the corresponding entry in your Transforms array.
     
    StevenAtkinson82 likes this.
  37. StevenAtkinson82

    StevenAtkinson82

    Joined:
    Feb 29, 2020
    Posts:
    17
    that sounds like a good idea ill try that thanks
     
    Raro- likes this.
  38. unity_24cooksonjb

    unity_24cooksonjb

    Joined:
    Oct 10, 2022
    Posts:
    1
    what variables do you put on the top?
     
  39. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,217
    At this point I'm beginning to wonder why can't threads be auto-locked after a year of inactivity....
    As you go back, you can see Charles Darwin discovering the theory of evolution for the first time.
     
    MaskedMouse likes this.
  40. koirat

    koirat

    Joined:
    Jul 7, 2012
    Posts:
    2,098
    I'm against locking threads, people can judge if they want to answer necro-threads or not..
     
    chbran, cloverme and mgear like this.