Разбираемся в одном из фундаментальных аспектов почти любой игры.
В основе большинства взаимодействий в игре лежат касания объектов — это и попадающий в противника снаряд, и булыжник, падающий на платформу.
Вместе с нашими преподавателями — геймплей-программистом Александром Балакшиным (курс GAMECODE), который работал над Tom Clancy’s Rainbow Six: Siege, и левел-дизайнером Денисом Куандыковым из Void Interactive (курс по созданию уровней OutBlock) — разобрались, как устроены коллайдеры и коллизии и как их используют в создании игр.
Определение коллизий — столкновений объектов в пространстве — это отдельная область вычислительной математики. Оно нужно не только в играх: коллизии просчитывают для автомобильных краш-тестов, систем наведения и ориентации в пространстве, симуляции в CGI для кино и рекламы. Но в играх есть существенное отличие.
Определять положение всех объектов друг относительно друга нужно в течение одного вызова отрисовки, то есть всего за 20-30 мс. За это время должна рассчитаться вся графика и физика в кадре, чтобы игра работала в стабильных 30FPS. А для достижения всех 60FPS нужно успеть «отрисовать» кадр за 16 мс. Чем больше вызовов отрисовки, тем дольше они обсчитываются, тем дольше строится каждый кадр и тем ниже производительность игры. Поэтому, например, разные визуальные эффекты и постобработка снижают частоту кадров в играх, ведь они добавляют количество необходимых вызовов отрисовки.
Расчёт коллизий состоит из нескольких этапов и сам встроен в условную последовательность шагов работы игры.
Когда вы запускаете программу, практически сразу же стартует «бесконечный» цикл. Сначала считывается ввод от пользователя — нажатия на клавиатуру, движение мышкой, управление геймпадом и так далее, затем выполняются некоторые действия в зависимости от текущего ввода и состояния игры — перемещения игрока, выстрел из винтовки, «смерть» врага. И, наконец, выполняются операции вывода — воспроизведение звука, вибрация геймпада или вывод на экран.
геймплей-программист, преподаватель курса по программированию
Этот алгоритм выполняется снова и снова, пока на первом шаге пользователь не решит выйти из игры. А второй шаг — это как бы основной пункт рабочего цикла, часто его называют функцией Update. На нём и происходит расчёт коллизий, который сам делится на несколько этапов: pre-physics, physics update и post-physics.
Pre-physic — это стадия до начала работы физики. Здесь происходит выставление некоторых начальных или новых параметров для объектов, которые необходимы для физической симуляции. Например, скорости или импульсов прикладываемых сил.
На Physics Update уже начинается работа физического движка игры, когда объекты перемещаются, и между ними определяются столкновения.
А на Post-physics все объекты занимают новую позицию, и можно делать вещи, которые мы не могли сделать в pre-physic из-за того, что информация о местоположении объектов у нас была с прошлого кадра. Например, регистрацию попаданий рекомендуют делать именно в этом шаге.
геймплей-программист, преподаватель курса по программированию
Грубо говоря, в Pre-physics задаётся скорость пули, в Physics Update она летит в цель, а в Post-physics становится понятно, достигла она её или нет.
Сама стадия физической симуляции тоже делится на подпункты — широкую фазу (broad phase) и узкую фазу (narrow phase). Возьмём две коробки с игрушками: в широкой фазе проверяется, касаются ли эти коробки, а уже в узкой коробки как бы раскрываются, и начинается проверка самих игрушек.
«Описывающие объёмы»
В широкой идёт работа с так называемыми «описывающими объёмами» — это, условно, самая маленькая «коробка», в которую может поместиться данный объект. Они применяются для того, чтобы понять, какие объекты пересекутся на этапе расчёта более точных коллайдеров. «Описывающими объёмами» могут быть любые простые фигуры, но чаще используют прямоугольные параллелепипеды. Делить их принято на два типа, у каждого из которых есть свои преимущества и недостатки — OOBB (object oriented bounding box) и AABB (axis-aligned bounding box).
OOBB — это описывающие параллелепипеды, оси которых параллельны локальным осям координат заданного объекта. ООВВ строятся один раз и в случае поворота (или масштабирования) объекта также поворачиваются и масштабируются вместе с ним. А оси AABB параллельны уже мировым осям координат. Их всегда надо перестраивать при повороте или масштабировании. Однако у них есть одно существенное преимущество: пересечение таких объектов математически проще проверить, так как все они привязаны к одной координатной сетке.
Принцип этих «описывающих объёмов» показан на картинке — OOBB звезды повернулся вместе с ней параллельно её осям, а AABB при повороте перестроился согласно мировой системе координат.
OOBB и AABB
После того, как на широкой фазе определены потенциально возможные столкновения, начинается узкая фаза, где уже учитываются коллизии объектов. То есть если широкая фаза через простые формы определяла, какие объекты в принципе могут столкнуться, то на узкой у них появляются сложные очертания. Условно, когда водитель видит перед собой фонарный столб, он понимает, что врежется в него, а не в столб позади — это «широкая фаза». Если же он врезается в него, урон получается автомобиль, какой бы сложной ни была его форма — это «узкая фаза».
В ней используются гораздо более сложные алгоритмы для определения пересечений объектов, однако в большинстве случаев хватает алгоритма Гильберта-Джонсона-Кирти, он же GJK: вычисляются разницы координат точек объектов, и если хоть одна из них равно нулю, то они пересекаются. Но у этого алгоритма небольшой недостаток.
GJK работает только с выпуклыми объектами, а такие редко встречаются и в играх, и в реальности. Чаще коллизию создают как совокупность прямоугольных параллелепипедов, боксов, капсул и других выпуклых многогранников, а для них уже применяют GJK. И даже в самом экстремальном случае — когда коллизия совпадает с геометрией объекта, то есть когда есть много очень мелких невыпуклых деталей, которые учитывают столкновения — её все равно можно разбить на выпуклые объекты, а именно треугольники сетки. При этом вычислительные затраты возрастут.
Также стоит заметить, что в некоторых проприетарных движках для объекта могут держать два варианта коллизии — Hi-Res и Lo-Res. Коллизии высокого разрешения максимально приближены к актуальной форме объекта и используются в случаях, когда даже самая небольшая деталь может сыграть роль (например, при броске гранаты). В противоположность им коллизии низкого разрешения могут вообще состоять из одного-двух выпуклых многогранников.
геймплей-программист, преподаватель курса по программированию
Для тех, кто хочет подробнее изучить, как происходит вычисление столкновений в играх, Александр советуеткнигу вице-президента Activision по технологиям Кристера Эриксона «Real-Time Collision Detection» и «Game Physics Cookbook», к которой даже есть репозиторий с исходным кодом на GitHub.
Определение столкновений не всегда сводится к симуляции физики. Часто нужно просто получить информацию об окружающем игрока пространстве.
Есть ли препятствие перед игроком, видит ли нас противник или, наконец, попадем ли мы в противника, если выстрелим в него прямо сейчас. Именно для этого существуют пространственные запросы. Самым популярным из них является трассировка луча, которая также известна как rayсast, raytrace или line trace и сейчас используется и за рамками определения столкновений.
геймплей-программист, преподаватель курса по программированию
Самый очевидный пример использования пространственных запросов в играх — хитбоксы в шутерах с системой стрельбы hitscan, при которой снаряд не летит до цели физически, а попадает в мгновение выстрела. Такая система используется в старых Call of Duty и у нескольких героев Overwatch. Хитбоксы — это невидимые «области удара» на объектах, и больше всего времени разработчики тратят на то, чтобы сделать их «честными».
Так же, как и простые коллизии, [хитбоксы] состоят, как правило, из самых простых примитивов: бокс, сфера, капсула. Главная сложность — подобрать их под модель так, чтобы во время регистрации столкновения создавалось ощущение, что ты попадаешь именно в тело персонажа, а не куда-то рядом с ним или только сильно внутри.
геймплей-программист, преподаватель курса по программированию
По слишком большим хитбоксам противникам легче попасть, а слишком маленькие могут сделать перестрелки слишком сложными. Например, недовольство игроков в Apex Legends на старте вызвали хитбоксы Рэйф, мимо которых многие промахивались, и Патфайндера, у которого хитбоксы были довольно крупными. Вот как высказался об «искусстве» создания «честных» хитбоксов разработчик платформеров серии N.
Я одержим [реализацией хитбоксов] последние 20 лет. Это открытая проблема. Никто её не решил. Я чувствую, что наконец понял, что делает её такой сложной, но не уверен, что могу это объяснить.
разработчик серии N
Источник цитаты: https://www.pcgamer.com/how-hitboxes-work/
N++
Сегодня некоторые движки упрощают создание хитбоксов, как UE4, где для них есть отдельный тип ассетов — PHYS_Asset.
Для того, чтобы найти пересечения луча с хитбоксом, есть различные формулы. По словам Александра, чтобы выполнить трассировку луча «в лоб», необходимо было бы перебрать все доступные коллизии на сцене, но это слишком затратно с точки зрения производительности. Поэтому для ускорения этого процесса используются другие, более оптимизированные способы.
Один из самых популярных — иерархия «описывающих объёмов», или BVH. Её суть в том, что «описывающие объёмы» объектов делятся на группы по 2 или 4 штуки. Для каждой из групп строятся свои «описывающие объёмы», которые также потом проходят процесс группировки. Так продолжается, пока не останется один «описывающий объём» самого верхнего уровня.
геймплей-программист, преподаватель курса по программированию
Пример BVH2
В этом случае вместо того, чтобы проверять пересечение со всеми объектами на сцене, луч сначала доказывает пересечение с одной из групп, затем с одной из групп внутри неё и так до конечного объекта. Будто задания на поиск в области из The Witcher 3 Wild Hunt — когда чем ближе Геральт подходил к цели, тем меньше становился круг поиска. Это позволяет сразу отбросить объекты, с которыми луч, ну или Геральт, никогда не пересечётся. В результате задача трассировки становится значительно проще.
BVH используется в определении столкновений на широкой стадии, когда вместо того, чтобы попарно сравнивать каждый объект, мы можем работать с определенными группами. Есть и другие способы оптимизации «рейкаста»: например, k-d дерево, октодерево (кстати, мы разбирали разрушения на его основе в Teardown) и двоичное разбиение пространства.
Трассировка луча получила развитие в концепции «трассировки объекта», или «шейпкаста». Вместо луча в ней «запускается» объект простой формы вроде сферы или куба. Такую трассировку используют, например, при броске гранаты или перелезании через препятствие. А разработчики Skylanders использовали цилиндрический «шейпкаст» на месте каждого из колёс, чтобы определить их расстояние до трассы и скорректировать их реакцию на ухабы.
При обычном определении столкновений может возникнуть ситуация, когда объекты движутся слишком быстро относительно друг друга, и из-за высокой скорости стандартные алгоритмы не срабатывают. Например, пуля пролетает сквозь противника или автомобиль проходит через стену — это называется «туннельным» эффектом. Такой проблемой страдала, например, печально известная Big Rigs: Over The Road Racing, где автомобиль легко мог проехать сквозь скалу.
«Туннельный» эффект
Для того, чтобы этого избежать, используются техники непрерывного определения столкновений.
Один из самых примитивных вариантов непрерывного определения — это увеличение шага физической симуляции. Т.е. если у нас промежуток между кадрами составляет 33мс, или 30FPS, и мы хотим осуществлять определение коллизий с шагом в 3мс, то этап физического обновления кадра Physics Update будет запущен 10 раз с соответствующим интервалом.
геймплей-программист, преподаватель курса по программированию
Но, по словам Александра, такой метод не даёт гарантии правильного расчёта столкновения, поэтому для быстрых объектов нужно делать «шейпкаст» в направлении движения одного из них.
Правильное использование коллизий очень важно ещё на самых ранних этапах создания уровня. По словам Дениса Куандыкова, преподавателя нашего курса по левел-дизайну и левел-дизайнера Ready Or Not и Frozen Flame, есть два основных подхода к работе с коллайдерами — областями коллизии объекта. Когда они важны для уровня, то есть от них зависит, например, простреливаемость поверхностей или траектории прокидывания гранат над крышами домов, левел-дизайнер расставляет их все самостоятельно.
Обычно они не столько отражают внешний вид объекта, то есть обтекают каждую его часть, сколько призваны облегчить передвижение. Например, лестницы — там может быть два коллайдера: один точный — он для всякой визуальной детализации. Какой-нибудь осколок падает и ударяется точно об лестницу, но не влияет на геймплей. А второй работает, как «рампа» — он не описывает силуэт лестницы, а нужен для комфортного перемещения игрока. Его закладывает левел-дизайнер.
левел-дизайнер, преподаватель курса OutBlock
Бросок гранаты над крышами в Counter-Strike: Global Offensive
Второй подход к коллайдерам на блокауте больше относится к одиночным играм, где высокая точность границ объектов не нужна. Тогда левел-дизайнер просто делает работающий уровень и после следит за тем, чтобы на финальных этапах, когда художники добавят детализацию, ничего не сломалось.
обычно это просто «надежда» — всегда что-то ломается, ибо на уровне получается слишком много элементов.
левел-дизайнер, преподаватель курса OutBlock
При этом на первое место в работе с коллайдерами на уровне ставится не точное соответствие геометрии объекта, а удобство игрока. Если бы коллизия рассчитывалась для соприкосновения с каждым камнем или впадиной на уровне, игрок просто не смог бы перемещаться по нему.
Если у вас есть стена, из которой выпирают разные камни, то, по факту, её игровой коллайдер — это просто примитивный куб, не описывающий эти камни. Для них есть разве что те самые влияющие не на геймплей, а только на визуал дополнительные коллайдеры.
левел-дизайнер, преподаватель курса OutBlock
По словам Дениса, иногда такой подход может привести к странным ситуациям. Например, игрок не упадёт с края пропасти, потому что на его неровной поверхности будет выпирать невидимый куб-коллайдер. Но это лучше, чем «тыкаться» об коллайдер каждого камушка, не говоря уже о том, что они сильно нагружают процессор.