Средний

11 мин

1.9K

Как одна модификация формулы превращает генератор карт в дизайнера уровней

Всем привет! Меня зовут Григорий Дядиченко, и я технический продюсер. Играли в Hades? Там дизайнер уровней не бросает кубики. Он точно знает, где игрок поймает дыхание после погони, где встретит соблазн свернуть с пути, где сундук стоит под прицелом элитника, а где — просто в углу за колонной. В простой случайной генерации таких решений нет: карты рождаются «равномерными» и драматургически мёртвыми. Сегодня хочется поговорить о том, как одной модификацией в формуле Wave Function Collapse вернуть в генератор жизнь. Разберём Entropy Bias, Entropy Cascade, Tile Probability Bias и семантические слои. Если вам интересна тема процедурной генерации и немножко математики — добро пожаловать под кат.

WFC за три минуты

Давайте быстро пробежимся по базе, чтобы дальше не спотыкаться. WFC — это процедурный алгоритм генерации карт, основанный на ограничениях соседства между тайлами. На входе — атлас тайлов и правила («зелёный рядом с синим нельзя, с коричневым можно»). На выходе — сетка, где каждая клетка содержит ровно один тайл, и все ограничения соблюдены.

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

Вопрос собственно один: какую клетку коллапсировать следующей? И вот тут появляется энтропия Шеннона.

где p(t) — вероятность того, что клетка станет тайлом t. Чем выше энтропия — тем больше неопределённость. Чем ниже — тем клетка «определённее»: осталось меньше вариантов.

WFC всегда коллапсирует клетку с минимальной энтропией. Ту, где выбор почти сделан, где противоречие вероятнее всего и решение дешевле проверить. По сути — жёсткий скелет алгоритма. Всё остальное (overlap model, simple-tiled, backtracking) — это детали реализации, сейчас они нас не интересуют.

Если хочется копнуть глубже, то вот хорошие ресурсы:

• https://github.com/mxgmn/WaveFunctionCollapse — оригинал от Максима Гумина.

• https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/ — лучший пошаговый разбор, который я видел.

• Shannon, C.E. (1948). A Mathematical Theory of Communication — корни энтропии, если захочется дойти до основ основ.

Проблема: WFC не знает, что он делает

Чтож, а теперь собственно проблема, ради которой вся статья и затевалась.

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

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

Две карты из одного генератора, с одним тайлсетом, с одними ограничениями.

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

Вторая. Игрок заходит — короткий коридор с одним мобом для разогрева. Развилка: влево — риск и сундук, вправо — безопасно, но длиннее. В центральной арене бой с несколькими волнами. Перед выходом — алтарь-выбор. Тоже валидный результат WFC. С тем же тайлсетом.

азница — в том, чего WFC не моделирует: темп, ожидание, направление. Дизайнер уровней оперирует понятиями «дальше от входа», «ближе к боссу», «в зоне риска», «после безопасной паузы». Алгоритм — только соседством. Если у дизайнера в голове лежит карта напряжения, то у алгоритма ничего похожего нет. Он равномерен.

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

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

Модификация: Entropy Bias

Было:

Стало:

Одно умножение, один новый множитель. Смотрите внимательно — в этой строке по сути всё содержание статьи.

W(x,y) — это семантический вес. Скалярное поле в диапазоне [0.0, 1.0], определённое на той же сетке, что и карта. Для каждой клетки (x, y) — одно число, которое говорит: насколько эта клетка важна для общей структуры. W = 1.0 — ключевая зона (босс-арена, стартовый хаб, ядро награды). W = 0.0 — проходная клетка, наполнитель.

f — монотонно убывающая функция: чем больше вес, тем меньше f. Простейший вариант:

где beta ∈ [0, 1] — сила смещения. При beta = 0 получаем классический WFC. При beta → 1 семантический вес полностью доминирует над энтропией.

