Как работает двигатель столкновения?

Как именно работает двигатель столкновения ?

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

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

Итак, что держит тиканье двигателя столкновения?

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

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

Обнаружение столкновений бывает двух видов: дискретное и непрерывное. Продвинутые движки поддерживают оба, так как они имеют разные свойства. В общем, непрерывное обнаружение столкновений очень дорого и используется только там, где это действительно необходимо. Большинство столкновений и физики обрабатываются с использованием дискретных методов. В дискретных методах объекты заканчивают тем, что проникают друг в друга, и физический двигатель тогда работает, чтобы раздвинуть их. Таким образом, движок фактически не мешает игроку частично пройти через стену или пол, он просто фиксирует его, обнаружив, что игрок частично находится в стене / полу. Я собираюсь сосредоточиться на дискретном обнаружении столкновений здесь, так как это то, что у меня больше всего опыта с нуля.

Обнаружение столкновений

Обнаружение столкновения относительно легко. Каждый объект имеет преобразование и форму (возможно, несколько форм). Наивные подходы заставили бы механизм столкновений выполнить цикл O (n ^ 2) через все пары объектов и проверить, есть ли перекрытие между парами. В более разумных подходах есть несколько пространственных структур данных (например, для статических и динамических объектов), ограничивающая форма для каждого объекта и многочастные выпуклые подформы для каждого объекта.

Структуры пространственных данных включают в себя такие вещи, как KD-деревья, динамические AABB-деревья, Octrees / Quadtrees, деревья двоичного разбиения пространства и так далее. У каждого есть свои преимущества и недостатки, поэтому некоторые более мощные двигатели используют более одного. Например, динамические AABB-деревья действительно очень быстры и хороши для обработки большого количества движущихся объектов, в то время как KD-дерево может быть более подходящим для геометрии статического уровня, с которой сталкиваются объекты. Есть и другие варианты.

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

Последняя фаза обнаружения столкновений состоит в том, чтобы точно определить, где геометрия пересекается. Обычно это подразумевает использование сетки (или многоугольника в 2D), хотя и не всегда. Цель этого этапа состоит в том, чтобы выяснить, действительно ли объекты действительно сталкиваются, требуется ли высокий уровень детализации (например, столкновение с пулей в шутере, когда вы хотите иметь возможность игнорировать выстрелы, которые едва пропускаются), и также, чтобы точно определить, где объекты сталкиваются, что повлияет на реакцию объектов. Например, если ящик находится на краю стола, двигатель должен знать, в какие точки стол давит на ящик; в зависимости от того, как далеко коробка висит над ней, она может начать наклоняться и падать.

Поколение контактных коллекторов

Используемые здесь алгоритмы включают в себя популярные алгоритмы уточнения GJK и Minkowski Portal, а также тест Separating Axis. Поскольку популярные алгоритмы обычно работают только для выпуклых фигур, необходимо разбить многие сложные объекты на выпуклые подобъекты и выполнить тесты столкновений для каждого из них в отдельности. Это одна из причин, по которой упрощенные сетки часто используются для столкновения, а также сокращение времени обработки для использования меньшего количества треугольников.

Некоторые из этих алгоритмов не только говорят вам, что объекты столкнулись наверняка, но и где они столкнулись - как далеко они проникают друг в друга и каковы «точки соприкосновения». Некоторые алгоритмы требуют дополнительных шагов, таких как обрезка полигонов, чтобы получить эту информацию.

Физический ответ

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

На самом базовом уровне физический движок сделает что-то вроде этого: он возьмет сталкивающиеся объекты и их контактный коллектор и вычислит новые позиции, необходимые для отделения сталкивающихся объектов. Это переместит объекты в эти новые позиции. Он также рассчитает изменение скорости в результате этого толчка в сочетании со значениями восстановления (упругости) и трения. Физический движок также будет применять любые другие силы, действующие на объекты, такие как гравитация, для расчета новых скоростей объектов, а затем (в следующем кадре) их новых положений.

