Методы обнаружения столкновений с широкой фазой?
8 ответов
Наилучший подход зависит от конкретного использования, но суть в том, что вы хотите подразделить свое мировое пространство так, чтобы (а) каждое тело находилось ровно в одном подразделении, ( б) каждое подразделение достаточно велико, чтобы тело в конкретном подразделении могло столкнуться только с телами в этом же подразделении или смежном подразделении, и (в) количество тел в конкретном подразделении как можно меньше.
Как вы это делаете, зависит от того, сколько у вас тел, как они движутся, каковы ваши требования к производительности и сколько времени вы хотите потратить на свой двигатель. Если вы говорите о телах, перемещающихся в основном в открытом пространстве, простейшим способом было бы разделить мир на сетку, каждая ячейка которой больше вашего самого большого объекта, и отслеживать список объектов в каждой ячейке. Если вы создаете что-то в масштабе классической аркадной игры, этого решения вполне может хватить.
Если вы имеете дело с телами, движущимися в большом открытом мире, простая сетка довольно быстро станет подавляющей, и вы » Возможно, мне понадобится какая-то древовидная структура, такая как четырехугольные деревья, как предлагает Арриу.
Если вы говорите о перемещении тел в ограниченном пространстве вместо открытого пространства, тогда вы можете рассмотреть BSP-дерево ; дерево делит мир на «пространство, в котором вы можете ходить» и «стены», и вырезание тела на дереве определяет, находится ли оно в правильном положении. В зависимости от геометрии мира вы также можете использовать BSP для широкого фазового обнаружения столкновений между телами в мире.
Другим вариантом для тел, движущихся в ограниченном пространстве, может быть портальный движок; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо «порталом» в другое вогнутое пространство, вы можете легко определить, находится ли тело в пределах области с помощью теста точки в многоугольнике и упростить обнаружение столкновений, глядя только на тела в одной и той же области или связанных областях.
пространство, в которое вы можете ходить, и стены, и вырезание тела на дереве определяет, находится ли оно в правильном положении. В зависимости от геометрии мира вы также можете использовать BSP для широкого фазового обнаружения столкновений между телами в мире.Другим вариантом для тел, движущихся в ограниченном пространстве, может быть портальный движок; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо «порталом» в другое вогнутое пространство, вы можете легко определить, находится ли тело в пределах области с помощью теста точки в многоугольнике и упростить обнаружение столкновений, глядя только на тела в одной и той же области или связанных областях.
пространство, в которое вы можете ходить, и стены, и вырезание тела на дереве определяет, находится ли оно в правильном положении. В зависимости от геометрии мира вы также можете использовать BSP для широкого фазового обнаружения столкновений между телами в мире.Другим вариантом для тел, движущихся в ограниченном пространстве, может быть портальный движок; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо «порталом» в другое вогнутое пространство, вы можете легко определить, находится ли тело в пределах области с помощью теста точки в многоугольнике и упростить обнаружение столкновений, глядя только на тела в одной и той же области или связанных областях.
вы также можете использовать BSP для широкого фазового обнаружения столкновений между телами в мире.Другим вариантом для тел, движущихся в ограниченном пространстве, может быть портальный движок; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо «порталом» в другое вогнутое пространство, вы можете легко определить, находится ли тело в пределах области с помощью теста точки в многоугольнике и упростить обнаружение столкновений, глядя только на тела в одной и той же области или связанных областях.
вы также можете использовать BSP для широкого фазового обнаружения столкновений между телами в мире.Другим вариантом для тел, движущихся в ограниченном пространстве, может быть портальный движок; если ваш мир может состоять из выпуклых многоугольных областей, где каждая сторона многоугольника является либо сплошной стеной, либо «порталом» в другое вогнутое пространство, вы можете легко определить, находится ли тело в пределах области с помощью теста точки в многоугольнике и упростить обнаружение столкновений, глядя только на тела в одной и той же области или связанных областях.
Я рекомендую quadtree разбиение на разделы. Это довольно просто и действительно хорошо работает. Вот демонстрация Flash обнаружения столкновений методом грубой силы по сравнению с обнаружением столкновений деревьев квадрантов. (Вы можете указать ему показать структуру дерева квадрантов.) Вы заметили, что обнаружение столкновений деревьев квадрантов составляет всего 3% от грубой силы в этой демонстрации?
Кроме того, если вы серьезно относитесь к своему движку, я настоятельно рекомендую вам выбрать обнаружение столкновений в реальном времени . Это не дорого, и это действительно отличная книга, охватывающая все, что вы когда-либо хотели бы знать. (Включая обнаружение столкновений на базе GPU.)
An alternative to QuadTrees or BSPTrees are SphereTrees (CircleTrees in 2D, the implementation would be more or less the same). The advantage that SphereTrees have are that they handle large loads of dynamic objects very well. If you're objects are constantly moving, BSPTrees and QuadTrees are much slower in their updates than a Sphere/Circle Tree would be.
If you have a good mix of static and dynamic objects, a reasonably good solution is to use a QuadTree/BSPTree for the statics and a Sphere/Cicle Tree for the dynamic objects. Just remember that for any given object, you would need to check it against both trees.
Все алгоритмы ускорения зависят от использования недорогого теста для быстрого исключения объектов (или групп объектов) и, таким образом, сокращения количества дорогостоящих тестов, которые вам нужно выполнять. Я рассматриваю алгоритмы по категориям, каждая из которых имеет множество вариаций.
Пространственное разбиение. Выделите место и дешево исключите кандидатов из разных регионов. Например, BSP, сетки, октодеревья и т. Д.
Разделение объектов. Подобно №1, но кластеризация сосредоточена на самих объектах больше, чем на пространстве, в котором они находятся. Например, ограничивающие иерархии томов.
Методы сортировки и поиска. Расположите объекты в пространственном порядке и исключите конфликты между несмежными объектами.
1 и 2 часто являются иерархическими, рекурсивно повторяющимися в каждом разделе по мере необходимости. С 3 вы можете при желании перебирать разные измерения.
Компромиссы во многом зависят от геометрии сцены. Объединяются ли объекты в кластеры или они распределены равномерно или редко? Все ли они примерно одинакового размера или есть огромные различия в размерах? Сцена динамична? Можете ли вы позволить себе много времени на предварительную обработку?
«Недорогие» тесты на самом деле находятся в диапазоне от действительно дешевых до довольно дорогих. Выбор лучшего алгоритма означает минимизацию соотношения стоимости недорогого тестирования к сокращению количества дорогостоящих тестов. Помимо алгоритмических проблем, вы можете заняться настройкой, например, беспокоиться о локализации кэша.
Альтернативой являются простые сетки, скажем, 20x20 или 100x100 (в зависимости от вашего мира и размера памяти). Реализация проще, чем рекурсивная структура, такая как quad / bsp-деревья (или сферические деревья, если на то пошло).
Объекты, пересекающие границы ячеек, в этом случае немного проще и не вырождаются так сильно, как наивная реализация bsp / quad / oct-tree подойдет.
Используя это (или другие методы), вы сможете быстро отсеять множество пар и получить набор потенциальных столкновений, которые требуют дальнейшего изучения.
Я только что придумал решение, которое не зависит от размера сетки и, вероятно, составляет O (nlogn) (это оптимум, когда нет коллизий), хотя худшее при O (n n logn) (когда все сталкивается).
Я также реализовал и протестировал это, вот ссылка на источник . Но я не сравнивал его с методом грубой силы.
Описание того, как это работает: image
Вы можете проверить, что Скотт сделал в Chipmunk с пространственным хешированием. Источник находится в свободном доступе. Я думаю, он использовал ту же технику, что и Box-2D , если не для столкновения, то определенно для сохранения контакта.
If the space that your objects move within is bounded, then you could use a grid to subdivide your objects. Put each object into every grid cell which the object covers (fully or partially). To check if object A collides with any other object, determine which grid cells object A covers, then get the list of unique objects in those cells, and finally test object A against each unique object. This approach works best if most objects are usually contained in a single grid cell.
If your space is not bounded, then you will need to implement some sort of dynamic grid that can grow on demand in each of the four directions (in 2D).
The advantage of this approach over more adaptive algorithsm (i.e. BSP, Quadtree, Circletree) is that the cells can be accessed in O(1) time (i.e. constant time) rather than O(log N) time (i.e. logarithmic time). However these latter algorithms are able to adapt themselves to large variability in the density of objects. The grid approach works best when object density is fairly constant across the space.