performance - How to continuously find all entities within a radius efficiently?

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

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[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).