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

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

Вот небольшая демонстрация работы моей камеры:

Праймер для камеры Arc Ball Camera Primer

Просто для того, чтобы начать с твердой почвы, я собираюсь объяснить геометрические принципы простой камеры от третьего лица, известной как «дуговая камера» или «орбитальная камера». Камера всегда будет находиться на сфере с центром в цели. Таким образом, нам требуются только три параметра для описания местоположения камеры: радиус R сферы и два угла тета и фи. Мы будем называть углы более описательными именами, где тета - это рыскание, а фи - шаг.

Чтобы получить положение камеры в декартовых координатах, мы должны начать с вектора (0, 0, 1), затем повернуть его вокруг оси Y по рысканью, а затем повернуть вокруг «оси тангажа» с помощью подача. Ось тангажа должна быть некоторым вектором, который ортогонален как оси Y, так и вектору, полученному в результате первого вращения. Вы можете найти этот ортогональный вектор, используя векторное произведение. Получив единичный вектор, указывающий в правильном направлении, масштабируйте его по радиусу сферы. Конечным результатом этого вычисления является вектор от цели до камеры, известный как «вектор глаза».

Полная процедура реализована в unit_vector_from_yaw_and_pitch, с хорошим использованием библиотеки nalgebra. (Масштабирование по радиусу будет сделано позже).

Вооружившись этими знаниями, довольно просто реализовать контроллер камеры, который принимает некоторые входные данные и перемещает камеру по сфере или даже масштабирует размер сферы, чтобы увеличивать и уменьшать масштаб камеры. Возьмем, к примеру, ввод с помощью мыши. Удерживая правую кнопку мыши, курсор (dx, dy) будет вызывать вращение (рыскание, тангаж). Величина поворота будет пропорциональна некоторым константам чувствительности в настройках игры. Чтобы масштабировать радиус, я использую колесо прокрутки мыши.

Вы должны обязательно принять во внимание одну деталь: что происходит, когда угол наклона приближается к ± 90 градусов. При использовании такой функции, как UnitQuaternion::face_towards, это вырожденный случай, поскольку вектор глаза коллинеарен «вектору вверх». Это дает мусор, когда камера теряет рассудок. Чтобы избежать этого, я не позволяю абсолютному значению угла тангажа превышать 89,9 градуса.

Создание камеры для вашей игры

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

Вот несколько полезных ресурсов, которые помогут вам ответить на важные вопросы о том, как вы хотите сконструировать камеру:

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

Такой вид сверху вниз довольно распространен. Лучший пример того, что мне нужно, - это камера из Dragon Age: Origins. Эта камера довольно стандартна, но под достаточно большим углом она фактически срезает верхнюю часть всей геометрии, поэтому она не закрывает важные части сцены и упрощает просмотр большей части карты сразу. А что произойдет, если вы захотите посмотреть вверх? Одна вещь, которую вы можете сделать, - это приблизиться к цели и эффективно использовать камеру от первого лица, чтобы осмотреться. Это дает игроку множество вариантов просмотра!

Очевидно, что самая сложная часть реализации такого типа камеры - это обрезать всю геометрию при просмотре издалека. Как вы определяете высоту рубки? Меняется ли высота измельчения при изменении высоты пола? Как вы на самом деле рубите? Как удалить ограничивающие объемы, чтобы можно было проводить лучи через прозрачные потолки? И т.д. Это сложная проблема сама по себе. Я не говорю, что это плохая идея, но это имеет большое значение для того, как вы проектируете свои карты и другую игровую механику. Хотя я ожидаю, что в конце концов вернусь к этой технике или к чему-то подобному, прежде чем попробовать расколоть карту, я решил попробовать что-то другое.

Вместо того, чтобы иметь разные режимы камеры в зависимости от угла обзора, почему бы просто не всегда делать столкновения камеры со всем ландшафтом карты? Причины, по которым этого не следует делать: это сложно и может поставить камеру в затруднительное или неоднозначное положение. Даже сейчас я думаю, что самым большим недостатком моей камеры является то, что она не всегда может дать достаточно широкий обзор сцены, когда она разрешает столкновения в ограниченном пространстве, например, в пещере или коридоре. И во многих случаях проблема нечетко определена! Вы должны сделать выбор за игроком относительно того, куда будет направлена ​​камера, даже если для нее есть несколько «подходящих» мест.

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

Понимание геометрии карты

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

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

Чтобы преобразовать эту дискретную карту во что-то, что можно использовать для непрерывного обнаружения столкновений, я создаю дерево ограничивающего объема (BVT) выровненных по оси ограничивающих прямоугольников (AABB), где каждый непустой воксель получает прямоугольник. Фактически, только те воксели, которые примыкают к пустому вокселю (разделяют с ним лицо), выбираются как имеющие AABB, поскольку в противном случае столкновения не должны достигать воксела. Таким образом, все «вокселы поверхности» будут иметь AABB для выполнения коллизий, что соответствует расположению поверхностей сетки. Общий эффект заключается в том, что если что-то сталкивается с одним из этих AABB, оно останавливается, прежде чем коснется поверхности меша.

