shigureni.dev

連結性 — BFSで到達できる範囲を塗る

マップが遊べるかどうかは、全部の床にたどり着けるかという連結性の問題になる。CAで彫った洞窟には、本体から切り離された小島ができることがある。そこへ行けないなら、その部屋は無いのと同じ。1点から幅優先探索（BFS）で水を流すように塗り広げて、どこまで届くかを見る。

連結性は、床のマスをノード、隣り合う床どうしの隣接を辺とみなしたグラフが一つの連結成分にまとまっているか、という問い。任意の1床から到達できる集合がすべての床を覆えば連結。覆わなければ、覆えなかった床が別の連結成分（小島）になる。一回の探索で到達集合を取れば判定が済む。

流す相手の床を用意する。Uint8Array 一本に壁=1・床=0 を入れて、左上に大きな床の塊と、右下に壁で切り離した小さな床を撒く。BFSを流したとき片方だけが染まって片方が取り残されるよう、連結していない盤面にしてある。

床が二つ、壁の海に浮いている。どちらも同じ明るさで塗っているので、繋がっているかは見ただけでは分からない。1点から幅優先探索（BFS）で波を流して判定する。

最初に見つけた床を始点にして、上下左右の隣の床へ一歩ずつ波を広げる。dist に始点からの歩数を書き込み、まだ -1 の床だけを次の層へ積む。同じ層をまとめて処理して、層が空になったら止まる。波が回り込めた床にだけ歩数が入り、届かなかった床は -1 のまま残る。

// start から幅優先で波を流す。dist[i] = 始点からの歩数（未到達は -1）
const dxs = [1, -1, 0, 0]
const dys = [0, 0, 1, -1]
let queue = [start]
dist[start] = 0
while (queue.length) {
  const layer = []
  for (const cur of queue) {
    const cx = cur % N
    const cy = (cur / N) | 0
    for (let k = 0; k < 4; k++) {
      const nx = cx + dxs[k]
      const ny = cy + dys[k]
      const ni = ny * N + nx
      if (grid[ni] !== 0 || dist[ni] >= 0) continue // 壁か既訪は飛ばす
      dist[ni] = dist[cur] + 1
      layer.push(ni)
    }
  }
  queue = layer
}

幅優先探索（BFS）。始点から近い順にノードを訪れる。距離 d のノードをすべて処理してから距離 d+1 へ移るので、辺の重みが一律のグリッドでは各床に最初に入る歩数がそのまま最短歩数になる。スタックで深く潜る深さ優先探索が一筆書きで奥へ進むのに対し、キューで層ごとに広げる幅優先探索は同心円状に進む。各床は一度だけ訪れるので、計算量は床と辺の数に比例する。

層ごとに処理するので dist には最短歩数が入る。深さ優先で潜るのではなく、近い床から順に同心円で広がる。歩数を明るさに焼くと、始点の近くが暗く、遠いほど明るいグラデーションになる。

下は、ランダムに埋めた盤面を2回CAで均してから、最初に見つけた床に波を流したもの。walls は周り8マスの壁数を数えて多数決で均すルール。波が届いた床を歩数で明るく、届かなかった孤立島を暗いまま残す。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const N = 56
  const cellW = w / N
  const cellH = h / N
  const idx = (x, y) => y * N + x

// ランダム埋め → CAで2回均す（壁=1 / 床=0）
  let grid = new Uint8Array(N * N)
  let next = new Uint8Array(N * N)
  for (let y = 0; y < N; y++) {
    for (let x = 0; x < N; x++) {
      const edge = x === 0 || y === 0 || x === N - 1 || y === N - 1
      grid[idx(x, y)] = edge ? 1 : Math.random() < 0.46 ? 1 : 0
    }
  }
  const walls = (x, y) => {
    let n = 0
    for (let dy = -1; dy <= 1; dy++)
      for (let dx = -1; dx <= 1; dx++) {
        if (dx === 0 && dy === 0) continue
        const nx = x + dx
        const ny = y + dy
        n += nx < 0 || ny < 0 || nx >= N || ny >= N ? 1 : grid[idx(nx, ny)]
      }
    return n
  }
  for (let s = 0; s < 2; s++) {
    for (let y = 0; y < N; y++)
      for (let x = 0; x < N; x++) {
        const wall = grid[idx(x, y)] === 1
        const n = walls(x, y)
        next[idx(x, y)] = n >= 5 || (wall && n >= 4) ? 1 : 0
      }
    const t = grid
    grid = next
    next = t
  }

// 最初に見つけた床から BFS。dist には歩数(波の到達)を入れる
  const dist = new Int32Array(N * N).fill(-1)
  let start = -1
  for (let i = 0; i < N * N && start < 0; i++) if (grid[i] === 0) start = i
  const dxs = [1, -1, 0, 0]
  const dys = [0, 0, 1, -1]
  let queue = [start]
  dist[start] = 0
  let far = 1
  while (queue.length) {
    const layer = []
    for (const cur of queue) {
      const cx = cur % N
      const cy = (cur / N) | 0
      const d = dist[cur] + 1
      for (let k = 0; k < 4; k++) {
        const nx = cx + dxs[k]
        const ny = cy + dys[k]
        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue
        const ni = idx(nx, ny)
        if (grid[ni] !== 0 || dist[ni] >= 0) continue
        dist[ni] = d
        far = Math.max(far, d)
        layer.push(ni)
      }
    }
    queue = layer
  }

return () => {
    c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    for (let y = 0; y < N; y++) {
      for (let x = 0; x < N; x++) {
        const i = idx(x, y)
        if (grid[i] === 1) continue // 壁は塗らない（紙のまま）
        if (dist[i] < 0) {
          c.fillStyle = colors.tint(70) // 孤立島: 届かなかった床
        } else {
          const t = dist[i] / far // 波の到達距離を明度に
          c.fillStyle = colors.tint(120 + t * 110)
        }
        c.fillRect(x * cellW, y * cellH, cellW + 0.5, cellH + 0.5)
      }
    }
  }
}

塗りの明るさは始点からの歩数で、近いほど暗く遠いほど明るい。どのマスも始点から何歩か、を焼いた距離場になっている。暗いまま残った床は波が回り込めなかった孤立島で、放っておくとプレイヤーが行けない部屋になる。Math.random() < 0.46 の壁率を上げると床が痩せて小島が増え、下げると一つの大きな空洞に繋がって孤立島が消える。