finding objects within radius.

Question

looking for a light weight way to find objects within a radius.

so far the answer that is obvious to me is go through each object, comparing its x and y position, with the center of the radius.

example:

Turret - looking for targets in radius. TargetArray - array of possible targets.

WithinRangeArray - array we push applicable targets to

Distance^2 = (TargetArray[n].x - Turret.x)^2 + (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){ WithinRangeArray.push(TargetArray[n]) }

avoiding the square root should save me some processing power. But i have the feeling there may be other algorithms/theories/methods that may be better (more light weight).

Language: Flash AS3

Ideal length of TargetArray: fewer than 500 targets at a time.

Answer 1

In 2D you could implement a Quadtree and in 3D you could implement an Octree which means that you would be able to group objects and more efficiently discard large groups of them before actually checking up on their exact distances. You should google for them if you want to know more. They are very useful data structures for worlds of objects.

The final implementation may not save space as much but it will be incredibly fast because you can discard a vast number of objects very quickly.

Answer 2

I highly recommend this article for ideas

Answer 3

You could store the possible targets in a multiset keyed on the grid square they occupy. Then you need only iterate over the targets which are in grid squares close enough to the turret's grid square that they might be targets.

Whether or not this is worth doing, depends on the number of targets and the number of targets that are likely to be withing range. I am working on an application with hundreds of thousands targets, of whith only 10 or 20 are likely to be withinn range. In this situation, it is worthwhile to invest in significant complexity to prune the potential target list. In you case, with just 500 targets it may well not be worthwhile.

Answer 4

Before you calculate radial distance, first check to see if the object is within the box centered on your turret location. If the target_x < turret_x-range then it's out of range and no need to check distance, also check turret_x+range, turret_y-range, turret_y+range. That requires a maximum of 4 comparisons and 4 add/subtract ops to determine whether the target is in the box.