Как пишется физика для игр - Правописание и грамматика

Мотор! или Что такое игровая физика

Время на прочтение
9 мин

Количество просмотров 21K

Разработчикам при создании игры приходится искать баланс не только в механиках, но и в физике. Реализм или аркада? В общем-то, кому что нравится. Главное — фан и удовольствие. Нужно создать фундаментальные законы своего мира, и объяснить, что возможность ходить по потолку — механика, а не баг.

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

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

Программирование физики может сводиться к одному-двум методам с парой строчек кода. А может и к сложной системе с отдельным физическим движком (например, Havok или PhysX) с миллионами строк кода. Независимо от сложности игровая физика делится на две категории: физика твердого тела и физика мягкого тела.

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

Важная роль игровой физики

Игровая физика служит разным целям, но самые главные — интуитивность и веселье. Если объект ведет себя непредсказуемо, будет сложно понять правила игры.

Если бы мяч в FIFA 20 каждый раз отскакивал в случайном направлении, было бы невозможно забить гол. Разработчики стараются воссоздать отскок мяча в зависимости от его траектории, скорости и других факторов, действующих в реальном мире. Чтобы игрок интуитивно понимал, как обращаться с мячом или другими объектами. К слову, у FIFA 20 куча плохих отзывов именно потому, что ее физика работает не так, как того ожидали фанаты.

При этом игры не обязаны строго соблюдать естественные законы природы. Главное — игра должна приносить удовольствие, а реализация реальных физических законов может уничтожить весь экспириенс. Представьте Grand Theft Auto V с суровой земной физикой (но если очень хочется, то можно поставить специальный мод). Даже легкая авария на высокой скорости закончилось бы фатально, убило бы темп и атмосферу. Не очень-то весело.

Разработчик должен найти нужный баланс между веселой игрой и игрой с реалистичной физикой. И он часто зависит от целевой аудитории. Хороший пример — гонки.

Многим нравятся аркадные гонки (Need For Speed), в которых касание отбойника или резкий поворот слабо сказываются на управлении машиной. Другие предпочитают реалистичные гоночные симуляторы (Gran Turismo).

Но даже создавая симуляторы, разработчики пытаются привлечь новую аудиторию — Gran Turismo делала ставку на фотореализм (и в какой-то мере это сработало). Но в итоге Polyphony Digital добавила аркадный режим, чтобы захватить рынок побольше.

Физика твердого тела

Говоря об игровой физике, мы обычно имеем в виду физику твердого тела (rigid body physics, RBP). Она описывает и воспроизводит физические законы, применимые к твердым массам вещества. Мяч в FIFA 20 — твердое тело, которым управляет физика игры.

Неважно рассматриваем мы 2D-тайтлы типа Pong или 3D типа Skyrim — в большинстве игр есть линейная физика твердого тела.

Физика 2D-игр

Возьмем Pong в качестве примера. Два твердых тела (мяч и ракетка) снова и снова сталкиваются друг другом. Звучит не слишком воодушевляюще. У дедушки видеоигр не было реалистичной физики.

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

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

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

Поведение твердых тел (в первую очередь снарядов) зависело от нескольких сил. В соответствии с ними менялись анимации. Стрелы и ракеты — отличный пример анимации твердых тел в подобных играх. Плоскость снаряда могла измениться во время полета, а стрела так и оставалась прямой. Две точки на объекте в системе твердых тел всегда будут на одинаковом расстоянии друг от друга.

Игры типа Donkey Kong и Mario Bros. сильно повлияли на физику 3D-проектов. Марио подружился с основными физическими законами — гравитацией, импульсом и инерцией. Прыжок стал основной механикой и остался в игровой индустрии навсегда.

Подпрыгнувший объект должен упасть обратно. Вопрос только в том, насколько высоко он поднимется и насколько быстро упадет? И насколько реалистичной должна быть гравитация в игре?

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

Дальнейшие игры серии расширили эти границы — появился двойной прыжок. В этой франшизе его впервые добавили в Super Mario 64, но ранее его уже использовали в Dragon Buster в 1984 году.

Двойной прыжок стали активно использовать в платформерах (иногда даже слишком). И он до сих пор есть во многих современных проектах, включая 3D. Например, Devil May Cry и Unreal Tournament.

Физика 3D-игр

Физика в 3D-играх не сильно отличается от физики в 2D-проектах. Вычисления усложняются за счет третьего измерения (оси Z) и того, что объекты состоят из нескольких твердых тел.

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

В 3D-играх одновременно сталкиваются сразу несколько твердых объектов. В Uncharted, когда Дрейк взбирается по скале, программа следит как минимум за его руками и ногами — отдельными твердыми телами. Он может подпрыгнуть и схватиться за лестницу одной рукой или двумя, и анимация будет разной.

В 3D-играх (и некоторых 2D) конечности персонажей разбиты на несколько твердых тел, которые соединены суставами. То есть модель человеческой руки состоит из предплечья и кисти, которые соединены запястьем и крепятся к плечу локтевым суставом. Это описывает рэгдолл-физика (от англ. ragdoll — тряпичная кукла).

Изображение: University of California, Riverside

Соединения твердых тел (суставы) создаются в системе скелетной анимации игрового движка. Каждое твердое тело должно двигаться по определенным правилам, чтобы выглядеть реалистично. Для просчета движений программисты используют различные техники. Самая известная — алгоритм Физерстоуна, ограничительный подход, который не дает конечностям болтаться как попало.

Есть и другие подходы к работе с рэгдоллом: интегрирование Верле (Hitman: Codename 47), инверсная кинематика (Halo: Combat Evolved и Half-Life), смешанный рэгдолл (Uncharted: Drakes Fortune и многие другие) и процедурная анимация (серия Medal of Honor).

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

Напомню, всегда нужно искать баланс между реализмом и весельем. Даже если игра будет немного «читерить».

Возьмем серию Sniper Elite. В реальном мире стрелок должен принимать в расчет кучу переменных: скорость ветра, направление ветра, диапазон, перемещение цели, мираж, источник света, температура, давление и эффект Кориолиса.

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

В Call of Duty: Modern Warfare есть уровень, где нужно поразить цель с дальнего расстояния. Игрок должен учесть эффект Кориолиса, а также скорость и направление ветра. Некоторым нравится такой челлендж, но я ее забросил.

Гонки — еще один жанр, в котором требуется много вычислений по твердым телам и действующим на них силам. Колеса контактируют с дорожным покрытием, подвеска соприкасается с колесами, машины сталкиваются друг с другом. Еще другие объекты прямо или косвенно участвуют в столкновениях.

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

В симуляторах Gran Turismo и Assetto Corsa действуют более реалистичные силы. Например, Assetto Corsa Competizione (версия 1.0.7) использует пятиточечную модель шин. Она включает две точки на передней кромке шины, две на задней и одну посередине — все вместе действуют как объединенное твердое тело. Точки могут двигаться и изгибаться в трех измерениях, независимо реагируя на внешние силы и контакт с поверхностью. Дополнительные точки значительно увеличивают количество вычислений, которые выполняет движок.

Физические модели в 3D-тайтлах намного сложнее, чем в 2D. Приходится отслеживать больше переменных и точек соприкосновения. Но большинство вычислений линейные, поэтому такие модели гораздо проще, чем модели мягкого тела.

Физика мягкого тела

Физика мягкого тела (soft body physics, SBP) описывает деформируемые объекты. Она используется реже и сильно урезана в видеоиграх из-за огромного количества вычислений.

Мягкие тела — это одежда, волосы, скопления частиц типа дыма или тумана. Точки твердого тела всегда остаются на одном и том же расстоянии друг от друга. А мягкое тело может деформироваться и двигаться так, что расстояние между его точками будет меняться.

Деформируемые твердые тела

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

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

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

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

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

Тут в дело вступают физические движки. В Batman: Arkham Knight студия Rocksteady использовала APEX Cloth PhysX. Этот инструмент позволяет создавать маску для тел, отображающих одежду, и настраивать параметры их движения. В зависимости от конфигурации можно отобразить все от шелка до мешковины.

Для улучшения производительности можно ограничить воздействие естественных сил на ткань. Например, Wind Method (Отображение ветра) можно установить на Accurate (Точное) или Legacy (Частичное). Частичное отображение игнорирует мелкие колебания, производится меньше вычислений.

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

Системы частиц мягкого тела

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

Физические движки значительно улучшили системы частиц за последние годы. Посмотрите на приветственный экран из Skyrim и насколько там реалистично выглядит дым.

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

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

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

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

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

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

Подытожим

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

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

Если хотите лучше разобраться в физике видеоигр, то посмотрите соответствующие разделы в руководстве Unity или руководстве Lumberyard.

Источник

Время на прочтение
14 мин

Количество просмотров 57K

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

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

В этой части туториала мы рассмотрим следующие темы:

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

Вот небольшое демо:

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

Необходимые знания

Для понимания этой статьи требуется неплохое знание математики и геометрии, и в гораздо меньшей степени — непосредственно программирования. В частности, вам потребуется следующее:

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

Распознавание коллизий

В Интернете достаточно статей и туториалов о распознавании коллизий, поэтому я не буду подробно рассматривать эту тему.

Ограничивающий прямоугольник, выровненный по координатным осям

Ограничивающий прямоугольник, выровненный по координатным осям (Axis Aligned Bounding Box, AABB) — это прямоугольник, четыре оси которого выровнены относительно системы координат, в которой он находится. Это значит, что прямоугольник не может вращаться и всегда находится под углом в 90 градусов (обычно выровнен относительно экрана). Обычно его называют «ограничивающим прямоугольником», потому что AABB используются для ограничения других, более сложных форм.

Пример AABB.

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

struct AABB
{
  Vec2 min;
  Vec2 max;
};

Эта форма позволяет задать AABB двумя точками. Точка min обозначает нижние границы по осям x и y, а max обозначает верхние границы — иными словами, они обозначают верхний левый и нижний правый углы. Чтобы определить, пересекаются ли два AABB, необходимо базовое понимание теоремы о разделяющей оси (Separating Axis Theorem, SAT).

Вот быстрая проверка, взятая с сайта Real-Time Collision Detection Кристера Эриксона, в которой используется SAT:

bool AABBvsAABB( AABB a, AABB b )
{
  // Выходим без пересечения, потому что найдена разделяющая ось
  if(a.max.x < b.min.x or a.min.x > b.max.x) return false
  if(a.max.y < b.min.y or a.min.y > b.max.y) return false

  // Разделяющая ось не найдена, поэтому существует по крайней мере одна пересекающая ось
  return true
}

Окружности

Окружность задаётся радиусом и точкой. Вот как может выглядеть структура окружности:

struct Circle
{
  float radius
  Vec position
};

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

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

