Sorting vector values by Distance in vector

Question

I have two locations, My player location (2D) and I'm looping over a vector of entitys each with a location (2D), I would like my function to return the closest distance to my location, But I don't know how to do it because I got stuck, in c# I could just use linq, But i'm learning c++ My function looks like this:

const Entity GetNearestEntity()
{
    for (Entity i : fb.Entities)
    {
        double xDiff = (double)abs(fb.PlayerLocation.X - i.X);
        double yDiff = (double)abs(fb.PlayerLocation.Y - i.Y);

        //Stuck here.. 
        //How can i get the closest object out of my vector<Entity> collection?
    }
}

help appreciated!

Answer 1

Since you're new to C++ (as you told), I wanted to present you a nice alternative which requires a little bit of different thinking, but once you got used to it, you'll love it.

The basic idea

You are looking for an element (or you want the reference to that element to maybe modify it later) which is the minimum element with respect to a certain comparison method. C++ lets you choose how to compare elements, separately for a particular query (don't think about comparison as well-defined "less-than" / "greater-than" operators in this case, but it's a similar concept).

You could define such an comparison locally for this particular scenario. Comparison methods can be implemented as stand-alone functions, as functors (function objects which implement the so-called "call-operator") or as lambda functions, which you should prefer.

The Lambda function syntax

Lambda functions are anonymous functions which are typically used at the same place you are writing them literally. The lambda function syntax is something you have to get used to, but once you did, it's a powerful thing!

[](Entity a, Entity b) {  return a.X < b.X;  }

This is a lambda function which takes two Entity instances and simply compares their X coordinates. Of course this is not what you want here, but I wanted to show you the syntax first.

Now we want to implement a comparison function which compares the coordinates relative to an origin (your player position), so this is something which is passed from outside of the function, but not as an argument (since comparison functions can only take the two values to be compared). This is done by capturing some context variables. Have a look here:

int captured = ...
...
[captured](Entity a, Entity b) {  return a.X + captured < b.X + captured;  }

Still not making any sense, it shows how you can refer to a variable which is defined outside of the lambda function from within the lambda function.

A Lambda function for your specific problem

Now we can write the comparison method correctly:

[fb](Entity a, Entity b) {
    double ax = fb.PlayerLocation.X - a.X;
    double ay = fb.PlayerLocation.Y - a.Y;
    double a = ax * ax + ay * ay; // we can save the sqrt()
    double bx = fb.PlayerLocation.X - b.X;
    double by = fb.PlayerLocation.Y - b.Y;
    double b = bx * bx + by * by; // we can save the sqrt()
    return a < b;
}

So we capture fb, we calculate the relative coordinates of the two entities a and b, compute the square of the length (so we can save the sqrt) and compare these distances. The code looks a bit bloated; we're improving this later.

Using the Lambda function in an STL algorithm

Once you understood how to write such comparison functions, the final step becomes trivial, as STL provides a lot of algorithms ready to use which can take such functions:

Entity closest = *std::min_element(fb.Entities.begin(), fb.Entities.end(),
    [fb](Entity a, Entity b) {
        double ax = fb.PlayerLocation.X - a.X;
        double ay = fb.PlayerLocation.Y - a.Y;
        double a = ax * ax + ay * ay; // we can save the sqrt()
        double bx = fb.PlayerLocation.X - b.X;
        double by = fb.PlayerLocation.Y - b.Y;
        double b = bx * bx + by * by; // we can save the sqrt()
        return a < b;
    }
);

As you can see, I'm just passing the lambda function directly to another function call (without first defining the function with a particular name, since it's an anonymous function). This function call is std::min_element, which finds the minimum element between two iterators (if you want to search within a whole container, use the begin/end iterator pair). It returns another iterator. With the * prefix operator, you access the element the iterator points to.

