shigureni.dev

制約で敷き詰める — WFC

タイルの一片一片に「この辺の右にはこの辺しか来られない」という隣接の制約をつけて、矛盾しないように一マスずつ確定させていく。各マスは最初すべてのタイルの可能性を重ね持っていて、いちばん候補の少ないマスから一枚に確定し、その確定が隣の候補を削り、削れた隣がさらにその隣を削る、と制約が伝播する。

Wave Function Collapse は、量子状態の重ね合わせと観測の比喩で組まれた制約充足。各セルが取りうるタイルの集合を持つ、その集合が波（重ね合わせ）。観測＝候補が最小のセルを一枚に確定すること、伝播＝その確定で破れた隣接制約を波及させて他セルの候補を削ること。エントロピー最小（候補数が最小）のセルから観測すると矛盾が起きにくい。Maxim Gumin が 2016 年に公開し、サンプル画像から隣接ルールを学べる版がレベル生成で広く使われる。

タイルは四辺それぞれが「繋がる／繋がらない」の二値を持つ配管片。上右下左の四ビットで状態を表すと、繋ぎ方は 0（無)から 15（十字)まで 16 通りある。隣接の約束はひとつ——あるタイルが右辺で繋がるなら、右隣は左辺で繋がっていなければならない。辺の有無が合うペアだけが隣り合える。

const DIRS = [
  { dx: 0, dy: -1, mine: 0, theirs: 2 },
  { dx: 1, dy: 0, mine: 1, theirs: 3 },
  { dx: 0, dy: 1, mine: 2, theirs: 0 },
  { dx: -1, dy: 0, mine: 3, theirs: 1 },
]

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const nx = 4
  const ny = 4
  const cellW = w / nx
  const cellH = h / ny
  let spin = 0

return () => {
    spin += 0.02

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineCap = "round"

for (let gy = 0; gy < ny; gy++) {
      for (let gx = 0; gx < nx; gx++) {
        const bits = gy * nx + gx
        const cx = gx * cellW + cellW / 2
        const cy = gy * cellH + cellH / 2
        const armX = cellW / 2
        const armY = cellH / 2
        const lit = (Math.sin(spin + bits) + 1) * 0.5
        c.lineWidth = Math.max(2, Math.min(cellW, cellH) / 8)
        c.strokeStyle = colors.tint(40 + lit * 60)
        c.fillStyle = colors.tint(30)
        c.beginPath()
        for (const d of DIRS) {
          if (bits & (1 << d.mine)) {
            c.moveTo(cx, cy)
            c.lineTo(cx + d.dx * armX, cy + d.dy * armY)
          }
        }
        c.stroke()
        const dot = Math.min(cellW, cellH) * 0.12
        c.fillRect(cx - dot, cy - dot, dot * 2, dot * 2)
      }
    }
  }
}

16 枚すべてが盤に並ぶ。左上が四辺とも繋がらない孤立片、右下が四方へ伸びる十字。隣接の制約は辺ビットの一致で書ける。あるタイルが向き d の辺で繋がっているなら、その隣に置けるのは反対辺で繋がっているタイルだけ。繋がっていないなら、隣は反対辺も繋がっていないものだけ。下は十字（15）を真ん中に固定して、四方それぞれで「右隣に置けるタイル」を回しながら見せる。中央が辺で繋がっている向きには、隣も必ず辺を返す。

const DIRS = [
  { dx: 0, dy: -1, mine: 0, theirs: 2 },
  { dx: 1, dy: 0, mine: 1, theirs: 3 },
  { dx: 0, dy: 1, mine: 2, theirs: 0 },
  { dx: -1, dy: 0, mine: 3, theirs: 1 },
]

const drawTile = (c, cx, cy, h, bits) => {
  c.beginPath()
  for (const d of DIRS) {
    if (bits & (1 << d.mine)) {
      c.moveTo(cx, cy)
      c.lineTo(cx + d.dx * h, cy + d.dy * h)
    }
  }
  c.stroke()
  c.fillRect(cx - h * 0.12, cy - h * 0.12, h * 0.24, h * 0.24)
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cx = w / 2
  const cy = h / 2
  const arm = Math.min(w, h) * 0.2
  const center = 15
  let t = 0

return () => {
    t += 0.012

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineCap = "round"
    c.lineWidth = Math.max(2, arm / 6)

for (const d of DIRS) {
      // 中央が向き d の辺で繋がるか
      const linked = (center & (1 << d.mine)) !== 0
      // 隣は反対辺(theirs)を合わせたタイルだけが置ける
      const candidates = []
      for (let b = 0; b < 16; b++) {
        const back = (b & (1 << d.theirs)) !== 0
        if (back === linked) candidates.push(b)
      }
      const pick = candidates[Math.floor(t) % candidates.length]
      const nx = cx + d.dx * arm * 2
      const ny = cy + d.dy * arm * 2
      c.strokeStyle = colors.tint(80)
      c.fillStyle = colors.tint(40)
      drawTile(c, nx, ny, arm * 0.8, pick)
    }

c.strokeStyle = colors.tint(40)
    c.fillStyle = colors.tint(20)
    drawTile(c, cx, cy, arm, center)
  }
}