Более сложный физический ответ быстро усложняется. Подход, описанный выше, сломается во многих ситуациях, включая один объект, расположенный поверх двух других. Работа с каждой парой сама по себе вызовет «дрожание», и объекты будут сильно подпрыгивать. Самым основным методом является выполнение ряда итераций коррекции скорости для пар сталкивающихся объектов. Например, если над двумя другими блоками «B» и «C» расположен блок «A», сначала будет обработан конфликт AB, в результате чего блок A будет отклоняться дальше в блок C. Затем обрабатывается конфликт AC, вечером несколько раз, но потянув A вниз в B. Затем выполняется другая итерация, поэтому ошибка AB, вызванная коррекцией AC, немного разрешается, создавая немного больше ошибок в ответе AC. Который обрабатывается, когда AC обрабатывается снова. Количество выполненных итераций не является фиксированным, и нет никакой точки, в которой оно становится «идеальным», а просто любое количество итераций, которое перестает давать значимые результаты. 10 итераций - это типичная первая попытка, но для того, чтобы определить наилучшее число для конкретного движка и потребностей конкретной игры, требуется настройка.

Кэширование контактов

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

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

Спать

Другой очень полезный метод - помечать объекты как «спящие», если с ними не взаимодействуют. Спящие объекты не получают обновлений физики, не сталкиваются с другими спящими объектами, и в основном просто сидят там замороженными во времени, пока другой не спящий объект не столкнется с ними.

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

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

Ограничения

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

Даже основы решения ограничений могут быть очень интенсивными по математике и выходят за рамки моего опыта в этой области. Я рекомендую проверить превосходную серию статей Рэнди Галла по физике для более глубокого объяснения темы.

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

Наивный, общий подход прост: для каждой возможной пары объектов вычислите объем пересечения. Это обычно не практично, поскольку требует O (n ^ 2) относительно дорогих операций пересечения.

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

Один «двигатель столкновения», который я использовал, чувствовал себя очень легко.

По сути, API предоставил вид объектов, имеющих метод collidesWith, такой, что

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

В моем приложении я просто периодически вызывал, collidesWithчтобы узнать, произошло ли столкновение или нет.

Довольно просто, не правда ли?

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

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

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

  

Я думаю, вы немного запутались в том, о чем говорите, и говорите о нескольких разных вещах.

способность сказать, что этот предмет перемещен из местоположения X в местоположение Y, основана на физике (это также атакует, как они двигаются, и почему они двигаются)

метод, который используется для обнаружения столкновений, определяется на основе структуры вашей игры. если ваша игра представляет собой большой открытый мир, то вам следует рассмотреть вопрос о разделении пространства (подход квад-дерева [окт-дерево для 3D], BSP, традиционная сетка или старомодный метод тестирования всего)

лучший способ реализовать систему обнаружения столкновений - это делать это поэтапно.

1. поместите все объекты в общий ограничивающий объем / форму, а затем проверьте их

2. если пройдено 1, повторите с более сложным повторением объема / формы, пока не будете готовы проверить абсолютную геометрию

3. Проверьте абсолютную геометрию. Сколько раз вы повторяете шаг 2, зависит от сложности ваших фигур и их точности.

Вы должны рассматривать каждый из этих шагов как ранний, с целью устранения коллизий по мере продвижения и возврата true на шаге 3, только если они действительно касаются.

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

традиционный цикл выглядит так:

receive input
update physics
collision detection
collision resolution
render
repeat

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

Смотрите BSP и Kd деревья для получения дополнительной информации. Есть и другие подходы к разделению.

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

Во-вторых, но это также важно, более детально (точно) сопоставьте оставшиеся объекты, которые не были отобраны на этом первом этапе.

В-третьих, используйте наиболее эффективные / подходящие методы для выполнения проверок.