Всегда ли обнаружение столкновений O (n ^ 2)?

14

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

Если нет, то делает ли это столкновение тривиальным для сфер (в 3d) или диска (в 2d)? Должен ли я сделать двойной цикл или создать массив пар вместо этого?

РЕДАКТИРОВАТЬ: Для физического движка, как bullet и box2d, обнаружение столкновения все еще O (N ^ 2)?

jokoon
источник
12
Два слова: пространственное разделение
MichaelHouse
Смотрите здесь: gamedev.stackexchange.com/questions/14373/find-nearest-object
MichaelHouse
1
Вы ставите. Я полагаю, что оба имеют реализации SAP ( Sweep и Prune ) (среди прочих), который является алгоритмом O (n log (n)). Ищите «Обнаружение столкновения с широкой фазой», чтобы узнать больше.
MichaelHouse
2
@ Byte56 Sweep and Prune имеет сложность O (n log (n)), только если вам нужно сортировать каждый раз, когда вы тестируете. Вы хотите сохранить отсортированный список объектов и каждый раз, когда вы добавляете один, просто сортируйте его в правильное место O (log (n)), поэтому вы получаете O (log (n) + n) = O (n). Это становится очень сложным, когда объекты начинают двигаться!
MartinTeeVarga
1
@ sm4, если движения ограничены, то об этом могут позаботиться несколько проходов пузырьковой сортировки (просто отметьте перемещенные объекты и перемещайте их вперед или назад в массиве, пока они не будут отсортированы. просто следите за другими движущимися объектами
чокнутый урод

Ответы:

14

Пространственное деление всегда равно O (N ^ 2) в худшем случае, и в этом заключается сложность информатики.

Однако существуют алгоритмы, которые работают за линейное время O (N) . Все они основаны на какой-то линии стрельбы.

По сути, вам нужно отсортировать объекты по одной координате. Допустим, X. Если вы выполняете сортировку каждый раз перед обнаружением столкновения, сложность будет O (N * logN). Хитрость заключается в сортировке, только когда вы добавляете объекты на сцену и позже, когда что-то в сцене меняется. Сортировка после движения не тривиальна. См. Связанную статью ниже для алгоритма, который принимает движение и все еще работает в линейном времени.

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

Наивной строкой развертки также является O (N ^ 2) в худшем случае (вы делаете все объекты охватывающими всю карту слева направо), но вы можете сделать это O (N), сделав его умнее (см. Ссылку ниже). Действительно хороший алгоритм будет довольно сложным.

Это простая диаграмма, как работает линия развертки:

Алгоритм развертки

Линия проходит слева направо. Объекты отсортированы по координате X

  • Случай первый: первые два объекта проверены. Остальное не важно.
  • Случай второй: первый объект был проверен и удален из списка. Два и три проверены.
  • Случай третий: даже если этот объект сталкивается, мы не проверяем.
  • Случай четвертый: Потому что мы проверяем в этом случае!

Подобные алгоритмы имеют сложность O (C * N) = O (N).

Источник: Два года курсов по вычислительной геометрии.

При обнаружении столкновений это обычно называют Sweep и Prune , но семейство алгоритмов линии развертки полезно во многих других областях.

Дальнейшее рекомендуемое прочтение, которое, я считаю, выходит за рамки этого вопроса, но тем не менее интересно: Эффективные крупномасштабные методы развертки и сокращения с вставкой и удалением AABB - В этом документе представлен улучшенный алгоритм развертки и сокращения, в котором используются ограничивающие прямоугольники с выравниванием по оси (AABB с сортировкой, учитывающей движение. Алгоритм представлен в работе работ за линейное время.


Теперь обратите внимание, что это лучший алгоритм в теории . Это не значит, что он используется. На практике алгоритм O (N ^ 2) с пространственным разделением будет иметь лучшую производительность в типичном случае (близко к O (N)) и иметь некоторые дополнительные требования к памяти. Это потому, что константа C в O (C * N) может быть очень высокой! Поскольку у нас обычно достаточно памяти, а в типичных случаях объекты равномерно распределены в пространстве - такой алгоритм будет работать ЛУЧШЕ. Но O (N) является ответом на оригинальный вопрос.

MartinTeeVarga
источник
это использует box2d / bullet?
Jokoon
3
«Подметай и сокращай» - это то, что обычно называют физикой. Приятно то, что вы можете обновлять сортировку по мере развития симуляции. Кроме того, линия развертки на вашем графике немного не подходит с точки зрения реализации (хотя это хорошо для теории) - вы просто перебираете начальные / конечные значения блока, поэтому вы будете проверять только реальные потенциальные коллизии. Видно, этот метод используется для создания более способных деревьев пространственного разделения, а не используется напрямую.
Шон Миддледич
3
Поскольку с технической точки зрения на самом деле может быть O (N ^ 2) попарных столкновений, не совсем верно утверждать, что развертка-обрезка всегда равна O (N). Скорее, основная сложность алгоритма - это O (N + c), где c - количество столкновений, обнаруженных алгоритмом - оно чувствительно к выходу , как и многие алгоритмы выпуклой оболочки. (Ссылка: en.wikipedia.org/wiki/Output-sensitive_algorithm )
Стивен Стадницкий,
1
Вы должны подкрепить свои претензии некоторыми публикациями или хотя бы именами алгоритмов.
Сэм Хочевар
1
@SamHocevar Я добавил ссылку на действительно продвинутый алгоритм Sweep and Prune, который работает за линейное время с подробной разбивкой констант. Тот факт, что алгоритмы называются «Sweep and Prune», был для меня новым, так как я никогда не работал с ним. Я использовал эти алгоритмы при выборе карты (что-то вроде столкновения 1 точки с другими объектами), поэтому я просто применил знания.
MartinTeeVarga
8

Нет. Обнаружение столкновения не всегда O (N ^ 2).

Например, скажем, у нас есть пространство 100x100 с объектами размером 10x10. Мы могли бы разделить это пространство на ячейки размером 10х10 с помощью сетки.

Каждый объект может содержать до 4 ячеек сетки (он может помещаться прямо в блоке или быть «между» ячейками). Мы могли бы хранить список объектов в каждой ячейке.

Нам нужно только проверить наличие столкновений в этих ячейках. Если в ячейке сетки имеется максимальное количество объектов (скажем, в одном блоке никогда не бывает более 4 объектов), то обнаружение столкновений для каждого объекта равно O (1), а обнаружение столкновений для всех объектов - O (N).

Это не единственный способ избежать сложности O (N ^ 2). Существуют и другие методы, более подходящие для других случаев использования - часто с использованием древовидных структур данных.

Алгоритм, который я описал, является одним из типов разделения пространства , но существуют и другие алгоритмы разделения пространства. Посмотрите Типы структур данных разделения пространства для большего количества алгоритмов, которые избегают временной сложности O (N ^ 2).

Механизмы поддержки Box2D и Bullet позволяют сократить количество проверяемых пар.

Из руководства , раздел 4.15:

Обработка столкновений на физическом этапе может быть разделена на узкофазную и широкофазную. В узкой фазе мы вычисляем точки контакта между парами фигур. Представьте, что у нас есть N фигур. Используя грубую силу, нам нужно выполнить узкую фазу для N * N / 2 пар.

Класс b2BroadPhase уменьшает эту нагрузку, используя динамическое дерево для управления парами. Это значительно уменьшает количество узкофазных вызовов.

Обычно вы не взаимодействуете с широкой фазой напрямую. Вместо этого Box2D создает и управляет внутренней фазой. Кроме того, b2BroadPhase разработан с учетом цикла симуляции Box2D, поэтому он, вероятно, не подходит для других случаев использования.

Из Bullet Wiki :

Существуют различные виды широкофазных алгоритмов, которые улучшают наивный алгоритм O (n ^ 2), который просто возвращает полный список пар. Эти оптимизированные широкие фазы иногда вводят еще больше не сталкивающихся пар, но это компенсируется их в целом улучшенным временем выполнения. У них разные рабочие характеристики, и ни одна из них не превосходит другие во всех ситуациях.

Динамическое дерево AABB

Это реализуется btDbvtBroadphase в Bullet.

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

Развертка и обрезка (SAP)

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

Следующая ссылка является общим введением в широкофазу, а также описанием алгоритма Sweep and Prune (хотя он называет его «Sort and Sweep»):

http://www.ziggyware.com/readarticle.php?article_id=128

Кроме того, взгляните на страницу википедии:

http://en.wikipedia.org/wiki/Sweep_and_prune

luiscubal
источник
Некоторые ссылки на похожие вопросы и внешние ресурсы сделали бы это отличным ответом.
MichaelHouse
3
Это не правильно. Вы все еще получаете O (N ^ 2). Это будет намного быстрее, что-то вроде N ^ 2/100, но все равно N ^ 2. В качестве доказательства просто учтите, что все объекты находятся в одной ячейке.
MartinTeeVarga
4
@ sm4 Это наихудший случай O (N ^ 2), что действительно происходит, если все объекты находятся в одной ячейке. Однако в физических движках объекты обычно не находятся в одной ячейке. В моем примере ни один объект не может совместно использовать одну и ту же ячейку с более чем 3 другими объектами. Это было бы то, что происходит в физическом движке для «нормальных» объектов (и под «нормальным» я подразумеваю «не просто датчик»).
luiscubal
Я думаю, что ваш алгоритм потребует проверить 8 ячеек вокруг, а не только 4 ячейки.
Jokoon
6
@luiscubal Сложность всегда "наихудший случай". Теоретически вы ищете «гарантированную» сложность. То же самое с быстрой сортировкой, которая является O (N ^ 2), и сортировкой слиянием, которая является O (N * logN). Быстрая сортировка работает лучше на реальных данных и имеет меньшие пространственные требования. Но Mergesort гарантирует лучшую сложность. Если вам нужно что-то доказать, используйте mergesort. Если вам нужно что-то отсортировать, используйте быструю сортировку.
MartinTeeVarga
2

O (N ^ 2) относится к тому факту, что если у вас есть N объектов, выяснение того, что сталкивается с тем, что в худшем случае N ^ 2 вычислениями столкновений. Скажем, у вас есть 3 объекта. Чтобы найти «кто кого бьет», вы должны найти:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

Это 6 проверок на столкновения или N * (N-1) проверок. В асимптотическом анализе мы расширили бы полином и приблизили бы как O (N ^ 2). Если бы у вас было 100 объектов, то это было бы 100 * 99, что достаточно близко к 100 * 100.

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

Таким образом, весь смысл O (N ^ 2) существует из-за природы каждого тела, проверяющего каждое другое тело в сцене. Это просто природа вычислений. Однако многое может помочь сделать это дешевле. Даже граф сцены (скажем, обнаружение между объектами только в одной комнате ) значительно сократит количество вычислений столкновений, но оно все равно будет O (M ^ 2) (где M - количество объектов в комнате до быть обнаружены столкновения). Сферические ограничивающие объемы делают начальную проверку очень быстрой ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), поэтому, даже если обнаружение столкновений равно O (N ^ 2), вычисления ограничивающей сферы, вероятно, будут происходить очень быстро.

bobobobo
источник
Нет необходимости принимать грубую проверку в качестве эталона: независимо от умных алгоритмов, каждый из N объектов может сталкиваться со всеми другими объектами, создавая O (N ^ 2) столкновений, которые требуют обработки O (N ^ 2). Хорошие алгоритмы могут работать лучше только при меньшем количестве столкновений.
Лоренцо Гатти