Sign in to follow this  
Nibbles

finding the closest object

Recommended Posts

Nibbles    569
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 this post


Link to post
Share on other sites
Hodgman    51324
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 this post


Link to post
Share on other sites
ToohrVyk    1596
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 this post


Link to post
Share on other sites
virus-    186
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 this post


Link to post
Share on other sites
abso    137
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 this post


Link to post
Share on other sites
Sc4Freak    643
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 this post


Link to post
Share on other sites
eq    654
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this