Вы можете задаться вопросом, почему мы не используем сам меш только для столкновений. Это должно быть возможно, хотя это более сложная геометрическая задача. Библиотека ncollide3d имеет тип TriMesh, реализующий свойствоShapetrait, поэтому его можно использовать для расчета лучей и времени столкновения. Я лично еще не пробовал, но обдумываю. Я выбрал воксельные AABB для выполнения трехмерного выбора вокселей в моем пользовательском интерфейсе. Так что имело смысл убить двух зайцев одним выстрелом.

Независимо от типа формы, используемой для столкновений, формы будут иметь ограничивающие объемы, которые позволяют хранить их в BVT. BVT реализует черту BVH от ncollide3d, которая позволяет мне использовать множество полезных функций для облегчения кастинга лучей и сфер.

Столкновения камер 101: литье сфер

Если мы следуем правилу «никогда не загораживайте персонажа игрока» в самом строгом смысле, тогда камера всегда должна быть ближайшим объектом к цели (обычно персонажу) на линии обзора. Мы могли бы попытаться направить луч от цели по линии взгляда, и точка, где он впервые сталкивается с объектом, может быть местоположением камеры.

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

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

Хотя сферическое приведение концептуально похоже на приведение лучей, технически оно не так похоже на реализацию. Расчет точки контакта между двумя объемами сильно отличается от вычисления луча и объема. Но ncollide3d снова покрывает нас функцией time_of_impact. Мы можем придать ему любые две формы и их векторы скорости, и он сообщит нам, когда они столкнутся.

Но time_of_impact работает только между двумя фигурами. У нас есть целый BVT AABB! Но не волнуйтесь, ncollide3d имеет Compound фигуру, которая объединяет множество фигур в одну. Это будет работать для большинства случаев использования.

Однако, поскольку у меня есть карта с множеством вокселей, на самом деле для меня менее эффективно хранить Cuboid и Isometry внутри Compound для каждого сплошного вокселя. Можно даже сказать, что хранить AABB для каждого твердого вокселя уже неэффективно, но я пошел на этот компромисс, чтобы быть совместимым с алгоритмами ncollide и сохранять простоту, пока я не буду работать в масштабе, требующем большей эффективности.

Итак, как мне выполнить отливку сфер с голым BVT и без составных форм? Уловка состоит в том, чтобы без больших затрат сузить набор AABB, с которыми наша сфера может столкнуться до вычисления точки контакта. Это можно сделать, вычислив AABB сферы вдоль всего луча и учитывая только AABB внутри него.

В ncollide3d есть BoundingVolumeInterferencesCollector, который делает именно это за нас. Учитывая AABB, он пересечет нашу BVT и найдет все AABB, которые «мешают» ему.

Затем, когда у нас будет более узкий набор AABB, с которыми можно столкнуться, мы должны преобразовать их в Cuboid, чтобы использовать time_of_impact. Мы будем делать это по очереди и помнить, какой куб испытал самое раннее время удара. Это будет последняя точка контакта, которую мы выберем для настройки положения камеры.

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

Где простое сотворение сфер терпит неудачу

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

Как вы думаете, каково будет игроку бегать, пока камера быстро приближается и отдаляется? Нехорошо. Обратите внимание: если мы хотим решить эту проблему, нам нужно нарушить правило, о котором мы упоминали ранее, «никогда не загораживайте персонажа игрока». Конечно, лучше нарушить это правило, чем заставлять камеру подпрыгивать и вызывать у игрока тошноту.

Начнем с простого

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

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

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

Что, если мы переместим цель над землей на некоторое расстояние, чтобы брошенная сфера с меньшей вероятностью столкнулась с землей? У мишени может быть анатомия, ступни и голова. Ноги движутся по земле, а цель камеры - голова. Это действительно очень хорошо работает из-за своей простоты! Но опять же, это не общее решение. Если ступни переместятся под какой-то выступ, голова может фактически войти внутрь геометрии. Тогда ваша сфера начнется с немедленного столкновения, и это заставит игрока почувствовать клаустрофобию.

Что-то немного умнее

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

Поэтому мы могли бы принять во внимание этот факт и сказать: «Мы должны проверять наличие столкновений на фактическом пути камеры».

И для этого мы можем использовать заливку сфер! Если мы запомним положение камеры в последнем кадре, то мы можем отбросить сферу из этого положения в новое желаемое положение в текущем кадре. И что нам делать, если мы столкнулись с столкновением? Мы могли бы просто остановить камеру там, но это внезапно изменило бы угол обзора. Мы могли бы попробовать провести камеру по объекту, с которым она столкнулась, к цели. Это открывает совершенно новую банку червей. Что значит «скользить» по произвольно сложному участку местности? Что ж, мы должны хотя бы снова попытаться избежать окклюзии, верно? Это возвращает нас к тому, с чего мы начали? да.