float Distance( Vec2 a, Vec2 b )
{
  return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 )
}

bool CirclevsCircleUnoptimized( Circle a, Circle b )
{
  float r = a.radius + b.radius
  return r < Distance( a.position, b.position )
}

bool CirclevsCircleOptimized( Circle a, Circle b )
{
  float r = a.radius + b.radius
  r *= r
  return r < (a.x + b.x)^2 + (a.y + b.y)^2
}

В общем случае умножение — это гораздо менее затратная операция, чем получение квадратного корня значения.

Разрешение импульсов силы

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

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

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

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

Чтобы достигнуть такого эффекта и при этом следовать интуитивному пониманию того, как должны вести себя объекты, мы используем твёрдые тела и немного математики. Твёрдое тело — это просто форма, задаваемая пользователем (то есть вами, разработчиком), которая явно определяется как недеформируемая. И AABB, и окружности в этой статье недеформируемы, и всегда будут являться либо AABB, либо окружностью. Все сжатия и растяжения запрещены.

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

Объекты столкнулись — что дальше?

Предположим, что мы обнаружили столкновение двух тел. Как их разделить? Будем считать, что распознавание коллизий предоставляет нам две важные характеристики:

Нормаль коллизии
Глубина проникновения

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

Теперь давайте подробно рассмотрим, как же вычислить величину импульса силы. Начнём с двух объектов, для которых обнаружено пересечение:

Уравнение 1

$V^{AB} = V^B - V^A$

Заметьте, что для создания вектора из положения A в положение B необходимо выполнить: endpoint - startpoint. $V^{AB}$ — это относительная скорость из A в B. Это уравнение можно выразить относительно нормали коллизии $n$ , то есть мы хотим узнать относительную скорость из A в B вдоль направления нормали коллизии:

Уравнение 2

$V^{AB} cdot n = (V^B - V^A) cdot n$

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

Уравнение 3

$V_1 = begin{bmatrix}x_1 \y_1end{bmatrix}, V_2 = begin{bmatrix}x_2 \y_2end{bmatrix} \ V_1 cdot V_2 = x_1 * x_2 + y_2 * y_2$

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

Чтобы выбрать нужную упругость (обозначаемую как $e$ , «эпсилон»), отвечающую интуитивно ожидаемым результатам, нам следует использовать наименьшую задействованную упругость:

// Два заданных объекта A и B
e = min( A.restitution, B.restitution )

Получив $e$ , мы можем подставить его в уравнение вычисления величины импульса силы.

Ньютоновский закон восстановления гласит следующее:

Уравнение 4

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

Уравнение 5

$V^{AB} cdot n = -e * (V^B - V^A) cdot n$

Заметьте, что здесь появилось отрицательное значение. Notice how we introduced a negative sign here. По ньютоновскому закону восстановления $V'$ , результирующий вектор после отталкивания, действительно направляется в обратную сторону от V. Так как же представить противоположные направления в нашем уравнении? Ввести знак «минус».

Теперь нам нужно выразить эти скорости под воздействием импульса силы. Вот простое уравнение для изменения вектора на скаляр импульса силы $j$ в определённом направлении $n$ :

Уравнение 6

Надеюсь, это уравнение вам понятно, потому что оно очень важно. У нас есть единичный вектор $n$ , обозначающий направление. Также у нас есть скаляр $j$ , обозначающий длину вектора $n$ . При суммировании отмасштабированного вектора $n$ с $V$ мы получаем $V'$ . Это просто сложение двух векторов, и мы можем использовать это небольшое уравнение для приложения импульса силы одного вектора к другому.

Здесь нам ещё предстоит проделать небольшую работу. Формально импульс силы определяется как изменение импульса. Импульс — это масса * скорость. Зная это, мы можем выразить импульс в соответствии с формальным определением так:

Уравнение 7

$Impulse = mass * Velocity \ Velocity = frac{Impulse}{mass} therefore V' = V + frac{j * n}{mass}$

Три точки в форме треугольника () можно прочитать как «следовательно». Это обозначение используется для того, чтобы из предшествующего ему вывести истинность последующего.

Мы неплохо двигаемся! Однако нам нужно выразить импульс силы с помощью $j$ относительно двух разных объектов. Во время коллизии объектов A и B объект A отталкивается в противоположном от B направлении:

Уравнение 8

$V'^A = V^A + frac{j * n}{mass^A} \ V'^B = V^B - frac{j * n}{mass^B}$

Эти два уравнения отталкивают A от B вдоль единичного вектора направления $n$ на скаляр импульса силы (величины $n$ ) $j$ .

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

Уравнение 9

$(V^A - V^V + frac{j * n}{mass^A} + frac{j * n}{mass^B}) * n = -e * (V^B - V^A) cdot n \ therefore \ (V^A - V^V + frac{j * n}{mass^A} + frac{j * n}{mass^B}) * n + e * (V^B - V^A) cdot n = 0$

Если помните, нашей исходной целью было изолировать величину, потому что мы знаем направление, в котором нужно разрешать коллизию (оно задаётся распознаванием коллизий), и нам осталось только определить величину в этом направлении. В нашем случае неизвестна величина $j$ ; нам нужно выделить $j$ и решить уравнение для неё.

Уравнение 10

$(V^B - V^A) cdot n + j * (frac{j * n}{mass^A} + frac{j * n}{mass^B}) * n + e * (V^B - V^A) cdot n = 0 \ therefore \ (1 + e)((V^B - V^A) cdot n) + j * (frac{j * n}{mass^A} + frac{j * n}{mass^B}) * n = 0 \ therefore \ j = frac{-(1 + e)((V^B - V^A) cdot n)}{frac{1}{mass^A} + frac{1}{mass^B}}$

Ого, довольно много вычислений! Но на этом всё. Важно понимать, что в окончательной форме уравнения 10 слева у нас $j$ (величина), а всё справа нам уже известно. Это значит, что мы можем написать пару строк кода для вычисления скаляра импульса силы $j$ . И этот код гораздо более читаем, чем математическая запись!

void ResolveCollision( Object A, Object B )
{
  // Вычисляем относительную скорость
  Vec2 rv = B.velocity - A.velocity

  // Вычисляем относительную скорость относительно направления нормали
  float velAlongNormal = DotProduct( rv, normal )

  // Не выполняем вычислений, если скорости разделены
  if(velAlongNormal > 0)
    return;

  // Вычисляем упругость
  float e = min( A.restitution, B.restitution)

  // Вычисляем скаляр импульса силы
  float j = -(1 + e) * velAlongNormal
  j /= 1 / A.mass + 1 / B.mass

  // Прикладываем импульс силы
  Vec2 impulse = j * normal
  A.velocity -= 1 / A.mass * impulse
  B.velocity += 1 / B.mass * impulse
}

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

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

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

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

A.inv_mass = 1 / A.mass

Во многих физических движках необработанная масса на самом деле не хранится. Часто физические движки хранят только величину, обратную массе. Просто так бывает, что в большинстве математических расчётов используется масса в виде 1/масса.

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

Для этого можно сделать следующее:

float mass_sum = A.mass + B.mass
float ratio = A.mass / mass_sum
A.velocity -= ratio * impulse

ratio = B.mass / mass_sum
B.velocity += ratio * impulse

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

Тонущие объекты

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

Я предлагаю использовать в качестве бесконечной массы ноль — однако если мы попробуем вычислить обратную массу объекта с нулевой массой, мы получим деление на ноль. Решить эту проблему при вычислении обратной массы можно следующим образом:

if(A.mass == 0)
  A.inv_mass = 0
else
  A.inv_mass = 1 / A.mass

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

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

Для исправления этой ошибки позиционирования необходимо её учитывать, поэтому я покажу вам способ, называемый «линейным проецированием». Линейное проецирование на небольшой процент снижает проникновение двух объектов друг в друга. Оно выполняется после приложения импульса силы. Исправление положения выполняется очень просто: перемещаем каждый объект вдоль нормали коллизии $n$ на процент глубины проникновения:

void PositionalCorrection( Object A, Object B )
{
  const float percent = 0.2 // обычно от 20% до 80%
  Vec2 correction = penetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n
  A.position -= A.inv_mass * correction
  B.position += B.inv_mass * correction
}

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

Однако в этой реализации есть небольшая проблема: если мы всегда разрешаем ошибку позиционирования, то объекты всегда будут дрожать, пока они находятся друг на друге. Чтобы устранить дрожание, нужно задать небольшой допуск. Мы будем выполнять корректировку положения только если проникновение выше определённого произвольного порога, который мы назовём «погружением» («slop»):

void PositionalCorrection( Object A, Object B )
{
  const float percent = 0.2 // обычно от 20% до 80%
  const float slop = 0.01 // обычно от 0.01 до 0.1
  Vec2 correction = max( penetration - k_slop, 0.0f ) / (A.inv_mass + B.inv_mass)) * percent * n
  A.position -= A.inv_mass * correction
  B.position += B.inv_mass * correction
}

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

Генерирование простого многообразия

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

Вот как выглядит объявление стандартного многообразия:

struct Manifold
{
  Object *A;
  Object *B;
  float penetration;
  Vec2 normal;
};

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

Окружность-окружность

Давайте начнём с простейшего алгоритма коллизии: коллизия окружность-окружность. Эта проверка в большей степени тривиальна. Можете ли вы представить, каким будет направление разрешения коллизии? Это вектор от окружности A к окружности B. Его можно получить вычитанием положения B из положения A.

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

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

bool CirclevsCircle( Manifold *m )
{
  // Объявление пары указателей на каждый объект
  Object *A = m->A;
  Object *B = m->B;

  // Вектор от A к B
  Vec2 n = B->pos - A->pos

  float r = A->radius + B->radius
  r *= r

  if(n.LengthSquared( ) > r)
    return false

  // У окружностей распознана коллизия, вычисляем многообразие
  float d = n.Length( ) // вычисляем sqrt

  // Если расстояние между окружностями не равно нулю
  if(d != 0)
  {
    // Расстояние - это разность между радиусом и расстоянием
    m->penetration = r - d

    // Используем d, потому что мы уже вычислили sqrt в Length( )
    // Направлен из A в B, и это единичный вектор
    c->normal = t / d
    return true
  }

  // Окружности имеют одинаковое положение
  else
  {
    // Выбираем случайные (но согласованные) значения
    c->penetration = A->radius
    c->normal = Vec( 1, 0 )
    return true
  }
}

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

AABB-AABB

Проверка AABB-AABB немного более сложна, чем окружность-окружность. Нормаль коллизии не будет вектором из A в B, а будет нормалью к ребру. AABB — это прямоугольник с четырьмя рёбрами. Каждое ребро имеет нормаль. Эта нормаль обозначает единичный вектор, перпендикулярный к ребру.

