Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a sizable game engine and I'd like a feature for finding the nearest of a list of points.

I could simply use the Pythagorean theorem to find the distances. I know I can't simply add x and y, because that's only the distance to the object if you took only right-angled turns. I'm wondering if there's something else I could do.

I also have a collision system, where essentially I turn objects into smaller objects on a smaller grid, kind of like a minimap, and only if objects exist in the same gridspace do I check for collisions. I could do that, only make the grid spacing larger to check for closeness. (Rather than checking every single object.) However, that would take additional setup in my base class and clutter up the already cluttered object.

tl;dr: Is there something efficient and accurate I could detect which object is closest, based on a list of points and sizes?

share|improve this question
    
to clear you question you have a list of points and a list objects and you want find the object that with minimum sum of distances to all the points? –  Ali.S Jul 1 '11 at 15:14
    
Store squared versions of x and y positions so you can do pythagoras theorem without having to do the expensive sqrt at the end. –  Jonathan Connell Jul 1 '11 at 15:31
3  
This is called a nearest neighbor search. There's plenty of writing on the internet about it. The usual solution is to use some sort of space-partitioning tree. –  BlueRaja - Danny Pflughoeft Jul 1 '11 at 16:00

4 Answers 4

up vote 28 down vote accepted

The problem with a quad/octree in nearest-neighbor searches is that the closest object may be sitting right across the division between nodes. For collisions, this is okay, because if it's not in the node, we don't care about it. But consider this 2D example with a quadtree:

Quadtree example

Here, even though the black item and green item are in the same node, the black item is closest to the blue item. ultifinitus' answer can only guarantee the nearest-neighbor only every item in your tree is placed in the smallest possible node that could contain it, or in a unique node - this leads to more inefficient quadtrees. (Note that there are many different ways to implement a structure which could be called a quad/octree - more strict implementations may work better in this application.)

A better option would be a kd-tree. Kd-trees have a very efficient nearest-neighbor search algorithm you can implement, and can contain any number of dimensions (hence "k" dimensions.)

A great and informative animation from Wikipedia: kd-tree nearest-neighbor search

The biggest problem with using kd-trees, if I recall correctly, is that they are more difficult to insert/remove items from while maintaining balance. Therefore, I would recommend using one kd-tree for static objects such as houses and trees which is highly balanced, and another which contains players and vehicles, which needs balancing regularly. Find the nearest static object and the nearest mobile object, and compare those two.

Lastly, kd-trees are relatively simple to implement, and I'm sure you can find a multitude of C++ libraries with them. From what I remember, R-trees are much more complicated, and probably overkill if all you need is a simple nearest-neighbor search.

share|improve this answer
1  
Great answer, small detail "an only guarantee the nearest-neighbor only every item in your tree is placed in the smallest possible node" I meant in my answer iterating over all items in the same and neighbour nodes, so you loop over 10 instead of 10.000. –  Roy T. Jul 2 '11 at 8:27
1  
Very true - I suppose "only" was a rather harsh word. There are definitely ways to coax quadtrees into nearest-neighbor searches depending on how you implement them, but if you're not using them for other reasons already (such as collision detection,) I'd stick with the more optimized kd-tree. –  dlras2 Jul 2 '11 at 8:56

You have to do spatial partitioning, in this case you make an efficient data structure (usually an octree). In this case each object is inside one or more spaces (cubes) And if you know in which spaces you are you can look up O(1) which spaces are your neighbors.

In this case the nearest object can be found by first iterating over all objects in your own space looking to which one is the closest there. If there is no-one there you can check your first neighbors, if no-one is there you can check their neighbors, etc...

This way you can easily find the nearest object without having to iterate through all objects in your world. As usual this speed gain does require a bit of bookkeeping, but it's really useful for all kinds of stuff so if you have a big world it's definitely worth implementing spatial partitioning and an octree.

As usual, see also the wikipedia article: http://en.wikipedia.org/wiki/Octree

share|improve this answer
6  
@ultifinitus To add to this: If your game is 2D you can use QuadTrees instead of Octrees. –  TravisG Jul 1 '11 at 16:13

sqrt() is monotonic, or order-preserving, for non-negative arguments so:

sqrt(x) < sqrt(y) iff x < y

And vice versa.

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt()-step from your Pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)²
pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)²
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

share|improve this answer
    
That metric is also referred to as the squared euclidean distance. –  moooeeeep Jul 31 at 15:42

Maybe try organizing your spatial data in an RTree, which is kind of like a btree for stuff in space and allows queries like "nearest N neighbors" etc... http://en.wikipedia.org/wiki/Rtree

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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