Шум Перлина, процедурная генерация контента и интересное пространство +28


Наверно худшее, что случилось в области процедурной генерации контента (если считать, что это действительно область процедурной генерации контента, в чём я уверен не полностью) — это шум Перлина. Шум Перлина невероятно хорошо подходит (по крайней мере, если не приглядываться слишком внимательно) для генерации интересных ландшафтов. В сабреддите /r/proceduralgeneration недели не проходит без того, чтобы кто-нибудь не опубликовал «систему процедурной генерации», которая оказывается визуализированным разными цветами шумом Перлина. (За время написания этой статьи появилось два таких поста!)


Я не хочу унизить шум Перлина. Это невероятно полезный для процедурной генерации инструмент, ставший точкой входа в эту область для множества людей, в том числе и меня. Но в то же время он очень сбивает с толку, потому что подразумевает, что процедурная генерация намного проще, чем это есть на самом деле. Большинство еженедельных постов о «системах процедурной генерации» в /r/proceduralgeneration исчезают без следа, когда их авторы обнаруживают, что следующий шаг в процедурной генерации гораздо сложнее. Истина в том, что шум Перлина стал своего рода счастливой случайностью. Он отлично подходит для генерации интересных ландшафтов, но на то нет систематических или повторяемых причин.

Майк Кук недавно опубликовал туториал, противопоставляющий пространство возможностей пространству генерации. Если вы создаёте систему генерации для создания X, то пространство возможностей равно всем возможным X, а пространство генерации — это все X, которые ваша система сможет сгенерировать на самом деле. Майк иллюстрирует эту идею на примере Minecraft:


В случае моей игры Dragons Abound пространство возможностей включает каждую возможную карту, в том числе и множество вырожденных случаев, например, карту, целиком состоящую из океана с одним небольшим островом. Пространство генерации — это меньшее пространство всех карт, которые Dragons Abound может генерировать на самом деле. Благодаря различным используемым правилам, Dragons Abound не может сгенерировать карту из океана с небольшим островком, поэтому эта карта не находится в пространстве генерации игры. Сопоставление пространства возможностей с пространством генерации — это интересный и полезный взгляд на процедурную генерацию, поэтому рекомендую вам прочитать пост Майка, в котором эта идея объясняется подробнее, а также есть несколько интерактивных примеров.

В дополнение к пространству возможностей и пространству генерации полезно также подумать об «интересном пространстве». Если мы создаём X, то это пространство всех интересных X. То есть в случае моей игры это пространство всех интересных фэнтезийных карт. Интересное пространство — это подмножество пространства возможностей и оно, как мы надеемся, пересекается с пространством генерации — например, я надеюсь, что хотя бы некоторые карты, генерируемые моей игрой, оказываются интересными.

Прежде чем двигаться дальше, я с готовностью признаю, что «интересность» — это смутное и субъективное понятие. Мои и ваши понятия об интересном скорее всего не совпадают. Я даже не всегда знаю, что покажется интересным мне — часто я вижу что-то новое и нахожу это интересным, хотя не думал, что это понравится мне, пока я это не увидел. Хуже того, чем больше мы видим интересного, тем менее оно становится интересным. Когда увидишь интересную особенность на двадцати картах подряд, то она больше не кажется интересной. Поэтому «интересность» не так просто ухватить. В будущем я подробнее расскажу о том, что делает вещи интересными (а в прошлом у меня было, что сказать о близкой идее пространства творчества), но пока это не очень важно. Нам достаточно согласиться с тем, что некоторые вещи интереснее других, и что более интересные вещи находятся в «интересном пространстве», а менее интересные — нет.

Можно ли проиллюстрировать интересное пространство аналогично тому, как Майк показал пространство возможностей и пространство генерации? Как предложено выше, интересное пространство — это подмножество пространства возможностей, которое (если повезёт) пересекается с пространством генерации:


Хороший генератор сильно пересекается с интересным пространством; плохой генератор — слабо.

Эти схемы — просто метафора, но в рамках этой метафоры я хочу задать следующий вопрос: правильно ли я указал формы разных пространств? Форма пространства возможностей на самом деле не важна, она просто должна содержать два других пространства. Но формы пространства генерации и интересного пространства — это более интересные (sic) вопросы. Я нарисовал их оба как единичные компактные формы в пределах пространства возможностей. Разумно ли это?

