Долгое введение.

В нашей прошлой игре The Unexpected Quest разработка уровня занимала около трех месяцев, включая оформление и синематики. Сейчас мы делаем тактическую стратегию Eternal Mist и в ней планируется более 100 уровней. Естественно они будут гораздо меньше и проще, но, даже если тратить на один уровень несколько дней, то разработка затянется на долгий срок. “Лучше день потерять, потом за пять минут долететь!” решили мы и принялись за работу над автоматической генерацией уровней. В итоге получилось вот так:

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

Из названия статьи, понятно, что после изучения возможных вариантов мы остановились на алгоритме Wave Function Collapse. Он достаточно прост в реализации и при этом может выдавать очень интересные комбинации. Тем более, игра которой мы вдохновлялись Bad North: Jotunn Edition, тоже использовала этот алгоритм для генерации уровней. В конце статьи я добавил ссылку на лекцию ее создателя об алгоритме WFC. Кстати, на этом алгоритме базируется и его новая игра Townscaper.

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

• уровень строится из тайлов,

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

• все поле разбивается на слоты и в начале работы, каждый слот заполнен всеми возможными тайлами,

• на каждом шаге выбирается один слот с наименьшей энтропией (если упрощенно, то с меньшим числом тайлов внутри) и “схлопывается” к одному тайлу,

• из остальных слотов удаляются тайлы, которые не могут соседствовать со схлопнувшимся слотом или его соседями (та самая “волна”),

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

Особенности реализации

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

Помимо “белых списков” разрешенных тайлов (обсуждаемые выше списки граней), крайне рекомендуется завести “черный список” запрещенных тайлов. Уже без указания граней. А просто вида: с этой стороны тайл такой-то не может присоединится. Например, с точки зрения соединения граней пример ниже допустим, но визуально он выглядит неестественно.

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

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

Производительность. Алгоритм медленный, с увеличением числа тайлов время работы существенно возрастает, и об оптимизации надо думать сразу. Мы думали сразу, что-то там кешировали и не попали совсем… Поэтому совет: оптимизировать надо именно тонкие места вашего алгоритма и на этапе разработки, вы о них скорее всего не знаете. В нашем случае помог внутренний профайлер UE4 и изучение всех подозрительных (все что вызывается в циклах) мест. То есть WFC_SCOPE_CYCLE_COUNTER пихали кругом и по всякому, а потом смотрели что больше всего жрет времени. Но точно надо обратить внимание на работу со списками граней и тайлов: объединение, пересечение и проверка содержит ли один список другой. Это будет вызываться много и часто.

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

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

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

Полезные ссылки.

1. Начать стоит с этого видео.

2. Отличная лекция Oskar Stålberg об его игре Bad North и его реализации WFC.

3. Статья о генерации бесконечных 3D уровней при помощи WFC.

   И ссылка на сам алгоритм для Unity.

4. Для Unreal Engine есть готовые плагины, но я не уверен в их качестве:

   Easy Level Generator

   Procedural Environment Generator (WFC)

5. Также в Unreal Engine 5 появился экспериментальный плагин WFC:
   [UE5_FOLDER]\Engine\Plugins\Experimental\WaveFunctionCollapse
   К сожалению, документации по нему я не нашел.

6. И немного ссылок с хабра:
   Доступное объяснение алгоритма коллапса волновой функции
   Разбираемся с алгоритмом коллапса волновой функции
   Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой
   Алгоритм размещения тайлов на основе ограничений

Минутка саморекламы

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

И мы будем рады видеть вас на нашей страничке в VK!