Случайный мир: разбор генераторов игровых уровней

Практические особенности разных алгоритмов.

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

Майк Кук, геймдизайнер и исследователь ИИ, на своём сайте опубликовал текст, в котором рассказал про разные алгоритмы для создания генераторов уровней. Особое внимание он уделил соотношению понятий «генеративное пространство» и «пространство возможностей». Мы выбрали главное из материала.

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

Мировой генератор Minecraft содержит в общей сложности 2⁶⁴ случайных номера, что является по-настоящему огромным числом: это 18 446 744 073 709 551 616 миров, которые он может сгенерировать. При каждом нажатии на кнопку «Новый мир», выпадает один из номеров. Число 2⁶⁴ является размером генеративного пространства Minecraft — набора всех вещей, которые он может сгенерировать.

Теперь нужно представить абсолютно пустой мир Minecraft. В нём нет ничего, кроме слоя травы. Помимо того, что он довольно скучный, этот мир не является чем-то, что можно сгенерировать в Minecraft (без модификации). Его можно представить, описать, можно даже открыть Minecraft и создать его самостоятельно, но Minecraft не может его сгенерировать. Такого не может быть хотя бы из-за разных биомов, присутствующих в игре: так или иначе они будут встречаться в мире, сгенерированным стандартным способом.

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

Диаграмма выше даёт представление о том, как это выглядит. Всё в генеративном пространстве Minecraft также находится пространстве возможностей. Но не всё в пространстве возможностей находится в генеративном пространстве. Например, это касается плоского травяного мира. Но диаграмма не отражает реальный масштаб. Фактически, пространство возможностей Minecraft намного больше, чем его генеративное пространство.

Чтобы увидеть, насколько оно велико, нужно посчитать размер отдельного мира Minecraft. Объём — это ширина, умноженная на высоту, умноженная на глубину. Миры Minecraft по умолчанию имеют 256 тайлов в высоту и около 30 000 000 тайлов в любом направлении от начала.

Каждый из этих блоков может отличаться по типу: камень, трава, воздух, вода. Всего в Minecraft насчитывается 64 стандартных типов блоков. Формула для вычисления количества возможных миров — это число вариантов каждого блока, возведённое в степень количества блоков:

Чтобы глубже погрузиться в тему генеративных пространств и пространств возможностей, нужен пример, который сможет проиллюстрировать их работу. На эту роль подходят Super Mario Bros. и Spelunky, так как для них существуют интерактивные генераторы уровней.

Генератор первого уровня очень прост — он абсолютно случайный. Каждая карта имеет стартовый тайл с левой стороны и тайл выхода с правой стороны. Любой другой тайл на карте имеет 33% шанс быть пустым, 33% шанс быть твёрдым и 33% шанс стать блоком усиления.

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

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

Самые забавные и интересные уровни находятся в этом генеративном пространстве. Здесь даже есть карта с надписью «SUPER MARIO IS AWESOME», составленная из блоков усиления. К сожалению, генеративное пространство настолько велико, что найти такой крутой уровень очень и очень маловероятно. Большинство возможных уровней просто мусор.

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

Это уже больше похоже на уровень платформера, не так ли? Чтобы сформировать более или менее подходящий уровень требуется около 10 попыток генерации.

Ниже представлен тот же алгоритм, который генерирует не 20 фигур, а 10. Он позволяет быстрее сформировать подходящий уровень.

Генератор с 20 фигурами имеет большее генеративное пространство. Фактически он содержит в себе всё генеративное пространство алгоритма с 10 фигурами. Тем не менее любой уровень с 20 фигурами никогда не может быть отрисован генератором с 10 фигурами.

Это означает, что генератор 20 фигур имеет больше уровней, что также означает, что он может иметь более интересные уровни. Но намного проще найти подходящий уровень, который можно было бы воспроизводить с помощью генератора 10 фигур.

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

Этот алгоритм основан на генераторе уровней, используемом в Spelunky. Генератор уровней случайным образом выбирает кусок уровня, разработанного человеком, и вставляет его в уровень. Затем он случайным образом выбирает другой кусок уровня и вставляет его рядом. И так далее, пока уровень не будет завершён.

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

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

Ниже представлен уровень, полностью сделанный человеком. Этот подход — окончательный компромисс контроля и качества.

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

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

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

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

Найти способ уравновесить сильные и слабые стороны этих двух крайностей — это искусство генеративного проектирования.