Пространственная структура данных для игр

Question

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

До сих пор я разрабатывал Quad Tree, чтобы сократить пространство поиска, но поскольку это для игры, все движущиеся объекты должны будут обновить свою позицию в дереве.Вернуться к началу.

Существуют ли какие-либо структуры данных или методы, которые могут помочь?Потребуется обработать около 10 000 объектов, поэтому грубая сила недостаточно хороша.

Answer 1

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

Логически этот тест делит пространство на регулярную сетку.Каждая ячейка сетки помечена списком объектов, которые пересекают эту ячейку.Сетка инициализируется путем сканирования всех объектов.Я не знаю javascript, поэтому я буду использовать псевдокод python-ish.

for each ob in objects:
  for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
    for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
      hashtable[hash(x, y)].append(ob)

Чтобы найти коллизии с заданным объектом, найдите почти коллизии в хеш-таблице и затем примените точный тест коллизийкаждому.

near_collisions = []
for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
  for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
    near_collisions = near_collisions ++ hashtable[hash(x, y)]

remove duplicates from near_collisions

for each ob2 in near_collisions:
  if exact_collision_test(ob, ob2):
    do_something

Answer 2

Вы все еще можете использовать квадродерево, даже если у вас есть движущиеся объекты - просто удалите и заново вставьте объект каждый раз, когда он перемещается или каждый раз, когда он пересекает границу региона.

Но квадродерева не очень хороши для хранения прямоугольников, и я бы рекомендовал вместо этого использовать R-дерево .