四方の隣がどう入れ替わっても、中央の辺が繋がる向きには隣も辺を返し、繋がらない向きには隣も辺を出さない。配管が途切れない。この一致だけを盤面全体で守らせると WFC になる。全マスを 16 ビットの候補集合 0xffff で初期化し、候補の少ないマスを一枚に確定（観測）して、隣接で潰せる候補を波及（伝播）させる。候補集合の AND だけで制約が伝わる。

const FULL = 0xffff

const DIRS = [
  { dx: 0, dy: -1, mine: 0, theirs: 2 },
  { dx: 1, dy: 0, mine: 1, theirs: 3 },
  { dx: 0, dy: 1, mine: 2, theirs: 0 },
  { dx: -1, dy: 0, mine: 3, theirs: 1 },
]

// 辺ビット b が立っているタイルだけを集めたマスク
const MASKS = [0, 1, 2, 3].map((bit) => {
  let m = 0
  for (let t = 0; t < 16; t++) if (t & (1 << bit)) m |= 1 << t
  return m
})

const popcount = (v) => {
  let count = 0
  for (let x = v; x; x &= x - 1) count++
  return count
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const NX = 20
  const NY = 16
  const cellW = w / NX
  const cellH = h / NY
  const cells = new Array(NX * NY).fill(FULL)

const reset = () => cells.fill(FULL)

const collapse = () => {
    // 候補が最小（>1）のマスを観測対象に選ぶ
    let best = -1
    let bestCount = 99
    for (let i = 0; i < cells.length; i++) {
      const count = popcount(cells[i])
      if (count > 1 && (count < bestCount || (count === bestCount && Math.random() < 0.3))) {
        bestCount = count
        best = i
      }
    }
    if (best < 0) return false

// 候補の中から一枚に確定
    const opts = []
    for (let t = 0; t < 16; t++) if (cells[best] & (1 << t)) opts.push(t)
    cells[best] = 1 << opts[Math.floor(Math.random() * opts.length)]

// 確定の影響を隣へ伝播。候補集合の AND で削る
    const work = [best]
    let guard = 0
    while (work.length > 0 && guard++ < 4000) {
      const idx = work.pop()
      const x = idx % NX
      const y = (idx / NX) | 0
      const mine = cells[idx]
      for (const d of DIRS) {
        const nx = x + d.dx
        const ny = y + d.dy
        if (nx < 0 || nx >= NX || ny < 0 || ny >= NY) continue
        const ni = ny * NX + nx
        let allowed = 0
        if (mine & MASKS[d.mine]) allowed |= MASKS[d.theirs]
        if (mine & ~MASKS[d.mine]) allowed |= FULL & ~MASKS[d.theirs]
        const next = cells[ni] & allowed
        if (next === 0) return false
        if (next !== cells[ni]) {
          cells[ni] = next
          work.push(ni)
        }
      }
    }
    return true
  }

c.fillStyle = colors.paper
  c.fillRect(0, 0, w, h)

return () => {
    if (cells.every((v) => popcount(v) === 1)) reset()
    else for (let step = 0; step < 4 && collapse(); step++) {}
    if (cells.some((v) => popcount(v) === 0)) reset()

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineCap = "round"
    c.lineWidth = Math.max(2, Math.min(cellW, cellH) / 6)
    const arm = Math.min(cellW, cellH) / 2

for (let i = 0; i < cells.length; i++) {
      const v = cells[i]
      const x = i % NX
      const y = (i / NX) | 0
      const cx = x * cellW + cellW / 2
      const cy = y * cellH + cellH / 2

if (popcount(v) === 1) {
        c.strokeStyle = colors.tint(40)
        c.beginPath()
        for (const d of DIRS) {
          if (v & (1 << d.mine)) {
            c.moveTo(cx, cy)
            c.lineTo(cx + d.dx * arm, cy + d.dy * arm)
          }
        }
        c.stroke()
        if (v !== 1) {
          c.fillStyle = colors.tint(20)
          c.fillRect(cx - arm * 0.1, cy - arm * 0.1, arm * 0.2, arm * 0.2)
        }
      } else {
        // まだ確定していないマスは候補の多さで明るく
        const count = popcount(v)
        c.fillStyle = colors.tintAlpha(200, 0.15 + (count / 16) * 0.3)
        c.fillRect(x * cellW, y * cellH, cellW + 1, cellH + 1)
      }
    }
  }
}

候補が少ないマスから確定し、確定が波及して隣の候補が潰れ、潰れた隣がまたその隣を削る。確定済みのマスは配管が引かれ、まだ迷っているマスは候補の多さで薄く塗られる。盤が全部確定すると、辺の約束を一つも破らない配管が画面いっぱいに繋がる。途中で候補がゼロになる矛盾に陥ったら盤をやり直す。Wang タイルの「辺の色を合わせて敷く」をバックトラックで解くのを、全マス同時に候補集合で進める版になる。