Миша пишет движок

Все заметки

Динамика твердых тел и интерполяция

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

Если указанные выше проблемы решить, то возникает вопрос – что делать с персонажами? Сейчас движок поддерживает два типа твердых тел: static и dynamic. Первый предназначен для статической геометрии, которая не двигается с места и на нее не действуют никакие силы. Второй тип, при получении вышеописанных свойств, будет скатываться с уклонов, переворачиваться от ударов и вести себя совсем не так, как того хочется при реализации механики перемещения персонажа. Таким образом, нужен третий тип тела – kinematic. Ну или character. Название разнится от движка к движку.

Помимо этого остается еще одна проблема, которую нужно решить перед тем как в очередной раз отложить физику и заняться другими делами. Речь идет об интерполяции. В моем движке физика обновляется с фиксированной частотой, в отличие от основного game loop-а, который работает настолько быстро, насколько позволяет устройство. Разница может быть довольно существенной, и это сразу будет заметно в игре: движущийся физический объект, который перемещается с частотой 50-60 фпс, будет заметно дергаться, если игра работает на частоте 100 фпс и более. Для решения этой проблемы используется интерполяция или экстраполяция положения объекта между итерациями физической симуляции.

Упругие столкновения и вращение

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

fixedUpdate(): void {
  // Применяем силы и импульсы, приложенные к телам.
  // Сюда входит учет гравитации и пользовательских воздействий.
  // Результат – обновление вектора скорости для каждого тела, если это требуется.
  this.physicsSubsystem.integrateVelocities();

  // Алгоритм обнаружения столкновений.
  // Широкая фаза для грубого отсечения непересекающихся пар
  // и узкая для получения детальной информации по подтвердившимся контактам.
  const contacts = this.collisionDetectionSubsystem.update();

  // Обрабатываем столкновения и с учетом этого корректируем скорость.
  this.constraintSolver.update(contacts);

  // Финальный шаг, на котором сдвигаем акторы
  // на основе набранных скоростей и корректировок солвера.
  this.physicsSubsystem.integratePositions();
}

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

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

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

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

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

interface Contact {
  actor1: Actor;
  actor2: Actor;
  normal: Vector2;
  penetration: number;
  contactPoints: Point[];
}

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

interface RigidBody {
  // Коэффициент упругости.
  // Принимает значения от 0 до 1. Чем выше значение, тем сильнее пружинит объект при столкновении,
  // где 1 – абсолютно упругий удар с отражением без потери энергии.
  restitution: number;
  // Коэффициент трения.
  // Используется солвером для замедления тела при скольжении.
  // Помимо составляющей скорости вдоль нормали столкновения,
  // вычисляется скорость по касательной столкновения,
  // что используется для получения импульса трения,
  // который также влияет на итоговую скорость.
  friction: number;
  // Аналог массы, только в контексте вращательного движения.
  // Чем выше значение, тем сложнее повернуть тело.
  // Вычисляется автоматически физической системой на основании массы и формы коллайдера.
  inertia: number;
  // Коэффициент замедления угловой скорости.
  // Используется, если требуется постоянное замедление угловой скорости с течением времени.
  angularDamping: number;
  // Блокировка вращения.
  lockRotation: boolean;

  // ...остальные поля
}

Результат выглядит следующим образом:

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

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

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

Стопки объектов все еще немного подергиваются, перед тем как успокоиться, но тоже ведут себя вполне прилично:

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

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

Контроллер перемещения персонажей

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

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

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

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

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

В основе практически всех shape cast запросов лежит сумма Минковского. Это операция сложения двух фигур, при которой одна фигура будто бы раздувается формой другой. Это позволяет упростить задачу от проверки на пересечение с движущейся фигурой до ray cast запросов, которые я добавлял ранее. Shape cast проверки получились наиболее сложными, потому что комбинируют все использованные ранее подходы в анализе пересечений. Даже при поддержке всего лишь 4 типов фигур, сложность возросла до пугающих размеров, и, надеюсь, в ближайшее время мне к этому больше возвращаться не придется.

По результатам всех доработок collision detection апишки физическая система обзавелась следующим набором методов:

  // методы для поиска ближайшего попадания
  raycast(params: RaycastParams): CastHit | null;
  shapeCast(params: ShapeCastParams): CastHit | null;
  // то же самое, что и shape cast, но вместо геометрии фигуры принимает актор
  // и сам, читая Collider компонент, строит геометрию
  castActor(params: CastActorParams): CastHit | null;

  // тесты пересечений с фигурой в заданной точке
  overlapShape(params: OverlapParams): OverlapHit[];
  overlapActor(params: OverlapActorParams): OverlapHit[];

  // поиск всех попаданий, возвращается массив, отсортированный по расстоянию
  raycastAll(params: RaycastParams): CastHit[];
  shapeCastAll(params: ShapeCastParams): CastHit[];
  castActorAll(params: CastActorParams): CastHit[];

  // тоже поиск всех попаданий,
  // но без создания массива, с проходом через callback функцию
  raycastEach(params: RaycastParams, callback: CastHitCallback): void;
  shapeCastEach(params: ShapeCastParams, callback: CastHitCallback): void;
  overlapEach(params: OverlapParams, callback: OverlapHitCallback): void;
  castActorEach(params: CastActorParams, callback: CastHitCallback): void;
  overlapActorEach(params: OverlapActorParams, callback: OverlapHitCallback): void;

