shigureni.dev

DFSで完全迷路を掘る

隙間なく壁で埋めた盤面を、細い通路だけで掘り抜くと迷路になる。各マスは上下左右の4枚の壁を持ち、最初は四方すべて閉じている。隣り合うマスの間の壁を一枚倒すと、その二マスがつながって通路になる。壁はマスごとに4ビットのフラグで持ち、一枚倒すたびに自分と相手の対応するビットを両方落とす。

深さ優先探索（DFS）で迷路を掘る手続き。再帰的バックトラッカ。いまいるマスから未訪問の隣をランダムに一つ選んで進み、間の壁を倒す。行き止まれば来た道をスタックで戻り、別の分岐を試す。全マスを一度ずつ訪れて止まると、どのマスからどのマスへも道がちょうど一本だけ、閉路がゼロの完全迷路になる。掘り跡が全域木を張るので、ループのない木構造になる。

二つのマスをつなぐのは壁ビットの操作だけ。下では左右に並んだ二マスの間の壁を、時間で倒したり立てたりしている。ビットが落ちている向きは壁を描かず、その辺が開いて通路になる。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cellW = w / 2
  const cellH = h
  const margin = Math.min(cellW, cellH) * 0.18
  let t = 0

const drawCell = (col, walls) => {
    const x0 = col * cellW + margin
    const y0 = margin
    const cw = cellW - margin * 2
    const ch = cellH - margin * 2
    const thick = margin * 0.5
    c.fillStyle = colors.tint(150)
    c.fillRect(x0, y0, cw, ch)
    c.fillStyle = colors.tint(20)
    if ((walls & 1) === 0) c.fillRect(x0, y0 - thick, cw, thick * 2)
    if ((walls & 2) === 0) c.fillRect(x0, y0 + ch - thick, cw, thick * 2)
    if ((walls & 4) === 0) c.fillRect(x0 - thick, y0, thick * 2, ch)
    if ((walls & 8) === 0) c.fillRect(x0 + cw - thick, y0, thick * 2, ch)
  }

return () => {
    t += 0.02
    c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)

const open = Math.sin(t) > 0
    let left = 0b1111
    let right = 0b1111
    if (open) {
      left = left & ~8
      right = right & ~4
    }
    drawCell(0, left)
    drawCell(1, right)
  }
}

壁が立っている間は二マスが箱で仕切られ、ビットが落ちると間の辺が消えて一本の通路でつながる。右マスの左壁（ビット 4）と左マスの右壁（ビット 8）を同時に倒すので、片側だけ開いて段差ができることがない。

この壁倒しを、スタックに積んだ道筋に沿って全マスへ広げる。いまいるマスから未訪問の隣をランダムに選んで間の壁を倒し、進んだ先をスタックに積む。四方すべて訪問済みなら一つ戻る。盤面いっぱいに格子を張り、cellW = w / cols、cellH = h / rows で全面を埋める。掘った跡を明るく、いま掘っている頭を白い点で示す。

const DX = [0, 0, -1, 1]
const DY = [-1, 1, 0, 0]
const OPP = [1, 0, 3, 2]

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cols = 24
  const rows = 19
  const cellW = w / cols
  const cellH = h / rows
  const thick = Math.min(cellW, cellH) * 0.16

let visited = new Uint8Array(cols * rows)
  let walls = new Uint8Array(cols * rows)
  let stack = []

const reset = () => {
    visited = new Uint8Array(cols * rows)
    walls = new Uint8Array(cols * rows).fill(0b1111)
    const start = ((Math.random() * rows) | 0) * cols + ((Math.random() * cols) | 0)
    visited[start] = 1
    stack = [start]
    c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
  }

const drawCell = (idx, head) => {
    const cx = idx % cols
    const cy = (idx / cols) | 0
    const px = cx * cellW
    const py = cy * cellH
    const ws = walls[idx]
    c.fillStyle = colors.tint(150)
    c.fillRect(px + thick, py + thick, cellW - thick * 2, cellH - thick * 2)
    if ((ws & 1) === 0) c.fillRect(px + thick, py - thick, cellW - thick * 2, thick * 2)
    if ((ws & 2) === 0) c.fillRect(px + thick, py + cellH - thick, cellW - thick * 2, thick * 2)
    if ((ws & 4) === 0) c.fillRect(px - thick, py + thick, thick * 2, cellH - thick * 2)
    if ((ws & 8) === 0) c.fillRect(px + cellW - thick, py + thick, thick * 2, cellH - thick * 2)
    if (head) {
      c.fillStyle = colors.paper
      const dot = Math.min(cellW, cellH) * 0.3
      c.fillRect(px + (cellW - dot) / 2, py + (cellH - dot) / 2, dot, dot)
    }
  }

reset()

return () => {
    for (let s = 0; s < 3; s++) {
      if (stack.length === 0) {
        reset()
        break
      }
      const cur = stack[stack.length - 1]
      const cx = cur % cols
      const cy = (cur / cols) | 0
      const order = [0, 1, 2, 3]
      for (let i = 3; i > 0; i--) {
        const j = (Math.random() * (i + 1)) | 0
        const tmp = order[i]
        order[i] = order[j]
        order[j] = tmp
      }

let next = -1
      let dir = -1
      for (const d of order) {
        const nx = cx + DX[d]
        const ny = cy + DY[d]
        if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue
        const ni = ny * cols + nx
        if (visited[ni] === 1) continue
        next = ni
        dir = d
        break
      }

if (next >= 0) {
        walls[cur] = walls[cur] & ~(1 << dir)
        walls[next] = walls[next] & ~(1 << OPP[dir])
        visited[next] = 1
        stack.push(next)
        drawCell(cur, false)
        drawCell(next, true)
      } else {
        stack.pop()
        drawCell(cur, false)
      }
    }
  }
}

掘り進む頭が未訪問のマスを食べていき、行き止まると白い点がスタックを戻って分岐の口まで下がる。OPP[dir] は反対向きの番号で、進む先の壁も同時に倒して両側を開ける。全マスを訪れてスタックが空になると、reset が別の出発点から掘り直す。どのマスからどのマスへも道が一本に決まり、閉じた輪のない通路網になる。cols と rows を上げると通路が細かく、出発点をランダムに振るたびに別の迷路が出る。