Я был одержим процедурными картами с ещё детства, когда кидал кубики на таблицы случайных подземелий из AD&D Dungeon Master's Guide. В этом есть что-то волшебное — ты не проектируешь подземелье, а исследуешь его, помещение за помещением, а кубики решают, попадёшь ли ты в сокровищницу или в тупик с кучей крыс.

Спустя годы я решил создать собственный генератор карт. Он создаёт маленькие средневековые островные миры с дорогами, реками, побережьями, горами, лесами и деревьями. И всё это полностью процедурным образом. Генератор написан на Three.js WebGPU с TSL-шейдерами, примерно 4100 шестиугольников в 19 сетках генерируются за ~20 секунд.

«Каркассон», который создаёт компьютер

Основой генератора стал Wave Function Collapse (WFC) — алгоритм, созданный Максимом Гуминым и ставший одним из любимых инструментов разработчиков игр с процедурной генерацией.

Если вы когда-нибудь играли в «Каркассон», то уже понимаете, что такое WFC. У нас есть стопка плиток, мы размещаем их так, чтобы всё совпадало. У каждой плитки есть грани — трава, дорога, город. Грани соседних плиток должны совпадать. Грань с дорогой должна соединяться с другой такой же гранью. Трава должна соединяться с травой. Единственное отличие заключается в том, что компьютер делает это быстрее и меньше жалуется, когда зайдёт в тупик.

У моего проекта есть тонкость: у шестиугольных плиток (тайлов) шесть граней вместо четырёх. То есть у плитки становится на 50% больше ограничений и происходит комбинаторный взрыв. Квадратный WFC — хорошо исследованная территория. А с шестиугольным WFC история более сложная.

Определения тайлов

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

Например, этот трёхсторонний перекрёсток имеет три грани с дорогой и три грани с травой. Определение тайла выглядит так:

{ name: 'ROAD_D', mesh: 'hex_road_D',
  edges: { NE: 'road', E: 'grass', SE: 'road', SW: 'grass', W: 'road', NW: 'grass' },
  weight: 2 }

Как работает WFC

1. Начинаем с хаоса. Каждая ячейка в сетке изначально является суперпозицией всех возможных тайлов — всех 30 типов, всех 6 поворотов, всех 5 уровней возвышения.

2. Выполняется коллапс ячейки с наибольшим количеством ограничений. Выбираем ячейку с наименьшим количеством оставшихся вариантов (самой низкой энтропией). Случайно выбираем одно из её допустимых состояний.

3. Распространение. Этот выбор накладывает ограничения на соседние тайлы. Удаляем все состояния соседей, грани которых не согласуются с исходной ячейкой. И этот принцип каскадно распространяется наружу — один коллапс может уничтожить сотни вероятностей в сетке.

4. Повторяем процесс, пока не найдём решения для всех ячеек или не зайдём в тупик.

Попадание в тупик — это интересный момент.

Проблема нескольких сеток

WFC надёжно работает для маленьких сеток. Но при увеличении сетки шанс зайти в тупик быстро возрастает. В сетке из 217 шестиугольников сбоев почти не бывает. В сетке из 4123 ячеек они происходят регулярно.

Решением может стать модульный WFC. Вместо одного гигантского решения карта разделяется на 19 сеток шестиугольников, выстроенных в два кольца вокруг центра, что суммарно даёт приблизительно 4100 ячеек. Решение для каждой сетки ищется отдельно, но должно соответствовать тем тайлам, которые уже размещены на соседних сетках. Эти граничные тайлы становятся фиксированными ограничениями.

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

Возвращение назад

И в этом заключается неприятный секрет WFC: у него часто возникают сбои. Мы последовательно делаем случайный выбор, распространяем ограничения, рано или поздно загоняя себя в угол, где у какой-то ячейки остаётся ноль допустимых вариантов. Поздравляю, этот пазл невозможно решить.

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

Но одного возврата назад недостаточно. Настоящая проблема заключается в границах между сетками.

Система восстановления

Попробовав множество неудачных подходов, я остановился на многослойной системе восстановления:

Слой 1: освобождение. Если при первоначальном распространении ограничений ячейка соседней сетки создаёт противоречие, солвер превращает её из фиксированного ограничения в решаемую ячейку. Новыми ограничениями становятся её соседи (две ячейки — «якоря»). Такое решение малозатратно и позволяет разрешать большинство простых случаев.

