В этом туториале я расскажу о двух терминах, которые используются мной для описания процедурных генераторов: пространство генерации (generative space) и пространство возможностей (possibility space). Мы дадим определения этим двум терминам, а затем рассмотрим интерактивные примеры, чтобы понять разницу между ними. Эти термины действительно полезны для описания процедурного генератора и для того, чтобы понимать разницу между двумя генераторами. Давайте приступим!
Представьте огромную книгу, в которой представлен скриншот каждого отдельного мира Minecraft. Каждый скриншот помечен случайным seed, уникальным числом, которое можно ввести в Minecraft и сгенерировать этот мир. На первой странице представлен мир, порождённый из seed = 0, на следующей — мир из seed = 1, и так далее. В целом генератор миров Minecraft содержит 264 случайных порождающих значений, и это огромное число: игра может сгенерировать 18 446 744 073 709 551 616 миров. Каждый раз, когда вы нажимаете на «New World», на основе одного из этих seed создаётся мир. Число 264 — это размер пространства генерации Minecraft, множество всего, что игра может сгенерировать.
Теперь представьте, что мир Minecraft состоит только из обычной травы, бесконечно распространяющейся во всех направлениях. Под ней нет ни пещер, ни камня, нет деревьев и холмов, нет животных. Просто один слой тайлов травы. Кроме того, что это очень скучно, такой мир никогда не будет сгенерирован в Minecraft (если не использовать моддинг). Мы можем представить его, можем описать его, даже открыть Minecraft и создать его сами вручную — но Minecraft не может сгенерировать его. Откуда мы это знаем? Можно доказать это множеством разных способов, но проще всего вспомнить о биомах Minecraft — таких областях, как пустыня или джунгли, разбросанные по каждому миру. В нашем примере с миром травы их нет, поэтому мы знаем, что его нельзя создать стандартным генератором.
Мир травы находится в том, что мы называем пространством возможностей миров Minecraft — множестве всех возможных миров Minecraft, которые мы можем вообразить, представить или описать. Но мир травы не находится в пространстве генерации Minecraft, потому что не может быть создан процедурным генератором игры. Мы можем представить мир Minecraft с совершенно точной копией Персеполиса в масштабе, или мир в виде вашей скульптуры из камня, сидящей и читающей эту статью — всё это возможные миры Minecraft, но игрой они генерироваться не будут.
Показанная выше схема даёт нам представление о том, как всё это выглядит. Всё, что находится в пространстве генерации Minecraft, должно также находиться в его пространстве возможностей, потому что если Minecraft может сгенерировать что-то, то это должно быть возможно создать в Minecraft! Но не всё из пространства возможностей находится в пространстве генерации, в том числе и наш пример с миром, состоящим из травы. Но в этой схеме не соблюдён масштаб. На самом деле, пространство возможностей Minecraft гораздо, гораздо больше, чем её пространство генерации.
Чтобы понять, насколько оно велико, давайте вычислим размер отдельного мира Minecraft. Объём — это ширина, умноженная на высоту, умноженная на глубину. По умолчанию миры Minecraft имеют высоту 256 тайлов, и они начинают разбиваться примерно на 30 000 000 тайлов во всех направлениях от начальной точки, то есть приблизительный объём мира равен:
256 x 60 000 000 x 60 000 000 = 921 600 000 000 000 000 блоков
Каждый из этих блоков может быть любым элементом: камнем, травой, водой, воздухом. Для нашей оценки мы будем щедры и используем только «блоки мира», которых, по данным Minecraft wiki, 64 типа. Это означает, что каждый блок в мире Minecraft имеет 64 возможных состояния. Формула для вычисления количества возможных миров равна количеству вариантов состояний каждого блока, возведённой в степень количества блоков:
64921 600 000 000 000 000 возможных миров Minecraft
Это число столь велико, что я не смог найти в Интернете калькулятор, способный его вычислить.
Чтобы ещё больше углубиться в пространства генерации и возможностей, нам нужен пример, который мы сможем лучше уложить в голове. Поэтому в оставшейся части туториала мы будем рассматривать уровни 2D-платформера для игр наподобие Super Mario Bros. или Spelunky. Мы рассмотрим несколько генераторов уровней для 2D-платформеров. В оригинале статьи все они интерактивны, поэтому вы можете генерировать собственные уровни. В процессе их изучения мы зададимся вопросами об их пространстве генерации. Все примеры доступны на нашем GitHub как написанный на Processing скетч с открытым исходным кодом.
В процессе изучения я буду задавать вопросы, выделенные жирным шрифтом, например: каков размер пространства возможностей для этих уровней платформера? Можете спокойно пропускать их, если просто хотите читать статью и играться с примерами. Также я иногда добавляю подсказки, помогающие в ответах на вопросы, например:
Подсказка: уровни имеют ширину 40 тайлов и высоту 10 тайлов, и каждый тайл может быть одним из трёх элементов: пустотой, землёй или бонусным блоком.
Можете приостановиться у подсказки и не прокручивать страницу вниз, если не хотите читать готовый ответ. Итак, давайте взглянем на наш первый генератор.
Алгоритм 1: случайность
Наш первый генератор уровней очень прост — он полностью случаен. У каждой карты есть тайл начала с левого края и тайл выхода с правого края. Все другие тайлы карты имеют вероятность 33% быть пустыми, 33% — быть занятыми, и 33% — быть бонусным блоком.
Вероятно, вы заметили, что это не очень хороший генератор уровней. На самом деле, в большинство этих уровней даже невозможно играть, не говоря уж об их интересности. Сгенерируйте ещё несколько уровней и задумайтесь над вопросом: какой размер имеет пространство генерации такого генератора по сравнению с пространством возможностей?
Подсказка: можете ли вы придумать уровень, находящийся в пространстве возможностей, но не в пространстве генерации? Можете ли вы придумать уровень, который этот генератор не может создать?
Правильный ответ заключается в том, что пространство генерации этого генератора одинаково с пространством возможностей. Любой тайл на карте может принимать любое значение, поэтому любой уровень, который мы можем представить, находится в пространстве генерации. Самые увлекательные, самые интересные уровни находятся в этом пространстве генерации, даже карта, на которой бонусными блоками написано SUPER MARIO IS AWESOME. К сожалению, пространство генерации настолько велико, что нахождение хорошего уровня чрезвычайно маловероятно. Как можно убедиться, понажимав на генератор, большинство уровней — это просто мусор.
Алгоритм 2: рисование случайных форм
Наш следующий алгоритм чуть сложнее, и он создаёт уровни, которые больше похоже на то, что можно применить в игре. Начиная с пустого уровня, он выбирает где-нибудь случайную точку, а затем отрисовывает линию или квадрат блоков бонусов или земли. Он выполняет эту операцию 20 раз, создавая несколько фигур, случайным образом отрисовываемых на уровне. Как и раньше, можно нажимать на пример в оригинале статьи, чтобы запускать алгоритм заново и генерировать новый уровень.
Это уже начинает напоминать уровень для платформера, правда? При генерации уровней мысленно представляйте, как играете в них (будьте щедры при необходимости — добавьте способность двойного прыжка, если она необходима, или возможность выпрыгивать за пределы потолка карты).
Сколько уровней нужно сгенерировать, прежде чем вы найдёте хотя бы один, который можно пройти?
Не стремитесь к абсолютной точности в своих мысленных прохождениях, просто сделайте примерную оценку.
Когда я провожу это упражнение с аудиторией, то для нахождения уровня в среднем обычно нужно около 10 попыток. А сколько потребовалось вам? Запомните это число, а теперь посмотрите на вариацию того же генератора, показанную ниже. Генератор тот же, который мы только что видели, но теперь он рисует на уровне не 20, а 10 фигур. Теперь подсчитайте снова: сколько уровней вам нужно сгенерировать, прежде чем вы найдёте тот, который можно пройти?
Вероятно, на поиск играбельного уровня вам понадобилось меньше времени. Давайте приостановимся на минуту и подумаем о различиях между этими двумя генераторами, которые почти идентичны, за исключением небольшой разницы параметров. У какого генератора пространство генерации больше — у генератора с 20 фигурами, или с 10?
Подсказка: подумайте об уровне, созданном генератором с 10 фигурами — сможет ли его создать генератор с 20 фигурами? А потом подумайте про обратный пример.
Правильный ответ заключается в том, что генератор с 20 фигурами имеет большее пространство генерации; на самом деле, он содержит в себе всё пространство генерации генератора с 10 фигурами. Чтобы показать это, представим любой уровень из генератора с 10 фигурами. Наш генератор с 20 фигурами может создать его, случайно отрисовав те же десять фигур, а затем случайно отрисовав их вторично поверх друг друга. Однако никакой уровень с двадцатью отдельными фигурами не может быть отрисован с помощью генератора с 10 фигурами.
Это означает, что генератор с 20 фигурами имеет больше уровней, в том числе и интересных уровней. Но стоит помнить, что найти играбельный уровень было намного легче при генераторе с 10 фигурами. Если бы вам нужно было выбрать генератор для своей видеоигры, то какой из них вы бы использовали? Здесь нет правильных ответов, но это очень важное решение, которое часто приходится делать при работе с процедурными генераторами. Один генератор может генерировать бОльшую вариативность и имеет больше сюрпризов, другой более надёжен и менее напрягает игрока.
Алгоритм 3: фрагменты уровня
Этот алгоритм основан на генераторе уровней, используемом в Spelunky; подробнее о нём можно прочитать здесь. Генератор уровней случайным образом выбирает фрагмент уровня, созданный человеком (мной), и вставляет его в уровень. Затем он выбирает ещё один случайный фрагмент уровня и вставляет его рядом, и так далее, пока уровень не будет завершён. Вот генератор, фон затемнён, чтобы чётче были видны границы фрагментов:
Сколько времени теперь потребуется для генерации играбельного уровня? Вы обнаружите, что почти каждый уровень играбелен. Мы точно знаем, что находится в каждом фрагменте, то есть можем гарантировать, что на уровне будут интересные объекты, на которые можно запрыгивать, и препятствия, которых нужно избегать. В то же время, он более динамичен, чем статичный уровень — мы не знаем, какие фрагменты в нём появятся и в каком порядке. Алгоритм Spelunky даже ещё богаче этого, в нём учитывается движение по вертикали, а к каждому фрагменту добавляются случайные вариации. Дариус Каземи создал потрясающий интерактивный генератор уровней Spelunky, который можно найти здесь.
Подобные генераторы являются хорошим компромиссом между приятными неожиданностями и возможностью контроля. Когда генератор выполняет выбор из каталога элементов и соединяет их вместе (иногда по особым правилам, как в Spelunky), мы называем это генератором на основе грамматики. Грамматика позволяет нам решать, какие строительные блоки должен использовать процедурный генератор, но менее строга относительно того, как их нужно соединять. Но этот контроль и безопасность имеют свою цену. Посмотрите снова на генератор, а затем подумайте о предыдущих примерах. Как часто такой генератор уровней будет нас удивлять?
Изначально генератор полон сюрпризов, потому что мы встречаем каждый фрагмент впервые. Но если играть больше, то быстро начинаешь замечать, где заканчивается один и начинается другой фрагмент. Даже если в этом генераторе есть сотни комбинаций фрагментов, всего через несколько уровней вы начинаете чувствовать, как будто видели их все. Простота и лёгкость понимания грамматики фрагментов отлично подходит разработчикам, но может стать недостатком с точки зрения увлекательности для игроков.
Алгоритм 4: дизайн, создаваемый человеком
В качестве последнего примера мы рассмотрим не алгоритм, а очень отличающийся вид творческого процесса: работу людей по дизайну уровней. Нажмите на генератор в оригинале статьи, и вы получите один из первых двух уровней Super Mario Bros. (точнее, самое их начало).
Начав с абсолютной случайности, мы закончили этим, одним из самых известных в истории примеров дизайна 2D-платформеров. Разумеется, это не генератор, но в каком-то смысле эти уровни можно воспринимать как генераторы, создающие всего один, высококачественный уровень. Максимальный компромисс между контролем и качеством. Глядя на этот уровень, подумайте о всех генераторах, которые мы рассматривали сегодня, и задумайтесь над вопросом: какие из этих генераторов содержат в своём пространстве генерации эти знаменитые уровни?.
- Случайная генерация
- Генерация 20 фигур
- Генерация 10 фигур
- Фрагменты уровней
Только первый генератор способен создавать такие уровни. Генераторы форм могли бы создавать их, если бы мы увеличили количество возможных отрисовываемых фигур, но это также значительно увеличило бы количество плохих или странных уровней. Генератор фрагментов уровней мог бы это сделать, если бы мы дали ему другой набор фрагментов, но будут ли все остальные комбинации этих фрагментов играбельными?
Это показывает нам, насколько сложно создать процедурный генератор. Мы хотим думать о своих генераторах как об обычном контенте игры, представлять, как игрок проходит определённый уровень и получает от него удовольствие. Но как дизайнеры генерации мы должны думать о всём пространстве генерации, а не только об единственном примере из него. Насколько велико пространство? Насколько оно богато на сюрпризы? Как часто оно создаёт нечто скучное или плохое? Можем ли мы обнаруживать и фильтровать эти случаи, или нужно искать обходной путь? Это всего лишь некоторые из вопросов, которые нужно учитывать при создании чего-то для генерации.
Подведём итог
Сегодня мы узнали о следующих понятиях:
Пространство генерации
Пространство генерации генератора процедурного контента (например, генератора мира Minecraft) — это множество всех результатов, которые он может сгенерировать. Если мы изменим алгоритм или зададим другое значение переменной, то пространство генерации изменится.
Пространство возможностей
Пространство возможностей определённого вида контента (например, мира Minecraft) — это множество всех примеров такого контента, которое мы можем представить или описать. Обычно, но не всегда, оно гораздо больше, чем пространство генерации процедурного генератора.
Больше — не всегда лучше
Генератор с большим пространством генерации обычно имеет больше хорошего контента, больше неожиданного контента и больше разнообразного контента. Но обычно у него и больше мусорного контента, больше скучного контента и больше непригодного контента.
Генератор с меньшим пространством генерации проще контролировать, проще тестировать и проще понимать. Но это может сделать его более предсказуемым и менее удивляющим.
Поиск способов балансирования сильных и слабых сторон этих двух противоположностей и является искусством создания ПО для генерации!
Дополнительное чтение и благодарности
На этом мой туториал заканчивается! Благодарю за прочтение.
Среди интересных материалов по рассмотренной нами теме я рекомендую следующие:
- Книга Spelunky by Derek Yu — отличный рассказ о том, как создавался дизайн Spelunky, в том числе обсуждение процедурного генератора игры.
- Tracery Tutorials, by Kate Compton — узнайте, как писать грамматику на основе текста, отличный способ практиковать о пространстве генерации!
- Глава превосходной книги доктора Джиллиан Смит о диапазоне выразительности (который мы рассмотрим в будущем туториале).
- У доктора Смит есть и множество бесплатных ресурсов, например её отличный доклад на GDC о компромиссах в процедурной генерации.
- И, наконец, не забывайте, что все генераторы из статьи можно найти в Processing-скетче с открытым исходным кодом (здесь).
Автор: PatientZero