Исследуем общее уравнение прямой в 2D:

$ax + by + c = 0 \ normal = begin{bmatrix}a \bend{bmatrix}$

В уравнении выше a и b — это вектор нормали к прямой, а вектор (a, b) считается нормализованным (длина вектора равна нулю). Нормаль коллизии (направление разрешения коллизии) будет направлена в сторону одной из нормалей рёбер.

Знаете ли вы, что обозначает c в общем уравнении прямой? c — это расстояния до начала координат. Как мы увидим в следующей части статьи, это очень полезно для проверки того, на какой стороне от прямой находится точка.

Всё, что теперь нужно — определить, какое из рёбер одного объекта сталкивается с другим объектом, после чего мы получим нормаль. Однако иногда могут пересекаться несколько рёбер двух AABB, например, при пересечении двух углов. Это значит, что нам нужно определить ось наименьшего проникновения.

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

Вот полный алгоритм генерирования многообразия AABB-AABB и распознавания коллизий:

bool AABBvsAABB( Manifold *m )
{
  // Задание пары указателей для каждого из объектов
  Object *A = m->A
  Object *B = m->B
 
  // Вектор из A в B
  Vec2 n = B->pos - A->pos
 
  AABB abox = A->aabb
  AABB bbox = B->aabb
 
  // Вычисление половины ширины вдоль оси x для каждого объекта
  float a_extent = (abox.max.x - abox.min.x) / 2
  float b_extent = (bbox.max.x - bbox.min.x) / 2
 
  // Вычисление наложения по оси x
  float x_overlap = a_extent + b_extent - abs( n.x )
 
  // Проверка SAT по оси x
  if(x_overlap > 0)
  {
    // Вычисление половины ширины вдоль оси y для каждого объекта
    float a_extent = (abox.max.y - abox.min.y) / 2
    float b_extent = (bbox.max.y - bbox.min.y) / 2
 
    // Вычисление наложения по оси y
    float y_overlap = a_extent + b_extent - abs( n.y )
 
    // Проверка SAT по оси y
    if(y_overlap > 0)
    {
      // Определяем, по какой из осей проникновение наименьшее
      if(x_overlap > y_overlap)
      {
        // Указываем в направлении B, зная, что n указывает в направлении от A к B
        if(n.x < 0)
          m->normal = Vec2( -1, 0 )
        else
          m->normal = Vec2( 0, 0 )
        m->penetration = x_overlap
        return true
      }
      else
      {
        // Указываем в направлении B, зная, что n указывает в направлении от A к B
        if(n.y < 0)
          m->normal = Vec2( 0, -1 )
        else
          m->normal = Vec2( 0, 1 )
        m->penetration = y_overlap
        return true
      }
    }
  }
}

Окружность-AABB

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

Схема пересечения AABB-окружность.

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

bool AABBvsCircle( Manifold *m )
{
  // Задание пары указателей для каждого из объектов
  Object *A = m->A
  Object *B = m->B

  // Вектор от A к B
  Vec2 n = B->pos - A->pos

  // Ближайшая к центру B точка A
  Vec2 closest = n

  // Вычисление половины ширины вдоль каждой оси
  float x_extent = (A->aabb.max.x - A->aabb.min.x) / 2
  float y_extent = (A->aabb.max.y - A->aabb.min.y) / 2

  // Ограничиваем точку ребром AABB
  closest.x = Clamp( -x_extent, x_extent, closest.x )
  closest.y = Clamp( -y_extent, y_extent, closest.y )

  bool inside = false

  // Окружность внутри AABB, поэтому нам нужно ограничить центр окружности
  // до ближайшего ребра
  if(n == closest)
  {
    inside = true

    // Находим ближайшую ось
    if(abs( n.x ) > abs( n.y ))
    {
      // Отсекаем до ближайшей ширины
      if(closest.x > 0)
        closest.x = x_extent
      else
        closest.x = -x_extent
    }

    // ось y короче
    else
    {
      // Отсекаем до ближайшей ширины
      if(closest.y > 0)
        closest.y = y_extent
      else
        closest.y = -y_extent
    }
  }

  Vec2 normal = n - closest
  real d = normal.LengthSquared( )
  real r = B->radius

  // Если радиус меньше, чем расстояние до ближайшей точки и
  // Окружность не находится внутри AABB
  if(d > r * r && !inside)
    return false

  // Избегаем sqrt, пока он нам не понадобится
  d = sqrt( d )

  // Если окружность была внутри AABB, то нормаль коллизии нужно отобразить
  // в точку снаружи
  if(inside)
  {
    m->normal = -n
    m->penetration = r - d
  }
  else
  {
    m->normal = n
    m->penetration = r - d
  }

  return true
}

Заключение

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

Сортировка и отсечение контактных пар
Широкая фаза
Расслоение
Интеграция
Такты
Пересечение полупространств
Модульность (материалы, масса и силы)

Источник

Making a 2D Physics Engine: The Series

This is the first article in the Making a 2D Physics Engine Series.

Making a 2D Physics Engine: The Math
Making a 2D Physics Engine: Spaces and Bodies
Making a 2D Physics Engine: Shapes, Worlds and Integration
Making a 2D Physics Engine: Mass, Inertia and Forces

Introduction

Why do we need physics in games?

Physics in games helps us simulate a semi-realistic world with which gamers can easily relate to. From the first Donkey Kong game to the latest The Last Of Us, physics help materialize a world. Physics can be realistic or unrealistic depending on the type of game you’re developing. This series of articles will hopefully give you an idea along with the algorithms of how physics engines work and give you enough knowledge to implement your own version of Box2D from scratch!

What do I need to know to simulate physics in my games?

You can always choose to code your own physics engine (which is the main focus of this series of articles) or you can use some commercially or freely available engines like NVIDIA’s PhysX Engine and Havok Physics that you can use in your projects. All game engines come with a physics engine bundled with them, though you still will have to implement game-specific physical entities/simulations such as a vehicle engine, boat, buoyancy, air resistance, and so on. All of these require knowledge in vectors and matrices in both 2D and 3D. This article will go through some of the more important concepts of vectors and matrices required for implementing 2D physics in your games.

Vectors

Let’s start with the most basic concept of points and direction in ‘n’ dimensions: Vectors.

What are Vectors?

A vector is a geometric object used to «carry» point A to point B. It has a magnitude as well as a direction. It is commonly used to represent «vector» quantities like forces, velocities which were talked about in high school physics.

Representing a Vector

A Vector in the ‘n’th dimension has ‘n’ components. 2D, 3D and 4D vectors are commonly used. A vector can be represented as a column matrix, i.e. an nD vector is represented as an n*1 matrix. It can also be represented as an ordered set, like so: ((a_1, a_2, ldots a_{n-1}, a_n))

The components of any vector of 2D or 3D vectors are generally represented by the x, y and z alphabets which also represent the corresponding cartesian coordinates of that vector.

The contents below are targeted towards 2D vectors, but can easily be extended to 3D vectors.

Vector Operations

Length of a Vector

The length (or magnitude) of a vector is equal to the Pythagorean distance between it and the origin (zero vector). It can be represented as follows: (mathbf{||A||} = sqrt{a_1^2 + a_2^2 + ldots + a_n^2})

In code, it can be defined as follows:

float length(Vec2 vec)
    return sqrt(vec.x * vec.x + vec.y * vec.y)

In many cases which require comparision of distances, the expensive sqrt operation is avoided and the square of the length of the vector is used instead.

float sqrLength(Vec2 vec)
    return vec.x * vec.x + vec.y * vec.y

Normalization of Vector (Unit Vector)

A unit vector is a vector whose length is 1. It is commonly used to represent directions like normals and tangents. To get the unit vector (direction) for a specific vector, that vector is divided by it’s length. This process is called normalization.

Vec2 normalized(Vec2 vec)
    return vec * (1 / length(vec))

Multiplication of Vectors

Vectors can be multiplied by a scalar as well as another vector of the same dimensions.

Multiplication of a Vector with a scalar

Vectors can be scaled by a scalar, i.e. each of its components will be multiplied by the scalar.

$mathbf{A}*s=(a_1*s, a_2*s, ldots, a_n*s)$

Multiplication of a Vector with another vector

Two vectors can be multiplied using the Dot (Scalar) Product or Cross (Vector) Product.

Dot Product

The dot product is the sum of the component-wise product of two vectors. It returns a scalar.

$mathbf{A cdotp B} = a_1*b_1 + a_2*b_2 + ldots + a_n*b_n)$

The dot product is one of the most used vector operations as it is closely related to the cosine of the angle between the two vectors.

cos theta = A dot B / (length(A) * length(B))

cos theta = normalized(a) dot normalized(b)

One important thing to remember is that if two vectors are perpendicular to each other, their dot product will be equal to zero (as cos theta = 0).

Cross Product

The cross product is a popular operation in 3D. The cross product, denoted a × b, is a vector perpendicular to both a and b and is defined as

Where n is the vector perpendicular to both a and b.

The cross product is properly defined only for 3D vectors. But since 2D vectors can be considered as 3D vectors lying on the XY plane, the cross product of any two 2D vectors can be defined as the cross product of their 3D planar representations, resulting in a vector along the Z axis which can be represented as a scalar (representing the magnitude of the Z axis vector).

Similarly, a 2D vector crossed with a scalar will result in another 2D vector perpendicular to the original 2D vector.

The cross product for 2D vectors looks as follows:

float cross(Vector2 a, Vec2 b)
  return a.x * b.y - a.y * b.x;
 

Vector2 cross(Vector2 a, float s)
  return Vec2(s * a.y, -s * a.x);
 
Vector2 cross(float s, Vector2 a)
  return Vec2(-s * a.y, s * a.x);

Vector2 Struct Pseudocode

In the programming language of your choice, the Vector2 structure should look as follows. You can change the names according to your choice.

struct Vector2 {
    float x, y;

    float length() {
        return sqrt(x * x + y * y);
    }
    float sqrLength() {
        return x * x + y * y;
    }
    
    Vector2 operator *(Vector2 v, float s) {
        return Vector2(v.x * s, v.y * s);
    }
    
    void normalize() {
        float inv_len = 1 / length();
        x *= inv_len; y *= inv_len;
    }
    
    float dot(Vector2 a, Vector2 b) {
        return a.x * b.x + a.y * b.y;
    }
    
        float cross(Vector2 a, Vec2 b) {
        return a.x * b.y - a.y * b.x;
    }
        Vector2 cross(Vector2 a, float s) {
        return Vec2(s * a.y, -s * a.x);
    }
    Vector2 cross(float s, Vector2 a) {
        return Vec2(-s * a.y, s * a.x);
    }
}

