Identifying groupings of objects

Question

I have a cloud of objects, each with a 3D position, and I want to pick out tight groups of these objects.

Specifically, I want to find all objects which form a grouping of radius r within a large cloud of objects. It is likely that the objects are spaced out in vague groupings already, but I need to identify these and essentially put a sphere of radius r around them.

I would prefer to avoid a brute force method if possible - which I presume would be a process of comparing objects against each other to find two within a distance 2r of each other, then putting a sphere in the middle and determining what other objects are within this sphere.

My actual use case is not games related at all, but if an game based example use case would help, here is how I might use it in a game;

The player is flying a plane over a battlefield and has been given orders to bomb the enemy.

To assist the player I want to highlight tight groups of enemies that make prime targets, however the troops on the ground do not move or coordinate in a flocking system, they move completely as individual entities.

Given those criteria, how might I identify the largest groups of objects within the bomb's blast radius?

Answer 1

To avoid brute-forcing, you could store the coordinates of your objects in a three-dimensional tree data-structure like a kd-tree or an AABB tree. These data-structures are very efficient at getting all objects withing a certain box-shaped area. To get all objects within a sphere-shaped area, you could first get all objects within a box which is large enough to contain the sphere to get a pre-selection.

But before you invest all that effort: Are you sure it actually matters? Did you measure it with a profiler? When your number of objects isn't very high, a n² algorithm which calculates the distance between every object and every other object might not actually be so slow that the player notices a framerate drop.

Answer 2

A kd-tree or AABB tree is a great data structure, if the objects are going to be static, or mostly static, as they are not cheap to update.

But it seems like those structures would be more useful to find what's around a certain point, rather than to figure out the largest cluster of objects.

For that, I'd use a simple grid. Have each object register itself in a square in a rectangular grid. This will effectively simplify the problem, so you can then go and score each square based on how many objects there are inside, plus some factor from the neighbors. The complexity will be related to the number of squares in your grid, instead of the number of objects in the map.

And as objects move around, you just remove that object from a square, and add it to another.

Finally, the grid will also allow you to run queries to find objects near a point if you want, by considering more than one square and then calculating distances with the objects inside it.

Answer 3

The other's have suggested kd tree's but I think that a more appropriate data structure for you would be using an R-Tree which is specifically for retrieving collections of near objects.

You can find out more here: http://en.wikipedia.org/wiki/R-tree

Answer 4

A high-powered family of algorithms you may need to look into are all "clustering" algorithms. These algorithms find groups of data points which could be Cartesian points or any other property (color, weight, etc.).

See K-means Clustering for one such algorithm. It's not a terrible algorithm to run in real-time, depending on how many entities you need to compare and how often you need to run it. Since there's presumably only one player and you only need to identify clusters nearby to the player, you shouldn't have much trouble with this algorithm.

There are other simpler algorithms to this, though I'd just start with k-means until you have firm evidence that it won't work for you.