웨이브 함수 붕괴

Wave function collapse

타일 몇 개와 "어떤 타일이 옆에 올 수 있는가"라는 규칙만으로 국소적으로 그럴듯한 큰 패턴을 채워나가는 알고리즘. Maxim Gumin이 2016년 공개했습니다.

다른 이름: WFCConstraint-based tiling
···
js
const c = document.createElement('canvas');
document.body.appendChild(c);
c.style.width = '100%'; c.style.height = '100%';
const ctx = c.getContext('2d');
const cs = getComputedStyle(document.documentElement);
const ACCENT = cs.getPropertyValue('--accent').trim() || '#5b5bf7';
// 타일 소켓: [N,E,S,W] 1=연결됨 0=끊김
const TILES = [[0, 0, 0, 0], [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 1]];
let w, h, cols, rows, SIZE = 42, cellsGrid = [], order = [], revealed = 0, genStart = 0;
function collapse() {
  const n = cols * rows;
  cellsGrid = new Array(n).fill(-1);
  order = [...Array(n).keys()];
  for (let i = order.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [order[i], order[j]] = [order[j], order[i]]; }
  for (const idx of order) {
    const x = idx % cols, y = (idx / cols) | 0;
    let candidates = TILES.map((_, ti) => ti);
    const nb = [[x, y - 1, 2, 0], [x + 1, y, 3, 1], [x, y + 1, 0, 2], [x - 1, y, 1, 3]];
    for (const [nx, ny, mySide, theirSide] of nb) {
      if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue;
      const other = cellsGrid[ny * cols + nx];
      if (other < 0) continue;
      candidates = candidates.filter((ti) => TILES[ti][mySide] === TILES[other][theirSide]);
    }
    cellsGrid[idx] = candidates.length ? candidates[Math.floor(Math.random() * candidates.length)] : 0;
  }
  revealed = 0;
  genStart = 0;
}
function resize() {
  const dpr = Math.min(devicePixelRatio || 1, 2);
  w = innerWidth; h = innerHeight;
  c.width = w * dpr; c.height = h * dpr;
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  cols = Math.max(4, Math.floor(w / SIZE)); rows = Math.max(3, Math.floor(h / SIZE));
  collapse();
}
addEventListener('resize', resize);
resize();

function drawTile(cx, cy, sockets) {
  ctx.strokeStyle = ACCENT; ctx.lineWidth = 5; ctx.lineCap = 'round';
  const half = SIZE / 2;
  const dirs = [[0, -half], [half, 0], [0, half], [-half, 0]];
  for (let i = 0; i < 4; i++) if (sockets[i]) { ctx.beginPath(); ctx.moveTo(cx, cy); ctx.lineTo(cx + dirs[i][0], cy + dirs[i][1]); ctx.stroke(); }
  ctx.fillStyle = ACCENT; ctx.beginPath(); ctx.arc(cx, cy, 3, 0, 7); ctx.fill();
}
function draw() {
  ctx.fillStyle = '#0d0d12'; ctx.fillRect(0, 0, w, h);
  for (let i = 0; i < revealed; i++) {
    const idx = order[i], x = idx % cols, y = (idx / cols) | 0;
    drawTile(x * SIZE + SIZE / 2, y * SIZE + SIZE / 2, TILES[cellsGrid[idx]]);
  }
}
// 칸 수와 무관하게 항상 같은 시간 안에 다 드러나도록 경과 시간 비율로 reveal 한다
const REVEAL_MS = 900, HOLD_MS = 2200;
draw();
(function loop(t) {
  if (!genStart) genStart = t;
  const elapsed = t - genStart;
  revealed = Math.min(order.length, Math.floor(order.length * Math.min(1, elapsed / REVEAL_MS)));
  if (elapsed > REVEAL_MS + HOLD_MS) collapse();
  draw();
  requestAnimationFrame(loop);
})(0);

이름은 양자역학의 "관측하기 전까지 여러 상태가 중첩돼 있다가, 관측하는 순간 하나로 붕괴한다"는 비유에서 왔습니다. 각 칸은 처음엔 "가능한 타일 전부"를 동시에 품고 있는 상태로 시작합니다. 한 칸을 골라 그중 하나로 확정(붕괴)하면, 그 타일의 가장자리와 맞물릴 수 없는 타일들이 바로 옆 칸의 가능성 목록에서 제거됩니다 — 이 제약이 다시 그 옆 칸으로 계속 전파됩니다. 이 데모는 파이프처럼 이어지거나 끊기는 8가지 타일(빈칸·직선·모서리·교차로 소켓 조합)만으로 이 과정을 보여줍니다.

핵심은 각 타일에 정의된 "이 방향 가장자리는 연결됨/끊김" 같은 단순한 인접 규칙뿐인데도, 전체적으로는 미로나 회로처럼 국소적으로 이치에 맞게 이어지는 큰 패턴이 나온다는 점입니다. Gumin의 원작은 완전한 알고리즘(최소 엔트로피 선택 + 역추적)을 구현했고, 이 데모는 개념을 보여주기 위해 칸을 무작위 순서로 채우는 단순화된 버전을 씁니다.

타일 기반 게임 맵 생성, 패턴이 자연스럽게 이어지는 텍스처, 절차적 레벨 디자인에 널리 쓰입니다.

언제 쓰나

타일 기반 게임 맵·레벨을 절차적으로 생성할 때, 파이프·회로처럼 이어져야 하는 패턴에. 여기 구현은 단순화된 버전이라 실제 프로젝트에는 원작 알고리즘(역추적 포함)을 쓰세요.