Efficiently detecting objects inside multiple radius

Question

I would like to create a game for mobile that require to calculate multiple time by seconds which moving objects are in the radius of moving points. The game is highly inspired from Gratuitous Space Battles, the radius being from the weapons. Thus, I would like to know if it's realist to expect to be able to know among 1000 moving objects, in which radius they are among 1000 moving points 100 times per seconds on an average android device. In term of complexity, if there is an algorithm better than O(N*M), N being the number of moving objects and M the number of radius from M moving center and if an algorithm can benefit from the fact that the moving objects are near their precedent position.

Answer 1

You might be interested in a so called quad tree. A quad tree is basically a structure where you divide the area in boxes and put all objects in lists on these boxes. You can then check for collisions only in the boxes that are actually in range of the object. The advantage of quad trees over say 2d arrays is that you they scale very well, if you have a large area with nothing in it and a small area with a lot in it then most other solutions will not work as well. This is how to maintain a simplified quad tree:

1 If a box loses an object check if it's now to small, if it is merge it with another square

2 if a box gains an object see if it's now to large if it is split, if you split an object always do so by spiting it over the largest side (a 10-20 should be split along side the 20 axis) and at such a position that both boxes now contain an equal number of objects.

3 Every box stores in it all of it's neighboring boxes and each object stores in which square it currently is.

Now if you want to check if an object is in range start by checking if it's box is in range if it is check for each of the objects in the box if they are in range and then check repeat this check for all neighboring boxes (recursive).

This does however carry a bit of overhead so if your range is likely to be larger then say 25% of the map it usually slows things down.

I think that what a game as Gratuitous Space Battles (at least for ai) does it first check if a ship is in range (any part of a ship is in range use a square for this) and then check each individual part. What most real games do is use a combination where large scale AI calculations are ran on the second system and the first is used for collision detection (and short ranged stuff).

Answer 2

First, do a preselection

When a weapon has a low range, it usually doesn't make much sense to check it for collisions with objects at the other end of the world. You can drastically reduce the number of comparisons when you can narrow it down to objects in local vicinity.

One option is to use a two-dimensional tree structure. These usually allow you to very efficiently iterate all objects in a rectangular area. When you first get all objects in a box as large as your circle and then check each result accurately with the pythagorean theoreme, you can often save a lot of CPU cycles.

Another alternative to a 2d tree which is less elegant but easier to implement is a chunk-based approach. Divide the map into a raster of chunks n pixels wide and high represented by a two-dimensional array of object-lists. When an object moves from one chunk to another, remove it from the list of the old chunk and add it to that of the new chunk. A low-range attack should usually only be able to affect a limited number of chunks, so you only need to check the object-lists of a few adjacent ones.

The ideal value for n depends on your game. When you pick it too large, you still need to check too many objects. When you pick it too small, you spend too many cycles managing chunk-transitions. The ideal size depends on how much your objects move around, how large the distances of usual range-checks are and how likely objects are to form clusters.

Second, store ranges already squared

On most platforms, the most expensive part of the pythagorean theorem dist = sqrt(distx * distx + disty * disty) is calculating the square-root. You can optimize this by calculating the square of the range of every weapon once in advance and then skip the square-root calculation. This, however, only works under the assumption that your range-checks are simply binary in-range-or-not-in-range and you don't need the exact distance.

Third, do you really need to check everything for everything 100 times per second?

You definitely want to run your movement at the full framerate so the animation looks fluid. But that doesn't mean that all interactions between objects also need to be checked that often. Checking for collisions only every n-th frame can sometimes be enough for some use-cases.

For AI, for example, it can make sense to run the decision-making only once per second. This results in a delayed reaction to events which even feels more natural and human than an instant reaction.