Широкополосные методы обнаружения столкновений?

Ответ 1

Наилучший подход зависит от конкретного использования, но суть в том, что вы хотите разделить ваше мировое пространство таким образом, чтобы (a) каждое тело находилось ровно в одном подразделении, (b) каждое подразделение достаточно велико, чтобы aa тело конкретное подразделение может сталкиваться только с телами в том же подразделении или смежным подразделением, и (в) количество тел в определенном подразделении как можно меньше.

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

Если вы имеете дело с телами, движущимися в более широком открытом мире, простая сетка станет довольно податливой, и вам, вероятно, понадобится какая-то древовидная структура, такая как квадранты, как предлагает Арриу.

Если вы говорите о перемещении тел в ограниченных пространствах вместо открытых пространств, вы можете рассмотреть Дерево BSP; дерево разбивает мир на "пространство, в которое вы можете ходить" и "стены", и отсечение тела в дерево определяет, находится ли оно в законном положении. В зависимости от геометрии мира вы также можете использовать BSP для вашего широкофазного обнаружения столкновений между телами в мире.

Другим вариантом для тел, движущихся в ограниченном пространстве, будет механизм портала; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо "порталом" в другое вогнутое пространство, вы можете легко определить, находится ли тело в области с тестом "точка-в-полигоне" и упростить обнаружение столкновений, только глядя на тела в той же области или связанных областях.

Ответ 2

Альтернативой QuadTrees или BSPTrees являются SphereTrees (CircleTrees в 2D, реализация будет более или менее одинаковой). Преимуществом SphereTrees является то, что они отлично справляются с большими нагрузками динамических объектов. Если вы постоянно перемещаете объекты, BSPTrees и QuadTrees будут намного медленнее в своих обновлениях, чем дерево Sphere/Circle.

Если у вас есть хорошее сочетание статических и динамических объектов, разумно хорошим решением является использование QuadTree/BSPTree для статики и дерева Sphere/Cicle для динамических объектов. Просто помните, что для любого заданного объекта вам нужно будет проверить его на деревья.

Ответ 3

Я рекомендую quadtree разбиение. Это довольно просто и работает очень хорошо. Вот Flash demo обнаружения столкновений грубой силы против обнаружения столкновения квадрантов. (Вы можете сказать ему, чтобы показать структуру квадрантов.) Вы заметили, что обнаружение столкновения с помощью quadtree составляет всего 3% от грубой силы в этой демонстрации?

Кроме того, если вы серьезно относитесь к своему движку, я настоятельно рекомендую вам выбрать обнаружение конфликтов в режиме реального времени. Это не дорого, и это действительно замечательная книга, которая охватывает все, что вы когда-либо хотели бы знать. (Включая обнаружение столкновений на основе GPU.)

Ответ 4

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

• Пространственное разбиение. Вырезать место и дешево исключить кандидатов, которые находятся в разных регионах. Например, BSP, сетки, octrees и т.д.

• Разделение объектов. Подобно # 1, но кластеризация сосредоточена на самих объектах больше, чем пространство, в котором они находятся. Например, ограничивающие иерархии томов.

• Сортировка и развертка. Поместите объекты в порядок пространственно и исключите столкновений между соседними.

1 и 2 часто являются иерархическими, рекурсивными в каждый раздел по мере необходимости. С помощью 3 вы можете выполнить итерацию по разным размерам.

Компромиссы сильно зависят от геометрии сцены. Разделяют ли объекты кластеры или они равномерно распределены? Все ли они примерно одного размера или существуют огромные различия в размере? Является ли сцена динамичной? Можете ли вы позволить себе много времени предварительной обработки?

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

Ответ 5

Альтернативой являются простые сетки, например 20x20 или 100x100 (в зависимости от вашего мира и объема памяти). Реализация проще, чем рекурсивная структура, такая как quad/bsp-tree (или деревья сферы в этом случае).

В этом случае объекты, пересекающие границы ячеек, в этом случае немного проще и не вырождаются так сильно, как это может сделать наивная реализация bsp/quad/oct-tree.

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

Ответ 6

Я просто придумал решение, которое не зависит от размера сетки и, возможно, O (nlogn) (это оптимально, когда нет столкновений), хотя хуже всего в O (nnlogn) (когда все сталкивается).

Я также внедрил и протестировал его, вот ссылка на источник . Но я не сравнивал его с решением грубой силы.

Описание того, как это работает:   (Я ищу столкновения прямоугольников)

• по оси x Я сортирую прямоугольники в соответствии с их правым краем (O (nlogn))

• для каждого прямоугольника в отсортированном списке Я беру левый край и выполняю двоичный поиск до тех пор, пока не нахожу крайний правый край слева от левого края и не вставляю эти прямоугольники между этими индексами в набор возможных_Collision_On_X_Axis (это n прямоугольников, logn для двоичного поиска, n вставляет int в набор в O (log n) для каждой вставки)

• на оси y Я делаю то же самое

• в каждом из множеств у меня теперь есть возможные столкновения на x (в одном наборе), а на y (int другой), я пересекаю эти множества, и теперь у меня есть столкновения как по оси x, так и по оси y (это означает, что я беру общие элементы) (O (n))

Извините за плохое описание, надеюсь, вы лучше поняли источник, а также пример, проиллюстрированный здесь: image

Ответ 7

Вы можете проверить, что Скотт сделал в Chipmunk с пространственным хешированием. Источник свободно доступен. Я думаю, что он использовал аналогичную технику Box-2D, если не для столкновения, определенно для сохранения контакта.

Ответ 8

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

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

Преимущество этого подхода в отношении более адаптивного алгоритма (например, BSP, Quadtree, Circletree) заключается в том, что к ячейкам можно получить доступ в O (1) время (то есть постоянное время), а не O (log N) время (то есть логарифмическое время). Однако эти последние алгоритмы способны адаптироваться к большой изменчивости плотности объектов. Подход к сетке лучше всего работает, когда плотность объекта довольно постоянна по всему пространству.

Ответ 9

Я хотел бы рекомендовать вступительную ссылку на физику игры от Яна Миллингтона, Game Engine Engine Development. Он имеет большой раздел по широкополосному обнаружению столкновения с образцом кода.

Ответ 10

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

Основная идея: вы создаете рекурсивную древовидную структуру, в которой хранятся дочерние объекты 4 (для четырех) или 8 (oct) того же типа, что и корень дерева. Каждый node в дереве представляет собой раздел декартового пространства, например, -100 → +100 на каждой применимой оси. каждый дочерний элемент представляет это же пространство, но подразделяется на половину (непосредственный ребенок примера будет представлять, например, -100- > 0 на оси X и -100- > 0 на оси Y).

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

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

Итак, прежде чем вы начнете и попытаетесь реализовать такой алгоритм, как вы:

Сколько объектов в моей игре? Если их много, мне, вероятно, нужна широкая фаза. Если нет, то Nnarrowphase должно быть достаточно. Кроме того, я имею дело со многими движущимися объектами?

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

Если это так, вам было бы лучше с Sweep и Prune, которая поддерживает минимальные/максимальные кучи экстентов фигур в вашем мире. Объекты не нужно вставлять повторно, но кучи нужно прибегать к каждому кадру, считая, что это обычно быстрее, чем дерево, обход с удалением и повторным вводом.

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