Дизайн физического движка

Когда The Cherno анонсировал серию игровых движков, я как раз начинал разрабатывать свой собственный. Мне хотелось поскорее узнать мнение профессионала в этом вопросе. Будучи программистом-самоучкой, трудно не сомневаться в себе, постоянно размышляя, правильно ли все сделано или так лишь кажется.

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

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

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

Приступаем к созданию движка

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

Я просмотрел способы сортировки движков у bullet и box2d и пришел к выводу, что первый более устойчив. Определившись с тем, что мне необходимо, я построил свой дизайн. Хороших статей, посвященных сложной математике, довольно много, поэтому я сосредоточусь лишь на аспекте дизайна, так как он тоже настоящая головная боль.

Проблему можно разделить на 3 части: динамика, обнаружение столкновений и реакция на столкновения.

Динамика

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

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

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

В этой структуре будет храниться информация об объекте:

struct Object {
	vector3 Position; // Структура с 3 числами с плавающей запятой для x, y, z или i + j + k
	vector3 Velocity;
	vector3 Force;
	float Mass;
};

Нам нужен способ отслеживать объекты, которые хотим обновить. В классическом подходе используется PhysicsWorld со списком объектов и функцией step, которая выполняет по ним цикл. Ниже пример того, как это может выглядеть (для краткости я опустил файлы header/cpp):

class PhysicsWorld {
private:
	std::vector<Object*> m_objects;
	vector3 m_gravity = vector3(0, -9.81f, 0);
 
public:
	void AddObject   (Object* object) { /* ... */ }
	void RemoveObject(Object* object) { /* ... */ }
 
	void Step(
		float dt)
	{
		for (Object* obj : m_objects) {
			obj->Force += obj->Mass * m_gravity; // Применяем силу
 
			obj->Velocity += obj->Force / obj->Mass * dt;
			obj->Position += obj->Velocity * dt;
 
			obj->Force = vector3(0, 0, 0); // Сбрасываем результирующую силу в конце
		}
	}
};

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

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

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

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

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

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

struct CollisionPoints {
	vector3 A; // Самая дальняя точка A в B
	vector3 B; // Самая дальняя точка B в A
	vector3 Normal; // Нормализированный BA
	float Depth;    // Длина BA
	bool HasCollision;
};
 
struct Transform { // Описывает расположение объектов
	vector3 Position;
	vector3 Scale;
	quaternion Rotation;
};

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

struct Collider {
	virtual CollisionPoints TestCollision(
		const Transform* transform,
		const Collider* collider,
		const Transform* colliderTransform) const = 0;
 
	virtual CollisionPoints TestCollision(
		const Transform* transform,
		const SphereCollider* sphere,
		const Transform* sphereTransform) const = 0;
 
	virtual CollisionPoints TestCollision(
		const Transform* transform,
		const PlaneCollider* plane,
		const Transform* planeTransform) const = 0;
};

Создадим оба типа коллайдеров и посмотрим, как они взаимодействуют. Сфера определяется как точка и радиус, а плоскость — как вектор и расстояние. Переопределяем функции из Collider, а о работе пока не беспокоимся.

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

struct SphereCollider
	: Collider
{
	vector3 Center;
	float Radius;
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const Collider* collider,
		const Transform* colliderTransform) const override
	{
		return collider->TestCollision(colliderTransform, this, transform);
	}
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const SphereCollider* sphere,
		const Transform* sphereTransform) const override
	{
		return algo::FindSphereSphereCollisionPoints(
			this, transform, sphere, sphereTransform);
	}
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const PlaneCollider* plane,
		const Transform* planeTransform) const override
	{
		return algo::FindSpherePlaneCollisionPoints(
			this, transform, plane, planeTransform);
	}
};

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

struct PlaneCollider
	: Collider
{
	vector3 Plane;
	float Distance;
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const Collider* collider,
		const Transform* colliderTransform) const override
	{
		return collider->TestCollision(colliderTransform, this, transform);
	}
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const SphereCollider* sphere,
		const Transform* sphereTransform) const override
	{
		// Повторно используем код сферы
		return sphere->TestCollision(sphereTransform, this, transform);
	}
 
	CollisionPoints TestCollision(
		const Transform* transform,
		const PlaneCollider* plane,
		const Transform* planeTransform) const override
	{
		return {}; // Отсутствие столкновения plane-plane
	}
};

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

