В этом посте описывается алгоритм, используемый в Generate Worlds — инструменте, позволяющем пользователям создавать и исследовать процедурные миры построением небольших множеств воксельных тайлов. Я приведу краткое описание алгоритма, а в следующих постах расскажу о его преимуществах в скорости и гибкости по сравнению с другими методами. Чтобы подробнее узнать о том, что такое процедурная генерация на основе ограничений (constraint-based procedural generation) и о том, чем она интересна, рекомендую прочитать мой предыдущий пост.
Если вы хотите проверить свои силы в создании процедурных миров при помощи этой системы, то можете приобрести Generate Worlds. Если цена для вас слишком высока, то продолжайте чтение: этот пост даст вам информацию о том, как самостоятельно реализовать алгоритм Generate Worlds.
Наборы тайлов
В Generate Worlds каждый мир собирается из набора тайлов (тайлсета). По сути, тайлы — это просто небольшие воксельные модели. Давайте начнём с примера. Показанное ниже изображение составлено из 9 тайлов. Как видите, каждый тайл состоит из вокселей, которые отображаются как цветные кубы.
Если расположить эти воксельные модели логичным образом, то можно создать красивую пасторальную сцену, как в показанной ниже анимации. Под «логичностью» я подразумеваю то, что тайлы подходят друг к другу, если их цвета вдоль грани стыка совпадают.
Задача алгоритма Generate Worlds заключается в быстром и автоматическом выполнении такой сборки. Прежде чем приступать к алгоритму, давайте рассмотрим постановку задачи.
Соединяем тайлы между собой
Взгляните на тайлсет, содержащий 4 тайла:
Эти тайлы аналогичны показанным выше трёхмерным тайлам.
Алгоритм Generate Worlds создаёт допустимые комбинации тайлов, применяя одно простое правило: если два тайла касаются друг друга, все цвета вдоль грани касания должны совпадать. Это правило формализует подход, используемый живым дизайнером, создающим 3D-мир из воксельных тайлов.
В допустимой комбинации представленных выше 4 тайлов светлые ячейки вдоль границ должны касаться только светлых ячеек, а тёмная ячейка должна касаться только тёмных ячеек. Например:
Примеры правильного и неправильного соединения.
Пример справа недопустим, потому что вдоль грани касания тайлов светлый квадрат касается тёмного квадрата. Ниже показаны две допустимые комбинации, сгенерированные для этого тайлсета:
В общем случае создание допустимых комбинаций тайлов оказывается нетривиальной задачей. Например, рассмотрим следующую простую «жадную» стратегию: мы начинаем с пустой сетки. В каждой итерации помещаем тайл в какую-то точку, выбирая такой тайл, который допустим с учётом уже размещённых тайлов. На схеме ниже показаны проблемы такой стратегии.
Если мы будем размещать тайлы, не предвидя, как размещение повлияет на будущие варианты выбора, то «жадный» алгоритм быстро заходит в тупик; на показанной выше схеме в красный квадрат невозможно поместить никакой допустимый тайл. И это основная проблема: предыдущие размещённые тайлы могут снижать количество текущих вариантов до нуля. Нам нужен какой-то способ защиты от размещения тайлов, которое может привести нас в тупик. Реализованный в Generate Worlds алгоритм начинает с того, что считает все тайлы возможными для размещения во всех точках сетки. Если мы располагаем в сетке один тайл, то очевидно, что часть будущих вариантов становится недоступной. После того, как алгоритм устранит эти варианты, мы можем заново исследовать оставшиеся варианты и устранить другие тайлы, которые теперь несовместимы с меньшим множеством оставшихся возможных тайлов в соседних точках.
Рассмотрим следующий пример. Алгоритм начинает с сетки 3x3, в центре которой расположен единственный тайл. Расположение этого тайла подразумевает, что 9 возможных тайлов в соседних точках сетки недопустимы, поэтому он отбрасывает их и больше не рассматривает. После удаления этих тайлов он может удалить тайлы, которые несовместимы со всеми тайлами, рассматриваемыми как кандидаты на размещение в соседних точках сетки. Красными квадратами на схеме отмечены точки, в которых удалены тайлы, потому что они несовместимы со всеми соседями, которые пока ещё рассматриваются. Если алгоритм продолжит этот процесс, пока не останется тайлов, которые можно удалить, то он придёт в состояние, представленное в левом нижнем углу схемы. Как видите, из рассмотрения были исключены многие тайлы. Если бы стратегия размещения тайлов заключалась только в выборе тайлов из этих оставшихся групп, то вероятность попадания в тупик оказалась бы значительно ниже, чем в описанном выше «жадном» подходе.
Проблема такого подхода заключается в том, что при каждом размещении тайла он требует затратного итеративного процесса. Но заметьте, что каждый раз, когда я размещаю тайл с перевёрнутой T, те 19 тайлов, которые я устранил в показанном выше примере, можно устранить из рассмотрения вокруг этого размещения. Я называю коллекцию тайлов, которые остаются допустимыми вариантами вокруг размещённого тайла, допустимым соседством этого тайла.
Быстрое размещение тайлов благодаря кэшированию информации
Важнейший принцип алгоритма Generate Worlds заключается в том, что информация, собранная о возможных соседях тайла, может повторно использоваться каждый раз, когда размещается этот тайл. Например, в случае перевёрнутой T для восьми окружающих её квадратов сетки мы можем убрать из рассмотрения 19 тайлов сразу после размещения этого тайла, взглянув в кэшированную версию допустимого соседства для этого тайла.
Например, в показанном ниже примере алгоритм заполняет тайлами сетку 5x5 при помощи кэшированного допустимого соседства 4 тайлов. После размещения первого тайла он убирает из рассмотрения 19 тайлов, которые оказались невозможными в примере выше. После размещения каждого тайла из рассмотрения убираются все варианты, отсутствующие в допустимом соседстве размещённого тайла.
Продолжая подобным образом, мы можем заполнить всю сетку благодаря только быстрым локальным обновлениям множеств тайлов, по-прежнему являющихся допустимыми вариантами для каждой из точек.
Допустимые соседства могут иметь любой нужный вам размер, благодаря чему при каждом размещении тайла можно убирать из рассмотрения далёкие несовместимые тайлы. Хотя генерация допустимого соседства выполняется довольно медленно, его нужно выполнить только один раз, после чего для размещения каждого тайла требуется время, линейно зависящее от размера соседства.
Расширяем систему в 3D
Алгоритм Generate Worlds естественным образом расширяется до миров, имеющих третье измерение. Вместо 2D-тайлов, соответствующих по цвету с 4 соседними тайлами вдоль общих граней, у нас появляются 3D-тайлы, которые должны соответствовать по цвету со своими соседями по 6 граням. Рассмотрим следующие 3D-тайлы:
Сборка этих тайлов в 3D выглядит следующим образом:
В данном случае допустимые соседства являются не двухмерными, а трёхмерными сетками, и алгоритм генерирует их аналогичным 2D-случаю образом.
Галерея результатов
Ниже показаны миры, сгенерированные при помощи реализаций этого алгоритма вместе с краткими описаниями.
Скриншот из Generate Worlds, демонстрирующий комнату с выходом. Выступы на потолке совпадают с границами тайлов.
Скриншот из другого создаваемого мной инструмента, в котором также используется алгоритм Generate Worlds; показаны различные типы комнат и коридоров.
Мир, похожий на предыдущий, но теперь в красивой изометрической проекции
Мир, на создание которого меня вдохновил девятый круг дантовского Ада: грешники, вмёрзшие в толщу льда. Отрендерено в MagicaVoxel.
Мир, на создание которого меня вдохновил второй круг дантовского ада: поливаемый горящим дождём ландшафт, который пересекает мост. Отрендерено в MagicaVoxel.
Мир травянистых платформ с водопадами и реками. Отрендерено в MagicaVoxel.
Ландшафт средневекового города со зданиями и стенами. Отрендерено в MagicaVoxel.
