Эта заметка приурочена к релизу версии 0.13 моего движка.

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

Первая проба пера - Ray Casting

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

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

Переосмысление - Bounding Volume

Размышляя о представлении уровня, я пришёл к простой идее: всё игровое пространство можно условно разделить на твёрдое и пустое. Тут же вспоминаются BPS-деревья из Quake, которые как раз и выстраивают уровни по такому принципу. Это эффективный подход, но в своей игре я не хотел использовать BSP, к тому же в большинстве игр нет BSP и они каким-то образом тоже справляются с коллизиями.

Мне нужен был самый простой способ обозначить твёрдые, непроходимые объёмы. Тогда я решил использовать в качестве коллизий на уровне простые 3D-коробки (их принято называть AABB), с которыми очень легко проверять пересечения. Игрока я тоже представил 3D-коробкой - так он перестаёт быть точкой и больше не пролезет в непроходимо узкие места.

Это работало лучше, но вскоре стало понятно: одними коробками весь уровень не опишешь. В игре нужны наклонные поверхности, скошенные углы и разные другие сложные формы. Требовался способ проверять пересечения не только с коробками, но и с произвольными 3D-объектами.

Попытка внедрить GJK

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

Этот алгоритм очень понравился мне своей красотой, и с ним я в итоге смог создать коллайдеры для скошенных углов, но всё же главное ограничение GJK не давало мне покоя: алгоритм работает только с выпуклыми фигурми. Это значит, что мне придется вручную разбивать сложную геометрию на множество мелких convex-примитивов и следить за тем, чтобы они были именно convex'ными. Мне начинает казаться, что я вновь иду не тем путём.

Озарение - нужны только треугольники

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

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

Penetration и Swept-тесты

Я начал с простого: реализовал мекотод, который проверяет, пересекается ли в текущий момент сфера игрока с треугольной геометрией, и возвращает глубину утопания сферы в коллизии. Это работало хорошо, но я обнаружил, что на большой скорости игрок может просто-напросто проскочить сквозь геометрию. В текущем кадре он был перед препятствием, а в следующем уже за ним. Столкновение не было обнаружено. Мне нужно вернуться к своей первой идее с Ray Casting'ом, только вместо луча должна быть сфера. Так я обнаружил алгоритм Sphere Casting, который больше известен как Swept Sphere Vs Triangle. Общее название у такого подхода - Continuous Collision Detection.

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

SDF Collision Detection

Удачным образом, в это же время YouTube начал подкидывать мне в рекомендации видеоролики о демосцене, шейдерах и алгоритме SDF (Signed Distance Function), который обычно применяется для визуализации дыма, тумана и облаков в играх. Алгоритм работает с расстояниями - а ведь коллизии тоже про расстояния между объектами. Я задумался: если SDF подходит для рендера, может, его можно адаптировать и под коллизии?

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

Назад к Continuous Collision Detection

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

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

Итоговая реализация

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

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

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

Что дальше

Дальше - дело за оптимизацией самого пространства. Предстоит реализовать Spatial Grid и предварительное отсечение по AABB. Но это уже тема для другой заметки про какую-нибудь из следующих версий моего движка.

А пока - приглашаю опробовать 13-й билд моей игры, в котором я и реализовал описанную систему. Убедитесь сами - такие коллизии работают стабильно и предсказуемо.