Физический движок

2004 год. Gravity Gun в Half-Life 2. Игроки швыряли унитазы в зомби, строили мосты из бочек, запускали циркулярные пилы в стены. Valve не скриптовала каждое взаимодействие - они запустили честную симуляцию. Каждый унитаз летел по-разному, потому что физика не знала заранее, куда его бросят. До этого - только заскриптованные анимации по триггеру. Gravity Gun стала иконой не потому что была красивой - а потому что впервые дала игроку настоящую физическую свободу.

• Havok Physics работает в Dark Souls, The Elder Scrolls, Assassin's Creed - более 250 AAA тайтлов
• NVIDIA PhysX симулирует до 100K частиц в реальном времени в Apex Destruction
• Bullet Physics - open source, используется в Blender для симуляций, в GTA V для транспорта и ragdoll
• Unity Physics на PBD обрабатывает 10K rigid bodies при 60 FPS на мобильных устройствах
• Box2D - стандарт для 2D indie игр: оригинальная механика Angry Birds основана на нём

Rigid Body и численное интегрирование

2004 год. Valve выпустила Half-Life 2 с движком Havok Physics. Игроки впервые брали Gravity Gun и решали головоломки физикой - толкали ящики, запускали пилы, складывали баррикады. До этого "физика" в играх была ложью: заранее заскриптованные анимации, срабатывающие по триггеру. Havok изменил это одним фундаментальным допущением - **каждый объект в сцене описывается уравнениями движения Ньютона** и симулируется честно, каждый кадр.

**Rigid body** - объект, форма которого не меняется под действием сил. Реальные тела деформируются, но для игр деформация либо не нужна, либо симулируется отдельно (soft body physics). Rigid body описывается шестью степенями свободы: три для позиции $(x, y, z)$ и три для ориентации (углы Эйлера или кватернион). Плюс производные - линейная скорость $\mathbf{v}$ и угловая скорость $\boldsymbol{\omega}$.

Второй закон Ньютона: $\mathbf{F} = m\mathbf{a}$, значит $\mathbf{a} = \mathbf{F}/m$. Каждый кадр накапливаются все силы (гравитация, контактные реакции, пружины), вычисляется ускорение и интегрируется скорость и позиция. Но как именно интегрировать - вопрос неоднозначный, и выбор метода меняет всё.

Три метода интегрирования

**Euler explicit** - самый простой: $\mathbf{v}_{n+1} = \mathbf{v}_n + \mathbf{a}_n \cdot dt$, затем $\mathbf{x}_{n+1} = \mathbf{x}_n + \mathbf{v}_n \cdot dt$. Проблема: численно нестабилен. При $dt$ чуть больше порогового значения энергия системы начинает расти - пружина раскачивается сильнее с каждым кадром. При 30 FPS ($dt = 0.033$) Euler взрывает симуляцию пружинных систем.

**Velocity Verlet** сохраняет энергию в консервативных системах лучше Euler при том же количестве вычислений. Box2D, Bullet, Havok используют его вариации. RK4 точнее, но в 4 раза дороже - оправдан только для симуляций с очень большим dt или мягкими телами.

**RK4** (Runge-Kutta 4-го порядка) делает четыре оценки производной за шаг: $k_1 = f(t_n, y_n)$, $k_2 = f(t_n + dt/2, y_n + k_1 \cdot dt/2)$, $k_3 = f(t_n + dt/2, y_n + k_2 \cdot dt/2)$, $k_4 = f(t_n + dt, y_n + k_3 \cdot dt)$. Итог: $y_{n+1} = y_n + (k_1 + 2k_2 + 2k_3 + k_4) \cdot dt/6$. Глобальная ошибка $O(dt^4)$ против $O(dt^2)$ у Verlet. Для игровой физики фиксированный шаг 60 Hz плюс Verlet дают достаточную точность при минимальных затратах.

Collision Detection: Broad Phase и Narrow Phase

Сцена с 1000 объектами - потенциально $1000 \times 999 / 2 = 499500$ пар для проверки коллизий. Каждая пара - точный геометрический тест. Проверять все - $O(n^2)$. Физический движок умрёт на первом же уровне с городом. Решение - двухфазная архитектура: **broad phase** отсеивает большинство пар дёшево, **narrow phase** точно проверяет только оставшиеся.

Broad Phase: AABB и BVH

**AABB** (Axis-Aligned Bounding Box) - прямоугольник, стороны которого параллельны осям координат. Пересечение двух AABB проверяется за 6 сравнений: если $a.maxX < b.minX$ (или по Y, Z) - пересечения нет. Это быстрее любого точного теста на порядок. Да, AABB даёт ложные срабатывания - но они идут в narrow phase, не в симуляцию.