Что происходит с правилом выбора? Была argmin H(c), стала argmin H(c) * f(W). Для клеток с высоким W множитель f маленький — итоговое значение падает — клетка с большей вероятностью попадает в минимум — коллапсирует раньше. Клетки с низким W, наоборот, отодвигаются в конец очереди.

И здесь собственно ключевое наблюдение: мы поменяли не порядок, а топологию.

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

Но WFC — алгоритм с propagation. Как только клетка коллапсирует, через правила соседства её состояние сужает варианты у соседей, соседей соседей и так далее. Клетка, севшая первой, становится источником ограничений, которые волной расходятся по сетке. Те клетки, что сядут позже, уже не выбирают из полного атласа тайлов — они выбирают из того, что им «оставили» предшественники.

Значит, решая «кто коллапсирует первым», вы на самом деле решаете, кто кому родитель в графе зависимостей. Поле W — это карта источников: вот здесь рождаются решения, отсюда информация течёт наружу. Это описывает не положение в очереди, а структуру связей: кто кого определяет, в каком направлении расходятся фронты ограничений, где встречаются волны от двух разных источников и спорят за пограничные клетки. Именно это я и называю топологией.

Представьте дождь на рельефе. Если просто перемешать порядок падения капель — ничего не изменится, вода всё равно соберётся туда же. А вот сама форма рельефа (где пики, где низины) определяет всю структуру потоков: где образуются реки, куда стекает с какого склона, где собираются озёра. Классический WFC — плоская плита, капли падают хаотично, карта пропитывается равномерно. Поле W в Entropy Bias — это и есть рельеф: задаёт, откуда информация стекает в какие области, какие зоны оказываются «вверх по течению», а какие пассивно принимают то, что к ним пришло.

Entropy Cascade

Давайте посмотрим, что происходит дальше. Когда клетка с высоким весом коллапсирует, включается propagation. Её состояние зафиксировано — у соседей сужается множество допустимых тайлов — у них падает энтропия. В следующей итерации argmin с большой вероятностью выберет одного из этих соседей: их энтропия упала, а их W тоже, скорее всего, немаленький (поле W обычно гладкое — ключевые зоны не выглядят как одинокий пиксель).

Соседи коллапсируют — propagation идёт дальше — их соседи садятся вторым кольцом. В общем, получается волна: расходящиеся из «горячих» зон концентрические фронты коллапса. Я это называю Entropy Cascade.

Следствие: структура карты определяется не правилами тайлов, а формой поля W. Если W имеет один пик в центре — карта строится от центра наружу. Два пика — две зоны роста, которые встречаются посередине и спорят за пограничные клетки. Длинный гребень — карта строится полосой. Круг — кольцо с "неважной" серединой, которая заполнится последней и, скорее всего, непредсказуемо.

В классическом WFC порядок коллапса практически случаен: минимальная энтропия ломается шумом, и структура карты — это эмерджентный результат локальных ограничений. В WFC + Entropy Bias порядок коллапса задан полем W, и через него — задана топология распространения информации по карте.

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

Выбор функции f

Форма f(W) — это важный дизайнерский выбор, а не формальность. Давайте разберём пару рабочих вариантов.

Линейная.

Гладкая. Даёт плавное смещение. Разумный стартовый выбор: легко дебажить, легко крутить beta.

Пороговая.

Жёсткая. Все клетки ниже порога ведут себя как в ванильном WFC, все выше — коллапсируют насильно первыми. Подходит, когда ключевые зоны должны быть почти детерминированы.

Экспоненциальная.

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

На практике у меня экспоненциальная чаще даёт осмысленные карты. В поле W обычно много шума (оно рисуется вручную или из низкоуровневых эвристик), и при линейной f этот шум пролезает прямо в порядок коллапса — карты получаются нестабильными между прогонами. Экспонента шум придавливает. Ну и банально удобно крутить одним параметром k силу «фокусировки».

