Find the last 3 values in a list

Unity Engine
,
1

Hi everyone,

I have several POI on a map, and I know their distance from the player, and I would like to filter out the 3 closest to me, and have this list of 3 update as I move around.

I found how to find the highest or lowest value in array or list, but I didn’t find how to retrieve the last three values.

If anyone has an idea, it would help me a lot.
Thx

2

If the size of the list is N and it is greater than or equal to 3, then just use a for loop:

for (int index = N - 3; index < N; index++)
{
  // do what you want with each index value here.
}
3

You can access them by index. The last index will be at index List.Count -1. Use -2 and -3 for the second and third last. That is assuming your list is sorted so the closest are at the end of the list.

If you also need to find the 3 closest in the list, you could either first sort the list by distance, or you could create a new list of the 3 closest by looping through the list checking distance.

4

Great, that works perfectly, thanks to you both.

1 Like
5

Are you trying to find the 3 items at the end of the list, or are you trying to find the 3 smallest numbers in the list? Unless you have already sorted the array, those are not the same thing.

1 Like
6

Yeah not only this, but if the player is moving around, the proper sorting would change frame to frame (as the distances would change frame to frame)

7

@Antistone I calculate the distance between every POI and the player, and I want to filter the 3 closest POI to me, by their distance, and as @PraetorBlue said, I’m moving around, and then access to their names and others

8

The simplest thing to do would be (each frame) sort the objects by distance then take the first three in the list. How many objects are there? If there’s not a huge number this shouldn’t be terrible performance-wise.

9

Around 50-70, I think …

10

That should be really fast to sort. Try this:

// Assuming we have a list populated with our POI
List<Transform> pointsOfInterest;

// And our player transform
Transform playerTransform;

// Sort the list, closest objects first.
pointsOfInterest.Sort((a, b) => {
  float aSqrDist = Vector3.SqrMagnitude(a.position - playerTransform.position);
  float bSqrDist = Vector3.SqrMagnitude(b.position - playerTransform.position);
  if (aSqrDist < bSqrDist) return -1;
  else if (aSqrDist == bSqrDist) return 0;
  else return 1;
});

// First three elements
List<Transform> closestThree = pointsOfInterest.GetRange(0, 3);
11

Sorting the list is simple and is something that it would be valuable for you to know how to do.

However, if you have a variable-size list and only want a fixed number of results (the bottom 3), sorting the whole list is a bit inefficient; it will take at least O(N log N) time, whereas it’s possible to do this in O(N) time.

Now, for a list of less than a thousand entries this probably isn’t a big deal. But most programmers wouldn’t sort the whole list to find the single lowest entry, and finding the three lowest entries isn’t a lot harder:

const int numResults = 3;
int foundResults = 0;
float[] closestDistances = new float[numResults];
int[] closestIndices = new int[numResults];

for (int i = 0; i < pointsOfInterest.Count; ++i)
{
    // SqrMagnitude is used instead of Magnitude because
    // Sqr is cheaper to calculate and won't change the order of results
    float dist =Vector3.SqrMagnitude(pointsOfInterest[i].position - playerTransform.position);

    // Decide where to insert this new item into our list of results
    int rank = foundResults;
    for (j = foundResults-1; j >= 0; --j)
    {
        if (dist < closestDistances[j])
        {
            // new result is better than this, so can be inserted above it
            rank = j;
            // If there is space in our results list, slide the old result down
            if (j+1 < numResults)
            {
                closestDistances[j+1] = closestDistances[j];
                closestIndices[j+1] = closestIndices[j];
            }
        }
        else break;
    }

    // If new result was good enough to make the cut, insert it
    if (rank < numResults)
    {
        closestDistances[rank] = dist;
        closestIndices[rank] = i;
        foundResults = Mathf.Min(numResults, i+1);
    }
}

// The closest thing is pointsOfInterest[closestIndices[0]]
// Second-closest is pointsOfInterest[closestIndices[1]]
// And so on up to foundResults

NOTE: If the number of results you need is greater than the logarithm of the length of the list, you are better off just sorting the whole thing rather than using this method.

1 Like
12

Thanks guys, I found out with your help

var distances = Filtres[FiltreId].Locations.OrderBy(x => x.Distance).ToList();