Note that all instances the Vector2 structure, like all primitives in most languages, should be copied by value and not by reference, unless explicitly required. Reference copying of vectors will lead to unnecessary problems and invisible bugs.

Matrices

A matrix is a rectangular array—of numbers, symbols, or expressions, arranged in rows and columns—that is treated in certain prescribed ways. Matrices are generally used in Computer Graphics and physics to transform a point from one basis to another, which includes rotation, translation and scaling.

In this article I will only be covering 2×2 matrices which are used to rotate 2D vectors.

Why Matrices?

If you remember high school mathematics, multiplication of a (l times m) matrix by a (m times n) matrix results in a (l times n) matrix. In this case, a 2×2 matrix multiplied by a vector represented as a 2×1 matrix gives another 2×1 matrix (2D vector). This makes it mathematically easier and computationally efficient to transform a vector. An important transformation, rotation, will be covered in the next few sub-sections.

Rotation in 2D

Each object has an orientation. In terms of rotation, orientation is synonymous with position (i.e the rotation of the object at an instant), angular velocity (the rate of change of orientation) is synonymous with velocity and torque with force. Since objects in 2D can only rotate about the imaginary z-axis, the orientation of a 2D body is a scalar which represents the rotation about the z-axis in radians. Since the distance of the point from the origin must stay constant (by the definition of rotation in angular kinematics), a rotating point will always lie on the circumference of a circle with center as the origin and radius equal to the distance from the origin.

Rotating a Vector by some angle

In a 2D Cartesian plane, for some vector P(x, y), where the angle through which P should be rotated is «theta» then

$begin{bmatrix} x’ \ y’ end{bmatrix} = begin{bmatrix} x cos theta — y sin theta \ x sin theta + y cos theta end{bmatrix} $

This comes directly from the trigonometric compound angle formulae after converting the vectors into polar form.

Using Matrices to Rotate a Vector

Look at the above equation again. I’ve presented it in matrix form so that it’s easier to obtaining the rotation matrix after creating a matrix equation. Try and find the rotation matrix yourself before moving ahead.

The formula for matrix-matrix multiplication for a 2×2 and 2×1 matrix will look somewhat like this:

$begin{bmatrix} A & B\ C & D end{bmatrix} begin{bmatrix} x \ y end{bmatrix} = begin{bmatrix} Ax + By \ Cx + Dy end{bmatrix}$

Now compare this result to the result of the previous equation.

$begin{bmatrix} Ax + By \ Cx + By end{bmatrix} = begin{bmatrix} x cos theta — y sin theta \ x sin theta + y cos theta end{bmatrix}$

From the above relation, we can conclude that

$begin{bmatrix} A & B\ C & D end{bmatrix} = begin{bmatrix}cos theta & -sin theta \ sin theta & cos theta end{bmatrix}$

Matrix2 Structure Pseudocode

A 2*2 matrix structure would look as follows:

struct Matrix2
{
    float m00, m01
    float m10, m11;
    
        void set(real radians) {
        real c = cos(radians);
        real s = sin(radians);

        m00 = c; m01 = -s;
        m10 = s; m11 =  c;
    }
    
    Matrix2 transpose() {
        return Matrix2(m00, m10,
                       m01, m11);
    }
    
    Vector2 operator*(Vector2 rhs) {
        return Vec2(m00 * rhs.x + m01 * rhs.y, m10 * rhs.x + m11 * rhs.y);
    }

    Matrix2 operator*(Matrix2 rhs ) {
    return Mat2(
      m00 * rhs.m00 + m01 * rhs.m10, m00 * rhs.m01 + m01 * rhs.m11,
      m10 * rhs.m00 + m11 * rhs.m10, m10 * rhs.m01 + m11 * rhs.m11);
    }
}

Just like the Vector2 structure, the instances of the Matrix2 structure must also be copied by value.

What Next?

The next article will get you started on making a very basic physics engine with the code. It will include concepts such as shapes, bodies and integration of velocities and forces. I hope to cover collision detection, collision resolution, concave shapes, broad phasing, raycasting, extending to 3D and other such concepts in future articles. I will try to split it into as many articles as I can because it can be a lot to take in!

If you have any comments/suggestions please do let me know!

History

13 Sep 2015: Initially posted

5 Nov 2017: Language and content improvements

Teen programmer with a great zeal for programming, and interested work on Assets for Unity3D, games in Unity3D and small tools and applications for Windows, Linux and Android under Evudio.

Источник

Making a 2D Physics Engine: The Series

This is the first article in the Making a 2D Physics Engine Series.

Making a 2D Physics Engine: The Math
Making a 2D Physics Engine: Spaces and Bodies
Making a 2D Physics Engine: Shapes, Worlds and Integration
Making a 2D Physics Engine: Mass, Inertia and Forces

Introduction

Why do we need physics in games?

What do I need to know to simulate physics in my games?

Vectors

Let’s start with the most basic concept of points and direction in ‘n’ dimensions: Vectors.

What are Vectors?

Representing a Vector

The components of any vector of 2D or 3D vectors are generally represented by the x, y and z alphabets which also represent the corresponding cartesian coordinates of that vector.

The contents below are targeted towards 2D vectors, but can easily be extended to 3D vectors.

Vector Operations

Length of a Vector

In code, it can be defined as follows:

float length(Vec2 vec)
    return sqrt(vec.x * vec.x + vec.y * vec.y)

In many cases which require comparision of distances, the expensive sqrt operation is avoided and the square of the length of the vector is used instead.

float sqrLength(Vec2 vec)
    return vec.x * vec.x + vec.y * vec.y

Normalization of Vector (Unit Vector)

Vec2 normalized(Vec2 vec)
    return vec * (1 / length(vec))

Multiplication of Vectors

Vectors can be multiplied by a scalar as well as another vector of the same dimensions.

Multiplication of a Vector with a scalar

Vectors can be scaled by a scalar, i.e. each of its components will be multiplied by the scalar.

$mathbf{A}*s=(a_1*s, a_2*s, ldots, a_n*s)$

Multiplication of a Vector with another vector

Two vectors can be multiplied using the Dot (Scalar) Product or Cross (Vector) Product.

Dot Product

The dot product is the sum of the component-wise product of two vectors. It returns a scalar.

$mathbf{A cdotp B} = a_1*b_1 + a_2*b_2 + ldots + a_n*b_n)$

The dot product is one of the most used vector operations as it is closely related to the cosine of the angle between the two vectors.

cos theta = A dot B / (length(A) * length(B))

cos theta = normalized(a) dot normalized(b)

One important thing to remember is that if two vectors are perpendicular to each other, their dot product will be equal to zero (as cos theta = 0).

Cross Product

The cross product is a popular operation in 3D. The cross product, denoted a × b, is a vector perpendicular to both a and b and is defined as

Where n is the vector perpendicular to both a and b.

Similarly, a 2D vector crossed with a scalar will result in another 2D vector perpendicular to the original 2D vector.

The cross product for 2D vectors looks as follows:

float cross(Vector2 a, Vec2 b)
  return a.x * b.y - a.y * b.x;
 

Vector2 cross(Vector2 a, float s)
  return Vec2(s * a.y, -s * a.x);
 
Vector2 cross(float s, Vector2 a)
  return Vec2(-s * a.y, s * a.x);

Vector2 Struct Pseudocode

In the programming language of your choice, the Vector2 structure should look as follows. You can change the names according to your choice.

struct Vector2 {
    float x, y;

    float length() {
        return sqrt(x * x + y * y);
    }
    float sqrLength() {
        return x * x + y * y;
    }
    
    Vector2 operator *(Vector2 v, float s) {
        return Vector2(v.x * s, v.y * s);
    }
    
    void normalize() {
        float inv_len = 1 / length();
        x *= inv_len; y *= inv_len;
    }
    
    float dot(Vector2 a, Vector2 b) {
        return a.x * b.x + a.y * b.y;
    }
    
        float cross(Vector2 a, Vec2 b) {
        return a.x * b.y - a.y * b.x;
    }
        Vector2 cross(Vector2 a, float s) {
        return Vec2(s * a.y, -s * a.x);
    }
    Vector2 cross(float s, Vector2 a) {
        return Vec2(-s * a.y, s * a.x);
    }
}

Matrices

In this article I will only be covering 2×2 matrices which are used to rotate 2D vectors.

Why Matrices?

Rotation in 2D

Rotating a Vector by some angle

In a 2D Cartesian plane, for some vector P(x, y), where the angle through which P should be rotated is «theta» then

$begin{bmatrix} x’ \ y’ end{bmatrix} = begin{bmatrix} x cos theta — y sin theta \ x sin theta + y cos theta end{bmatrix} $

This comes directly from the trigonometric compound angle formulae after converting the vectors into polar form.

Using Matrices to Rotate a Vector

The formula for matrix-matrix multiplication for a 2×2 and 2×1 matrix will look somewhat like this:

$begin{bmatrix} A & B\ C & D end{bmatrix} begin{bmatrix} x \ y end{bmatrix} = begin{bmatrix} Ax + By \ Cx + Dy end{bmatrix}$

Now compare this result to the result of the previous equation.

$begin{bmatrix} Ax + By \ Cx + By end{bmatrix} = begin{bmatrix} x cos theta — y sin theta \ x sin theta + y cos theta end{bmatrix}$

From the above relation, we can conclude that

$begin{bmatrix} A & B\ C & D end{bmatrix} = begin{bmatrix}cos theta & -sin theta \ sin theta & cos theta end{bmatrix}$

Matrix2 Structure Pseudocode

A 2*2 matrix structure would look as follows:

struct Matrix2
{
    float m00, m01
    float m10, m11;
    
        void set(real radians) {
        real c = cos(radians);
        real s = sin(radians);

        m00 = c; m01 = -s;
        m10 = s; m11 =  c;
    }
    
    Matrix2 transpose() {
        return Matrix2(m00, m10,
                       m01, m11);
    }
    
    Vector2 operator*(Vector2 rhs) {
        return Vec2(m00 * rhs.x + m01 * rhs.y, m10 * rhs.x + m11 * rhs.y);
    }

    Matrix2 operator*(Matrix2 rhs ) {
    return Mat2(
      m00 * rhs.m00 + m01 * rhs.m10, m00 * rhs.m01 + m01 * rhs.m11,
      m10 * rhs.m00 + m11 * rhs.m10, m10 * rhs.m01 + m11 * rhs.m11);
    }
}

Just like the Vector2 structure, the instances of the Matrix2 structure must also be copied by value.

What Next?

If you have any comments/suggestions please do let me know!

History

13 Sep 2015: Initially posted

5 Nov 2017: Language and content improvements

