shigureni.dev

制約で繋ぐ — タイル

距離でなく隣との制約で詰める。同じ絵柄のタイルを向きだけ変えて1セルに1枚ずつ敷き、辺で線が繋がるように置くと、タイル単体には無い大きな曲線網が盤面に出る。Truchet タイル。

Truchet タイルは、Sébastien Truchet が 1704 年に対角線で二分した正方形タイルの並べ方を論じたのが始まり。一枚の絵柄を向きだけ変えて敷き詰める。各タイルが辺の中点で線を受け渡すように描いてあると、隣どうしで線が継がって、一枚には無い大域的な曲線網ができる。向きの決め方をランダムにするか規則にするかで模様が変わる。

各マスに2つの向きのどちらかを置く。タイルは向かい合う角を四分円で結ぶだけ。向き 0 は左上と右下の角に四分円、向き 1 は右上と左下。隣り合うマスの弧の端は辺の中点で合うので、向きが揃わなくても線が継がる。各マスの向きを毎フレーム数枚だけコイン投げで裏返している。一マス変わると、そこを通る曲線の繋ぎ方が変わる。

const drawCell = (c, x, y, cell, r, o) => {
  c.fillStyle = colors.paper
  c.fillRect(x, y, cell + 1, cell + 1)
  c.strokeStyle = colors.tint(28)
  c.lineWidth = 2
  if (o === 0) {
    c.beginPath()
    c.arc(x, y, r, 0, Math.PI / 2)
    c.stroke()
    c.beginPath()
    c.arc(x + cell, y + cell, r, Math.PI, Math.PI * 1.5)
    c.stroke()
  } else {
    c.beginPath()
    c.arc(x + cell, y, r, Math.PI / 2, Math.PI)
    c.stroke()
    c.beginPath()
    c.arc(x, y + cell, r, Math.PI * 1.5, Math.PI * 2)
    c.stroke()
  }
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cell = w / 14
  const cols = Math.ceil(w / cell)
  const rows = Math.ceil(h / cell)
  const r = cell / 2
  const grid = Array.from({ length: cols * rows }, () => (Math.random() < 0.5 ? 0 : 1))

c.fillStyle = colors.paper
  c.fillRect(0, 0, w, h)
  for (let gy = 0; gy < rows; gy++) {
    for (let gx = 0; gx < cols; gx++) {
      drawCell(c, gx * cell, gy * cell, cell, r, grid[gy * cols + gx])
    }
  }

return () => {
    for (let k = 0; k < 3; k++) {
      const gx = Math.floor(Math.random() * cols)
      const gy = Math.floor(Math.random() * rows)
      const i = gy * cols + gx
      grid[i] = grid[i] === 0 ? 1 : 0
      drawCell(c, gx * cell, gy * cell, cell, r, grid[i])
    }
  }
}

向きが2通りしかなくても、隣どうしで弧が継がって迷路のような連続曲線になる。一マス裏返すと、その曲線の経路が組み替わる。

Truchet は向きが自由で、どう置いても線は継がる。辺に色をつけて隣り合う辺の色が一致しないと置けないという制約を足すと、どこに何を置けるかが互いに縛り合う。Wang タイル。

Wang タイルは Hao Wang が 1961 年に考案した、四辺に色を持つ正方形タイル。回転・反転は禁じ、隣り合う辺の色が一致する組だけ並べられる。あるタイル集合が平面を敷き詰められるかは決定不能で、周期的には敷けないのに非周期には敷ける集合（aperiodic set）が存在する。色一致の制約を満たすよう端から置いていき、合うタイルが無ければ手前へ戻す（バックトラック）。

各マスのタイルは四辺の色 n e s w（上右下左）を持つ。左隣の右辺の色 e が自分の左辺 w と一致し、上隣の下辺の色 s が自分の上辺 n と一致するときだけ置ける。端から順に、ランダムな色の組を作っては fits で判定し、合えば置いて次へ、何度試しても合わなければ一つ前へ戻ってやり直す。盤が埋まったら描く。辺の色は辺上の点の位置に写し、向かい合う辺の点を曲線で結ぶ。

const fits = (grid, cols, i, tile) => {
  const x = i % cols
  const y = Math.floor(i / cols)
  if (x > 0) {
    const left = grid[i - 1]
    if (left && left.e !== tile.w) return false
  }
  if (y > 0) {
    const up = grid[i - cols]
    if (up && up.s !== tile.n) return false
  }
  return true
}

const build = (cols, rows, palette) => {
  const total = cols * rows
  const grid = new Array(total)
  const tries = new Array(total).fill(0)
  let i = 0
  let guard = 0
  while (i < total && guard < 60000) {
    guard++
    let placed = false
    while (tries[i] < 30) {
      tries[i]++
      const tile = {
        n: Math.floor(Math.random() * palette),
        e: Math.floor(Math.random() * palette),
        s: Math.floor(Math.random() * palette),
        w: Math.floor(Math.random() * palette),
      }
      if (fits(grid, cols, i, tile)) {
        grid[i] = tile
        placed = true
        break
      }
    }
    if (placed) {
      i++
    } else {
      tries[i] = 0
      i = Math.max(0, i - 1)
    }
  }
  for (let k = 0; k < total; k++) {
    if (!grid[k]) grid[k] = { n: 0, e: 0, s: 0, w: 0 }
  }
  return grid
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cell = w / 16
  const cols = Math.ceil(w / cell)
  const rows = Math.ceil(h / cell)
  const palette = 3
  const mid = (color) => (color + 1) / (palette + 1)
  let grid = build(cols, rows, palette)
  let timer = 0

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

return () => {
    timer++
    if (timer >= 90) {
      timer = 0
      grid = build(cols, rows, palette)
    }

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

for (let i = 0; i < cols * rows; i++) {
      const tile = grid[i]
      const ox = (i % cols) * cell
      const oy = Math.floor(i / cols) * cell
      const cx = ox + cell / 2
      const cy = oy + cell / 2
      const nx = ox + mid(tile.n) * cell
      const sx = ox + mid(tile.s) * cell
      const ey = oy + mid(tile.e) * cell
      const wy = oy + mid(tile.w) * cell
      const flip = (tile.n + tile.e + tile.s + tile.w) % 2 === 0
      c.strokeStyle = flip ? colors.tint(28) : colors.tint(58)
      c.beginPath()
      if (flip) {
        c.moveTo(nx, oy)
        c.quadraticCurveTo(cx, cy, ox, wy)
        c.moveTo(ox + cell, ey)
        c.quadraticCurveTo(cx, cy, sx, oy + cell)
      } else {
        c.moveTo(nx, oy)
        c.quadraticCurveTo(cx, cy, ox + cell, ey)
        c.moveTo(ox, wy)
        c.quadraticCurveTo(cx, cy, sx, oy + cell)
      }
      c.stroke()
    }
  }
}

