Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Game Physics
Gamedevelopment

Как создать собственный 2D-движок физики: основы и разрешение импульса

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called How to Create a Custom Physics Engine.
How to Create a Custom 2D Physics Engine: The Core Engine

Russian (Pусский) translation by Shaun Murphy (you can also view the original English article)

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

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

 К концу этого учебника в следующих разделах будут покрыты, в двух измерениях:

  • Простое обнаружение столкновений
  • Простой коллектор поколения
  • Разрешение импульс

Вот краткий демо:

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


Предпосылки

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

  • Базовое понимание простой векторной математики
  • Умение выполнять алгебраические математика

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

Есть немало статей и руководств по всему интернету, в том числе и здесь на Tuts+, которые охватывают обнаружения столкновений. Зная это, я хотел бы пробежаться по теме очень быстро, так как этот участок не является темой этой статьи.

Оси Выровнены Ограничивающих Прямоугольников

Оси выровнены прямоугольника (ААВВ) - это окно, которое имеет четыре оси совмещена с системой координат, в которой он проживает.  Это означает, что это поле, которое не может вращаться, и всегда квадрат на 90 градусов (обычно выравнивается с экрана).  В целом это называется "прямоугольник", потому что AABBs используются для связаны другие, более сложные формы.

An example AABB

Пример ААВВ.

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

Эта форма позволяет ААВВ быть представлены две точки.  Минимальная точка представляет собой нижнюю границы X и оси Y, и Макс представляет собой верхние пределы - иными словами, они представляют собой верхний левый и нижний правый углы. Для того, чтобы сказать, являются ли два ААВВ формы пересекающихся необходимо иметь базовое понимание разделения Теорема оси (СБ).

Вот быстрый тест, взятый из реального времени обнаружение столкновений Кристер Эриксон, которая позволяет использовать в сб.:

 Круги

 Круг представляет собой радиус и точка. Вот то, что ваша структура круг должен выглядеть так:

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

Важным оптимизации, чтобы сделать здесь, это избавиться от необходимости использования оператора квадратного корня:

В целом размножение-это намного дешевле, чем операция взятия квадратного корня из значения.


Разрешение Импульс

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

 В целом объект в физический движок имеет три степени свободы (в двух измерениях): движение в плоскости XY и вращения.  В этой статье мы неявно ограничить вращение и использовать только AABBs и круги, так что единственная степень свободы, мы действительно должны рассмотреть движение вдоль плоскости XY.

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

Simple example of what impulse resolution can achieve

Простой пример того, что разрешение импульс может достичь.

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

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

Наши Объекты Столкнулся - Теперь Что?

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

  •  Столкновение нормально
  • Глубина проникновения

 Для того, чтобы применить импульс к объектам, но и перемещать их друг от друга, мы должны знать, в каком направлении толкать их и на сколько. Нормальное столкновение направление, в котором импульс будет применяться. Глубина проникновения (вместе с некоторыми другими вещами) определить, как большие импульса будет использоваться. Это означает, что единственная ценность, которую нужно решить для масштабов нашего импульса.

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

Уравнение 1

\[ В^{АВ} = V и^Б - В^А \] заметим, что для того, чтобы создать вектор из позиции a в позицию B, вы должны сделать: конечная точка - Исходная позиция.  \(В^{АВ}\) - относительная скорость из А в Б. Это уравнение должно быть выражено в терминах столкновения нормальный \(н\) - то есть, мы хотели бы знать относительную скорость от А до Б вдоль линии столкновения нормального направления:

Уравнение 2

\[ В^{АВ} \cDOT на Н = (В^Б - В^А) \cDOT на п \]

Мы сейчас используем скалярное произведение. Скалярное произведение простых; это сумма покомпонентно продуктов:

Уравнение 3

 \[ В_1 = всегда \begin{bmatrix}x_1 места \\y_1\конец{bmatrix}, В_2 = всегда \begin{bmatrix}x_2 \\y_2\конец{bmatrix} \\ В_1 \cDOT на В_2 = x_1 места * x_2 + y_2 * y_2 \]

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

 Чтобы решить, что реституция использовать (обозначается \(Е\) для Эпсилон), вы должны всегда использовать самой низкой реституции, вовлеченные в конфликт, для интуитивного результаты:

После того как \(Е\) является приобретенным, мы можем разместить его в нашем решая уравнение для величины импульса.