Слой 2: локальный WFC. При неудаче основного решения солвер выполняет мини-WFC для небольшой области радиусом 2 вокруг проблемной области — повторно решает 19 ячеек в области пересечения для создания более совместимой границы. Он выполняет до 5 попыток, каждая из которых нацелена на отдельную проблемную ячейку. Локальный WFC стал прорывом: вместо того, чтобы решать невозможную задачу, нужно вернуться назад и изменить саму задачу.

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

Третье измерение

Эта карта не плоская, а имеет пять уровней возвышений. Океан и Трава начинаются на уровне 0, однако склоны и обрывы могут сдвигаться вверх и вниз. Низкие склоны поднимаются на 1 уровень, высокие — на 2. Тайл дороги на уровне 3 должен соединяться с другим тайлом дороги на уровне 3 или с тайлом склона, обеспечивающим переходы между уровнями. Если ошибиться, что дороги будут упираться в грани обрывов, а реки — течь наверх. Ось возвышения превращает 2D-задачу ограничений в 3D-задачу, и из-за этого возникает большое разнообразие тайлов (и куча сбоев солвера).

Тайлы раскрашиваются при помощи основанного на нодах PBR-материала MeshPhysicalNodeMaterial с нодом цвета TSL. Возвышение каждого тайла кодируется в цвет инстанса, который шейдер использует для смешивания между двумя текстурами палитр — рельеф внизу получает летние цвета, наверху — зимние.

Координаты шестиугольников: неожиданная странность

Математика шестиугольников странная. Так как у нас есть не четыре, а шесть направлений, нельзя просто сопоставить позиции шестиугольников с 2D-координатами x,y. Наивный подход заключается в смещении координат — нумерации ячеек слева направо, сверху вниз, как в обычной сетке. Это работает до тех пор, пока нам не нужно находить соседей, вычислять расстояния и выполнять любые действия, касающиеся направлений. Потом всё сразу становится запутанным, появляются разные формулы для чётных и нечётных строк.

Более удобное решение: кубические координаты (q, r, s, где s = -q-r). Это система 3D-координат для трёх осей шестиугольников. Поиск соседей становится тривиальной задачей — достаточно прибавить или вычесть 1 из двух координат.

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

Если вы когда-нибудь работали с сетками шестиугольников, то обязаны выразить благодарность Амиту Пателю из Red Blob Games. Его руководство по сеткам шестиугольников — это канонический справочный материал.

Деревья, здания и почему не всё должно быть WFC

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

Решение: старый добрый шум Перлина. Глобальное поле шума определяет плотность размещения деревьев и зданий совершенно отдельно от WFC. Области, в которых шум больше порогового значения, располагаются деревья; зданиями управляет немного другой шум. Благодаря этому мы получаем органичную кластеризацию — леса, опушки, деревья — которую ни за что бы не обеспечил WFC. Также я использовал дополнительную логику для размещения здания в концах дорог, портов и ветряных мельниц на побережьях, земляных сооружений на вершинах холмов и так далее.

WFC занимается рельефом. Шум генерирует декорации. Каждый инструмент делает то, в чём он хорош.

Вода: сложнее, чем кажется

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

Мерцание

Я хотел получить мультяшный эффект мерцания на поверхности воды в стиле Zelda: The Wind Waker. Изначально я пытался генерировать каустику процедурно при помощи четырёх слоёв шума Вороного. Оказалось, что этот процесс сильно нагружает GPU, а выглядит не очень красиво. В итоге я решил сэмплировать маленькую текстуру каустики со скроллингом при помощи простой маски шума; это выглядело намного лучше и почти не требовало затрат. Иногда правильным решением оказывается самое простое.

Прибрежные волны

Волны — это полосы синусоид, излучаемые наружу от линий побережья. На такое решение меня вдохновил красивый эффект побережья в Bad North. Чтобы знать, насколько далеко от берега находится каждый пиксель, система рендерит маску побережья — ортографический рендер всей карты с видом сверху, где белым обозначена суша, а чёрным вода, после чего она расширяется и размывается в градиент. Шейдер волн считывает этот градиент, чтобы размещать анимированные полосы синусоид с равными интервалами, а шум позволяет добавить разнообразия.

Проблема бухт

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

Я пробовал это исправить разными способами:

• Производные в экранном пространстве для распознавания растягивания градиентов — на одном уровне зума это работало, но ломалось на других.

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

• Дополнительные проходы растяжения — влияли и на ровные побережья.

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

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

Создание тайлов в Blender