Чтобы обойти эту проблему, создадим пространство имен algo и поместим в него фактическую работу. Нам понадобится функция для каждой пары коллайдеров, которую нужно будет проверить. Я создал Sphere-Sphere и Sphere-Plane, но не Plane-Plane, потому что она вряд ли пригодится. Я не буду подробно описывать эти функции, так как по сути они не являются частью дизайна, но вы можете просмотреть их исходный код.

namespace algo {
	CollisionPoints FindSphereSphereCollisionPoints(
		const SphereCollider* a, const Transform* ta,
		const SphereCollider* b, const Transform* tb);
 
 
	CollisionPoints FindSpherePlaneCollisionPoints(
		const SphereCollider* a, const Transform* ta,
		const PlaneCollider* b, const Transform* tb);
}

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

struct Object {
	float Mass;
	vector3 Velocity;
	vector3 Force;
 
	Collider* Collider;
	Transform* Transform;
};

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

Для начала еще одна вспомогательная структура:

struct Collision {
	Object* ObjA;
	Object* ObjB;
	CollisionPoints Points;
};

Повторюсь, у нас есть PhysicsWorld (я сокращаю части, которые мы уже рассмотрели):

class PhysicsWorld {
private:
	std::vector<Object*> m_objects;
	vector3 m_gravity = vector3(0, -9.81f, 0);
 
public:
	void AddObject   (Object* object) { /* ... */ }
	void RemoveObject(Object* object) { /* ... */ }
 
	void Step(
		float dt)
	{
		ResolveCollisions(dt);
 
		for (Object* obj : m_objects) { /* ... */ }
	}
 
	void ResolveCollisions(
		float dt)
	{
		std::vector<Collision> collisions;
		for (Object* a : m_objects) {
			for (Object* b : m_objects) {
				if (a == b) break;
 
				if (    !a->Collider
					|| !b->Collider)
				{
					continue;
				}
 
				CollisionPoints points = a->Collider->TestCollision(
					a->Transform,
					b->Collider,
					b->Transform);
 
				if (points.HasCollision) {
					collisions.emplace_back(a, b, points);
				}
			}
		}
 
		// Решение столкновений
	}
};

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

Есть лишь один неприятный момент: поскольку порядок объектов неизвестен, иногда вы будете получать проверку Sphere-Plane, а временами — Plane-Sphere. Если бы мы просто вызвали функцию algo для Sphere-Plane, то получили бы реверсивный ответ. Таким образом, нам нужно добавить немного кода в коллайдер плоскости, чтобы поменять порядок CollisionPoints.

CollisionPoints PlaneCollider::TestCollision(
	const Transform* transform,
	const SphereCollider* sphere,
	const Transform* sphereTransform) const
{
	// Повторно вводим код сферы
	CollisionPoints points = sphere->TestCollision(sphereTransform, this, transform);
 
	vector3 T = points.A; // У вас может быть алгоритм Plane-Sphere для обмена
	points.A = points.B;
	points.B = T;
 
	points.Normal = -points.Normal;
 
	return points;
}

Теперь, когда мы обнаружили столкновение, нужно как-то отреагировать на него.

Реакция на столкновения

Поскольку мы заменили концепцию различных форм на точки, реакция на столкновение — это практически чистая математика. Дизайн относительно прост по сравнению с тем, что рассмотрено выше. А начнем мы с концепции Solver. Он используется для решения проблем в PhysicsWorld и представляет собой импульс от столкновения или изменение исходной позиции — все, что вы захотите реализовать.

Начнем с интерфейса:

class Solver {
public:
	virtual void Solve(
		std::vector<Collision>& collisions,
		float dt) = 0;
};

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

class PhysicsWorld {
private:
	std::vector<Object*> m_objects;
	std::vector<Solver*> m_solvers;
	vector3 m_gravity = vector3(0, -9.81f, 0);
 
public:
	void AddObject   (Object* object) { /* ... */ }
	void RemoveObject(Object* object) { /* ... */ }
 
