android - Efficiently detecting objects inside multiple radius

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

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