Ассеты 3D-тайлов взяты из потрясающего низкополигонального Medieval Hexagon pack KayKit. Но для завершения подмножества тайлсета мне не хватало важных соединений, поэтому вспомнил старое и создал в Blender новые тайлы: наклонные реки, завершения рек, соединения рек и побережий, а также множество вариаций граней с обрывами.

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

Украшательства

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

WebGPU и TSL-шейдеры

В качестве рендерера используется Three.js с WebGPU и TSL (Three.js Shading Language) — новая система шейдеров на основе нодов, заменившая сырой GLSL. Все мои визуальные эффекты написаны на языке TSL, который похож на немного инопланетный диалект JavaScript, выполняемый в GPU.

Стек постобработки

Новый сырой рендер выглядит... нормально. Плоско. Как настольная игра, сфотографированная при лампах дневного света. Придать ему атмосферности может конвейер постобработки:

1. GTAO Ambient Occlusion — затемняет сгибы между тайлами, вокруг зданий и деревьев. Благодаря этому всё выглядит более массивным. Результат AO подвергается удалению шума для снижения ряби. Этот процесс выполняется при половинном разрешении, потому что AO и удаление шума — это затратные операции.

2. Depth of Field — размытие tilt-shift в зависимости от расстояния до камеры придаёт ощущение миниатюры/диорамы. Фокусная длина DOF масштабируется с зумом камеры, чтобы при увеличении зума DOF тоже увеличивалось.

3. Виньетирование + зерно плёнки — небольшое затемнение краёв и шум. Ровно столько, чтобы добавить аналоговости.

Динамические карты теней

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

Оптимизации

На карте тысячи тайлов и объектов. При отрисовке всего этого по отдельности частота кадров резко упадёт. Решить проблему можно двумя способами:

BatchedMesh — каждая сетка шестиугольников получает два BatchedMesh: один для тайлов, другой для объектов. Удобство BatchedMesh заключается в том, что каждый меш может иметь отдельную геометрию и преобразования, но все они рендерятся за один вызов отрисовки. GPU занимается преобразованиями и смещениями геометрии для каждого инстанса, поэтому после подготовки затраты CPU, по сути, равны нулю.

Вся сцена рендерится всего за несколько вызовов отрисовки вне зависимости от сложности карты. Благодаря этому базовый рендер остаётся малозатратным, поэтому можно потратить бюджет GPU на AO, DoF и цветокоррекцию.

Один общий материал — все меши в сцене имеют один материал. UV мешей отображаются в маленькую текстуру палитры, чтобы им всем можно было извлекать свой цвет из одного изображения. Благодаря использованию всего одного материала между вызовами отрисовки не происходит переключения между состояниями шейдеров, поэтому GPU может без пауз обрабатывать 38 BatchedMesh.

В результате мы получаем 4100+ ячеек, 38 BatchedMesh, и вся картинка рендерится в 60fps на десктопах и мобильных.

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

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

Числа

30 типов тайлов

19 сеток шестиугольников

~4100 ячеек

2 вызова отрисовки на сетку

Максимум 500 возвратов назад

5 попыток локального WFC

~20 секунд на создание всех сеток

Показатель успеха 100% (проверено на 500 прогонах)

Технологический стек

• Three.js r183 с рендерером WebGPU

• TSL (Three.js Shading Language) для всех шейдеров

• Веб-воркеры для решения WFC вне потоков

• Vite для сборок

• BatchedMesh для эффективного рендеринга тайлов (один вызов отрисовки)

• Генератор случайных чисел с порождающими значениями для создания детерминированных, воспроизводимых карт

Попробуйте сами

Интерактивное демо — нажимайте на шестиугольные кнопки для расширения карты или нажмите на «Build All», чтобы сгенерировать всё целиком. Там есть полная панель GUI с более чем 50 настройками на случай, если вы захотите поэкспериментировать с освещением, цветокоррекцией, эффектами воды и параметрами WFC.

Полный исходный код выложен на GitHub

Благодарности и ссылки

• KayKit Medieval Hexagon Pack — тайловые ассеты, с которых всё началось

• WFC Максима Гумина — исходная реализация коллапса волновой функции

• Red Blob Games — Hexagonal Grids — библия сеток шестиугольников

• Boris the Brave — бесценные статьи по WFC о блоковой модификации

• Codrops — статья, благодаря которой я взялся за WebGPU BatchedMesh

• Источники вдохновения по стилю: Bad North, Dorfromantik