← Модуль 11/Wave Function Collapse
EN
Модуль 11 · Процедурная генерация

Wave Function Collapse

Удовлетворение ограничений, переодетое в квантовую метафору. Главный урок PCG: генерация без ограничений = шум.
🏠 лаба~15 мин
Суть за 20 секунд
Каждая клетка стартует в «суперпозиции» — список всех возможных тайлов. Цикл: (1) observe — найди клетку с наименьшей энтропией (меньше всего вариантов) и «схлопни» её в один тайл, выбранный по частотам; (2) propagate — выкинь у соседей варианты, несовместимые с выбором, и протолкни эти ограничения дальше волной; (3) повторяй, пока все клетки не определены. Имя «квантовое», суть — constraint satisfaction. Совместимость задаётся правилами смежности тайлов.

Механизм (simple-tile)

Базовый вариант — simple-tile: ты вручную задаёшь, какие тайлы могут соседствовать (трава рядом с травой и с кромкой; вода рядом с водой и кромкой; кромка — между ними). Алгоритм:

Цикл WFC псевдокод
пока есть неопределённые клетки:
    cell = клетка с минимальной энтропией   # меньше всего вариантов
    tile = выбрать из cell.options по весам   # частотность тайла
    cell.collapse(tile)                       # observe
    очередь = [cell]
    пока очередь не пуста:                     # propagate
        c = очередь.pop()
        для соседа n клетки c:
            до = n.options
            n.options ∩= совместимые_с(c)      # срез по смежности
            если n.options изменились: очередь.push(n)
    если у какой-то клетки options пусто:
        противоречие → backtrack или restart
{трава,кромка,вода} → observe →{трава} → соседи теряют«вода» (propagate)
Каждый выбор сужает соседей. Низкая энтропия первой — чтобы реже упираться в противоречие.

Есть и второй вкус — overlapping / NxN-pattern: правила смежности не задаются руками, а извлекаются из примера-картинки (все N×N окошки). Мощнее (учится у образца), но дороже и капризнее. В лабе — simple-tile, чтобы увидеть механику без магии.

🕹 В какие игры поиграть — и что заметить

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

Townscaper 2021 · ты и есть WFC

Городок-песочница Оскара Стольберга: ставишь домик-воксель — а движок сам достраивает крыши, стены, окна и арки так, чтобы всё стыковалось. Под капотом — WFC на нерегулярной сетке + marching cubes: каждый блок «коллапсит» геометрию по правилам смежности с соседями. Ты буквально дёргаешь observe рукой, а propagate доводит остальное.

🎮 Сыграй: поставь и убери пару блоков подряд — смотри, как крыши/окна/арки пересобираются под новых соседей. Поставь блок на отшибе, потом соедини с домом — увидишь, как геометрия «схлопывается» под стык. Это constraint propagation, которым управляешь пальцем (ровно как якорь в лабе).

Bad North 2018 · WFC для уровней

Тот же Стольберг, но WFC генерит геометрию островов (его доклад EPC2018 так и называется — «Wave Function Collapse in Bad North»). Каждый остров — связная, играбельная топология: нет невозможных обрывов, есть где высадиться и обороняться. Реализация неинтерактивная (генерит до боя), в отличие от Townscaper.

🎮 Сыграй: пробеги кампанию по карте — каждый остров разный, но всегда когерентный и проходимый; заметь, что «странных» обрывов и тупиков-ловушек нет. Это ограничения смежности держат форму.

Caves of Qud WFC в проде (первый коммерческий)

Первое коммерческое применение WFC (Брайан Баклю, Freehold Games; доклады GDC 2019 / Roguelike Celebration). Генерация многопроходная: грубая структура → средние проходы добивают детали через WFC → финальные пасы чинят связность и населяют. Баклю прямо разбирал боли — overfitting/гомогенность и связность уровней — и как их лечит.

🎮 Сыграй: брожи по руинам и постройкам — узоры стен и полов разнообразны, но локально когерентны (WFC учился у примеров), при этом уровень всегда связен (финальный пас-проверка). Контраст «разнообразно, но не мусор».

Spelunky контраст: не WFC, но тот же урок

