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

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-tree.