Может ли физический движок уменьшить эту сложность, например, группируя объекты, которые находятся рядом друг с другом, и проверять наличие столкновений внутри этой группы вместо всех объектов? (например, удаленные объекты можно удалить из группы, посмотрев на их скорость и расстояние от других объектов).
Если нет, то делает ли это столкновение тривиальным для сфер (в 3d) или диска (в 2d)? Должен ли я сделать двойной цикл или создать массив пар вместо этого?
РЕДАКТИРОВАТЬ: Для физического движка, как bullet и box2d, обнаружение столкновения все еще O (N ^ 2)?
Ответы:
Пространственное деление всегда равно 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) является ответом на оригинальный вопрос.
источник
Нет. Обнаружение столкновения не всегда O (N ^ 2).
Например, скажем, у нас есть пространство 100x100 с объектами размером 10x10. Мы могли бы разделить это пространство на ячейки размером 10х10 с помощью сетки.
Каждый объект может содержать до 4 ячеек сетки (он может помещаться прямо в блоке или быть «между» ячейками). Мы могли бы хранить список объектов в каждой ячейке.
Нам нужно только проверить наличие столкновений в этих ячейках. Если в ячейке сетки имеется максимальное количество объектов (скажем, в одном блоке никогда не бывает более 4 объектов), то обнаружение столкновений для каждого объекта равно O (1), а обнаружение столкновений для всех объектов - O (N).
Это не единственный способ избежать сложности O (N ^ 2). Существуют и другие методы, более подходящие для других случаев использования - часто с использованием древовидных структур данных.
Алгоритм, который я описал, является одним из типов разделения пространства , но существуют и другие алгоритмы разделения пространства. Посмотрите Типы структур данных разделения пространства для большего количества алгоритмов, которые избегают временной сложности O (N ^ 2).
Механизмы поддержки Box2D и Bullet позволяют сократить количество проверяемых пар.
Из руководства , раздел 4.15:
Из Bullet Wiki :
источник
O (N ^ 2) относится к тому факту, что если у вас есть N объектов, выяснение того, что сталкивается с тем, что в худшем случае N ^ 2 вычислениями столкновений. Скажем, у вас есть 3 объекта. Чтобы найти «кто кого бьет», вы должны найти:
Это 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), вычисления ограничивающей сферы, вероятно, будут происходить очень быстро.источник