Wave Function Collapse для процедурної генерації

1. Основна ідея — квантова метафора, класичний алгоритм

WFC запозичує назву з квантової механіки, але сам алгоритм — це суто класична задача задоволення обмежень. Кожна клітинка вихідної сітки починається в суперпозиції усіх типів тайлів, які потенційно можуть у ній опинитися. Алгоритм постійно обирає клітинку з найменшою невизначеністю, "згортає" її до одного конкретного тайла, а потім поширює це рішення на сусідів, видаляючи будь-який тайл, що більше несумісний. Так триває, доки кожна клітинка не міститиме рівно один тайл — хвиля повністю згорнулася в узгоджений класичний результат.

Техніку запропонував Максим Гумін 2016 року як опенсорсний проєкт, і відтоді вона стала опорним інструментом процедурної генерації рівнів у виданих іграх (Bad North, Caves of Qud, Townscaper), бо дає локально узгоджену структуру — стіни сходяться, дороги з'єднуються, ріки течуть безперервно — і при цьому кожен запуск генерує іншу розкладку.

2. Клітинки, суперпозиція та домени

Формально вихід — це сітка клітинок C₁ … Cₙ. Кожна клітинка має домен D(Cᵢ) — множину тайлів, які ще дозволені в цій позиції. До будь-якого згортання кожен домен дорівнює повному алфавіту тайлів T:

Це точно структура задачі задоволення обмежень (CSP): змінні — клітинки, значення — мітки тайлів, обмеження — попарна сумісність суміжності між сусідніми клітинками. WFC, по суті, є розв'язувачем CSP зі специфічною евристикою впорядкування змінних (мінімум залишкових значень, зважений за частотою) і специфічним алгоритмом поширення (арк-консистентність), загорнутим у предметно-специфічну термінологію.

3. Витягнення правил суміжності зі зразка

Замість того щоб вручну писати "трава може сусідити з піском" для кожної пари тайлів, "проста тайлова модель" WFC сканує зразкову карту (або вручну намальований набір тайлів із крайовими сокетами) і фіксує, який тайл фактично торкався якого, у якому напрямку, у цьому зразку. Результат — відношення сумісності:

Поширений спосіб скоротити роботу для вручну складених наборів тайлів — крайові сокети: позначити кожен з чотирьох країв тайла символом (наприклад, "трава", "трава-дзеркало", "стежка"), і два тайли сумісні через край лише тоді, коли символи сокетів збігаються (з урахуванням горизонтальної симетрії-дзеркала). Це прибирає потребу у зразковому зображенні взагалі — автор набору тайлів неявно декларує суміжність через мітки країв.

4. Вибір наступної клітинки — ентропія Шеннона

На кожному кроці WFC має вирішити, яку не згорнуту клітинку розв'язувати наступною. Вибір клітинки з найнижчою ентропією Шеннона — найменшою залишковою невизначеністю — зазвичай дає менше протиріч, ніж випадковий вибір, бо алгоритм спершу фіксує найбільш обмежені частини сітки — та сама інтуїція, що лежить в основі евристик мінімуму залишкових значень у розв'язувачах судоку.

Коли цільову клітинку обрано, WFC згортає її, вибираючи один тайл із D(Cᵢ) з імовірністю, пропорційною w(t) — тому тайли, які були поширеними у вихідному зразку, залишаються поширеними і в згенерованому результаті, а не просто структурно допустимими.

5. Поширення обмежень (у стилі AC-3)

Згортання однієї клітинки до одного тайла робить недійсними деякі можливості в її сусідів, що своєю чергою робить недійсними можливості в їхніх сусідів, і так далі. WFC поширює ці виключення за допомогою алгоритму робочого списку, майже ідентичного класичному алгоритму арк-консистентності AC-3 з теорії CSP:

Оскільки зміна в одній клітинці може каскадно поширитися як завгодно далеко — згортання в кутку може врешті відсіяти тайли на протилежному боці великого рівня — поширення повинно досягти фіксованої точки, перш ніж алгоритм обере наступну клітинку для згортання. Саме цей крок надає WFC фірмового вигляду: локально узгоджену глобальну структуру, що виникає з суто локальних правил.

6. Протиріччя та відкат

Жадібне згортання за мінімумом ентропії не гарантує існування розв'язку — домен може звузитися до порожньої множини (протиріччя) навіть при цілком коректному наборі правил, особливо на невеликих сітках або з розрідженими даними суміжності. Промислові реалізації розв'язують це одним з трьох способів:

