Get closest Entity from the Player on a 2D battlefield I am building a little game in using Unity, and recently made an algorithm to get the closest Entity to the player on the battlefield. I made a working sample in RexTester (it is not the real code, but the algorithm is exactly the same).

I am interested in the GetCloserEntityFromPlayer function. Basically, it loops through all the entities and find the closest one. The function is defined as below:

public static Entity GetCloserEntityFromPlayer(){
    List&lt;Entity&gt; temp = new List&lt;Entity&gt;();
    temp.AddRange(allies);
    temp.AddRange(enemies);

    //assume the first is the closest, and compare to the others
    Entity aux = temp[0];
    int distance = Math.Abs((aux.X + aux.Y) - (player.X + player.Y));

    for(int i = 1; i &lt; temp.Count; i++)
    {
        //in my game, the distance is the absolute difference 
        //between the sum of both Entities x and y values
        int temp_distance = Math.Abs((temp[i].X + temp[i].Y) - (player.X + player.Y));
        if(temp_distance &lt; distance)
        {
            aux = temp[i];                    
        }
    }
    return aux;
}


When the Entity number starts growing, the game seems to get a little slow, with FPS dropping. I was thinking of maintaining the Entities list ordered, so I would help the branch predictor.
First of all, this function would be more idiomatic using a foreach loop:

Entity closest = null;
int distance = int.MaxValue;

for (var other in entities)
{
    int d = Math.Abs((other.X + other.Y) - (player.X + player.Y));
    if(d &lt; distance)
    {
        closest = other;
    }
}
return closest;



  When the Entity number starts growing, the game seems to get a little slow, with FPS drop. I was thinking of maintaining the Entities list ordered, so I would help the branch predictor, I don't know...


If you can keep entities sorted by their e.X + e.Y value,
then you could significantly speed up the search using binary search:
you will be able to find the position of the player in the list,
and check only its two neighbors to find the closest.

However, keeping the entities sorted might be costly as well.
I don't know if that's the case here,
it depends on the rest of your application that you did not include in the post.
My guess is that it's going to be so costly that you will not gain any benefit at all.

On the other hand,
if you need to find the closest entity for not only one player,
but multiple entities,
and if you perform that step for all entities at once,
then you will benefit from performing the sort right before you look for the closest neighbors.
This is different from keeping the entities sorted at all times.
You would only sort right before it's needed.