Не WFC, а соседний подход: уровень собирается из рукотворных комнат-шаблонов на сетке 4×4, поверх прокладывается гарантированный путь вход→выход. Но мораль — ровно из урока: генерация без ограничений = мусор; «связно и проходимо» — это жёсткие констрейнты поверх рандома, а валидный ≠ играбельный.

🎮 Сыграй: пробеги десяток уровней — каждый разный, но путь от входа к выходу есть всегда (тот самый carved path). Попробуй «застрять без бомб» — нащупаешь, где кончается констрейнт проходимости и начинается мастерство дизайна.

Хардкор: WFC как CSP, энтропия Шеннона и неразрешимость замощенияможно пропустить

WFC = задача удовлетворения ограничений (CSP)

Переменные — клетки, домены — множества тайлов, ограничения — смежности. Шаг propagate() — это enforcement дуговой согласованности (AC-3): для каждой дуги (клетка → сосед) выкидываем из домена соседа значения без поддержки и пере-кладываем в очередь затронутые дуги. Псевдокод WFC буквально и есть специализированный AC-3.

Что такое «энтропия» строго

«Клетка с минимальной энтропией» — это энтропия Шеннона по взвешенным вариантам:

H(cell) = − Σ_t p_t · log p_t, p_t = w_t / Σ_s w_s

(w_t — частотный вес тайла; обычно + малый шум для разрыва ничьих). При равных весах вырождается в «меньше всего оставшихся вариантов» — эвристику MRV (minimum remaining values) из классического CSP.

Завершаемость и сложность

AC-3 корректна, но не полна: дуговая согласованность не гарантирует существование глобального решения. Поэтому WFC без бэктрекинга неполон — может упереться в противоречие, даже когда решение есть. Полнота требует поиска с откатом.

В общем случае жёстче: «замостить плоскость данным набором тайлов Ванга» — неразрешимая задача (Бергер, 1966, domino problem); конечная версия (n×n) — NP-полна. WFC наследует эту жёсткость; работает на практике, потому что игровые тайлсеты «рыхлые» (валидных конфигураций много), а рестарт дёшев.

Хардкор · дизайн: контролируемость против сюрпризаможно пропустить

Чистая процедурка быстро ощущается «одинаковой» и бездушной — это её главный дизайн-провал, не технический. Рычаги контроля:

  • Якоря и сет-пизы: вручную фиксируешь ключевые клетки/комнаты, генератор заполняет остальное (босс-арена и вход заданы, путь между — процедурный).
  • Гибрид handcrafted + procedural: Spelunky/Diablo собирают уровень из рукотворных кусков процедурно — лучшее из двух миров.
  • QA генерации: валидный ≠ интересный и ≠ проходимый. Нужен авто-чек на связность (flood-fill/A*), на тупики, на скучность — иначе игрок получит «технически корректный» мусор.
  • Build-time vs runtime: генерить на билде (контроль, кураторство) или на лету (бесконечность, риск) — выбор дизайнерский, не только технический.
Аналогия
WFC — это судоку, который решает сам себя случайно. В судоку клетка может быть {1..9}; ставишь цифру — у соседей по строке/столбцу/квадрату варианты сужаются. WFC делает то же с тайлами: «схлопывает» самую определённую клетку и распространяет последствия. «Противоречие» = клетка, у которой не осталось ни одного варианта (как судоку без решения) → откат.
Почему это важно
WFC — концентрат главного принципа PCG: генерация требует ограничений. Чистый рандом даёт мусор; красивый процедурный контент — это рандом, зажатый правилами совместимости. Тот же принцип потом всплывёт в diffusion (управляемая генерация) и в structured-output у LLM (генерация по схеме).
🔁 За пределами игр — куда это переносится
WFC — это удовлетворение ограничений (CSP) + constraint propagation. Один из самых переносимых приёмов:

Общее: расписания, расстановка (timetabling), раскладка, конфигураторы товаров — всё CSP; под капотом SAT/SMT-солверы.

ML / AI: constrained / grammar-guided decoding — это WFC над токенами (генерация строго по схеме); structured output; diffusion с guidance = генерация под ограничениями; синтетические данные/аугментация = procgen для обучения.

Бэкенд: разрешение зависимостей (npm/cargo/apt) = constraint solving; типичный источник «версионного ада».

Принцип: «генерация = рандом, зажатый правилами»; где «собери валидное целое из кусков с ограничениями» — там CSP.

