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

StackOverflow https://stackoverflow.com/questions/1569220

  •  21-09-2019
  •  | 
  •  

Вопрос

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

До сих пор ответ, который является для меня очевидным, - это пройти через каждый объект, сравнивая его положение 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 целей за раз.

Это было полезно?

Решение

Прежде чем вычислять радиальное расстояние, сначала проверьте, находится ли объект в центре ящика в месте вашего места башни. Если gartic_x <range range turret_x, то это не в диапазоне и не нужно проверять расстояние, также проверьте диапазон Turret_x+, Turret_y-Range, диапазон Turret_y+. Для этого требуется максимум 4 сравнения и 4 добавления/вычесть OPS, чтобы определить, находится ли цель в коробке.

Другие советы

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top