Что происходит с noise

noise(c) в исходной формуле — небольшой случайный член, который разрывает ничьи между клетками с одинаковой энтропией. После модификации он нужен в той же роли, но его амплитуду приходится подбирать аккуратно. Если H(c) f(W) превратилось в маленькое число (оба множителя меньше единицы), а noise остался прежнего размера — шум перекроет сигнал, клетки начнут выбираться случайно, смещение исчезнет. По сути, нужно масштабировать шум долей от среднего H f по сетке, а не оставлять абсолютную константу. Мелочь, но если её забыть — удивитесь, почему вся модификация не работает.

Что это меняет для дизайнера

В классическом WFC вы контролируете карту через атлас: какие тайлы существуют, какие соседства разрешены. Это низкоуровневый контроль — вроде задания грамматики для языка, на котором потом говорит алгоритм. Вы не можете сказать «здесь должен быть тяжёлый момент», вы можете сказать только «этот тайл может стоять рядом с вот этим».

Entropy Bias добавляет отдельный уровень управления поверх грамматики: где в картинной плоскости должен быть тяжёлый момент. Этот уровень не конфликтует с ограничениями — он работает в полностью валидном подмножестве. Его проще рисовать: одна тепловая карта, кисть, слайдеры. И собственно, это и есть тот интерфейс, которого всегда не хватало дизайнеру уровней в процедурной генерации.

Второй рычаг: Tile Probability Bias

Entropy Bias решает, когда клетка коллапсирует. Остаётся вопрос, чем клетка становится, когда очередь дошла.

В классическом WFC выбор тайла внутри клетки — это взвешенный случайный выбор из оставшихся вариантов, где веса p(t) берутся из частот тайлов в обучающем атласе. Если сундук встречается в атласе в 2% случаев — примерно в 2% клеток, где он допустим, он и выпадет. Банально.

Модификация:

Вероятность тайла теперь зависит не только от атласа, но и от места. g — функция, заданная для каждого тайла отдельно: для одних растёт с W, для других падает, для третьих не меняется.

Пример: перки. Как в каком-нибудь Diablo или Hades. В атласе есть тайлы общих, редких и легендарных перков. В ванильном WFC они выпадают со своими частотами — легендарный, условно, с 5%, где попало. С Tile Probability Bias:

где W_e(x,y) — близость к выходу уровня: высокая в конце, низкая в начале. Чем дальше игрок прошёл — тем выше tier доступного перка.

Это уже не геометрия. Это нарратив: «чем дольше держался, тем лучше награда». Закодирован прямо в вероятностную функцию. Правил вида «легендарный не может стоять рядом со входом» — нет. Есть скалярное поле и модуляция частоты. Собственно и всё.

Entropy Bias двигает скелет карты. Tile Probability Bias — наполняет уже сложившийся скелет. Они ортогональны: можно включить один без другого. Вместе — карты, где и структура, и содержание подчинены одной дизайн идее.

Семантические слои

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

• W_d(x,y) — danger: где появляются враги и ловушки

• W_r(x,y) — reward: где падают перки, сундуки, алтари

• W_e(x,y) — exit: направленность к выходу уровня

• W_n(x,y) — narrative: специальные зоны (босс-арена, safe room, триггер катсцены)

Каждый слой — это отдельное скалярное поле. Отдельно рисуется, отдельно дебажится, отдельно влияет на соответствующий тип тайлов через g(t, W_i).

Итоговый вес для Entropy Bias — взвешенная сумма:

где alpha_i — дизайнерские коэффициенты: «на этом уровне важнее динамика награды, alpha_r = 0.5», «а тут важен путь, alpha_e = 0.7».

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

Чтож, давайте посмотрим на три сценария, где слои работают вместе.

Награда за риск

