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

Приятного чтения!

Идея Wave Function Collapse
Wave Function Collapse – это алгоритм, вдохновленный идеями квантовой механики. Согласно одной из таких идей для каждого объекта существует огромное множество возможных состояний.

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

Как же применить эту идею для реализации процедурной генерации карты?

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

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

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

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

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

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

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

Наверняка на этом месте некоторые подумают: "да-да, на словах всё прекрасно, но как реализовать такое поведение в коде?". На самом деле не так сложно, как может показаться на первый взгляд. Далее мы познакомимся с алгоритмом процедурной WFC-генерации, а после кратко рассмотрим его простую реализацию.

Алгоритм процедурной WFC-генерации
В общем виде алгоритм процедурной генерации на основе Wave Function Collapse выглядит следующим образом:

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

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

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

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

5. Пункты 2-4 повторяются, пока хотя бы для одной ячейки существует более одного состояния:

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

Прекрасно! Наша карта успешно сгенерирована!

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

Возможная реализация WFC для процедурной генерации карты
Итак, давайте посмотрим, как может выглядеть базовая реализация алгоритма Wave Function Collapse в контексте процедурной генерации местности в Unity.

- MapSize – размер карты;
- CellSize – размер одной ячейки карты (предполагается, что ячейка имеет форму квадрата);
- MapModules – набор шаблонов модулей, из вариантов которых будет генерироваться карта;
- ContactTypes – список типов контактов и их ограничений. Контакт представляет собой одну из граней ячейки. Каждый контакт имеет тип, а также список типов других контактов, с которыми соединение запрещается.

2. Создаётся набор шаблонов модулей для генерации. К каждому шаблону прикрепляется скрипт MapModulePrefab.cs. В демонстрационных целях я подготовил 4 простеньких шаблона:

3. В скрипте MapModulePrefab каждого из шаблонов задаётся тип контакта для каждой стороны шаблона. Также задаётся объект Map, который используется для получения списка с ограничениями для данного типа.

4. На этом наша работа заканчивается и начинается работа Unity. Жмём кнопку Play и смотрим на результат.

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

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

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

1. Класс Map. Является компонентом Unity. Представляет собой генерируемую карту. С помощью остальных классов он реализует 3 основных этапа генерации:

- Инициализация пустой карты в виде двумерного массива объектов класса MapCell. В множество состояний каждого такого объекта помещаются все возможные варианты модулей, из которых может генерироваться карта (объекты класса MapModuleState);
- Выбор конкретного состояния для каждой ячейки в карте с помощью алгоритма Wave Function Collapse (сам алгоритм по большей части реализован в классе MapCell);
- Создание модулей, соответствующих состояниям ячеек, на сцене.

Кроме этого, Map содержит информацию о типах контактов и их ограничениях в виде объектов MapModuleContact.

2. Класс MapModule. Является компонентом Unity. Реализует функционал для генерации списка вариантов шаблона с разным вращением вокруг оси Y (объекты класса MapModuleState). Так как основание модуля представляет собой квадрат, поворот каждого последующего варианта отличается от предыдущего на 90 градусов. В классе Map этот функционал используется для формирования списка всех возможных состояний.

3. Класс MapModuleState. Не является компонентом Unity. Объекты этого класса представляют собой варианты модулей с различным поворотом вокруг оси Y. Помимо поворота объекта, MapModuleState также содержит информацию о контактах модуля в виде коллекции Dictionary, в которой key имеет тип Vector2 и указывает в какую сторону направлен контакт, а value – экземпляр класса MapModuleContact. Также класс MapModuleState реализует функционал для проверки на возможность соединения одного модуля с другим.

4. MapModuleContact. Не является компонентом Unity. Объект этого класса хранит информацию о типе контакта одного модуля и список типов, с которыми соединение этого контакта запрещено. Он также реализует метод для проверки на возможность соединения этого контакта с другим. Этот функционал используется в MapModuleState для реализации проверки на возможность соединения модулей.

5. Класс MapCell. Не является компонентом Unity. Представляет собой ячейку карты. Реализует функционал для определения конкретного состояния объекта с последующим "волновым" обновлением множеств состояний других ячеек. На случай, если в результате такого обновления для одной из ячеек не осталось возможных состояний, предусмотрен откат обновлений с последующим выбором другого состояния для ячейки.

Заключение

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

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

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

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

**

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

- Зачем разработчикам игр на Unity использовать статический анализ?
- Ошибки в коде движка Unity: часть 1, часть 2.

На этом всё — чистого вам кода и успешных проектов. :)

Оригинал статьи

Правка: 12:38