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

Как именно работает механизм столкновения ?

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

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

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

74 голоса | спросил JXPheonix 31 MaramSat, 31 Mar 2012 01:04:46 +04002012-03-31T01:04:46+04:0001 2012, 01:04:46

6 ответов


162

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

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

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

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

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

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

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

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

Генерация контактов с коллекторами

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

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

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

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

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

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

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

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

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

Спящий

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

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

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

Ограничения

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

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

ответил Sean Middleditch 31 MaramSat, 31 Mar 2012 03:04:41 +04002012-03-31T03:04:41+04:0003 2012, 03:04:41
3

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

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

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

ответил ipeet 24 MarpmSat, 24 Mar 2012 18:46:49 +04002012-03-24T18:46:49+04:0006 2012, 18:46:49
2

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

В принципе, API предоставил объекты, имеющие метод collidesWith, так что

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

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

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


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

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

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

    http://i.stack.imgur.com/4Wn5B.jpgответил 24 MarpmSat, 24 Mar 2012 19:38:50 +04002012-03-24T19:38:50+04:0007 2012, 19:38:50

2

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

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

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

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

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

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

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

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

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

традиционный цикл выглядит следующим образом:

получить ввод
обновить физику
обнаружение столкновения
разрешение столкновения
оказывать
повторение
ответил gardian06 31 MaramSat, 31 Mar 2012 01:18:29 +04002012-03-31T01:18:29+04:0001 2012, 01:18:29
1

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

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

ответил 24 MarpmSat, 24 Mar 2012 21:44:52 +04002012-03-24T21:44:52+04:0009 2012, 21:44:52
0

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

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

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

ответил Steve H 31 MarpmSat, 31 Mar 2012 21:27:31 +04002012-03-31T21:27:31+04:0009 2012, 21:27:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132