поиск объектов в радиусе

Question

Ищите легкий способ поиска объектов в радиусе.

До сих пор для меня очевидным является ответ через каждый объект, сравнивающий его положение x и y с центром радиуса.

Пример:

Turret - ищет цели в радиусе.

TargetArray - массив возможных целей.

WithinRangeArray - массив мы помещаем применимую к цели

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

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

Избежанию квадратного корня должен сохранить мне вычислительную мощность. Но у меня есть ощущение, что могут быть другие алгоритмы/теории/методы, которые могут быть лучше (более легкие).

Идеальная длина TargetArray: менее 500 целей одновременно.

Answer 1

Прежде чем рассчитать радиальное расстояние, сначала проверьте, находится ли объект внутри коробки, расположенной по центру вашего места на башне. Если target_x < turret_x-range, то он выходит за пределы диапазона и не нужно проверять расстояние, также проверьте диапазон turret_x +, turret_y-range, turret_y + range. Для этого требуется максимум 4 сравнения и 4 команды add/subtract, чтобы определить, находится ли цель в поле.

Answer 2

В 2D вы можете реализовать Quadtree и в 3D вы можете реализовать Octree, что означает, что вы сможете группировать объекты и более эффективно отбрасывать большие группы из них, прежде чем проверять их точное расстояние. Если вы хотите узнать больше, вы должны сделать для них Google. Они являются очень полезными структурами данных для миров объектов.

Окончательная реализация не может сэкономить место, но это будет невероятно быстро, потому что вы можете очень быстро отбросить огромное количество объектов.

Answer 3

Вы можете сохранить возможные цели в мультимножестве, набранном на квадрат сетки, который они занимают. Затем вам нужно только перебирать цели, которые находятся в квадратах сетки, достаточно близко к квадрату решетки башни, чтобы они могли быть мишенями.

Независимо от того, стоит ли это делать, зависит от количества целей и количества целей, которые могут иметь диапазон. Я работаю над приложением с сотнями тысяч целей, из которых только 10 или 20, вероятно, будут в пределах диапазона. В этой ситуации стоит инвестировать в значительную сложность, чтобы сократить потенциальный целевой список. В вашем случае, имея всего 500 целей, это может оказаться нецелесообразным.