Долгое введение.
В нашей прошлой игре The Unexpected Quest разработка уровня занимала около трех месяцев, включая оформление и синематики. Сейчас мы делаем тактическую стратегию Eternal Mist и в ней планируется более 100 уровней. Естественно они будут гораздо меньше и проще, но, даже если тратить на один уровень несколько дней, то разработка затянется на долгий срок. “Лучше день потерять, потом за пять минут долететь!” решили мы и принялись за работу над автоматической генерацией уровней. В итоге получилось вот так:
Я хочу сразу отметить, что мы не планируем динамическую генерацию уровней в самой игре. Поэтому, с одной стороны стало проще: меньше требований к устойчивости алгоритмов (в случае ошибки или неудовлетворительного результата всегда можно сгенерировать уровень заново) и их производительности. С другой стороны, дополнительные инструменты для разработчика: отладка и визуализация нехороших моментов, UI для редактора и т.п. Сейчас процесс работы над уровнем выглядит так:
Из названия статьи, понятно, что после изучения возможных вариантов мы остановились на алгоритме Wave Function Collapse. Он достаточно прост в реализации и при этом может выдавать очень интересные комбинации. Тем более, игра которой мы вдохновлялись Bad North: Jotunn Edition, тоже использовала этот алгоритм для генерации уровней. В конце статьи я добавил ссылку на лекцию ее создателя об алгоритме WFC. Кстати, на этом алгоритме базируется и его новая игра Townscaper.
Я не собираюсь подробно рассказывать о самом алгоритме, так как в сети, в том числе и на хабре, огромное количество материала по этой теме. Полезные ссылки я добавлю в конце этой статьи. Просто, напомню основной принцип работы:
уровень строится из тайлов,
каждый тайл - это визуальное представление и список возможных тайлов-соседей для каждой стороны,
все поле разбивается на слоты и в начале работы, каждый слот заполнен всеми возможными тайлами,
на каждом шаге выбирается один слот с наименьшей энтропией (если упрощенно, то с меньшим числом тайлов внутри) и “схлопывается” к одному тайлу,
из остальных слотов удаляются тайлы, которые не могут соседствовать со схлопнувшимся слотом или его соседями (та самая “волна”),
алгоритм повторяется, пока все слоты не схлопнуться или не возникнет ошибка.
Особенности реализации
Чтобы определить какой тайл может находится рядом, недостаточно обычного списка соседних тайлов. Просто потому, что с ростом числа тайлов эти списки будут тоже расти. Причем очень быстро и запутанно. Поэтому, вместо тайлов хранят грани. Этот список гораздо меньше и следить за ним проще. Так как тайлы могут поворачиваться, то еще нужно разработать соглашение о стыковке граней. В видео ниже (ссылка с привязкой ко времени), все подробно объяснено и мы у себя сделали также:
Помимо “белых списков” разрешенных тайлов (обсуждаемые выше списки граней), крайне рекомендуется завести “черный список” запрещенных тайлов. Уже без указания граней. А просто вида: с этой стороны тайл такой-то не может присоединится. Например, с точки зрения соединения граней пример ниже допустим, но визуально он выглядит неестественно.
Крайне рекомендуется сделать хоть какой-то дамп уже зарегистрированных граней и в каких тайлах они используются. Визуальный формат - это идеал, но даже текстовый формат будет очень полезен на поздних этапах разработки. Высший пилотаж, продумать систему граней так, чтобы их можно было сгенерировать автоматически, мы, к сожалению, до этого уровня не доросли. У нас все выглядит так:
И еще один важный момент по поводу граней и тайлов. Успешность алгоритма WFC и реалистичность генерируемых уровней в основном зависит от того, как вы реализуете тайлы и способы их стыковки. Мы только с третьей попытки, подобрали подходящий вариант. Основной нашей ошибкой было то, что мы всеми силами пытались сократить число возможных видов граней, что приводило к небольшому числу вариаций для алгоритма и, как следствие, некрасивым и нереалистичным результатам. На первых порах, лучше всего отталкиваться от набора тайлов из каких-нибудь примеров, результаты которых вам нравятся.
Производительность. Алгоритм медленный, с увеличением числа тайлов время работы существенно возрастает, и об оптимизации надо думать сразу. Мы думали сразу, что-то там кешировали и не попали совсем… Поэтому совет: оптимизировать надо именно тонкие места вашего алгоритма и на этапе разработки, вы о них скорее всего не знаете. В нашем случае помог внутренний профайлер UE4 и изучение всех подозрительных (все что вызывается в циклах) мест. То есть WFC_SCOPE_CYCLE_COUNTER пихали кругом и по всякому, а потом смотрели что больше всего жрет времени. Но точно надо обратить внимание на работу со списками граней и тайлов: объединение, пересечение и проверка содержит ли один список другой. Это будет вызываться много и часто.
Отладка ошибок. Подобрать набор тайлов, при котором алгоритм всегда сможет генерировать уровень, очень сложно. Для большого набора тайлов - нереально. Поэтому, на этапе разработки, крайне важно понимать почему уровень не смог сгенерироваться: какая комбинация тайлов привела к ошибке. У нас это выглядит вот так:
Красная сфера обозначает слот, в котором не осталось никаких тайлов и он не может “схлопнуться”. Чаще всего это связано с тем, что не хватает тайла, который бы соединил близлежащие слоты. Какие именно слоты надо соединить, выводится в лог внизу. В дополнение к этому в лог, выводится номер итерации, на которой произошла ошибка. А для детальной отладки, мы сделали возможность остановить алгоритм не только в любой момент итерации, но и на любом шаге волны, т.е. когда все соседние слоты обновляют списки возможных граней. Это панель справа. Без подобного функционала, будет крайне сложно подобрать работающий набор тайлов и мы рекомендуем озаботиться о нем сразу.
Если вы планируете игру с автоматической генерацией уровней, то в случае ошибки обязательно надо продумать систему генерации уровня заново (это может работать долго), либо систему откатов назад и продолжением генерации уровня, но с новыми случайными числами (это должно работать быстрее). К счастью, для наших задач это не понадобилось.
Полезные ссылки.
Отличная лекция Oskar Stålberg об его игре Bad North и его реализации WFC.
Для Unreal Engine есть готовые плагины, но я не уверен в их качестве:
Также в Unreal Engine 5 появился экспериментальный плагин WFC:
[UE5_FOLDER]\Engine\Plugins\Experimental\WaveFunctionCollapse
К сожалению, документации по нему я не нашел.И немного ссылок с хабра:
Доступное объяснение алгоритма коллапса волновой функции
Разбираемся с алгоритмом коллапса волновой функции
Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой
Алгоритм размещения тайлов на основе ограничений
Минутка саморекламы
Нам будет очень приятно, если вы добавите нашу игру в вишлист и будете следить за проектом. С удовольствием ответим на ваши вопросы. Обещаем писать новые статьи, заметки и выкладывать интересные материалы об игре.
И мы будем рады видеть вас на нашей страничке в VK!