Teen programmer with a great zeal for programming, and interested work on Assets for Unity3D, games in Unity3D and small tools and applications for Windows, Linux and Android under Evudio.

Источник

Часть 2: ядро движка.

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

Введение

В предыдущем посте я рассмотрел тему разрешения импульсов силы. Прочитайте сначала его, если вы ещё это не сделали!

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

Интегрирование
Метки времени
Модульная архитектура
- Тела
- Формы
- Силы
- Материалы
Широкая фаза
- Отсечение дубликатов контактных пар
- Система слоёв
Проверка пересечения полупространств

Интегрирование

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

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

Он утверждает, что сумма всех сил, действующих на объект, равна массе этого объекта m, умноженной на ускорение a. m указывается в килограммах, a — в метрах/с, а F — в ньютонах.

Немного преобразуем уравнение для вычисления a и получим:

$Уравнение : 2: a=frac{F}{m} therefore a=F * frac{1}{m}$

Следующий этап включает в себя ускорение для перемещения объекта из одного места в другое. Поскольку игра отображается в дискретных отдельных кадрах, создающих иллюзию анимации, необходимо вычислить места каждой из позиций этих дискретных шагов. Более подробный анализ этих уравнений см. в демо интегрирования Эрина Катто с GDC 2009 и в дополнении Ханну к симплектическому методу Эйлера для повышения стабильности в средах с низким FPS.

Интегрирование явным методом Эйлера показано в следующем фрагменте кода, где x — это позициия, а v — скорость. Стоит заметить, что, как объяснено выше, 1/m * F — это ускорение:

// Явный метод Эйлера
x += v * dt
v += (1/m * F) * dt

dt здесь обозначает дельту (прирост) времени. Δ — это символ дельты, и его можно буквально прочитать как «изменение в величине», или записать как Δt. Поэтому когда вы видите dt, это можно читать как «изменение времени». dv — это «изменение скорости».

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

// Симплектический метод Эйлера
v += (1/m * F) * dt
x += v * dt

Заметьте, что я всего лишь преобразовал порядок двух строк кода — см. вышеупомянутую статью Ханну.

В этом посте объясняются численные неточности явного метода Эйлера, но учтите, что Ханну начинает рассматривать RK4, который лично я не рекомендую: gafferongames.com: неточность метода Эйлера.

Этих простых уравнений достаточно для перемещения всех объектов с линейной скоростью и ускорением.

Метки времени

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

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

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

Для начала давайте рассмотрим простую версию постоянной метки времени. Вот пример:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

Этот код ждёт и рендерит игру, пока не пройдёт достаточно времени для обновления физики. Прошедшее время записывается, а дискретные блоки времени размером с dt берутся из accumulator и обрабатываются физикой. Это гарантирует, что в любых условиях физике передаётся одинаковое значение, и что переданное физике значение является точным отображением действительного времени, прошедшего в реальной жизни. Блоки dt удаляются из accumulator, пока accumulator не становится меньше блока dt.

Здесь мы можем устранить пару проблем. Первая связана с тем, сколько времени требуется на обновление физики: что будет, если обновление физики займёт слишком много времени и с каждым игровым циклом accumulator будет всё больше и больше? Это называется «спиралью смерти». Если не решить эту проблему, то движок быстро придёт к полному останову, если расчёт физики будет недостаточно быстрым.

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

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  // Избавляемся от спирали смерти и ограничиваем dt, таким образом
  // ограничивая количество вызовов UpdatePhysics за
  // один игровой цикл.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

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

Следующая проблема гораздо меньше по сравнению со спиралью смерти. Этот цикл получает блоки dt из accumulator, пока accumulator не становится меньше dt. Это здорово, но в accumulator всё равно остаётся немного времени. В этом заключается проблема.

Допустим, что в accumulator каждый кадр остаётся 1/5 от блока dt. На шестом кадре в accumulator будет достаточно оставшегося времени на выполнение ещё одного обновления физики для всех других кадров. Это приведёт к тому, то примерно в одном кадре в секунду, или около того, будет выполняться немного больший дискретный прыжок во времени, и это может быть очень заметно в игре.

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

// линейная интерполяция для a от 0 до 1
// от t1 до t2
t1 * a + t2(1.0f - a)

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

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

Вот полный пример:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  // Избавляемся от спирали смерти и ограничиваем dt, таким образом
  // ограничивая количество вызовов UpdatePhysics за
  // один игровой цикл.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  const float alpha = accumulator / dt;

  RenderGame( alpha )

void RenderGame( float alpha )
  for shape in game do
    // вычисляем интерполированную трансформацию для рендеринга
    Transform i = shape.previous * alpha + shape.current * (1.0f - alpha)
    shape.previous = shape.current
    shape.Render( i )

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

Игрок никогда не догадается, что рендеринг постоянно отстаёт от физики, потому что он будет знать только то, что видит, а видеть он будет идеально плавные переходы от одного кадра к другому.

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

Модульная архитектура

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

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

Тела

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

struct body
{
  Shape *shape;
  Transform tx;
  Material material;
  MassData mass_data;
  Vec2 velocity;
  Vec2 force;
  real gravityScale;
};

Это отличная отправная точка для создания структуры физического тела. Здесь приняты логичные решения для создания хорошей структуры кода.

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

Интерфейс тела и формы.

Сам shape ответственен за вычисление граничных форм, вычисления массы на основании плотности и за рендеринг.

mass_data — это небольшая структура данных для хранения связанной с массой информации:

struct MassData
{
  float mass;
  float inv_mass;

  // Для вращений (будут рассматриваться ниже)
  float inertia;
  float inverse_inertia;
};

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

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

Некоторые из примеров форм, таких как AABB и окружности, можно найти в предыдущей части туториала.

Материалы

Все эти разговоры о массе и плотности приводят нас к вопросу: где же хранится значение плотности? Оно находится в структуре Material:

struct Material
{
  float density;
  float restitution;
};

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

Последнее, о чём стоит упомянуть — это gravity_scale. Масштабирование гравитации для разных объектов очень часто пригождается при тонкой настройке игрового процесса, поэтому в каждое тело стоит добавить это значение специально под эту задачу.

Полезные настройки для самых распространённых материалов можно использовать для создания значения перечисления объекта Material:

Rock       Density : 0.6  Restitution : 0.1
Wood       Density : 0.3  Restitution : 0.2
Metal      Density : 1.2  Restitution : 0.05
BouncyBall Density : 0.3  Restitution : 0.8
SuperBall  Density : 0.3  Restitution : 0.95
Pillow     Density : 0.1  Restitution : 0.2
Static     Density : 0.0  Restitution : 0.4

Силы

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

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

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

HeavyObject object
for body in game do
  if(object.CloseEnoughTo( body )
    object.ApplyForcePullOn( body )

Функция ApplyForcePullOn() может относиться к небольшой силе, притягивающей body к HeavyObject, только если body находится достаточно близко.

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

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

Широкая фаза

В предыдущей статье серии мы ввели процедуры распознавания коллизий. Эти процедуры на самом деле независимы от того, что называется «узкой фазой». Различия между широкой и узкой фазами можно довольно просто найти в Google.

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

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

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

Так как мы работаем с парами объектов, то будет полезно создать подобную структуру:

struct Pair
{
  body *A;
  body *B;
};

Широкая фаза должна собрать группу возможных коллизий и сохранить их все в структурах Pair. Затем эти пары могут быть переданы другой части движка (узкой фазе) для последующего решения.

Пример широкой фазы:

// Генерирует список пар.
// При вызове этой функции все предыдущие пары сбрасываются.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Пространство кэша для AABB, которое будут использоваться
  // для вычисления граничного прямоугольника каждой формы
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Пропуск проверки с самим собой
      if(A == B)
        continue

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}

Приведённый выше код довольно прост: проверяем каждое тело с каждым другим телом, и пропускаем проверки коллизий с самим собой.

Отсечение дубликатов

В последнем разделе есть одна проблема: будет возвращаться множество дубликатов пар! Эти дубликаты нужно убрать из результатов. Если у вас нет под рукой библиотеки сортировки, то для этого понадобится знакомство с алгоритмами сортировки. Если вы пишете на C++, то вам повезло:

// Сортируем пары для выявления дубликатов
sort( pairs, pairs.end( ), SortPairs );

// Создаём очередь из многообразий для решения
{
  int i = 0;
  while(i < pairs.size( ))
  {
    Pair *pair = pairs.begin( ) + i;
    uniquePairs.push_front( pair );

    ++i;

    // Пропускаем дубликаты, выполняя итерации, пока не найдём уникальную пару
    while(i < pairs.size( ))
    {
      Pair *potential_dup = pairs + i;
      if(pair->A != potential_dup->B || pair->B != potential_dup->A)
        break;
      ++i;
    }
  }
}

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

The last thing to mention is the predicate SortPairs(). Эта функция SortPairs() используется для сортировки. Она может выглядеть вот так:

bool SortPairs( Pair lhs, Pair rhs )
{
  if(lhs.A < rhs.A)
    return true;

  if(lhs.A == rhs.A)
    return lhs.B < rhs.B;

  return false;
}

Члены lhs и rhs можно расшифровать как «left hand side» (сторона слева) и «right hand side» (сторона справа). Эти члены обычно используются для работы с параметрами функций, в которых элементы можно логически рассматривать как левую и правую часть какого-то уравнения или алгоритма.

Система слоёв

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

Объяснение системы слоёв: некоторые объекты сталкиваются друг с другом, другие же нет.

Систему слоёв лучше всего реализовать с помощью битовых масок. Чтобы узнать, как битовые маски используются в движках, см. для ознакомления краткое введение в битовые маски для программистов, страницу на Википедии и раздел Filtering в руководстве Box2D.

Система слоёв реализуется в широкой фазе. Здесь я просто вставлю готовый пример широкой фазы:

// Генерирует список пар.
// При вызове этой функции все предыдущие пары сбрасываются.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Пространство кэша для AABB, которое будут использоваться
  // для вычисления граничного прямоугольника каждой формы
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Пропуск проверки с самим собой
      if(A == B)
        continue

      // Учитываться тольк соответствующие слои
      if(!(A->layers & B->layers))
        continue;

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}

Система слоёв оказывается высокоэффективной и очень простой.

Пересечение полупространств

Полупространство можно рассматривать в 2D как одну сторону прямой. Определение того, находится ли точка на одной или другой стороне прямой — довольно распространённая задача, и при реализации собственного физического движка нужно хорошо разобраться в ней. Очень плохо, что эта тема, как мне кажется, нигде в Интернете подробно не раскрыта, и мы это исправим!

Общее уравнение прямой в 2D имеет следующий вид:

Учтите, что несмотря на своё название, вектор нормали не всегда обязательно нормализирован (то есть он не обязательно имеет длину 1).

