# finding the closest object

## Recommended Posts

hey, i find my function for finding the closest object kind of tedious. maybe i'm wrong but here it is:
// targets closest ship to player
int c_ship::target_closest_ship()
{
float closest_dist;
int closest_id = -1;
float distance;
int i;

// start at 1 because 0 is the player
for (i=1;i<universe.ship.size();i++)
{
// x, y = player position
distance = get_length(x, y, universe.ship[i].x, universe.ship[i].y);

// set the closest to the very first check
if (closest_id == -1)
{
closest_dist = distance;
closest_id = i;
}
else
{
if (distance < closest_dist)
{
closest_dist = distance;
closest_id = i;
}
}
}

return closest_id;
}

anyone have a quicker, or easier/cleaner method?

##### Share on other sites
You can get rid of the "if (closest_id == -1)" section by setting the initial value of distance to positive infinity.

[EDIT] also, I'm guessing that your get_length function performs a square-root operation, which is slow.
You can optimise this by also writing a get_length_squared function, seeing as in this test you don't need to know the exact distance, just whether one distance is bigger than another.
e.g.
//use this function inside your loop instead, as it's much faster:float get_length_squared(float x1, float y1, float x2, float y2){ float x = x1-x2, y = y1-y2; return x*x+y*y;}//you probably still need get_length in other places:float get_length(float x1, float y1, float x2, float y2){ return sqrt( get_length_squared(x1,y1,x2,y2) );}

##### Share on other sites
First, a function which computes a squared distance between two vectors:
float sq_dist(const vector2 & a, const vector2 & b){  float dx = a.x - b.x, dy = a.y - b.y;  return dx * dx + dy * dy;}
This function will be quite useful for a lot of checks that you will do as part of collision detection and similar tasks.

Then, since you might want to look for the closest object other than a ship (pickups, bullets, and so on), you can generalize your closest-object function to take an arbitrary list of objects (represented as a begin-end pair of iterators), a point in space, and a distance function which returns the position of a provided object. Also provides a 'skip' argument, in case the tested distance is actually part of the sequence, at which point the given element will simply be ignored.
template<typename It, typename F>It get_closest_to(const vector2 & where, F pos, It begin, It end, int skip = -1){  if (skip == 0 && begin != end)     ++begin;  if (begin == end)     return end;  It best_it = begin;  float best = sq_dist(where, pos(*begin));  while (++begin != end)  {    if (--skip == 0)       continue;    const float d = sq_dist(where, pos(*begin));    if (d < best)     {      best_it = begin;      best = d;    }  }}

Finally, you can apply your get_closest_to function to ship objects.
boost::optional<unsigned> ship::get_closest_ship(){  unsigned index =     get_closest_to( this -> get_pos(),                    this -> neighbors.begin(),                    this -> neighbors.end(),                    std::mem_fun_ref( &ship::get_pos ),                    this -> index )    - this -> neighbors.end();  if (index == this -> neighbors.size())    return boost::optional<unsigned> ();  else    return boost::optional<unsigned>(index);}

##### Share on other sites
Well if (as your example conveys) your universe is the whole universe with all the ships some kind of spatial partitioning scheme would do wonders in eliminating the ships that are further than few sectors away.

##### Share on other sites
A well known problem...and an Algorithms class classic.
Closest pair of points

Best solved via divide and conquer...

Here is one implementation...Closest Pair: Divide and Conquer

##### Share on other sites
Quote:
 Original post by virus-Well if (as your example conveys) your universe is the whole universe with all the ships some kind of spatial partitioning scheme would do wonders in eliminating the ships that are further than few sectors away.

I second this. You should consider implementing some type of bounding-volume hierarchy to store all of the objects in your scene (for example, using an oct-tree if things are in 3D, or a quad-tree if in 2D). You would use the player's current position to traverse the tree, stopping when you hit an intermediate node within some distance threshold. This will greatly reduce the amount of search time from O(n) for your sequential list check, down to O(log base 8(n)) if using an oct-tree (O(log base 4(n)) for a quad-tree), which is a huge increase in efficiency once you get a large number of objects in there. You can also use this type of tree to determine when collisions have occured and with what object (search for oct-tree collision detection on google).

Changing your traversal technique will net you far more of an improvement in efficiency than any subtle changes to the number of operations performed.

##### Share on other sites
As usual, the best optimisation here is a high-level algorithmic optimisation. As others have mentioned, you should look into spatial partitioning, which will greatly speed up this kind of search.

##### Share on other sites
Quote:
 You should consider implementing some type of bounding-volume hierarchy to store all of the objects in your scene (for example, using an oct-tree if things are in 3D, or a quad-tree if in 2D).

I second the vote to use a BVH (Bounding volume hierarchy) but to be picky, neither oct- or quad tree is a BVH in it's original form, they area spatial subdivision schemes (as is a KD-tree).

I'd go for an AABB tree (Axis aligned bounding box) or if you have a lot of dynamic objects or want the "best" solution ,I'd look into the recently popular BIH (bounding intervall hieracrhy) since it has very fast to builds and shares some nice properties of spatial subdivision schemes.

My 2c.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628329
• Total Posts
2982104

• 22
• 9
• 9
• 13
• 11