Хабрахабр

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

Наверно худшее, что случилось в области процедурной генерации контента (если считать, что это действительно область процедурной генерации контента, в чём я уверен не полностью) — это шум Перлина. Шум Перлина невероятно хорошо подходит (по крайней мере, если не приглядываться слишком внимательно) для генерации интересных ландшафтов. В сабреддите /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 будет вдвое интереснее. Итак, интересность имеет некоторые элементы прерывности — это не плавная функция, изменяющаяся рациональным и предсказуемым способом при движении по пространству возможностей. Вероятно, вы сможете придумать и другие примеры того, как «интересность» ведёт себя странным и контринтуитивным образом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть