Quadtree для двумерного обнаружения столкновений

Я пытаюсь использовать дерево квадрантов для обнаружения 2D-столкновений, но я немного не понимаю, как его реализовать. Прежде всего, у меня было бы квадродерево, содержащее четыре поддерева (по одному, представляющее каждый квадрант), а также набор объектов, которые не помещаются в одно поддерево.

При проверке объекта на коллизии в дереве я бы сделал что-то вроде этого (спасибо QuadTree for 2D обнаружение столкновений):

  1. Проверьте объект на предмет столкновений с любыми объектами в текущем узле.
  2. Для любого поддерева, пространство которого перекрывает объект, используйте рекурсию.

Чтобы найти все столкновения в дереве квадрантов:

  1. Сравните каждый объект в текущем узле с другим объектом в текущем узле.
  2. Проверяйте каждый объект в текущем узле на каждое поддерево.

Чтобы вставить в квадродерево:

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

Чтобы обновить дерево квадрантов:

  1. Рекурсия в каждое поддерево.
  2. Если какой-либо элемент в текущем узле больше не умещается полностью в текущем дереве, переместите его в родительский.
  3. Если какой-либо элемент в текущем узле помещается в поддерево, вставьте его в поддерево.

Это нормально? Можно ли это улучшить?


data-structures collision game-physics quadtree
person bfops    schedule 13.02.2011    source источник
comment
Реализуйте это так, как вы это описываете, я сделал это так, и как это сделал Дэйв О., и это проще кодировать и быстрее. Управление большим количеством списков, чтобы отслеживать все оставленные вами листы, увеличивает накладные расходы, которых можно избежать. Вот источник (на Java) одной из моих версий: Steerio   -  person ClickerMonkey    schedule 12.09.2013

Ответы (3)


arrow_upward
38
arrow_downward

Ваша структура квадродерева не оптимальна. Вы правы, храня 4 поддерева на узел, но фактические объекты должны храниться только внутри листьев, а не внутренних узлов. Поэтому коллекцию, содержащую фактические объекты, необходимо переместить на листья.

Давайте посмотрим на реализацию операций:

  1. Вставьте объект в квадродерево:
    Проверьте, пересекает ли объект текущий узел. Если да, то рекурсивно. Если вы достигли конечного уровня, вставьте объект в коллекцию.
  2. Удаление объекта из квадродерева:
    Выполните те же действия, что и при вставке объекта, но когда вы достигнете конечного уровня, удалите его из коллекции.
  3. Проверьте, пересекает ли объект какой-либо объект внутри квадродерева:
    Выполните те же шаги, что и при вставке объекта, но когда вы достигнете конечного уровня, проверьте на столкновение со всеми объектами в Коллекция.
  4. Проверка всех столкновений между всеми объектами внутри квадродерева:
    Для каждого объекта в квадродереве выполните тест на столкновение одного объекта.
  5. Обновите дерево квадрантов:
    Удалите все объекты из дерева квадрантов, положение которых было изменено, и вставьте их снова.

У этого есть несколько преимуществ:

  • Сохраняя объекты только в листьях, очень легко обрабатывать операции с деревом квадрантов (меньше особых случаев).
  • У квадродерева могут быть листья разной глубины, что позволяет вам адаптировать плотность квадродерева в зависимости от пространственной области, которую оно покрывает. Эта адаптация может происходить во время выполнения, таким образом поддерживая оптимальное соотношение объект / узел.

Только недостаток:

  • Объекты могут принадлежать нескольким коллекциям внутри квадродерева. Вам понадобится дополнительная линейная коллекция вне квадродерева, чтобы перечислить каждый объект без дубликатов.
person Dave O.    schedule 13.02.2011
comment
Меня беспокоит этот лишний недостаток. Не приведет ли это к добавлению дополнительного кода (например, линейной коллекции вне квадродерева), чтобы гарантировать, что A только один раз столкнется с B, даже если B может быть в нескольких поддеревьях? - person bfops; 13.02.2011
comment
@RobotGymnast Столкновение не является проблемой, поскольку вы возвращаете только истину / ложь, и если объект принадлежит нескольким наборам, он по-прежнему идентичен для них. Перечисление есть. Вы не можете использовать квадродерево для просмотра всех ваших объектов, потому что вы посетите некоторые из них несколько раз. - person Dave O.; 14.02.2011
comment
Это может быть наивно, но как насчет добавления к объектам функции типа touched ()? Таким образом, во время обхода, когда объект был проверен, вы можете установить флаг касания и, таким образом, игнорировать его, если он вернется? Я знаю, что это может быть не совсем чистый или даже элегантный метод, но он кажется достаточно простым, и я использовал его для большого эффекта с моими реализациями квадродерева. - person leeor_net; 30.07.2013
comment
Еще один недостаток, который я только что обнаружил, заключается в том, что если у вас есть четыре больших объекта, скажем, покрывающих все дерево, оно будет делиться на части, пока вы не достигнете предела глубины. Добавьте пятый, и без сложной обработки крайних случаев он выйдет из строя. - person Rei Miyasaka; 02.06.2019
comment
Еще один заключается в том, что вычисление ограничивающего прямоугольника для многих объектов (линий, окружностей, прямоугольников, даже многоугольников) намного дешевле и тривиальнее, чем вычисление пересечений. - person Rei Miyasaka; 02.06.2019

arrow_upward
11
arrow_downward

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

Есть и другие совершенно другие подходы, которые могут быть даже лучше. Например, вы можете попробовать реализовать алгоритм Зомородиана и Эдельсбруннера, как я сделал в следующем модуле:

Вот несколько статей, которые я написал, в которых эти вопросы обсуждаются более подробно:

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

person Mikola    schedule 15.06.2015
comment
эти сообщения в блоге превосходны. некоторые из лучших сведений по этой теме, которые я нашел - person Asad-ullah Khan; 08.01.2021

arrow_upward
0
arrow_downward

Я еще не уверен, насколько он эффективен, но, похоже, он отлично работает с моим основным дуэтом в eclipse, все еще работает со скоростью более 2400 кадров в секунду, смеется ..

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

получить ссылки на все остальные объекты в одной ячейке очень просто:

list temp_checklist = object.cells[cell_index].objects
//('objects' being some sort of array or list of object references as described above)

надеюсь, что это кому-то поможет;)

person Lazouskie    schedule 08.05.2014