Я считаю, что обозначение пространства генерации как компактного эллипса — хороший выбор для многих процедурных генераторов, и в особенности для чего-то наподобие шума Перлина. Форма подразумевает, что генератор создаёт все решения в пределах единого чётко очерченного и компактного пространства. Если генератор может создать X, то обычно может создать и всех соседей X. В пространстве генерации обычно нет больших «дыр» или странных искажений.

Пространства генерации обычно выглядят так по двум причинам. Во-первых, на уровне практического применения генератор — это небольшой объём кода, связанного с пространством возможностей. На текущий момент Dragons Abound содержит около 28 тысяч строк исходного кода. По сравнению со многими другими процедурными генераторами карт это много (возможно, даже рекорд), но это всё равно чрезвычайно мало по сравнению с пространством возможностей всех фэнтезийных карт. Поэтому как бы ни был умён код игры, его пространство генерации займёт только небольшую часть пространства возможностей, а поскольку компьютерный код по определению является алгоритмическим и детерминированным, это пространство окажется относительно компактным. То есть если игра может создавать один тип карт, то почти точно создаст множество других похожих карт.

Вторая причина, по которой пространства генерации компактны — стратегическая. Для меня цель создания Dragons Abound — это генерация интересных карт, чтобы они как можно больше пересекались с интересным пространством. А в интересное пространство сложно попасть, оно очень мало по сравнению с пространством возможностей. На самом деле оно очень, очень мало. Все эти пространства имеют огромное количество измерений, а размер пространства по сути растёт как степень числа измерений. Реальное соотношение между интересным пространством и пространством возможностей выглядит примерно так:


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


Только зелёные точки гораздо меньше. Шансы попадания с одной из случайных карт в крошечное интересное пространство по сути равны нулю. Чтобы повысить шансы попадания в интересное пространство, создатель процедурной генерации использует знание о пространстве возможностей и интересном пространстве для управления генерацией — создатель сдвигает пространство генерации так, чтобы оно в основном находилось по соседству с интересным пространством, а не просто распределялось случайным образом.

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

Но я считаю, что рисовать так интересное пространство было бы, вероятно, полностью неверно. Оно должно описываться как разбросанное, разделённое множество областей странной формы. Почему? Потому что (1) вещи могут быть интересными по разным, ортогональным причинам, и (2) интересность — это прерывная функция.

Рассмотрим, например, эти два фрагмента карты:



Первый фрагмент интересен тем, что береговая линия причудливо детализирована и содержит множество мелких островов. Второй фрагмент имеет скучную, плавную береговую линию, но побережье имеет интересные черты — оно необитаемо и имеет зловещее название «Печальный берег» («Bleak Shore»). В каком-то смысле оба эти фрагмента интересны, но по совершенно разным причинам. Поэтому мы не будем ожидать, что эти две части интересного пространства будут соседями.

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

Итак, интересное пространство — это не единая область, а набор разделённых областей. Имеет ли каждое такое интересное пространство плавные, компактные формы?

Повторюсь, я не заявляю, что могу дать полное определение «интересности». Но в некоторых аспектах мы можем прийти к согласию по нескольким пунктам. Во-первых, если X интересен, то это не означает, что 2X будет вдвое интереснее. Возьмём пример с Печальным берегом — одна область загадочного побережья на карте интересна, но десяток их будет очень неинтересным. Вероятно, вы сможете придумать и другие примеры того, как «интересность» ведёт себя странным и контринтуитивным образом. Итак, интересность имеет некоторые элементы прерывности — это не плавная функция, изменяющаяся рациональным и предсказуемым способом при движении по пространству возможностей.

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


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

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


Генератор шума Перлина имеет больше пересечение с конкретным интересным пространством внутри вселенной всех возможных ландшафтов. И это отлично — почти всё, что можно создать с помощью шума Перлина, попадает в эту область и выглядит довольно интересно.