色一致の制約があるので、隣のマスが先に置いた色によって、自分に置けるタイルが絞られる。端から埋めていって行き詰まると i が戻り、前のマスを別の色で置き直す。色の数 palette を増やすと制約が緩んで詰まりにくくなり、減らすと戻りが増える。

その制約を最後まで詰めると WFC（波動関数の崩壊）になる。Wang は一マスずつ確定させて、駄目なら戻すだけだった。WFC は各マスにまだ置ける候補ぜんぶを持たせ、一つに確定するたびに、その制約を隣へ、また隣へ伝播させる。置けなくなった候補が先回りで消えるので、無駄な試行が減る。

WFC（Wave Function Collapse）は Maxim Gumin が 2016 年に公開したタイル配置アルゴリズム。各マスを重ね合わせ（置ける候補の集合）として持ち、エントロピー（候補数）が最小のマスを一つに確定（collapse）させ、隣接制約を波及（propagate）させて他マスの候補を削る。これを全マス確定まで繰り返す。量子力学の波動関数の収縮になぞらえた名で、制約充足問題（CSP）のアーク整合性を貪欲に解いている。

各マスを16通りの向き（上下左右4辺それぞれに線が伸びるか否かの組）の候補集合とし、ビットで持つ。collapse は候補数が最小のマスを選んで一つに絞り、そこから制約を伝播する。あるマスの線が右へ伸びるなら、右隣は左から線を受ける向きしか残せない。隣の候補が削れたらさらにその隣へ、と作業リストで波及させる。候補が空になったマスが出たら矛盾なので盤をリセットする。

const FULL = 0xffff
const DIRS = [
  { dx: 0, dy: -1, mi: 0, ti: 2 },
  { dx: 1, dy: 0, mi: 1, ti: 3 },
  { dx: 0, dy: 1, mi: 2, ti: 0 },
  { dx: -1, dy: 0, mi: 3, ti: 1 },
]
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
}

const collapse = (cells, cols, rows) => {
  let best = -1
  let bestCount = 99
  for (let i = 0; i < cells.length; i++) {
    const count = popcount(cells[i])
    if (count > 1 && count < bestCount) {
      bestCount = count
      best = i
    }
  }
  if (best < 0) return true

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)]

const work = [best]
  let guard = 0
  while (work.length > 0 && guard++ < 6000) {
    const idx = work.pop()
    const x = idx % cols
    const y = Math.floor(idx / cols)
    const mine = cells[idx]
    for (const d of DIRS) {
      const nx = x + d.dx
      const ny = y + d.dy
      if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue
      const ni = ny * cols + nx
      let allowed = 0
      if (mine & MASKS[d.mi]) allowed |= MASKS[d.ti]
      if (mine & ~MASKS[d.mi]) allowed |= FULL & ~MASKS[d.ti]
      const next = cells[ni] & allowed
      if (next === 0) return false
      if (next !== cells[ni]) {
        cells[ni] = next
        work.push(ni)
      }
    }
  }
  return true
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cell = w / 16
  const cols = Math.ceil(w / cell)
  const rows = Math.ceil(h / cell)
  const half = cell / 2
  const cells = new Array(cols * rows).fill(FULL)

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

return () => {
    const settled = cells.every((v) => popcount(v) === 1)
    if (settled) cells.fill(FULL)
    else {
      for (let b = 0; b < 12; b++) {
        if (!collapse(cells, cols, rows)) {
          cells.fill(FULL)
          break
        }
      }
    }

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineWidth = 2
    c.lineCap = "round"
    c.strokeStyle = colors.tint(28)

for (let i = 0; i < cells.length; i++) {
      const v = cells[i]
      if (popcount(v) !== 1) continue
      const cx = (i % cols) * cell + half
      const cy = Math.floor(i / cols) * cell + half
      c.beginPath()
      for (const d of DIRS) {
        if (v & (1 << d.mi)) {
          c.moveTo(cx, cy)
          c.lineTo(cx + d.dx * half, cy + d.dy * half)
        }
      }
      c.stroke()
    }
  }
}

候補数が最小のマスから確定するので、迷いの少ない所が先に決まり、その制約が周りの候補を削る。確定済みのマスが盤を埋めていって、全部が一つに決まると盤がリセットされて次の生成が始まる。線が伸びる向きが隣どうしで噛み合い、繋がった経路になる。

棄却サンプリングが距離で弾く手だったのと同じで、WFC は制約で候補を弾く。詰めるという行為が、距離の制約から隣接の制約へ姿を変えて、同じ問いを解いている。