«Это комната? Когда мы вошли в него? »

После некоторого глубокого размышления о том, какие типы препятствий для камеры важны, а какие следует игнорировать, вы можете начать задавать себе глупые вопросы вроде: «Что такое комната в геометрическом смысле?» Или «где граница между пребыванием снаружи и внутри комнаты?»

И даже когда вы почти уверены, что что-то является коридором, когда вы действительно переступаете порог между внешней и внутренней?

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

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

Прояснение проблемы

Самое большее, о чем мы должны прямо сейчас попросить, - это чтобы камера вела себя одинаково и минимизировала движение, удовлетворяя при этом паре «простых» ограничений:

  1. Оставайтесь за пределами твердой геометрии
  2. Уважайте вклад игрока

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

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

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

Минимизация движения означает, что мы должны иметь некоторую память о предыдущем положении камеры. И затем в следующем кадре мы должны выбрать точку на новой линии обзора, которая близка к предыдущему положению камеры. В приведенном ниже примере мы бы выбирали между размещением камеры в t2A или t2B. Поскольку t2A находится ближе к камере в t1, мы должны выбрать это!

Следующий вопрос: как мы можем быть уверены, что t2A - допустимая позиция? В конце концов, нам нужно обойти препятствие, чтобы его найти. И на самом деле может иметь место второе столкновение на линии обзора, которое мы должны учитывать! Нужно ли нам слепить несколько сфер? И с чего начать эти слепки сфер?

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

Поиск препятствий

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

Я думаю, что если вы достаточно умны, вы, вероятно, сможете заставить эту стратегию работать. Лично мне это показалось дорогим и запутанным. Как узнать, как далеко можно обойти препятствие? Какой угол выбрать? Как узнать, с чего начать сотворение сферы? Я так и не понял. Может, у тебя получится!

Вместо этого я решил немного схитрить и воспользоваться тем фактом, что у меня есть сетка вокселей, которая сообщает мне, где находятся препятствия!

Мое решение: поиск по графику

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

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

Но что тогда нам делать с путем? Мы должны использовать его, чтобы выяснить, где мы должны начать нашу сферу, и это должно быть место, которое:

  1. на линии взгляда
  2. еще не сталкивается с местностью
  3. близко к предыдущему положению камеры

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

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

Итак, вся эта информация попадает в мою эвристическую классификацию. Я говорю, что точка пути «заблокирована», если:

  1. Точка отклоняется слишком далеко от линии обзора. (Я использую некоторый порог минимального расстояния).
  2. Воксель, содержащий проекцию точки на линию обзора, не связан по пути с пустым пространством.

Я определяю №2, пытаясь найти путь между этим проецируемым вокселем и путем.

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

Из всех этих многообещающих точек я выбираю ту, которая ближе всего (по пути) к предыдущему положению камеры (минимизируя движение камеры), и с этой точки я начинаю слепок сферы вдоль линии обзора.

Вот и все! Я просто резюмировал весь алгоритм, который вы видели в действии в верхней части статьи. Конечно, есть некоторые более тонкие детали, которые нужно проработать. Для этого взгляните на проект с открытым исходным кодом Voxel Mapper. Соответствующий код можно найти здесь.

Выбор хорошего алгоритма поиска по графу

Одна деталь, которую я хотел бы немного пояснить, - это мой выбор алгоритма поиска по графу. Есть из чего выбирать. Сначала я попробовал A *, так как он настолько знаком и гарантирует кратчайший путь. Однако стало очевидно, что я не смогу поддерживать хорошую производительность при поиске пути на больших расстояниях, поскольку A * будет расширять многие-многие параметры пути для достижения оптимальности. В моем случае мне не нужен оптимальный путь. По этой причине я переключился на использование жадного поиска по первому наилучшему, который всегда будет расширять наиболее многообещающую вершину строго за счет эвристики и без учета фактической стоимости пути. Не всегда можно найти оптимальный путь, но он быстрый.

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

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

За эту эвристику я должен поблагодарить Амита из RedBlobGames за его замечательную статью об эвристике поиска пути.

Сглаживание движений камеры

В качестве очищающей палитры давайте поговорим о другом: сглаживании камеры.

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

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

s(n + 1) = (1 — w) * x(n) + w * s(n)

x (n) - это входное значение, а s (n) - сглаженное значение. w - вес в [0, 1). Чем ближе w к 1, тем более плавным будет s (n). Я использую w = 0.9, но, вероятно, игрок должен это настроить.

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

Будущая работа

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

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

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

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

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

Если мне удастся реализовать что-то из этого, я постараюсь написать об этом и, как всегда, оставлю исходный код открытым. «До следующего раза, продолжай создавать потрясающие вещи и делиться ими с миром. До свидания!