🏠 Лаба — коллапс вживую
Интерактивная лаба без кода: смотри, как сетка из суперпозиций схлопывается тайл за тайлом — жёлтая рамка отмечает клетку минимальной энтропии, после выбора волна propagate срезает варианты у соседей. Шагай поштучно, включай показ энтропии, ставь якоря пальцем и лови противоречие. Открыть лабу →
Лучший момент: пройди по «Шаг» и проследи, как один коллапс решает целую полосу соседей; потом поставь несовместимые якоря и поймай рестарт.
🔧 Запусти и поковыряй — на домашнем компе
Во что поиграть и что заметить — выше (🕹). Здесь — для тех, кто хочет влезть в сам алгоритм:
🔧 Поковырять (debug) ~3 ч, Python
Рабочий wfc.py (simple-tile: extract_adjacency, propagate, weighted collapse, anchoring) — запускается как есть. Подбрось в него лог «кто кого схлопнул» и смотри порядок observe / propagate в консоли. Модификации по нарастанию: добавь тайл-гору с редким весом (участишь противоречия), затем backtracking вместо рестарта (полнота вместо «попробуй заново»), затем overlapping-режим — правила из картинки-образца, а не руками. Папка labs/lab-05-wfc-terrain/.
🧪 Потестить (глазами QA генерации) ~20 мин
Валидный ≠ интересный ≠ проходимый. Прогони генератор сотню раз и проверяй авто-чеком: связность (flood-fill / A* от входа к выходу), долю тупиков, «скучность» (однородные простыни одного тайла), частоту противоречий. Найди тайлсет/веса, на которых WFC начинает тупить (подобрался к фазовому переходу SAT/UNSAT) — это и есть граница «рыхлого» набора.
Чеклист: увидел порядок observe→propagate в логе; заменил рестарт на backtracking; нашёл веса, на которых растёт число противоречий; прогнал авто-чек связности.
Связи
основа
Pathfinding — сгенерированный уровень обязан быть проходимым: после WFC часто гоняют flood-fill/A*, чтобы проверить связность.
контраст
Классика vs ML — PCG-спектр: от чистых правил (WFC, BSP) до ML-аугментации (GAN-уровни).
дальше
LLM-NPC — та же идея «генерация по ограничениям», но ограничение там — persona и схема действий.
Вопросы пытливого ума
«Минимальная энтропия» — это эвристика MRV из CSP?
Да. При равных весах энтропия Шеннона монотонна по числу вариантов, так что «минимум энтропии» = «минимум оставшихся значений» (MRV) — самая зажатая переменная первой. Веса тайлов лишь добавляют частотное смещение. WFC переоткрыл классическую CSP-эвристику под красивым именем.
Если propagate = AC-3, почему он не гарантирует решение?
Дуговая согласованность локальна: убирает значения без поддержки на отдельных рёбрах. Глобальная совместимость требует k-согласованности/поиска. AC-3 корректна (не удалит нужного), но неполна (может оставить домены, для которых глобального решения нет). Отсюда противоречия в WFC без бэктрекинга — это не баг, а предел метода.
WFC наследует NP-полноту замощения — почему он тогда мгновенный в играх?
Игровые тайлсеты «рыхлые»: валидных конфигураций экспоненциально много, и жадная случайная сборка почти всегда попадает в одну — это далеко от фазового перехода SAT/UNSAT, где задачи реально тяжелы. Плюс рестарт дёшев. Дай WFC «жёсткий» тайлсет на грани разрешимости — и он затупит ровно как NP-солвер.
Чем overlapping-вариант вычислительно дороже simple-tile?
Simple-tile берёт смежности готовыми правилами (ребро тайл↔тайл). Overlapping извлекает все N×N-паттерны из образца и считает совместимыми согласованно перекрывающиеся — число «тайлов»-паттернов взрывается, домены больше, propagate тяжелее, противоречий больше. Мощнее (учится у картинки), но капризнее и медленнее.
Это вообще «волновая функция»?
Нет, имя — метафора. Никакой квантовой механики: constraint propagation с рандомизированным выбором, родственник AC-3 и судоку-солверов. «Суперпозиция → коллапс» удачна как интуиция, но алгоритмически это CSP.
Что почитать