	void AddSolver   (Solver* solver) { /* ... */ }
	void RemoveSolver(Solver* solver) { /* ... */ }
 
	void Step(float dt) { /* ... */ }
 
	void ResolveCollisions(
		float dt)
	{
		std::vector<Collision> collisions;
		for (Object* a : m_objects) { /* ... */ }
 
		for (Solver* solver : m_solvers) {
			solver->Solve(collisions, dt);
		}
	}
};

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

Демо:

Другие опции

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

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

Самое большое изменение, которое мы можем внести, — это различие между объектами, имитирующими динамику, и теми, что не имитируют динамику. Поскольку динамическим объектам требуется еще много настроек, давайте отделим их от тех элементов, что необходимы для обнаружения столкновений. Мы можем разделить Object на структуры CollisionObject и Rigidbody. Rigidbody будет наследовать от CollisionObject для повторного использования свойств коллайдера и легкости хранения обоих типов.

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

struct CollisionObject {
protected:
	Transform* m_transform;
	Collider* m_collider;
	bool m_isTrigger;
	bool m_isDynamic;
 
	std::function<void(Collision&, float)> m_onCollision;
 
public:
	// Геттеры и сеттеры, отсутствие сеттера для isDynamic
};

В Rigidbody можно добавить еще много настроек. У каждого объекта должна быть собственная гравитация, трение и упругость. Это откроет двери для всевозможных эффектов, основанных на физике. В игре у вас может быть способность на время изменять гравитацию в пространстве. Некоторые объекты могут быть упругими, а другие — более твердыми. Пол можно сделать из льда для скольжения и усложнения испытания.

struct Rigidbody
	: CollisionObject
{
private:
	vector3 m_gravity;  // Гравитационное ускорение
	vector3 m_force;    // Результирующая сила
	vector3 m_velocity;
 
	float m_mass;
	bool m_takesGravity; // Если rigidbody заберет у мира гравитацию
 
	float m_staticFriction;  // Коэффициент статического трения
	float m_dynamicFriction; // Коэффициент динамического трения
	float m_restitution;     // Эластичность столкновений (упругость)
 
public:
	// Геттеры и сеттеры
};

Также разделим PhysicsWorld на CollisionWorld и DynamicsWorld. Функцию Step можно переместить в DynamicsWorld, а ResolveCollisions — в CollisionWorld. Это избавляет тех, кому динамика не нужна, от необходимости просматривать бесполезные функции.

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

class CollisionWorld {
protected:
	std::vector<CollisionObject*> m_objects;
	std::vector<Solver*> m_solvers;
 
	std::function<void(Collision&, float)> m_onCollision;
 
public:
	void AddCollisionObject   (CollisionObject* object) { /* ... */ }
	void RemoveCollisionObject(CollisionObject* object) { /* ... */ }
 
	void AddSolver   (Solver* solver) { /* ... */ }
	void RemoveSolver(Solver* solver) { /* ... */ }
 
	void SetCollisionCallback(std::function<void(Collision&, float)>& callback) { /* ... */ }
 
	void SolveCollisions(
		std::vector<Collision>& collisions,
		float dt)
	{
		for (Solver* solver : m_solvers) {
			solver->Solve(collisions, dt);
		}
	}
 
	void SendCollisionCallbacks(
		std::vector<Collision>& collisions,
		float dt)
	{
		for (Collision& collision : collisions) {
			m_onCollision(collision, dt);
 
			auto& a = collision.ObjA->OnCollision();
			auto& b = collision.ObjB->OnCollision();
 
			if (a) a(collision, dt);
			if (b) b(collision, dt);
		}
	}
 
