В последнее время я много экспериментировал с процедурной генерацией на основе ограничений. В частности, с алгоритмом Wave Function Collapse (WFC, коллапс волновой функции). Я даже написал собственную open source-библиотеку и ассет unity.

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

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

Основы

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

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

Он имеет два вида — с соседним расположением или с наложением элементов. Его можно выполнять в 2D или в 3D, и даже на сетках шестиугольников или неравномерных сетках. Большинство из моих советов применимо вне зависимости от способов использования алгоритма.

Предлагаю вам поиграть с этим демо, чтобы получить представление об алгоритме, и прочитать это введение [перевод на Хабре], если вам интересны технические подробности.

Дизайн тайлсетов

Алгоритм WFC основан на тайлах. В этом смысле его качество зависит от тайлов, которые вы ему передаёте для работы. Я не художник, поэтому мало чем могу помочь в рисовании красивых тайлсетов (хотя можете посмотреть здесь), однако для хорошего тайлсета также требуются технические знания.

Marching Cubes

Marching cubes — это алгоритм, выбирающий, какие тайлы нужно ставить в зависимости от того, является каждая вершина тайла заполненной или пустой. Вот список тайлов, используемый для 2D.


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

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

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

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

Комнаты

Иногда легче всего работать с простыми тайлсетами. Это сочетание из 4 тайлов (один тайл пуст) запросто генерирует квадратные комнаты.



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

Фундамент

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


Мы можем использовать это поведение, чтобы стимулировать WFC к генерированию множества узнаваемых структур.

Вот пример замка (вдохновлённый @greentecq):


В нём я использовал следующий тайлсет:


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

Аппроксимация рекурсивного разбиения

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

Большие тайлы

Можно дополнить WFC, чтобы он поддерживал тайлы, которые в несколько раз больше обычного тайла. Например, это поддерживается в моём аддоне Tessera.

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

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

Ограничения

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

Фиксированные тайлы

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


До генерации


После генерации

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

• Зафиксировать точки входа и выхода с уровня
• Изготовить вручную какой-нибудь контент, и позволить WFC отрисовать вокруг него уровень.
• Сгенерировать части уровня другим алгоритмом, а затем заполнить деталями
• Нарисовать границу/план уровня и позволить WFC заполнить внутреннюю часть

Ограничение путями

Ограничение путями (Path constraint) — это мой собственный вклад в WFC. Это чрезвычайно мощная техника, но для её полного описания, скорее всего, потребуется отдельная статья.

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

Я выяснил, что добавление этого ограничения сильно влияет на внешний вид генерируемого уровня. Без него WFC часто генерирует несколько разделённых комнат или областей, выглядящих нереалистичными и не созданными человеком.


До добавления ограничения путями


После добавления ограничения путями. Теперь между всеми комнатами автоматически вставляются двери.

Рисование рек и дорог

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

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


Пути, сгенерированные фиксацией всех четырёх углов в качестве конечных точек путей

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

Разнообразие

Альтернативные тайлы

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


Два тайла стены, один из них с окном. Они полностью взаимозаменяемы и просто добавляют в дизайн вариативности.

Вариативность тайлов по уровням

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

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

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


Всего примерно 10% островов имеют элементы пещер, заметные в правом верхнем углу.

Вариативность тайлов в пределах карты

В смешивании тайлсета можно зайти ещё дальше.

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

Наилучшее решение этой проблемы я увидел в игре Caves of Qud. В рассказе разработчиков о генерации (1, 2) они говорят о том, что разбивают карту на разные области, а затем запускают WFC с отдельными параметрами для подмножеств карты. Это значит, что на карте может быть область руин и область города, в которых используются совершенно разные шаблоны и тайлы.


Пример из Math for Game Developers: Tile-Based Map Generation using Wave Function Collapse in ‘Caves of Qud’

Заключение

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

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

Рекомендую вам сыграть в Bad North и в Caves of Qud. Обе игры являются великолепными примерами использования WFC в реальных условиях, и разработчики хорошо продумали оптимальное применение алгоритма в своих играх.