Pull to refresh

Мир на геодезической сфере: алгоритмы игры Planet

Reading time6 min
Views6.1K
Original author: Boris the Brave
Я уже больше года не писал статей с анализом процедурной генерации в играх. Сегодня мы изучим Planet — игру 2016 года с уютным дизайном, созданную одним из моих любимых разработчиков, Оскаром Сталбергом.


Другие скриншоты



Planet — наполовину технологическое демо, наполовину игра, в итоге создающая настоящую магию. Не так уж просто разобраться, как она работает, однако, к счастью, мне удалось узнать основные подробности из постов в Twitter и статей самого Оскара.

В ней используется множество хороших техник, большая часть которых использовалась в следующих проектах Сталберга наподобие Bad North и Townscaper. Давайте разберёмся, как же устроена эта игра.

Around the World


Наиболее уникальная особенность Planet заключается в том, что её действие происходит на «глобусе». Он выглядит круглым, однако на самом деле весь мир является геодезической сферой.


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

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



Поверхность планеты с приблизительным указанием отдельных треугольников

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

На самом деле, на этапе разработки Оскар экспериментировал, размещая тайлы на плоской поверхности.


Planet на этапе проектирования. К сожалению, церкви в окончательную версию игры не попали

Двойная сетка


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

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

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


Такой стиль выбора, когда пользователь изменяет данные в углах, после чего на основании этого выбираются тайлы, постоянно встречается в работах Оскара, начиная с Brick Block. Он написал о нём хороший пост в Twitter.

Он называет это «двойной сеткой», то есть сеткой, составленной из базовой сетки (также называемой «основной»). Для создания двойной сетки нужно нарисовать по одной вершине в центре каждой грани базовой сетки. Затем нарисовать ребро между двумя двойными вершинами, если соответствующие грани базовой сетки имеют общее ребро. В конечном итоге мы получим новую сетку, имеющую одну грань в двойной сетке для каждой вершины основной сетки, и наоборот.

Конкретно в этом случае основная сетка — это геодезическая сфера, поэтому двойная сетка называется сферой Голдберга.


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

Выбор тайлов


В более раннем проекте Brick Block процесс выбора, который получает данные, хранящиеся в базовых вершинах (или в двойных гранях), и выбирает, какой тайл использовать — это обычный алгоритм Marching Cubes, о котором я уже писал.

Однако Planet работает иначе. Существует 8 возможных высот для рельефа и 4 разных типов рельефа для каждого из трёх углов треугольника. Чтобы учесть все комбинации, необходимо создать $(8\times 4)^3$ разных тайлов. Даже с использованием поворотов и отражений это слишком большое количество для создания вручную и даже для загрузки игры.

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

Ландшафтный дизайн


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

Planet преобразует карту высот в 3D-решётку точек, а затем заполняет эту решётку процессом, напоминающим Marching Cubes. Это позволяет нам многократно использовать одни и те же модули на разных высотах и решать проблему большой разницы высот благодаря сегментам вертикальной стены.

Я проиллюстрирую это 2D-примером. Допустим, у нас есть одномерный массив высот.


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


Затем мы выбираем, что хотим нарисовать, как в обычном marching cubes.


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


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

Утёсы


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


Двухмерные тайлы утёсов


Карты высот, использующие утёсы

В нашем 2D-примере требуется лишь 4 тайла, однако в 3D будет довольно много комбинаций.


Некоторые из тайлов, используемых в Planet

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

Другие слои


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

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

Затем на основании старой карты высот создаётся новая, всем областям без ледников присваивается высота 0. Это используется для размещения модулей ледников.


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

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


На самом деле, нужно не очень много модулей стен (не показаны варианты для разных высот)

Меши из вершин


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


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

Нечто похожее происходит и с тайлами леса.

Мосты


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


В последующих проектах Оскар использовал коллапс волновой функции (Wave Function Collapse), который гораздо умнее выбирает взаимно согласованные тайлы без ручной подстройки алгоритмов. На самом деле, по сравнению с его более поздними проектами намного меньше тайлов.

Технический арт


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

  • Специальный ambient occlusion
  • Симуляция жидкостей для волн на тайлах океана
  • На тайлы рядом с полюсами при помощи шейдера накладывается больше снега
  • Объёмные облака и анимированная луна, атмосферное свечение

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

Подведём итог


Мне кажется, Planet — это демонстрация возможностей автора. В каком-то смысле это промежуточный этап между Brick Block и поздними проектами автора на основе WaveFunctionCollapse, например, Townscaper. Однако мне кажется, что он выглядит более естественно, чем другие. Он показывает, что для реализации сложного выбора тайлов необязательно применять WFC.







Скриншоты, сделанные Оскаром в процессе разработки Planet
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 32: ↑32 and ↓0+32
Comments3

Articles