	void ResolveCollisions(
		float dt)
	{
		std::vector<Collision> collisions;
		std::vector<Collision> triggers;
		for (CollisionObject* a : m_objects) {
			for (CollisionObject* b : m_objects) {
				if (a == b) break;
 
				if (    !a->Col()
					|| !b->Col())
				{
					continue;
				}
 
				CollisionPoints points = a->Col()->TestCollision(
					a->Trans(),
					b->Col(),
					b->Trans());
 
				if (points.HasCollision) {
					if (    a->IsTrigger()
						|| b->IsTrigger())
					{
						triggers.emplace_back(a, b, points);
					}
 
					else {
						collisions.emplace_back(a, b, points);
					}
				}
			}
		}
 
		SolveCollisions(collisions, dt); // Don't solve triggers
 
		SendCollisionCallbacks(collisions, dt);
		SendCollisionCallbacks(triggers, dt);
	}
};

Для удобства чтения также разделим функцию Step на части:

class DynamicsWorld
	: public CollisionWorld
{
private:
	vector3 m_gravity = vector3(0, -9.81f, 0);
 
public:
	void AddRigidbody(
		Rigidbody* rigidbody)
	{
		if (rigidbody->TakesGravity()) {
			rigidbody->SetGravity(m_gravity);
		}
 
		AddCollisionObject(rigidbody);
	}
 
	void ApplyGravity() {
		for (CollisionObject* object : m_objects) {
			if (!object->IsDynamic()) continue;
 
			Rigidbody* rigidbody = (Rigidbody*)object;
			rigidbody->ApplyForce(rigidbody->Gravity() * rigidbody->Mass());
		}
	}
 
	void MoveObjects(
		float dt)
	{
		for (CollisionObject* object : m_objects) {
			if (!object->IsDynamic()) continue;
 
			Rigidbody* rigidbody = (Rigidbody*)object;
 
			vector3 vel = rigidbody->Velocity()
					  + rigidbody->Force() / rigidbody->Mass()
					  * dt;
 
			rigidbody->SetVelocity(vel);

			vector3 pos = rigidbody->Position()
					  + rigidbody->Velocity()
					  * dt;
 
			rigidbody->SetPosition(pos);
 
			rigidbody->SetForce(vector3(0, 0, 0));
		}
	}
 
	void Step(
		float dt)
	{
		ApplyGravity();
		ResolveCollisions(dt);
		MoveObjects(dt);
	}
};

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

Также хочу затронуть еще одну опцию. PhysicsWorld не нуждается в обновлении каждого кадра. Допустим, игра вроде CS:GO рендерится со скоростью 300 кадров в секунду. Она не проверяет физику в каждом кадре. Вместо этого она может работать на частоте 50 Гц. Если бы игра использовала позиции только из физического движка, объекты обновлялись бы каждые 0,02 секунды, что приводило бы к эффекту тряски. И это идеальная скорость. Некоторые игры обновляются с частотой лишь 20 Гц, а интервал между обновлениями составляет 0,05 секунды!

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

Сначала избавляемся от указателя. Нам также нужно добавить последнее преобразование, которое будет установлено непосредственно перед обновлением в MoveObjects.

struct CollisionObject {
protected:
	Transform m_transform;
	Transform m_lastTransform;
	Collider* m_collider;
	bool m_isTrigger;
	bool m_isStatic;
	bool m_isDynamic;
 
	std::function<void(Collision&, float)> m_onCollision;
public:
	// Геттеры и сеттеры для всех элементов, отсутствие сеттера для isDynamic
};

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

class PhysicsSmoothStepSystem {
private:
	float accumulator = 0.0f;
 
public:
	void Update() {
		for (Entity entity : GetAllPhysicsEntities()) {
			Transform*       transform = entity.Get<Transform>();
			CollisionObject* object    = entity.Get<CollisionObject>();
 
			Transform& last    = object->LastTransform();
			Transform& current = object->Transform();
 
			transform->Position = lerp(
				last.Position,
				current.Position,
				accumulator / PhysicsUpdateRate()
			);
		}
 
		accumulator += FrameDeltaTime();
	}
 
	void PhysicsUpdate() {
		accumulator = 0.0f;
	}
};

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

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

Спасибо за чтение!

Читайте также:

• Тест рабочего цикла C++ через написание кода для декодера base85
• Распознаём 50 видов текста на C++ с Plywood
• Шаблон проектирования прототипов в современном C++

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Winter’s Blog: Designing a physics engine