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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Penetration и Swept-тесты

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

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

SDF Collision Detection

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

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

Назад к Continuous Collision Detection

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

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

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

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

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

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

Что дальше

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