**BVH** (Bounding Volume Hierarchy) - дерево AABB. Корень охватывает всю сцену, листья - отдельные объекты. Запрос: спуститься по дереву, проверяя AABB узлов - если узел не пересекается с запросом, отсечь всё поддерево. Поиск потенциальных коллизий за $O(\log n)$ вместо $O(n)$. Unreal Engine 5 использует DBVT (Dynamic BVH) - дерево перестраивается инкрементно при движении объектов, без полной перестройки каждый кадр.

Narrow Phase: GJK

AABB часто ложно срабатывает - пара прошла broad phase, но реально не пересекается. Для точного теста нужен narrow phase. **GJK** (Gilbert-Johnson-Keerthi, 1988) - до сих пор стандарт для выпуклых тел. Идея: два выпуклых тела пересекаются тогда и только тогда, когда их **разность Минковского** содержит начало координат.

Разность Минковского $A \ominus B = \{a - b \mid a \in A, b \in B\}$ - множество всех возможных векторов от точки в $B$ до точки в $A$. Если тела пересекаются, $\mathbf{0} \in A \ominus B$. GJK итеративно строит симплекс (тетраэдр в 3D) внутри $A \ominus B$, приближаясь к началу координат. Конвергирует за 4-5 итераций в среднем - очень быстро для такой сложной задачи.

Для невыпуклых тел используют разложение на выпуклые части (convex decomposition) или GJK + EPA (Expanding Polytope Algorithm) для нахождения вектора наименьшего проникновения. Bullet, PhysX, Havok - все используют GJK+EPA как narrow phase основу. Результат narrow phase - **contact manifold**: набор точек контакта с нормалями и глубинами проникновения.

Constraint Solver: Gauss-Seidel и стабильность

Contact manifold готов: 3 объекта, 7 точек контакта. Каждая точка - ограничение: объекты не должны проникать друг в друга. Плюс суставы (joints), пружины, моторы - ещё 20 ограничений. Итого 27 уравнений. Нужно найти импульсы, которые удовлетворяют всем одновременно. Это **constraint solver** - сердце физического движка.

Идеальное решение - MLCP (Mixed Linear Complementarity Problem). Точное решение занимает $O(n^3)$ - слишком дорого для реального времени. Havok, Box2D, Bullet используют **итерационный Gauss-Seidel**: обходить все ограничения по одному, исправлять каждое по очереди, повторить N раз (обычно 8-10 итераций). Неточно - но быстро и достаточно стабильно.

**Warm starting** - ключевая оптимизация: кешировать импульсы предыдущего кадра и использовать как начальное приближение. Gauss-Seidel начинает с хорошего guess и конвергирует за 2-3 итерации вместо 10. Box2D использует warm starting с 2006 года - это разница между 4 FPS и 60 FPS при 100 контактах.

**Positional correction** нужна из-за численных ошибок: объекты медленно проникают друг в друга (sinking). Два подхода - Baumgarte stabilization (добавить штраф за проникновение, быстро, но вносит лишнюю энергию) и Split impulse (корректировать позицию и скорость раздельно, стабильнее). Box2D 2.x использует split impulse.

Современные движки (PhysX 5, Havok 2024) используют **PBD** (Position Based Dynamics) как альтернативу impulse solver для одежды и мягких тел - обновляют позиции напрямую без скоростей. Unity Physics и Nvidia Flex основаны на PBD. Для rigid body constraint solving impulse-based методы всё ещё доминируют - 36 лет после Half-Life 2, Gauss-Seidel всё ещё жив в продакшне.

Итоги

• Rigid body - 6 степеней свободы (позиция + ориентация) плюс линейная и угловая скорость
• Velocity Verlet стабильнее Euler и дешевле RK4 - стандарт игровых физических движков
• Broad phase (AABB + Sort and Sweep / BVH) сокращает O(n^2) пар до O(n log n)
• GJK проверяет пересечение выпуклых тел через разность Минковского за 4-5 итераций
• Constraint solver (Gauss-Seidel) с warm starting: 8-10 итераций достаточно для стабильной симуляции

Связанные темы

Физический движок лежит в основе многих аспектов разработки игр:

• Collision Detection детально — Narrow phase и contact generation для сложных фигур в 2D и 3D
• Game AI и физика — AI агенты используют физику для навигации и предсказания траекторий
• Производительность движка — Физика - один из трёх главных CPU bottleneck в AAA играх

Вопросы для размышления

• Half-Life 2 Gravity Gun изменила gamedev. Какие другие механики сегодня считаются базовыми, но когда-то потребовали прорыва в физическом движке? Что ещё остаётся заскриптованным в современных играх из-за ограничений симуляции?

Связанные уроки

• gd-07 — Детальный разбор collision detection для 2D и 3D
• gd-01 — Game loop - основа fixed-step физического симулятора
• la-01-vectors-intro — Векторы - язык всех вычислений rigid body
• calc-01-sequences — Численное интегрирование - дискретная аппроксимация непрерывной математики
• alg-01-big-o — Broad phase AABB - O(n log n) против O(n^2) naive
• de-01