Первые тесты работы контроллера показали, что наивная попытка переиспользовать старый sweep and prune алгоритм для широкой фазы в случае запросов – это не самый эффективный вариант. Каждый запущенный тест повторно запускает упрощенную версию sweep and prune с ранним выходом, но даже так сложность может доходить до O(n). Только контроллер для каждого kinematic тела проводит несколько тестов за раз, не говоря об ИИ, для которого могут потребоваться регулярные cast запросы.

Поэтому я решил заменить свой старый SAP на Bounding Volume Hierarchy. Это бинарное дерево, где листья – это объекты, содержащие ссылку на актор и его ограничивающий объем. В роли такого объема выступает AABB, который я ранее уже использовал для широкой фазы. Листья группируются в более крупные узлы, которые составляют объем, включающий геометрию своих потомков. При вставках и обновлениях дерево нужно регулярно ребалансировать, чтобы поддерживать эффективность поиска. Дерево позволило ускорить поиск потенциальных пересечений в среднем с линейной сложности до логарифмической. Поскольку дерево можно было использовать и для основной широкой фазы collision detection подсистемы, от SAP я отказался полностью.

Для теста производительности собрал небольшую демку со случайно передвигающимися kinematic телами. Две тысячи персонажей мой ноутбук выдержал, хоть уже и заметны просадки фпс со 120 до 70. Можно продолжить мучить профайлер и оптимизировать, но без реальной необходимости в играх (которые я когда-нибудь обязательно начну делать) пока не будем этим больше заниматься.

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

Реализация kinematic движения отняла у меня гораздо больше времени, чем я планировал, но результатом я доволен. Благодаря контроллеру и новому компоненту CharacterBody появляется широкий спектр настроек. Можно регулировать, насколько крутые склоны осилит персонаж. При спусках с горок есть механизм, который “примагничивает” персонажа к склону, чтобы он не спускался рывками. Также стало намного проще определить, есть ли у персонажа под ногами опора, ударился ли он о потолок или стену.

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

interface CharacterBody {
  // Режим перемещения – плавает ли персонаж в воздухе или перемещается по поверхности.
  // Первое можно использовать для летающих врагов или top-down игр, а второе – для платформеров.
  motionMode: CharacterMotionMode;
  // Текущая скорость персонажа.
  velocity: Vector2;
  // Безопасный отступ между персонажем и преградами, чтобы снизить вероятность застревания.
  skinWidth: number;
  // Насколько крутые склоны персонаж может преодолеть.
  maxSlopeAngle: number;
  // Сколько итераций cast запросов нужно выполнить, чтобы скорректировать направление движения.
  maxSlides: number;
  // Сколько итераций overlap запросов нужно выполнить, чтобы вытащить персонажа, застрявшего в преградах.
  maxRecoveries: number;
  // Расстояние до земли, в пределах которого нужно приклеивать персонажа к поверхности.
  // Делает перемещение по неровной поверхности более плавным, особенно на спусках.
  groundSnapDistance: number;
  // Вектор, указывающий, что для персонажа является направлением вверх.
  upDirection: Vector2;
  // Стоит ли сейчас персонаж на земле.
  onGround: boolean;
  // Вектор нормали к поверхности.
  groundNormal: Vector2;
  // Ссылка на актор, представляющий собой поверхность.
  groundActor: Actor | null;
  // Упирается ли сейчас персонаж в стену (препятствие сбоку).
  onWall: boolean;
  // Упирается ли сейчас персонаж в потолок (препятствие сверху).
  onCeiling: boolean;
  // Флаг отключения работы контроллера для данного актора.
  disabled: boolean;
}

Ну и короткая демка напоследок:

Интерполяция

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

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

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

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

Реализация вышла намного проще, чем я думал. Чтобы не перемешивать физику и рендеринг, я добавил отдельную систему Interpolator и Interpolate компонент. Компонент хранит текущие и предыдущие координаты объекта и в зависимости от режима работы (добавил оба: interpolate и extrapolate) вычисляет координаты для отрисовки. Рендерер, при наличии у актора Interpolate компонента, берет позицию оттуда.

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

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

Подводим итоги

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

За это время я писал код сам, мучил Codex, а затем Claude, чтобы реализовать вещи, за которые я бы сам, скорее всего, не взялся и снова отложил задачу в долгий ящик. Агенты помогли пробиться через стену непонимания и отгородили меня от необходимости тратить часы, изучая исходники других библиотек и научные статьи.

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

Результатом я доволен. И в плане объема знаний, который я приобрел, и в плане изменений. То чем была физическая система до доработок и чем стала после – это небо и земля. Еще и юнит тестами все покрыто.

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