Но этот быстрый успех обманчив. Если вы новичок в процедурной генерации, то увидите, как хорошо работает шум Перлина и скорее всего решите, что шум Перлина — это волшебная палочка для генерации всех видов интересных ландшафтов, не говоря уже о всех видах процедурной генерации. Но как показывает схема, пространство генерации шума Перлина на самом деле расположено далеко от многих других частей интересного пространства ландшафтов. Стандартный второй шаг в процедурной генерации ландшафтов — добавление рек. Но если вы попытаетесь реализовать реки с помощью шума Перлина, то обнаружите, что это невозможно! Никаким образом нельзя расширить границы пространства генерации шума Перлина, чтобы достичь далёких интересных пространств, содержащих реалистичные реки.

Шум Перлина обманчив и в другом смысле. Выше я говорил о том, что интересное пространство настолько мало, что если вы хотите в него попасть, то необходимо обладать определёнными знаниями о пространстве возможностей и интересном пространстве, чтобы управлять процедурной генерацией. Но алгоритм шума Перлина ничего не знает о ландшафтах, геологических процессах, о том, что люди находят интересным, и тем не менее, каким-то образом хорошо работает без этого знания! Шум Перлина оказался исключением, подтверждающим правило (*). Но если вы новичок в процедурной генерации, то вы, скорее всего, этого правила не знаете. На самом деле, вы выводите ошибочное правило — вся процедурная генерация в целом должна работать подобно шуму Перлина.

(* Он не просто случайно «оказался» исключением. Шум Перлина стал популярной начальной точкой именно потому, что является исключением. Очень легко начать с шума Перлина без необходимости изучать большой объём информации о ландшафтах.)

Рассмотрим ещё одну популярную начальную точку в генерации процедурного контента: схемы подземелий. В отличие от генерации ландшафтов, схемы подземелий не имеют алгоритма, похожего на шум Перлина, который волшебным образом создаёт решения в интересном пространстве. С учётом того, что мы знаем о пространстве генерации и интересном пространстве, можно догадаться, что генераторы подземелий должны или (1) включать в себя конкретное знание о поздемельях и интересности, или (2) создавать в основном неинтересные подземелья. И действительно — если вы просмотрите генераторы подземелий, опубликованные за последний год в /r/proceduralgeneration, то увидите, что большинство из них не содержит никакого знания о подземельях, кроме проверки соединения всех комнат, а потому выводимые этими проектами данные скорее случайны, чем интересны.


Итак, если считать, что вы более-менее согласны с написанным мной, то какие уроки можно извлечь из этой концепции интересного пространства?

  • Процедурная генерация фундаментально сложна, потому что интересное пространство — очень маленькая и сложная для попадания цель.
  • Несмотря на случайные исключения наподобие шума Перлина, не стоит ожидать, что простые, наивные алгоритмы успешно будут генерировать интересный контент. Хорошая процедурная генерация должна включать в себя и использовать обширное, глубокое знание предметной области и понимание того, что делает контент интересным.
  • Но даже в лучших алгоритмах генерации пространство генерации компактно, а интересное пространство — нет, поэтому стоит ожидать, что процедурная генерация будет часто промахиваться, а потому нужно выстраивать системы соответствующим образом.
  • В сложных предметных областях интересное пространство разделено и имеет странную форму. Не стоит ожидать, что алгоритм или подход, хорошо работающий в одной части интересного пространства, обязательно так же хорошо сработает в другой части. Поэтому следует ожидать, что процедурная генерация будет включать в себя множество различных алгоритмов, использующих различные части интересного пространства.

Если вы только начинаете работать с процедурной генерацией, то рекомендую вам задуматься об интересности. Что сделает выходные данные интересными? Что нужно понимать алгоритму, чтобы выдавать данные, которые чаще оказываются интересными? Какой другой способ вывода данных может быть интересным? Какой новый алгоритм мне нужен, чтобы сгенерировать подобную интересность? Как скомбинировать/сбалансировать его с первым алгоритмом?

Например, если бы я хотел создать генератор подземелий, то какое-то время поразмышлял над подземельями, и решил, что по моему мнению подземелья являются интересными, если:

  1. Они выглядят как будто их создавали, чтобы они стали складами, тюремными камерами
    и другой подземной инфраструктурой большого замка
  2. Позже они были заполнены монстрами и перестроены ими, чтобы удовлетворять их потребности в убежище, еде, воде, защите от нападений и т.д.

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




К сожалению, не доступен сервер mySQL