Чтобы определить, находится ли точка на определённой стороне прямой, всё, что нам нужно — подставить точку в переменные x и y уравнения и проверить знак результата. Результат 0 будет означать, что точка находится на прямой, а положительное/отрицательное значение означают разные стороны прямой.

И на этом всё! Зная это, от точки до прямой является результатом предыдущей проверки. Если вектор нормали не нормализован, то результат отмасштабирован на величину вектора нормали.

Заключение

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

Часть 3: трение, сцена и таблица переходов

В этой части статьи мы рассмотрим следующие темы:

Трение
Сцена
Таблица переходов коллизий

Видео демо

Вот краткое демо того, над чем мы будем работать в этой части:

Трение

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

В реальной жизни трение — это невероятно сложное взаимодействие между различными веществами и для его моделирования принимаются серьёзные допущения и аппроксимации. Эти допущения относятся к математике и обычно формулируются примерно так: «трение можно приближенно представить как один вектор», аналогично тому, как динамика твёрдых тел симулирует взаимодействия реального мира, допуская использование недеформируемых тел с одинаковой по всему объёму плотностью.

Взгляните на видео демо из первой части статьи:

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

Импульсы силы, снова?

Как вы наверно помните из первой части туториала, для разделения проникновения двух объектов при коллизии необходимо значение j, представляющее собой величину импульса силы. Эту величину можно обозначить как jnormal или jN, потому что она используется для изменения скорости вдоль нормали коллизии.

Для добавления реакции трения необходимо вычислить ещё одну величину, обозначаемую как jtangent или jT. Трение можно смоделировать как импульс силы. Эта величина будет изменять скорость объекта вдоль отрицательного касательного вектора коллизии, или, другими словами, вдоль вектора трения. В двух измерениях вычисление вектора трения является решаемой задачей, но в 3D она становится гораздо сложнее.

Трение довольно просто, и мы можем снова воспользоваться нашим предыдущим уравнением для j, только заменим все нормали n на касательный вектор t.

$Уравнение : 1: j=frac{-(1 + e)(V^{B}-V^{A})cdot n)} {frac{1}{mass^A} + frac{1}{mass^B}}$

Заменим n на t:

$Уравнение :2:j=frac{-(1 + e)((V^{B}-V^{A})cdot t)}{frac{1}{mass^A} + frac{1}{mass^B}}$

Хотя в этом уравнении на t заменено всего одно вхождение n, после добавления вращения необходимо будет заменить ещё несколько вхождений, кроме одного в числителе Уравнения 2.

Теперь возникает вопрос, как же вычислить t. Касательный вектор — это вектор, перпендикулярный нормали коллизии, который направлен ближе к нормали. Это может сбивать с толку — не волнуйтесь, у нас есть рисунок!

На рисунке ниже видно, что касательный вектор перпендикулярен нормали. Касательный вектор может быть направлен влево или вправо. Если влево, то он «дальше» от относительной скорости. Однако он определяется как перпендикуляр к нормали, направленный «ближе» к относительной скорости.

Различные виды векторов в кадре времени коллизии твёрдых тел.

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

Если мы знаем это, то касательный вектор равен (где n — нормаль коллизии):

$V^R=V^{B}-V^{A} t=V^R - (V^R cdot n) * n$

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

// Перерасчёт относительной скорости после приложения
// нормального импульса (импульса силы из первой статьи, этот код идёт сразу
// после в той же функции разрешения)
Vec2 rv = VB - VA

// Вычисляем касательный вектор
Vec2 tangent = rv - Dot( rv, normal ) * normal
tangent.Normalize( )

// Вычисляем величину, прилагаемую вдоль вектора трения
float jt = -Dot( rv, t )
jt = jt / (1 / MassA + 1 / MassB)

Вышеприведённый код непосредственно соответствует Уравнению 2. Повторюсь, важно понимать, что вектор трения указывает в направлении, противоположном касательному вектору. Поэтому мы должны добавить знак «минус» при скалярном произведении относительной скорости по касательной, чтобы вычислить относительную скорость вдоль касательного вектора. Знак «минус» переворачивает касательную скорость и внезапно указывает в направлении, в котором должно аппроксимироваться трение.

Закон Амонтона — Кулона

Закон Амонтона — Кулона — это та часть симуляции трения, в которой испытывают затруднение большинство программистов. Мне самому пришлось достаточно долго изучать его, чтобы найти правильный способ моделирования. Хитрость в том, что закон Амонтона — Кулона — это неравенство.

Он гласит:

Другими словами, сила трения всегда меньше или равна нормальной силе, умноженной на некую константу μ (значение которой зависит от материалов объектов).

Нормальная сила — это просто наша старая величина j, умноженная на нормаль коллизии. Так что если вычисленная jt (представляющая собой силу трения) меньше нормальной силы в μ раз, то мы можем использовать нашу величину jt в качестве трения. Если же нет, то вместо неё надо использовать нормальную силу, умноженную на μ. Это условие «если» ограничивает наше трение каким-то максимальным значением, где максимумом будет нормальная сила, умноженная на μ.

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

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

// Перерасчёт относительной скорости после приложения
// нормального импульса (импульса силы из первой статьи, этот код идёт сразу
// после в той же функции разрешения)
Vec2 rv = VB - VA

// Вычисляем касательный вектор
Vec2 tangent = rv - Dot( rv, normal ) * normal
tangent.Normalize( )

// Вычисляем величину, прилагаемую вдоль вектора трения
float jt = -Dot( rv, t )
jt = jt / (1 / MassA + 1 / MassB)

// PythagoreanSolve = A^2 + B^2 = C^2, вычисляем C для заданных A и B
// Используем для аппроксимации мю для заданных коэффициентов трения каждого тела
float mu = PythagoreanSolve( A->staticFriction, B->staticFriction )

// Ограничиваем величину трения и создаём вектор импульса силы
Vec2 frictionImpulse
if(abs( jt ) < j * mu)
  frictionImpulse = jt * t
else
{
  dynamicFriction = PythagoreanSolve( A->dynamicFriction, B->dynamicFriction )
  frictionImpulse = -j * t * dynamicFriction
}

// Прикладываем
A->velocity -= (1 / A->mass) * frictionImpulse
B->velocity += (1 / B->mass) * frictionImpulse

Я решил использовать эту формулу для определения коэффициентов трения между двумя телами при заданных для каждого тела коэффициентах:

$Уравнение :4: Friction=sqrt[]{Friction^2_A + Friction^2_B}$

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

Важно то, что в сравнении используется абсолютное значение jt, потому что теоретически сравнение ограничивает «сырые» величины каким-то порогом. Поскольку j всегда положительно, его нужно перевернуть, чтобы оно представляло истинный вектор трения в случае использования динамического трения.

Статическое и динамическое трение

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

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

Так происходит из-за принципа работы трения на микроскопическом уровне. Здесь поможет ещё одна иллюстрация:

Микроскопические причины необходимости энергии активации при трении.

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

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

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

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

Сцена

Если вы внимательно прочитали раздел «Трение», то поздравляю! Вы завершили самую сложную (по моему мнению) часть всего туториала.

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

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

class Scene
{
public:
  Scene( Vec2 gravity, real dt );
  ~Scene( );

  void SetGravity( Vec2 gravity )
  void SetDT( real dt )

  Body *CreateBody( ShapeInterface *shape, BodyDef def )

  // Вставляет тело в сцену и инициализирует тело (вычисляет массу).
  void InsertBody( Body *body )

  // Удаляет тело из сцены
  void RemoveBody( Body *body )

  // Обновляет сцену одной меткой времени
  void Step( void )

  float GetDT( void )
  LinkedList *GetBodyList( void )
  Vec2 GetGravity( void )
  void QueryAABB( CallBackQuery cb, const AABB& aabb )
  void QueryPoint( CallBackQuery cb, const Point2& point )

private:
  float dt     // Метка времени в секундах
  float inv_dt // Величина, обратная метке времени в секундах
  LinkedList body_list
  uint32 body_count
  Vec2 gravity
  bool debug_draw
  BroadPhase broadphase
};

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

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

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

Таблица переходов

Нам нужен простой способ выбора вызываемой функции коллизий в зависимости от типа двух разных объектов.

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

Таблица переходов в C или C++ — это таблица указателей функций. Индексы, представляющие собой произвольные имена или константы, используются как индекс таблицы и для вызова конкретной функции. Использование одномерной таблицы переходов может выглядеть следующим образом:

enum Animal
{
  Rabbit
  Duck
  Lion
};

const void (*talk)( void )[] = {
  RabbitTalk,
  DuckTalk,
  LionTalk,
};

// Вызываем функцию из таблицы с одномерной виртуальной диспатчеризацией
talk[Rabbit]( ) // Вызываем функцию RabbitTalk

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

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

collisionCallbackArray = {
  AABBvsAABB
  AABBvsCircle
  CirclevsAABB
  CirclevsCircle
}

// Вызываем процедуру коллизий для распознавания коллизии между
// двумя коллайдерами A and B, не зная их точного типа коллайдера
// тип может быть AABB или окружностью
collisionCallbackArray[A->type][B->type]( A, B )

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

Однако стоит заметить, что AABBvsCircle и CirclevsAABB являются дубликатами. Необходимы обе функции! Для одной из этих функций необходимо отразить нормаль, и в этом заключается их единственная разница. Это позволяет выполнять правильное разрешение коллизий вне зависимости от сочетания объектов.

Заключение

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

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

Разрешение вращения оказывается достаточно простым, однако распознавание коллизий становится сложнее.

Часть 4: ориентированные твёрдые тела

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

В этой части мы поговорим о следующих темах:

Математика вращения
Ориентированные формы
Распознавание коллизий
Разрешение коллизий

Пример кода

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

В этом репозитории GitHub содержится сам пример движка вместе с проектом Visual Studio 2010. Для удобства GitHub позволяет просматривать код без необходимости скачивания.

Другие статьи по теме

Филип Диффендерфер форкнул репозиторий, чтобы создать Java-версию движка!

Математика ориентаций

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

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

Векторное произведение

Векторное произведение в 3D — это хорошо известная операция. Однако векторное произведение в 2D может довольно сильно сбивать с толку, потому что оно на самом деле не имеет удобной геометрической интерпретации.

Векторное произведение в 2D, в отличие от версии в 3D, возвращает не вектор, а скаляр. Это скалярное произведение на самом деле определяет величину ортогонального вектора вдоль оси Z, как будто векторное произведение выполняется в 3D. В каком-то смысле, векторное произведение в 2D — это упрощённая версия векторного произведения в 3D, потому что является расширением трёхмерной векторной математики.

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

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

