Колапс хвильової функції — процедурна генерація, керована обмеженнями

1. Метафора суперпозиції

Уявіть сітку, де кожна клітинка може бути будь-яким із T типів плиток. Спочатку кожна клітинка має всі T плиток у своїй «суперпозиції» (множина ще можливих плиток). Мета — призначити рівно одну плитку кожній клітинці так, щоб усі обмеження суміжності задовольнялися.

2. Спостереження, кероване ентропією

Яку клітинку колапсувати наступною? Завжди обирайте клітинку з найнижчою ентропією Шеннона (ще не сколапсовану). Низька ентропія означає, що в неї менше можливостей — обираючи її першою, ми мінімізуємо суперечності:

3. Поширення обмежень (AC-3)

Після колапсу клітинки її сусіди можуть більше не підтримувати певні плитки. Ми поширюємо, видаляючи з сусідів плитки, які не мають дійсної сусідньої плитки для парування — подібно до алгоритму дугової узгодженості AC-3 у розв’язанні CSP:

4. Відкат при суперечності

Коли поширення спорожнює можливості клітинки, поточне спостереження несумісне з обмеженнями. Класичний підхід WFC перезапускається з нуля; просунуті версії реалізують хронологічний відкат або відкат, керований залежностями:

5. Перекривна модель проти плиткової

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

7. Реалізація на JavaScript

// Мінімальна плиткова модель WFC
class WFC {
  constructor(W, H, tiles, rules, weights) {
    // rules[dir][tileA][tileB] = bool; напрямки: 0=N 1=E 2=S 3=W
    this.W = W; this.H = H;
    this.T = tiles.length;
    this.rules = rules;
    this.weights = weights ?? new Array(this.T).fill(1);
    this._init();
  }

  _init() {
    // Кожна клітинка починається з усіма можливими плитками
    this.grid = Array.from({length: this.H}, () =>
      Array.from({length: this.W}, () =>
        new Set(Array.from({length: this.T}, (_,i) => i))
      )
    );
  }

  entropy(x, y) {
    const poss = this.grid[y][x];
    if (poss.size === 1) return 0;
    const total = [...poss].reduce((s,t) => s + this.weights[t], 0);
    return [...poss].reduce((s,t) => {
      const p = this.weights[t] / total;
      return s - p * Math.log2(p);
    }, 0);
  }

  observe() {
    // Знаходимо незколапсовану клітинку з мінімальною ентропією
    let minH = Infinity, cx = -1, cy = -1;
    for (let y = 0; y < this.H; y++) {
      for (let x = 0; x < this.W; x++) {
        const sz = this.grid[y][x].size;
        if (sz <= 1) continue;
        const h = this.entropy(x, y);
        if (h < minH) { minH = h; cx = x; cy = y; }
      }
    }
    if (cx === -1) return 'done';

    // Зважений випадковий вибір плитки
    const poss = [...this.grid[cy][cx]];
    const total = poss.reduce((s,t) => s + this.weights[t], 0);
    let r = Math.random() * total;
    const chosen = poss.find(t => (r -= this.weights[t]) <= 0) ?? poss[poss.length-1];
    this.grid[cy][cx] = new Set([chosen]);
    return this.propagate(cx, cy);
  }

  propagate(startX, startY) {
    const queue = [[startX, startY]];
    const DX = [0,1,0,-1], DY = [-1,0,1,0];
    const OPP = [2,3,0,1);  // індекс протилежного напрямку
    while (queue.length) {
      const [cx,cy] = queue.shift();
      for (let d = 0; d < 4; d++) {
        const nx = cx+DX[d], ny = cy+DY[d];
        if (nx<0||ny<0||nx>=this.W||ny>=this.H) continue;
        const nbPoss = this.grid[ny][nx];
        const before = nbPoss.size;
        for (const tNb of [...nbPoss]) {
          // Видаляємо tNb, якщо жодна плитка в поточній клітинці його не підтримує
          const ok = [...this.grid[cy][cx]].some(tC => this.rules[d][tC][tNb]);
          if (!ok) nbPoss.delete(tNb);
        }
        if (nbPoss.size === 0) return 'contradiction';
        if (nbPoss.size < before) queue.push([nx, ny]);
      }
    }
    return 'ok';
  }

  run(maxRestarts = 50) {
    for (let attempt = 0; attempt < maxRestarts; attempt++) {
      this._init();
      let status;
      do { status = this.observe(); } while (status === 'ok');
      if (status === 'done') return true;
    }
    return false; // невдача
  }

  result() {
    return this.grid.map(row => row.map(s => [...s][0]));
  }
}

8. Застосування та розширення

Нещодавні розширення включають WFC, кероване обмеженнями (користувач малює клітинки «має бути водою» / «має бути стіною» перед генерацією), ієрархічний WFC (спершу генерувати план кімнат, потім заповнювати кожну кімнату) та анімований WFC (генерувати плиткові карти, що також правильно анімуються, розширюючи правила на часовий вимір).