#algorithm #collision-detection
#алгоритм #обнаружение столкновений
Вопрос:
Предыстория:
Я нахожусь в начале создания игры, в ней есть объекты, которые должны иметь возможность взаимодействовать друг с другом с помощью «звука» (не обязательно реального звука, может быть имитированный звук, но он должен вести себя как звук).
Это означает, что они могут общаться друг с другом, только если находятся в пределах слышимости.
Вопрос:
Есть ли какой-нибудь умный способ проверить, находится ли другой объект в пределах слышимости, без необходимости перебирать все остальные объекты? (это стало бы действительно неэффективным, когда их много).
Примечание: в пределах слышимости может быть более 1 объекта, поэтому все объекты в пределах слышимости добавляются в массив (или список, еще не решил) для связи.
Данные
В настоящее время объект обладает этими свойствами (при необходимости их можно изменить).
Object {
id = self.id,
x = self.x,
y = self.y,
hearing_max_range = random_range(10, 20), // eg: 10
can_hear_other = []; // append: other.id when in other in range
}
Комментарии:
1. Какие языки / движки вы используете?
2. Разбивайте ваши объекты на квадратные ячейки шириной
hearing_range. Затем просто выполните итерацию по 9 окружающим ячейкам, сравнивая расстояние.3. @molamk Сейчас я создаю прототип в Game Maker, но позже, возможно, переключу язык, если это сработает так, как я надеюсь. Но язык на самом деле не имеет значения, используйте тот, который вам удобен, я понимаю большинство языков программирования, мне просто нужно знать, что я должен сделать, чтобы заставить его работать без перебора всего.
4.@DillonDavis Нравится виртуальная шахматная доска? что-то вроде:
bin_size = 10;index = floor(self.x / bin_size);global_bin_x[ index ] = self.id;а затем сделайте то же самое для Y и проверьте все записи, которые есть вindex 1 amp; -1, находятся ли они в диапазоне?5. @SebastianNorr по сути, да. Я бы использовал словарь, индексированный
(self.x//bin_size, self.y//bin_size)кортежами, но идея остается той же.
Ответ №1:
Вы могли бы изучить некоторые хитроумные структуры данных, такие как квадратичные деревья или kd-деревья, но для решения проблемы с запросом с фиксированным диапазоном, возможно, было бы неплохо просто использовать простое биннинг. Я представлю общий алгоритм в псевдокоде, подобном python.
Сначала создайте свои ячейки:
from collections import defaultdict
def make_bin(game_objects, bin_size):
object_bins = defaultdict(list)
for obj in game_objects:
object_bins[(obj.x//bin_size, obj.y//bin_size)].append(obj)
Затем запрашивайте по мере необходимости:
def find_neighbors(game_object, object_bins, bin_size):
x_idx = game_object.x // bin_size
y_idx = game_object.y // bin_size
for x_bin in range(x_idx - 1, x_idx 2):
for y_bin in range(y_idx - 1, y_idx 2):
for obj in object_bins[(x_bin, y_bin)]:
if (obj.x - game_object.x)**2 (obj.y - game_object.y)**2 <= bin_size**2:
yield obj