// Векторное произведение двух векторов возвращает скаляр
float CrossProduct( const Vec2& a, const Vec2& b )
{
  return a.x * b.y - a.y * b.x;
}

// Более экзотичные (но необходимые) виды векторных произведений
// с вектором a и скаляром s, оба возвращают вектор
Vec2 CrossProduct( const Vec2& a, float s )
{
  return Vec2( s * a.y, -s * a.x );
}

Vec2 CrossProduct( float s, const Vec2& a )
{
  return Vec2( -s * a.y, s * a.x );
}

Крутящий момент и угловая скорость

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

$T$ обозначает крутящий момент. Крутящий момент — это сила вращения.

$r$ — это вектор из центра масс (ЦМ) в определённую точку объекта. $r$ можно считать «радиусом» от ЦМ до точки. Для каждой уникальной точки объекта нужно своё значение $r$ для подстановки в Уравнение 2.

$omega$ называется «омега» и обозначает скорость вращения. Это отношение будет использоваться для интегрирования угловой скорости твёрдого тела.

Важно понимать, что линейная скорость — это скорость ЦМ твёрдого тела. В предыдущей части у всех объектов не было компонентов вращения, поэтому линейная скорость ЦМ была такой же, что и скорость всех точек тела. При добавлении ориентации точки, удалённые от ЦМ, вращаются быстрее, чем ближние к ЦМ. Это значит, что нам нужно новое уравнение для нахождения скорости точки тела, потому что тела теперь одновременно могут вращаться и перемещаться.

Воспользуется следующим уравнением для понимания связи между точкой тела и скоростью этой точки:

$v$ обозначает линейную скорость. Для преобразования линейной скорости в угловую, необходимо найти векторное произведение радиуса $r$ и $v$ .

То есть мы можем преобразовать Уравнение 3 в другой вид:

Уравнения из предыдущего раздела справедливы, только если твёрдые тела имеют равномерную плотность. Неравномерная плотность делает всю математику, относящуюся к вращению и поведению твёрдого тела, слишком сложной. Более того, если тело, представляющее твёрдое тело, не находится в ЦМ, то вычисления с участием $r$ будут совершенно шаткими.

Инерция

В двух измерениях объект вращается вокруг воображаемой оси Z. Это вращение может быть достаточно сложным и зависит от того, насколько далеко от ЦМ находится масса объекта. Окружность с массой, равной массе длинного тонкого прутка, проще вращать, чем пруток. Этот фактор «сложности вращения» можно воспринимать как момент инерции объекта.

В каком-то смысле, инерция — это вращательная масса объекта. Чем большей инерцией он обладает, тем сложнее привести его во вращение.

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

Интегрирование

Каждому твёрдому телу потребуется ещё несколько полей для хранения информации о вращении. Вот быстрый пример структуры, хранящей дополнительные данные:

struct RigidBody
{
  Shape *shape

  // Линейные компоненты
  Vec2 position
  Vec2 velocity
  float acceleration

  // Угловые компоненты
  float orientation // радианы
  float angularVelocity
  float torque
};

Интегрирование угловой скорости и ориентации тела очень похоже на интегрирование скорости и ускорения. Вот краткий пример кода демонстрирующий его выполнение (подробности интегрирования рассмотрены в предыдущей части):

const Vec2 gravity( 0, -10.0f )
velocity += force * (1.0f / mass + gravity) * dt
angularVelocity += torque * (1.0f / momentOfInertia) * dt
position += velocity * dt
orient += angularVelocity * dt

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

`Mat22`

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

Хорошим примером этого является ориентированный граничный прямоугольник (Oriented Bounding Box, OBB). OBB состоит из ширины и высоты, которые можно представить как векторы. Эти два вектора размерностей можно вращать с помощью матрицы поворота два на два, представляющей оси OBB.

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

struct Mat22
{
  union
  {
    struct
    {
      float m00, m01
      float m10, m11;
    };

    struct
    {
      Vec2 xCol;
      Vec2 yCol;
    };
  };
};

Он имеет следующие полезные операции: создание по углу, создание по векторам столбцов, транспонирование, умножение на Vec2, умножение на другую Mat22, вычисление абсолютного значения.

Последняя функция позволит нам получить из вектора столбец x или y. Функция столбца работает примерно так:

Mat22 m( PI / 2.0f );
Vec2 r = m.ColX( ); // получаем столбец оси x

Эта техника полезна для получения единичного вектора вдоль оси вращения: x или y. Кроме того, матрицу два на два можно создать из двух ортогональных единичных векторов, потому что каждый вектор можно непосредственно вставить в строки. Хотя такой способ создания довольно необычен для двухмерных физических движков, он всё равно может быть полезен для общего понимания работы поворотов и матриц.

Этот конструктор может выглядеть примерно так:

Mat22::Mat22( const Vec2& x, const Vec2& y )
{
  m00 = x.x;
  m01 = x.y;
  m01 = y.x;
  m11 = y.y;
}

// или

Mat22::Mat22( const Vec2& x, const Vec2& y )
{
  xCol = x;
  yCol = y;
}

Поскольку самая важная операция матрицы поворота — это выполнение поворотов на основе угла, то важно иметь возможно создать матрицу из угла и умножить вектор на эту матрицу (чтобы повернуть вектор против часовой стрелки на угол, с которым была создана матрица):

Mat2( real radians )
{
  real c = std::cos( radians );
  real s = std::sin( radians );

  m00 = c; m01 = -s;
  m10 = s; m11 =  c;
}

// Вращаем вектор
const Vec2 operator*( const Vec2& rhs ) const
{
  return Vec2( m00 * rhs.x + m01 * rhs.y, m10 * rhs.x + m11 * rhs.y );
}

Ради краткости я не буду выводить, почему матрица поворота против часовой стрелки имеет следующий вид:

a = angle
cos( a ), -sin( a )
sin( a ),  cos( a )

Однако важно по крайней мере знать, что таков вид матрицы поворота. Подробнее о матрицах поворота можно прочитать на странице в Википедии.

Другие статьи по теме

Создаём собственный программный 3D-движок, часть 2: линейные преобразования

Преобразование к базису

Важно понимать разницу между пространством модели и мира. Пространство модели — это система координат, локальная к физической форме. Её точка начала координат находится в ЦМ, а ориентация системы координат сонаправлена с осями самой фигуры.

Чтобы преобразовать фигуру в пространство мира, её нужно повернуть и переместить. Поворот выполняется в первую очередь, потому что он всегда выполняется относительно точки начала координат. Поскольку объект находится в пространстве модели (точка начала в ЦМ), поворот выполняется относительно ЦМ фигуры. Поворот выполняется с матрицей Mat22. В коде примера матрицы ориентации называются u.

После выполнения поворота объект можно переместить к его позиции в мире сложением векторов.

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

Обратное преобразование (слева направо) из пространства мира в пространство модели красного полигона.

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

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

Распознавание коллизий и генерирование многообразий

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

Полигон с полигоном

Давайте начнём с самой сложной процедуры распознавания коллизий во всём этом туториале. Идея проверки коллизий между двумя полигонами наиболее удачно (по моему мнению) реализуется с помощью теоремы о разделяющей оси (Separating Axis Theorem, SAT).

Однако вместо проецирования размерностей каждого полигона друг на друга существует более новый и эффективный метод, описанный Дирком Грегориусом в лекции на GDC 2013 (бесплатные слайды лежат здесь).

Первое, что нужно понять — это концепция опорных точек.

Опорные точки

Опорная точка полигона — это вершина, наиболее удалённая в заданном направлении. Если две точки имеют одинаковое в заданном направлении расстояние, то выбрать можно любую из них.

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

// Крайняя точка вдоль направления в полигоне
Vec2 GetSupport( const Vec2& dir )
{
  real bestProjection = -FLT_MAX;
  Vec2 bestVertex;

  for(uint32 i = 0; i < m_vertexCount; ++i)
  {
    Vec2 v = m_vertices[i];
    real projection = Dot( v, dir );

    if(projection > bestProjection)
    {
      bestVertex = v;
      bestProjection = projection;
    }
  }

  return bestVertex;
}

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

Поиск оси разделения

Благодаря концепции опорных точек можно выполнить поиск оси разделения между двумя полигонами (полигоном A и полигоном B). Идея этого поиска заключается в том, чтобы пройти в цикле по всем рёбрам полигона A и найти опорные точки в отрицательной нормали к ребру.

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

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

Вот пример функции из исходного кода, которая ищет возможную ось наименьшего проникновения с помощью функции GetSupport:

real FindAxisLeastPenetration( uint32 *faceIndex, PolygonShape *A, PolygonShape *B )
{
  real bestDistance = -FLT_MAX;
  uint32 bestIndex;

  for(uint32 i = 0; i < A->m_vertexCount; ++i)
  {
    // Получаем нормаль к ребру от A
    Vec2 n = A->m_normals[i];

    // Получаем опорную точку от B вдоль -n
    Vec2 s = B->GetSupport( -n );

    // Получаем вершину на ребре от A, преобразуем в
    // пространство модели B
    Vec2 v = A->m_vertices[i];

    // Вычисляем расстояние глубины проникновения (в пространстве модели B)
    real d = Dot( n, s - v );

    // Сохраняем наибольшее расстояние
    if(d > bestDistance)
    {
      bestDistance = d;
      bestIndex = i;
    }
  }

  *faceIndex = bestIndex;
  return bestDistance;
}

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

Эту функцию нужно вызывать дважды, меняя местами при каждом вызове объекты A и B.

Отсечение ребра соударения и базового ребра

На этом этапе стоит определить ребро соударения и базовое ребро, а ребро соударения необходимо отсечь относительно боковых плоскостей базового ребра. Это достаточно нетривиальная операция, хотя Эрин Катто (создатель Box2D и всей физики, используемой Blizzard) подготовил отличные слайды, подробно рассматривающие эту тему.

Это отсечение создаёт две возможные точки контакта. Все точки контакта за базовым ребром можно считать точками контакта.

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

Окружность с полигоном

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

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

После нахождения ближайшего ребра проверка превращается в тест отрезка прямой и окружности. У отрезка прямой есть три интересных области, называемых областями Вороного. Посмотрите на схему:

Области Вороного для отрезка прямой.

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

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

Чтобы вычислить, в какой из областей Вороного лежит окружность, мы используем скалярное произведением между парой вершин. Идея заключается в том, чтобы создать воображаемый треугольник для проверки того, больше или меньше 90 градусов угол, созданный с вершиной отрезка. Для каждой вершины отрезка прямой создаётся по одному треугольнику.

Проецируем на ребро вектор из вершины ребра к центру окружности.

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

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

Разрешение коллизий

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

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