• Перезапуск з нуля: найпростіший і найпоширеніший підхід — заново згенерувати з новим випадковим сідом. Дешево, бо запуски WFC зазвичай швидкі (мілісекунди — низькі секунди для сіток ігрового масштабу).
• Відкат (backtracking): зберігати знімок стану доменів перед кожним згортанням; при протиріччі відкочуватися до останнього знімка й пробувати інший вибір тайла. Гарантує розв'язок, якщо він існує, але додає витрати на облік.
• Послаблення обмежень: ослабити жорстке правило (наприклад, дозволити рідкісний "заповнювальний" тайл будь-де), щоб протиріччя стали структурно неможливими, ціною випадкових візуальних дивностей.

7. Модель перекриття — синтез текстур

"Проста тайлова модель" вище потребує вручну складеного набору тайлів. Модель перекриття натомість вчиться безпосередньо з одного зображення, ковзаючи вікном N×N (типово N = 2 або 3) по вихідному зображенню й розглядаючи кожен відмінний патерн вікна як "тайл". Два патерни сумісні за суміжністю в заданому напрямку, якщо їхня область перекриття збігається піксель у піксель:

Оскільки патерни перекриваються з сусідами на N−1 пікселів, машинерія арк-консистентності з розділу 5 застосовується без жодних змін — змінилося лише визначення "тайла" й "суміжності": від кураторської таблиці правил до порівняння піксельних вікон. Саме тому те саме ядро WFC може генерувати як чіткі тайлові розкладки підземель, так і органічні, ніби намальовані вручну текстури з прикладу 20×20 пікселів без жодних змін коду, окрім парсера вхідних даних.

8. Мінімальна реалізація WFC

// WFC простої тайлової моделі — сітка клітинок, кожна містить Set дозволених id тайлів
class WFC {
  constructor(width, height, tiles, adjacency, weights) {
    this.w = width;
    this.h = height;
    this.tiles = tiles;              // масив id тайлів
    this.adjacency = adjacency;      // adjacency(a, b, dir) -> bool
    this.weights = weights;          // id тайла -> ваговий коефіцієнт частоти
    this.grid = new Array(width * height)
      .fill(null)
      .map(() => new Set(tiles));
    this.dirs = [[0,-1],[1,0],[0,1],[-1,0]]; // N,E,S,W
  }

  idx(x, y) { return y * this.w + x; }

  entropy(domain) {
    const total = [...domain].reduce((s, t) => s + this.weights[t], 0);
    let h = 0;
    for (const t of domain) {
      const p = this.weights[t] / total;
      h -= p * Math.log2(p);
    }
    return h + Math.random() * 1e-6; // шум для розбиття нічиїх
  }

  lowestEntropyCell() {
    let best = -1, bestH = Infinity;
    for (let i = 0; i < this.grid.length; i++) {
      const d = this.grid[i];
      if (d.size > 1) {
        const h = this.entropy(d);
        if (h < bestH) { bestH = h; best = i; }
      }
    }
    return best;
  }

  collapse(i) {
    const domain = [...this.grid[i]];
    const total = domain.reduce((s, t) => s + this.weights[t], 0);
    let r = Math.random() * total;
    let chosen = domain[0];
    for (const t of domain) {
      r -= this.weights[t];
      if (r <= 0) { chosen = t; break; }
    }
    this.grid[i] = new Set([chosen]);
  }

  propagate(start) {
    const queue = [start];
    while (queue.length) {
      const i = queue.pop();
      const x = i % this.w, y = Math.floor(i / this.w);
      for (let d = 0; d < 4; d++) {
        const nx = x + this.dirs[d][0], ny = y + this.dirs[d][1];
        if (nx < 0 || ny < 0 || nx >= this.w || ny >= this.h) continue;
        const ni = this.idx(nx, ny);
        let changed = false;
        for (const t of [...this.grid[ni]]) {
          const ok = [...this.grid[i]].some(t2 => this.adjacency(t2, t, d));
          if (!ok) { this.grid[ni].delete(t); changed = true; }
        }
        if (this.grid[ni].size === 0) throw new Error('contradiction');
        if (changed) queue.push(ni);
      }
    }
  }

  run() {
    while (true) {
      const i = this.lowestEntropyCell();
      if (i === -1) return this.grid.map(d => [...d][0]); // повністю згорнуто
      this.collapse(i);
      this.propagate(i);
    }
  }
}

9. Практичні поради для ігрових рівнів

WFC не замінює вручну спроєктовані рівні — його найкраще застосовувати там, де локальна узгодженість плюс глобальна різноманітність важливіші за вручну розставлені сюжетні акценти: фонові міські пейзажі, заповнювальні поверхи підземель, текстури рельєфу, або як швидкий чорновий варіант, який дизайнер потім доопрацьовує вручну. У поєднанні з простим постпроходом (видалення недосяжних кімнат, забезпечення шляху між спавном і ціллю) це дає рівні, що відчуваються авторськими, майже нічого не коштуючи у генерації.