Драматургия уровней с помощью математики

Есть много способов генерировать уровни. Давайте разберем метод с WFC и Entropy Bias. Его плюсы и минусы, как и зачем он вообще нужен. А так же как работает. В конце небольшая игрушка с демонстрацией того, как это всё работает в финале.

Разберем откуда вообще берутся комнаты, что такое WFC и причем тут энтропия Шеннона.

Откуда берётся комната

Способов получить связную карту немного, и все они старше большинства читателей.

Прямоугольники и коридоры. Бросаем на сетку N прямоугольников, соединяем центры соседних Г-образными коридорами. Узнаётся с первого взгляда, пишется за вечер. Платим двумя вещами: коридоры выходят кишками — прямая, поворот, прямая, и ни одна из них не значит ничего.

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

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

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

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

Чтож, к алгоритму. На входе у WFCWave Function Collapse — алгоритм генерации по ограничениям соседства: на входе набор тайлов и правила стыковки, на выходе сетка, где каждая клетка занята одним тайлом и все правила соблюдены. две вещи: набор тайлов и правила соседства между ними. «Вот этот край стыкуется с вот этим, а с вот этим нет». На выходе — сетка, где каждая клетка заняла ровно один тайл и ни одно правило не нарушено.

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

Вопрос ровно один: какую клетку коллапсировать следующей? Здесь и появляется энтропия Шеннона — мера того, насколько клетка ещё не определилась:

Осталось шестнадцать равновероятных вариантов — энтропия большая. Остался один — энтропия ноль, выбора нет.

WFC всегда коллапсирует клетку с минимальной энтропией. Ту, где выбор почти сделан: там дешевле всего проверить результат и там раньше всего вылезет противоречие, если набор тайлов неудачный. По сути это весь скелет алгоритма — остальное детали реализации.

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

Отсюда и равномерность. Не из-за тайлсета, не из-за шума, а из устройства правила выбора.

Одно умножение

Раз алгоритму не хватает понятия места, дадим ему понятие места.

$W(x,y)$ — семантический вес: скалярное поле от нуля до единицы, заданное на той же сетке, что карта. Одно число на клетку, и означает оно «насколько эта клетка важна для структуры уровня». Единица — ключевая зона: арена босса, стартовый хаб, ядро награды. Ноль — проходная клетка, наполнитель.

$f$ — убывающая функция: чем больше вес, тем меньше множитель. Простейший вариант — $f(W) = 1 - \beta W$, где $\beta$ от нуля до единицы задаёт силу смещения. При $\beta = 0$ множитель равен единице, и мы получаем обратно классический WFC — ровно тот же, вплоть до порядка коллапса.

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

Поменялся не порядок, а топология

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

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

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

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

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

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

Форма f — дизайнерский выбор

Линейная $f(W) = 1 - \beta W$ гладкая и даёт плавное смещение: разумный старт, легко отлаживать. Пороговая жёсткая: всё ниже порога ведёт себя как в ванильном WFC, всё выше коллапсирует первым — подходит, когда ключевые зоны почти детерминированы. Экспоненциальная $f(W) = e^{-k\beta W}$ нелинейна: мелкие различия в весе почти не влияют, крупные влияют драматически.

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

Про шум легко забыть

$\text{noise}(c)$ в формуле — небольшая случайная добавка, которая разрывает ничьи между клетками с одинаковой энтропией. После модификации она нужна в той же роли, но амплитуду приходится подбирать заново. Произведение $H \cdot f$ стало маленьким числом — оба множителя меньше единицы, — а шум остался прежнего размера. Он перекроет сигнал, клетки начнут выбираться случайно, и смещение исчезнет целиком.

Лечится тем, что шум масштабируется долей от среднего $H \cdot f$ по сетке, а не остаётся абсолютной константой. Мелочь на одну строку, но без неё модификация просто не работает, и понять это по картинке невозможно — карты выглядят как обычные карты WFC.