Вот разрешение импульсов силы в том виде, в котором мы оставили его в предыдущей части про трение:

$Уравнение : 5: j=frac{-(1 + e)((V^{A} - V^{B}) * t)}{frac{1}{mass^{A}} + frac{1}{mass^{B}}}$

Если мы добавим компоненты вращения, то конечное уравнение будет выглядеть так:

$Уравнение : 6: j=frac{-(1 + e)((V^{A} - V^{B}) * t)}{frac{1}{mass^{A}} + frac{1}{mass^{B}} + frac{(r^{A} times t)^{2}}{I^{A}} + frac{(r^{B} times t)^{2}}{I^{B}}}$

В приведённом выше уравнении $r$ — это снова «радиус», как в векторе из ЦМ объекта к точке контакта. Это уравнение подробно выводится на сайте Криса Хекера.

Важно понимать, что скорость заданной точки объекта равна:

С учётом условий вращения приложение импульсов силы немного изменилось:

void Body::ApplyImpulse( const Vec2& impulse, const Vec2& contactVector )
{
  velocity += 1.0f / mass * impulse;
  angularVelocity += 1.0f / inertia * Cross( contactVector, impulse );
}

Заключение

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

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

Автор: PatientZero

Источник

Источник

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

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

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

чтобы при прыжке персонаж возвращался на землю, а не улетал в небо;

чтобы мяч летел с нужным ускорением и по заданной траектории, а не туда, куда вздумается;

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

чтобы персонаж ходил и бегал естественно;

и мн. др.

Все эти моменты — это часы работы над программным кодом.

Физика в компьютерных играх

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

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

«шлифовал» на старте;

реагировал на переключение коробки передач;

уходил в заносы;

разгонялся и тормозил, как настоящий автомобиль;

и др.

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

Виды физики в компьютерных играх

Условно физика для разработчиков компьютерных игр разделяется на несколько основных направлений:

для твердых тел;

физика в 3D—проектах;

физика мягких тел;

деформация тел в игре.

Физика твердых тел

Когда мы говорим: «Физика в компьютерных играх», то чаще всего подразумеваем именно этот раздел физики в играх. Например, поведение описанного выше мяча — это физика твердых тел в компьютерных играх.

Она подразумевает соблюдение у объектов в игре законов:

гравитации,

сопротивления,

ускорения,

воздействия других объектов на какой-то объект;

природных катаклизмов;

и мн. др.

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

Физика в 3D-проектах

Физика в 3D-проектах намного сложнее физики 2D-игр, при том что и там и там часто используются одни и те же законы поведения игровых объектов. 3Д усложняется тем, что при разработке таких игр добавляется еще одно пространственное измерение — ось Z. В 2D, как мы знаем, только две оси — X и Y. Поэтому 2Д-игры проектировать проще, так как продумывать нужно небольшое количество взаимодействий между объектами.

В 3Д же один только персонаж — это огромное количество «твердых тел», которым нужно прописывать воздействие физических законов, и при этом все они должны работать как «единый» организм и взаимодействовать по заданному алгоритму. Например, если персонаж игры — человек, то его «твердыми телами» будут:

голова,

руки,

ноги,

суставы на руках и ногах,

пальцы на руках и ногах,

части лица,

и др.

А в 2Д—игре один объект — это одно «твердое тело». Понимаете, насколько сложнее проектировать качественную 3Д-игру? Но при этом не нужно забывать о балансе «реалистичности и увлекательности» игры. Поэтому даже в 3Д—играх приветствуется максимально простой из возможных подходов в разработке. То есть многие мелкие моменты из реальной жизни «упускаются» специально, чтобы не усложнять процесс игры. К примеру, в играх про снайперов могут не учитываться такие мелкие моменты, как:

температура воздуха при выстреле;

скорость и направление ветра;

атмосферное давление;

угол вхождения пули;

и др.

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

Физика мягких тел

С «твердыми телами» в играх вроде все ясно, но, помимо «твердых тел», в играх встречаются еще и «мягкие тела», например:

одежда персонажей,

вода,

снег,

облака,

дым,

туман,

волосы персонажей,

и мн. др.

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

Давайте представим, что все объекты в игре состоят из множества точек. В этом случае «точки» «твердого тела» всегда будут располагаться на одинаковом расстоянии друг от друга. А «точки» «мягкого тела» будут то отдаляться, то приближаться, меняя расстояние между собой.

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

Деформация тел в игре

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

Другое дело, если «мягкое тело» — это центр внимания. Например, у персонажа игры есть плащ, который должен деформироваться и реагировать на действия персонажа игры. Если этот плащ просто «зациклить», то это сразу будет заметно и выглядеть будет очень неестественно. Поэтому тут применяют подход для постоянного расчета нужной деформации такого тела. Именно это добавляет реалистичности.

Почему для всех «мягких тел» не применяют такой подход? Потому что расчет такой деформации — это серьезная нагрузка на процессор и видеокарту вашего компьютера, так как это сложные математические вычисления. И если представить, что все «мягкие тела» реализованы в таком подходе, то ваш компьютер просто не выдержит нагрузки.

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

Заключение

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

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

Источник

Оптимизация под слабые устройства и синхронный PvP.

Технический 3D-художник Banzai Games Роман Терский рассказал, как его команда интегрировала физику в игровой процесс мобильного файтинга Shadow Fight 3, какие приемы использовала для оптимизации и как переписала «с нуля» физику для персонажей для достижения её полной детерминированности в синхронном PvP.

Физика твёрдых тел

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

Детач костей

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

Однако мы столкнулись с небольшой погрешностью, возникающей при просадке FPS: в этом случае кость, подверженная физической симуляции, с небольшой задержкой «догоняет» кость, с которой связана с помощью Joint. Как правило, эта погрешность настолько незначительна, что ей можно пренебречь. Для остальных случаев было применено альтернативное решение.

Фейковый импульс

Рассмотрим это решение на примере шлема мародёра, спартанский гребень которого подвержен физической симуляции. Мы разбили гребень на 5 частей, каждая из которых была прискинена к разным костям. В настройках Joint этих костей выставили лимиты на поворот по нужной оси и задали параметр Twist Limit Spring, отвечающий за эффект пружины.

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

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

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

У каждой анимации (опять же кроме боевой стойки) есть преднастроенный период, в течение которого игрок не может её прервать. По истечении этого срока или в момент получения удара интервал uninterrupted заканчивает своё действие, и в этот момент срабатывает наш импульс. Нужно было только настроить исключения для нескольких анимаций.

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

Элементы снаряжения

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

В ряде случаев (например, с металлическими пластинами) использование коллайдеров неизбежно. Однако основную нагрузку несёт не само наличие коллайдеров, а расчёт их столкновений. Минимизировать эту нагрузку помогает тонкая настройка матрицы столкновения слоёв (Layer Collision Matrix) в Project Settings. Для подобных элементов мы используем два отдельных слоя, которые коллизятся только между собой, таким образом избегая просчёта столкновения с коллайдерами других слоев (оружия, пола, стен и так далее).

Физический клон

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

Манипулируя параметром Is Kinematic в компоненте Rigidbody костей, в зависимости от ситуации мы включаем и выключаем физику для них.

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

Решением стало создание физического клона. Рассмотрим это на примере ножа на цепи.

Во время загрузки боя для него инициализируется два скелета: основной, который находится внутри иерархии персонажа, и его физический клон. В костях основного скелета отсутствует компонент Rigidbody, на их трансформацию влияют только анимационные треки. Кости второго имеют настроенные связи (Joint) и компонент Rigidbody с активным параметром Is Kinematic.

В то время как на трансформацию костей основного скелета влияет анимационный трек, например, во время удара, параметр Is Kinematic в компоненте Rigidbody костей физического клона остаётся активным. Кости не трансформируются и не подвергаются физической симуляции. Во время последнего кадра анимации происходит синхронизация трансформов костей двух скелетов.

Физический клон считывает положение и ротацию костей основного скелета и задаёт своим точно такие же параметры. Затем деактивируется Is Kinematic, и кости физического клона подвергаются симуляции. Далее, вплоть до начала следующей атакующей анимации, уже основной скелет считывает каждый кадр трансформ костей физического клона, которые в этот момент двигаются по физике, и задаёт эти параметры своим костям. Такой подход позволил существенно снизить нагрузку на физический движок и улучшить производительность на слабых устройствах.

Симуляция тканей

При настройке симуляции тканей в рамках производительности мобильных устройств основное ограничение — использование коллизии тканей с коллайдерами. Более дешёвой альтернативой служит тонкая настройка Surface Penetration для констрейнтов ткани. Так как в нашей игре множество анимаций и различных поз персонажей, был составлен список самых «опасных» из них, на которых все ткани проверялись на предмет проникновения сквозь другие части тела.

Также симуляцию тканей мы использовали при создании FX-эффекта пламени на оружиях и на голове босса Теневой разум. В настройках Cloth для этих элементов мы отключили влияние гравитации и задали значения ускорения (Acceleration) по оси Y: постоянный, чтобы пламя стремилось вверх, и рандомный — для эффекта трепыхания. Чтобы при движении не было резкого искажения геометрии, мы выставили повышенное значение сопротивления (Damping). Таким образом мы получили достаточно реалистичный и дешёвый в плане производительности эффект пламени.

Детерминированная физика для синхронного PvP

В момент смерти и в определённых ситуациях при получении удара для персонажей в Shadow Fight 3 активируется симуляция физики. Долгое время для этого использовалась стоковая физика твёрдых тел Unity. Однако при внедрении синхронного PvP в проект от неё пришлось отказаться в пользу собственной разработки.

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

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

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

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

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

Итак, что же представляет из себя наш регдолл? Тело состоит из узлов, которые являются материальными точками. У них нет ориентации, но есть положение и масса, и между ними реализованы связи регулируемой жесткости. К каждой кости внутри скелета персонажа привязана группа таких узлов. Данная архитектура подразумевает отсутствие внутренних коллизий и ограничений в суставах, а внешние коллизии и трение реализованы на уровне узлов. При движении узлов в пространстве учитываются гравитация, внешние силы и инерция.

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

Рёбра

Мышцы

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

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

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

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

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

Изначально при переходе в физику мышцы жёстко расталкивали узлы, приводя их в нужную позицию. Зачастую резкость этого расталкивания также приводила к тому, что конечности сильно выкручивались. Мы добавили плавное увеличение силы мышц, чем сильно улучшили ситуацию.

В течение первых двух кадров после начала симуляции физики сила мышц сохраняется максимальной, чтобы стабилизировать узлы после применения к ним импульса. Затем мышцы расслабляются, их сила становится 55% , а далее в течение 120 кадров сила постепенно увеличивается вплоть до 100%.

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

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

Источник