W_d и W_r оба высокие в центре. Ядро карты одновременно — зона опасности и зона награды. Алгоритм коллапсирует это ядро первым (суммарный W большой) — туда попадают тайлы, совместимые одновременно с элитным врагом и с хорошим сундуком. Propagation от ядра задаёт коридоры: они «знают», что ведут в опасную зону. К моменту, когда периферия коллапсирует, она уже адаптирована под это ядро — стены, ограничение видимости, узкие проходы.

Эффект для игрока: подходя к центру, вы чувствуете нарастание давления. Находите элитника — и сразу видите сундук с легендаркой за его спиной. Выбор: рискнуть или уйти. Карта рассказала эту историю без единого скрипта. По сути, классическая связка «риск — награда» из World of Warcraft или любой рогалик-игры, но сгенерированная автоматически.

Путь наименьшего сопротивления ведёт не к выходу

W_e направлен в одну сторону — это «правильная» дорога к выходу. Но W_d вдоль этой дороги высокий: там мобы, препятствия, узкие места. Параллельно — более открытый коридор с низким W_d, но уводящий в тупик или длинный обход.

Игрок интуитивно выбирает лёгкий путь. Через пять минут понимает, что ушёл не туда. Возвращается. Это не баг, это дизайн: карта создаёт ощущение выбора и его цены. В WFC без Entropy Bias такое случается редко и случайно. С Entropy Bias — стабильно, и интенсивность настраивается контрастом полей.

Тайная комната

W_r имеет локальный пик в углу, далеко от старта и выхода. W_n низкий везде, кроме этого пика. В поле W образуется «остров»: клетки с высоким весом, окружённые низким.

Алгоритм коллапсирует остров одним из первых (высокий W → низкий f → коллапс). Через propagation остров формирует маленькую замкнутую зону с лучшей наградой уровня. От него фронт коллапса слабый (вес падает резко), и соседство с остальной картой определяется обычным WFC — как пойдёт. Часто комната оказывается за стеной, за секретным проходом, за непроходимой на первый взгляд преградой. Её надо найти. Найдёте — забираете лучший перк уровня. Как в Skyrim, только без ручной расстановки.

И собственно разница с «ручным» размещением тайника: он не фиксирован в координатах. Он фиксирован в отношении — как аномалия поля W. Где конкретно он окажется на карте — решает алгоритм через propagation. Каждый прогон даёт новое размещение, но свойство «далеко, тяжело найти, хорошо платит» сохраняется.

Это и есть то, ради чего вся модификация: инвариант дизайна сохраняется, конкретная реализация варьируется от прогона к прогону. Дизайнер задаёт идею, а не результат.

Интерактивное демо

По сути, всё это удобнее один раз увидеть, чем прочитать. Я собрал интерактивное демо: вы рисуете три тепловые карты (danger, reward, exit). Алгоритм выдаёт уровень в реальном времени. Меняете кисть — перегенерируете. Видно, как форма поля W проявляется в геометрии карты и какие сценарии получаются из каких комбинаций слоёв.

Итого

Собственно, что мы получили. Классический WFC коллапсирует карту по локальной энтропии — структура эмерджентна и драматургически равномерна. Добавили f(W(x,y)) в формулу выбора клетки — получили Entropy Bias: ключевые зоны коллапсируют первыми, от них расходятся волны Entropy Cascade, и топология карты перестаёт быть случайной. Добавили g(t, W(x,y)) в вероятность тайлов — получили Tile Probability Bias: наполнение карты тоже зависит от места. Разбили W на семантические слои — получили интерфейс, который понимает дизайнер уровней. В канале просили что-то сложное — получайте. Если половина слов не совсем понятна в этом абзаце — это нормально.

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

Источники, из которых собиралась картина:

• Wave Function Collapse, Maxim Gumin

• WFC explained, Robert Heaton

• Shannon, C.E. (1948). A Mathematical Theory of Communication

• Procedural Content Generation in Games

• GDC 2021, Oskar Stålberg — Beyond Townscaper