Подтвердить что ты не робот

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

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

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

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

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

  • Проверяйте каждый объект в текущем node на каждый другой объект в текущем node.
  • Проверяйте каждый объект в текущем node на каждое поддерево.

Вставить в квадрат:

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

Чтобы обновить quadtree:

  • Считайте в каждом поддереве.
  • Если какой-либо элемент текущего node больше не подходит полностью в текущем дереве, переместите его в родительский.
  • Если какой-либо элемент текущего node вписывается в поддерево, вставьте его в поддерево.

Это хорошо? Можно ли улучшить?

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

  • Вставить объект в квадрат:
    Проверьте, пересекает ли объект текущий node. Если да, рекурсия. Если вы достигли уровня листа, вставьте объект в коллекцию.
  • Удалить объект из quadtree:
    Выполните те же шаги, что и вставки объекта, но когда вы достигли уровня листа, удалите его из коллекции.
  • Проверить, пересекает ли объект какой-либо объект внутри quadtree:
    Выполните те же действия, что и вставка объекта, но когда вы достигли уровня листа, проверьте наличие конфликта со всеми объектами в коллекции.
  • Тест для всех столкновений между всеми объектами внутри quadtree:
    Для каждого объекта в квадратике выполните односторонний столкновение.
  • Обновить квадрант:
    Удалите все объекты из квадранта, положение которых было изменено, и вставьте их снова.

Это имеет ряд преимуществ:

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

Только disatvantage:

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

Ответ 2

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

Существуют и другие совершенно разные подходы, которые могут быть еще лучше. Например, вы можете попробовать реализовать алгоритм Zomorodian и Edelsbrunner, как это было в следующем модуле:

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

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

Ответ 3

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

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

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

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

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