Порисуйте по карте мышкой: ржавым проступает поле весов. Поставьте $\beta$ в ноль — получите классический WFC, порядок коллапса решает одна энтропия. Поднимите до единицы с экспонентой — и фронт пойдёт из ваших мазков.

Чем клетка становится

Чтож, смещение энтропии решает, когда клетка коллапсирует. Остаётся второй вопрос: чем она становится, когда очередь дошла.

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

Модификация того же сорта:

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

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

Четыре карты вместо одной

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

• $W_d$ — danger: где появляются враги и ловушки;
• $W_r$ — reward: где падают перки, сундуки, алтари;
• $W_e$ — exit: направленность к выходу уровня;
• $W_n$ — narrative: особые зоны, от арены босса до safe room.

Каждый слой рисуется, отлаживается и влияет на свой тип тайлов отдельно. Итоговый вес для смещения — взвешенная сумма:

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

Три сценария

Награда за риск. Danger и reward оба высокие в центре. Ядро карты одновременно зона опасности и зона награды, коллапсирует оно первым, и коридоры, севшие следом, уже «знают», что ведут в опасную зону: узкие проходы, ограниченная видимость. Игрок подходит к центру, чувствует нарастание давления, натыкается на самую плотную группу противников — и сразу за ней сундук. Выбор: рискнуть или уйти. Классическая связка, рассказанная картой без единого скрипта.

Лёгкий путь ведёт не к выходу. Слой exit направлен в одну сторону — это «правильная» дорога. Но danger вдоль неё высокий: мобы, узкие места, препятствия. Параллельно идёт более открытый коридор с низкой опасностью, уводящий в обход или в тупик. Игрок интуитивно выбирает лёгкое, через пять минут понимает, что ушёл не туда, возвращается. Карта дала выбор и назначила ему цену; интенсивность настраивается контрастом полей.

Тайная комната. Reward имеет локальный пик в углу, далеко от старта и выхода, а narrative низкий везде, кроме этого пика. В поле образуется остров: клетки с высоким весом, окружённые низким. Алгоритм коллапсирует остров одним из первых, а дальше вес падает резко, фронт от острова слабый, и соседство с остальной картой достаётся обычному WFC — как пойдёт. Часто комната оказывается за стеной или секретным проходом.

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

Уровень, по которому ходят

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

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

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

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

По сути у любого генератора уровней два слоя: вероятностный, который делает уровни интересными, и проверочный, который делает их проходимыми.

Что в итоге

• Прямоугольники с коридорами, BSP и случайное блуждание раздают геометрию, но не отвечают, что в комнате происходит.
• Классический WFC коллапсирует карту по локальной энтропии, и структура получается эмерджентной и равномерной — не из-за тайлсета, а из устройства правила выбора.
• Множитель f(W) в формуле выбора клетки меняет не порядок коллапса, а топологию распространения ограничений: поле весов становится картой источников.
• Из горячих зон расходятся концентрические фронты, и форму карты начинает задавать форма поля, а не набор тайлов.
• Модуляция вероятностей тайлов привязывает к месту содержимое; разложение поля на danger, reward, exit и narrative превращает всё это в четыре тепловые карты, которые дизайнер умеет рисовать.

Что почитать дальше

Оригинальную реализацию WFC выложил Максим Гумин — читать стоит именно её, она компактная и без наслоений. Пошаговый разбор алгоритма у Роберта Хитона. Корни меры неопределённости — в работе Клода Шеннона о математической теории связи 1948 года. За общей картиной методов — книга «Procedural Content Generation in Games». И доклад Оскара Столберга «Beyond Townscaper» с GDC 2021 — про то, во что WFC превращается, когда сетка перестаёт быть квадратной.

Рядом на сайте: четыре стратегии производства уровней и их экономика — про то, сколько всё это стоит студии; и разбор процедурного шума, если поле весов хочется не рисовать, а генерировать.