How to continuously find all entities within a radius efficiently?

Question

I have a very large number of entities (units). On each step, each unit needs to know the positions of all units near it (distance is less then given constant R). All units move continuously. This is in 3D.

On average, there will be 1% of the total unit count near any other given unit with the given constraints.

How can I do this efficiently, without bruteforcing?

Answer 1

Use one of the common space partitioning algorithms, such as a Quadtree, Octree, BSP tree, or even a simple Grid System. Each has their own pros and cons for each specific scenario. You may read more about them in these books.

Generally (or so I've heard, I'm not too familiar with the reasoning behind this) a Quadtree or Octree is better fit for outdoor environments, while the BSP tree fits indoor scenes better. And the choice between using a Quadtree or an Octree depends on how flat your world is. If there's little variation in the Y axis using an Octree would be wasteful. An Octree is basically a Quadtree with an additional dimension.

Finally, don't disregard the simplicity of the Grid solution. Many people ignore that a simple grid can sometimes be enough (and even more efficient) for their problems, and jump straight to a more complex solution instead.

Using a grid consists simply in dividing the world into evenly spaced regions and storing the entities in the appropriate region of the world. Then, given a position, finding the neighbouring entities would be a matter of iterating over the regions that intersect your radius of search.

Let's say your world ranged from (-1000, -1000) to (1000, 1000) in the XZ plane. You could for instance divide it into a 10x10 grid, like so:

var grid = new List<Entity>[10, 10];

Then you'd place entities into their appropriate cells in the grid. For instance an entity with XZ (-1000, -1000) would fall on cell (0,0) while an entity with XZ (1000, 1000) would fall on cell (9, 9). Then given a position and a radius in the world, you could determine which cells are intersected by this "circle" and iterate only over those, with a simple double for.

Anyway, research all of the alternatives and pick the one that seems to fit your game better. I admit I'm still not knowledgeable enough on the subject to decide which of the algorithms would be best for you.

Edit Found this on another forum and it might help you with the decision:

Grids work best when the vast majority objects fit within a grid square, and the distribution is fairly homogenous. Conversely, quadtrees work when the objects have variable sizes or are clustered in small areas.

Given your vague description of the problem, I'm leaning against the grid solution too (which is, assuming units are small and fairly homogeneously distributed).

Answer 2

I wrote this some time back. It's now on a commercial site, but you can get the source for personal use for free. It may be overkill and it's written in Java, but it's well documented so it should not be too hard to trim and rewrite in another language. It basically uses an Octree, with tweaks to handle really large objects and multi-threading.

I found an Octree offered the best combination of flexibility and efficiency. I started out with a grid, but it was impossible to size the squares properly and large patches of empty squares used up space and computing power for nothing. (And that was just in 2 dimensions.) My code handles queries from multiple threads, which adds a lot to the complexity, but the documentation should help you work around that if you don't need it.

Answer 3

To boost your efficiency, try to trivially reject the 99% of "units" that are not near the target unit using a very inexpensive bounding box check. And I would hope you could do this without structuring your data spatially. So if all your units are stored in a flat data structure you could try to race through it from start to finish and firstly check is the current unit outside the bounding box of the unit of interest.

Define an oversized bounding box for the unit of interest such that it can safely reject items that have no chance of being considered "near" it. The check for exclusion from a bounding box could be made cheaper than a radius check. However on some systems where this was tested it was found not to be the case. The two perform almost equally. This edited after much debate below.

First: 2D bounding box clip.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

Compared with something like this (in 3D):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

If the object is not trivially rejected then you perform a more expensive and accurate collision test. But you are just looking for nearnesss so the sphere test is suitable for that, but only for the 1% of objects that survive the trivial rejection.

This article supports the box for trivial rejection. http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

If this linear approach doesn't give you the performance you need, then a hierarchical data structure may be required such as the other posters have been talking about. R-Trees are worth considering. They support dynamic changes. They are the BTrees of the spatial world.

I just didn't want you going to all that trouble of introducing such complexity if you could avoid it. Plus what about the cost of keeping this complex data strucure up to date as objects move around several times per second?

Bear in mind that a grid is a one level deep spatial data structure. This limit means that it is not truly scaleable. As the world grows in size, so do the number of cells you need to cover. Eventually that number of cells itself becomes a performance problem. For a certain sized world however, it will give you a massive performance boost over no spatial partitioning.

Answer 4

I have to make this an answer because I don't have the points to comment or upvote. For 99% of the people who ask this question, a bounding box is the solution, as described by Ciaran. In a compiled language, it will reject 100,000 irrelevent units in the blink of an eye. There's a lot of overhead involved with non-brute-force solutions; with smaller numbers (say under 1000) they'll be more expensive in terms of processing time than brute force checking. And they'll take vastly more programming time.

I'm not sure what "a very large number" in the question means, or what other people looking here for answers will mean by it. I suspect my numbers above are conservative and could be multiplied by 10; I am personally quite prejudiced against brute force techniques and am seriously annoyed at how well they work. But I wouldn't want someone with, say, 10,000 units to waste time with a fancy solution when a few quick lines of code will do the trick. They can always get fancy later if they need to.

Also, I would note that a bounding sphere check requires multiplication where the bounding box does not. Multiplication, by its nature, takes several times as long as addition and comparisons. There's bound to be some combination of language, OS, and hardware where the sphere check will be faster than a box check, but in most places and times the box check has to be faster, even if the sphere does reject a few irrelevant units the box accepts. (And where the sphere is faster, a new release of the compiler/interpreter/optimizer is very likely to change that.)