5

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!

2
  • 1
    Seeing your range-based for-loop I'm assuming you are either using the shiny new C++11 standard or just don't know that it's a pretty new syntax. While it is totally fine to use it, I just wanted to tell you that it's not compatible with older compilers. No reason to not using it in general ;)
    – leemes
    Commented Dec 22, 2012 at 1:54
  • ... This is why I added another answer which uses modern facilities of C++11, although the other answers are also correct.
    – leemes
    Commented Dec 22, 2012 at 2:15

4 Answers 4

13

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

17
  • 2
    This is the best solution so far. +1
    – chrulri
    Commented Dec 22, 2012 at 2:47
  • +1 for a thorough answer that introduces a lot of useful topics. The performance junkie in me feels the need to mention that the calls to abs are unnecessary (since the signs will cancel eachother out) and also that you may want to capture fb by reference [&fb] instead of by value [fb] in order to avoid making a copy of it. Commented Dec 22, 2012 at 3:07
  • +1 as well. @leemes, the only check I would do against this is to capture fb by reference. I honestly can't remember if capture-byref or capture-byval is the default, so it may be nothing.
    – WhozCraig
    Commented Dec 22, 2012 at 3:23
  • 1
    @WhozCraig Default (I mean, when not writing either & or =) is to capture by value. You guys are right. Do you know if there is a way to capture by "const reference"? I don't think so. This is why I often capture by value, because you can't accidentally change the value from within the lambda. Just a "security thing".
    – leemes
    Commented Dec 22, 2012 at 12:20
  • We should also note that this algorithm probably is a bit slower than a custom loop as seen in the other answers, since we're calculating distances for both objects for every comparison. We need n-1 comparisons, so 2n-2 distances are computed. In the other answers, they only compute n distances. However, I think writing the more verbose alternative loop because of this performance difference falls under Premature Optimization. In practice, we should analyze it to be sure.
    – leemes
    Commented Dec 22, 2012 at 12:22
4

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.

5
  • actually for an odd reason this gives me the furthest entiry
    – Dean
    Commented Dec 22, 2012 at 2:21
  • @Dean There have been bugs in the code, such as an off-by-one-error and assignment instead of check for equality in the if-statement. If you want to learn something new, have a look at my answer.
    – leemes
    Commented Dec 22, 2012 at 12:50
  • @leemes - thanks, I've been using a horrible language at work that uses "=" for both assignments and comparisons, which is making me hate myself. Corrections much appreciated. Commented Dec 22, 2012 at 20:40
  • @leemes -"Openedge advanced business language," also known as "progress." It makes some interesting design decisions such as starting arrays at 1, not 0, and using '~' instead of '\' to escape characters, so it can throw me off occasionally when I return to standard languages - thanks for the corrections. Commented Dec 24, 2012 at 1:45
  • 1
    @MarshallConover Same in VBA: Arrays start at 1, there is no real escaping but " is written as "", also very strange. Ah, and no dynamic data structures :) I have to program some Microsoft Office macros at work (all in VBA), this is driving me crazy...
    – leemes
    Commented Dec 24, 2012 at 11:53
3

You need to keep track of the entity that has the smallest squares addition. Something like this:

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

    // this is not the actual distance, for that you would need sqrt(). But
    // it is enough to know if it is bigger or smaller.
    dist = xDiff*xDiff + yDiff*yDiff;
    closestEnt = ( dist < smallestDist ? i : closestEnt );
    smallestDist = ( dist < smallestDist ? dist : smallestDist );
}
...

Where dist and smallestDist are numbers and closestEnt an Entity, don't really know your types.

Rember to initialize smallestDist to the biggest possible number for the number type you choose. e.g. long smallestDist = 0xffffffff;

4
  • I'm having trouble understanding this, so your saying to get the min/max ?
    – Dean
    Commented Dec 22, 2012 at 1:37
  • @Dean What you do is calculate the distance of each entity and keep track of the smallest one so far. I added the loop if it wasnt clear the code goes inside the loop.
    – imreal
    Commented Dec 22, 2012 at 1:39
  • 2
    "this is not the actual distance, for that you would need sqrt(). But it is enough to know if it is bigger or smaller."" You know, I've written this function a hundred times, and never once did it occur to me that I could just use the result of the addition and skip the square root. Thanks! Commented Dec 22, 2012 at 1:43
  • I see what you mean, Ill give it a try
    – Dean
    Commented Dec 22, 2012 at 1:44
0
int GetNearestEntity()
{
    int closestEnt = 0;
    int smallestDist = -1;
    int i = 0;

    if (fb.Entities.size() > 0)
    {
        for (Entity entity : fb.Entities) 
        {
           double xDiff = (double)abs(fb.PlayerLocation.X - entity.X);
           double yDiff = (double)abs(fb.PlayerLocation.Y - entity.Y);
           double totalDist = sqrt(pow(xDiff,2) + pow(yDiff,2));

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

           i++;
        }
        return closestEnt;
    }
    return 0;
}
1
  • 1
    Just my two cents: Returning an index of 0 as a special case looks dangerous to me. You might accidentally just access the vector with this index outside of this function. To handle this special case in the caller, you have to check the length again. Working with negative indices is a more common way to indicate "no index", for example -1. So the caller just tests if the returned index is >= 0, which can be seen as "check for validity".
    – leemes
    Commented Dec 22, 2012 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.