Note that once storing it as an Entity value, it's copied, so modifications are no longer written into the vector directly but to a local copy. To avoid this, use Entity&, which is a (modifiable) reference to the element within the vector, which your function can return without problems (as long as the referenced value is valid outside your function, which it is in your case).

Improvements

If you write a distance function comparing two entities, this becomes simpler: (note the lack of abs, which is because we are going to square the value anyhow, any negative sign will disappear)

double distance(Entity p, Entity q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return sqrt(delta_x * delta_x + delta_y * delta_y);
}

Or, again, saving the sqrt:

double distanceSquare(Entity p, Entity q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return (delta_x * delta_x + delta_y * delta_y);
}

So the code becomes:

Entity closest = *std::min_element(fb.Entities.begin(), fb.Entities.end(),
    [fb](Entity a, Entity b) {
        return distanceSquare(a, fb.PlayerLocation) <
               distanceSquare(b, fb.PlayerLocation);
    }
);

Another improvement is to pass variables by (non-modifiable) references instead of passing them by value. This means that the variable doesn't need to be copied. Placing the code in the method as you've written in your question, the code becomes (with the call-by-reference concept applied and returning a modifiable reference):

double distanceSquare(const Entity & p, const Entity & q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return (delta_x * delta_x + delta_y * delta_y);
}

Entity & GetNearestEntity()
{
    return *std::min_element(fb.Entities.begin(), fb.Entities.end(),
        [fb](const Entity & a, const Entity & b) {
            return distanceSquare(a, fb.PlayerLocation) <
                   distanceSquare(b, fb.PlayerLocation);
        }
    );
}

(Note the nested return statements. The inner one is part of the lambda function and returns the result of the comparison logic. The outer one returns the final result, so the entity with the lowest distance.)

At the end, it looks cleaner (at least in my opinion). Once you've understood this concept, you see the beauty in it. :)

The final improvement I will show you was mentioned in the comments to this answer by Andrew Durward: The Lambda function as we've written it now, copies the value fb once for every call to GetNearestEntity because it might have changed since the last call. We can avoid this copy operation by capturing by reference, which is the same concept as call by reference, but for the captured variables. Just write & in front of the variable name in the capture expression:

//...
        [&fb](const Entity & a, const Entity & b) {
            return distanceSquare(a, fb.PlayerLocation) <
                   distanceSquare(b, fb.PlayerLocation);
        }
//...

The capture syntax might look a bit strange at the beginning, but it provides a powerful control over which variables in the enclosing context you capture by reference or by value:

Source: http://www.cprogramming.com/c++11/c++11-lambda-closures.html

[]          Capture nothing (or, a scorched earth strategy?)
[&]         Capture any referenced variable by reference
[=]         Capture any referenced variable by making a copy
[=, &foo]   Capture any referenced variable by making a copy, but capture variable foo by reference
[bar]       Capture bar by making a copy; don't copy anything else
[this]      Capture the this pointer of the enclosing class

If you want to read more about capturing variables in lambda functions, read here or google for "C++11 lambda capture syntax".

Demonstration of this code: http://ideone.com/vKAFmx

Answer 2

This may be easier to do by keeping track of the index of the closest element to you, which would be easier in a 'for' loop like:

Entity GetNearestEntity()
{
    int closestEnt = 0;
    double smallestDist = -1.0;

    for (int i = 0; i < Entities.length(); i++) 
    {
        double xDiff = (double)abs(fb.PlayerLocation.X - Entities[i].X);
        double yDiff = (double)abs(fb.PlayerLocation.Y - Entities[i].Y);
        double totalDist = sqrt(pow(xDiff, 2) + pow(yDiff, 2));

        if ((totalDist < smallestDist) || (smallestDist == -1.0))
        {
            closestEnt = i;
            smallestDist = totalDist;
        }
    }

    return Entities[closestEnt];
}

This may not compile off the bat, it's been a while since I've played with C++, and I'm blanking on whether that's the right way to do square roots and powers. However, it has the nice benefit of only keeping track of a double and an int, instead of an object.