Закон Ньютона о реституции говорится следующее:

 Уравнение 4

 \[В' = Е * \в]

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

Уравнение 5

 \[ В^{АВ} \cDOT на Н = -Е * (В^Б - В^А) \cDOT на п \]

 Обратите внимание, как мы ввели здесь отрицательный знак.  В закон Ньютона о реституции, \(в\), получим результирующий вектор после отказов, на самом деле происходит в направлении, противоположном В.  Так как мы представляем противоположных направлениях в нашем деривации? Ввести отрицательный знак.

 До сих пор так хорошо. Теперь мы должны быть в состоянии выразить эти скорости в то время как под влиянием импульса. Вот простое уравнение для изменения вектора каким-импульса скалярного \(к\) вдоль определенной \направление(Н\):

Уравнение 6

\[ В' = в + J В * Н \]

Надеюсь, что приведенное выше уравнение имеет смысл, так как это очень важно понимать. У нас есть единичный вектор \(Н\), который представляет собой направление. У нас есть скаляр \(К\), которая представляет как долго наши \(Н\) вектор будет.  Затем мы добавляем наш масштабируется \(Н\) вектор \(\v), чтобы привести в \(в\).  Это просто добавление одного вектора на другой, и мы можем использовать этот небольшой уравнение, чтобы применить импульс от одного вектора к другому.

Есть немного больше работы, чтобы быть сделано здесь. Формально, импульс определяется как изменение импульса. Импульс-это масса * скорость. Зная это, мы можем представить импульс как формально определяется так:

Уравнение 7

\[ Импульс = масса * скорость \\ скорость = \фрац{импульс}{масса} \следовательно, в' = в + \фрац{Дж * Н}{масса}\]

Три точки в маленький треугольник (\(\поэтому\)) можно читать Как "поэтому".  Он используется, чтобы показать, что дело заранее может быть использован, чтобы сделать вывод, что все, что дальше верно.

Хороший прогресс был достигнут до сих пор! Однако мы должны быть в состоянии выразить импульс через \(К\) в отношении двух разных объектов. При столкновении с объектом A и B, а сдвигаются в противоположном направлении Б:

Уравнение 8

\[ В'^В = В^А + \фрац{Дж * Н}{масс^а} \ \ в'^В = В^Б - \фрац{Дж * Н}{масса^Б} \]

Эти два уравнения будут толкать от Б вдоль направления единичного вектора \(н\) с импульсным скаляр (величина \(н\)) \(к\).

Все, что сейчас требуется, это объединить уравнения 8 и 5. Наши полученное уравнение будет выглядеть так:

Уравнение 9

 \[ (В^А - В^В + \фрац{Дж * Н}{масс^а} + \фрац{Дж * Н}{масса^б}) * н = -е * (В^Б - В^А) \cDOT на п \\ \Поэтому \\ (В^А - В^В + \фрац{Дж * Н}{масс^а} + \фрац{Дж * Н}{масса^Б}) * П + Е * (В^Б - В^А) \cDOT на н = 0 \]

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

Уравнение 10

 \[ (П^Б - В^А) \cDOT на н + з * (\фрац{Дж * Н}{масс^а} + \фрац{Дж * Н}{масса^б}) * н + е * (В^Б - В^А) \cDOT на н = 0 \\ \поэтому \\ (1 + е)((В^Б - В^А) \cDOT на н) + з * (\фрац{Дж * Н}{масс^а} + \фрац{Дж * Н}{масса^Б}) * П = 0 \\ \поэтому \\ Дж = \фрац{-(1 + е)((В^Б - В^А) \cDOT на Н)}{\ГРП{1}{масс^а} + \ГРП{1}{масса^Б}} \]

 Ух! Это было немного математики! Это сейчас, хотя во всем. Важно заметить, что в окончательном варианте уравнение 10 мы имеем \(к\) слева (наши масштабы) и все, что справа-это все известно. Это означает, что мы можем написать несколько строк кода, чтобы решить для нашего импульса скалярного \(к\). И мальчик-это код намного более читабельным, чем математической нотации!

Есть несколько ключевых вещей, чтобы отметить в приведенном выше примере кода. Первым делом проверка в строке 10, если(VelAlongNormal > 0). Эта проверка очень важна, она гарантирует, что вы только разрешать коллизию, если объекты движутся навстречу друг другу.

Two objects collide but velocity will separate them next frame Do not resolve this type of collision

Два объекта сталкиваются, но скорость их будет отделять следующий кадр. Не разрешать подобные коллизии.

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

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

Многие физики двигатели на самом деле не хранить сырой массы. Физика двигатели часто магазин обратная массы и один инверсный массы. Просто так получилось, что большинство математических участием масс в виде 1/масса.

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

Для того чтобы сделать это, вы могли бы сделать:

Важно понимать, что приведенный выше код эквивалентен ResolveCollision() пример функции раньше. Как уже говорилось, обратная масс весьма полезны в физический движок.

Тонуть Объектов

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

Я предлагаю использовать ноль как бесконечную массу - Хотя, если мы попытаемся вычислить обратную масса объекта с нуля у нас будет деление на ноль. Обходной путь для этого это сделать следующее при вычислении обратных масс:

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

Это тонет из-за плавающей ошибки точек. Во время каждого расчета плавающей точкой небольшой плавающей ошибки вводится из-за аппаратных. (Для получения дополнительной информации, компания Google [ошибка плавающей точкой IEEE754].) С течением времени эта ошибка накапливается в позиционную ошибку, заставляя объекты погружаться в друг друга.

Для того, чтобы исправить эту ошибку она должна быть учтена. Чтобы исправить эту позиционную ошибку я покажу вам метод, называемый линейной проекции. Линейная проекция уменьшает проникновение двух объектов на небольшой процент, и это происходит после применения импульса.  Позиционная коррекция очень проста: перемещение каждого объекта вдоль линии столкновения нормальный \(н\) в процентах от глубины проникновения:

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

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

Это позволяет объектам проникнуть очень немного без коррекции положения в ногами.


Простой Коллектор Поколения

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

Вот типичный коллектор установки:

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

Круг против круга

Давайте начнем с алгоритма простейшей столкновения: круг против круга. Этот тест в основном тривиальными. Можете ли вы представить, что в направлении разрешения конфликта будет? Это вектор от точки А в точку Б. Этот круг может быть получен путем вычитания установки Б У в.

Глубина проникновения связана с окружностей радиусов и расстояния друг от друга. Перекрытия кругов может быть вычислено путем вычитания сумма радиусов на расстояние от каждого объекта.

Вот полный пример алгоритма для генерации коллектор круга против столкновения кругу:

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

ААВВ В. ААВВ

ААВВ в ААВВ тест является немного более сложным, чем круг против круга.  Столкновение нормального не будет вектор из A в B, но будет лицо нормальное. В ААВВ-это коробка с четырьмя лицами. Каждое лицо имеет нормальный. Это нормально представляет собой единичный вектор, который перпендикулярен к лицу.

Изучить общее уравнение линии в 2D:

\[ ах + ьу + с = 0 \\ нормальный = всегда \begin{bmatrix} \а\б\конец{bmatrix} \]

custom-physics-line2d

В приведенном выше уравнении, A и B-вектор нормали к линии, а вектор (А, B) предполагается нормированной (длина вектора равна нулю). Опять же, наши столкновения нормальное (направление разрешения конфликта) будет в направлении одного из нормалей к граням.

Вы знаете, что c представляет собой в общее уравнение линии?   c - расстояние от начала координат.  с-расстояние от источника. Это очень полезно для тестирования, чтобы увидеть, если точка находится на одной стороне линии или другой, как вы увидите в следующей статье.

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

Two axes of penetration the horizontal x axis is axis of least penetration and this collision should be resolved along the x axis

Две оси проходки; горизонтальная ось X является осью крайней мере проникновение и эта коллизия должна разрешаться вдоль оси X.

Вот полный алгоритм ААВВ в ААВВ коллектор поколение и обнаружение столкновений:

custom-physics-aabb-diagram

Круг против ААВВ

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

AABB to Circle intersection diagram
ААВВ с круговой диаграммой пересечения.

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


Заключение

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

  • Контактной пары сортировки и выбраковки
  • Broadphase
  • Наслаивать
  •  Интеграция
  •  Timestepping
  • Пересечение полупространство
  •  Модульная конструкция (материалы, массы и силы)

 Я надеюсь, вам понравилась эта статья и я с нетерпением жду ответов на вопросы в комментариях.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.