shigureni.dev

全マスに波を広げる — 幅優先とフローフィールド

ゴールから波を広げると、壁を回り込んだ本当の距離が測れる。ゴールを 0 として、隣を 1、その隣を 2、と一段ずつ等距離の輪を太らせていく。各マスには最初に届いた波だけが残り、そのマスへの最短歩数になる。

幅優先探索（BFS, breadth-first search）。始点から近い順にマスを訪れる探索。訪問待ちのマスをキュー（先入れ先出し）に並べ、取り出したマスの未訪問の隣をキューの末尾に足す。これで同じ距離のマスが必ずまとめて処理され、各マスに最初に届く経路が辺の本数で見た最短になる。辺の重みがすべて等しいグラフでの最短経路がこれで求まる。

壁のない盤で波だけを見る。各マスに「ゴールまで何歩か」を覚える dist を持ち、ゴールを 0、未到達を -1 で埋めておく。front がいまの波面で、フレームごとにその外側を一段ぶん塗る。シミュレーションは N×N の格子配列で持ち、描画は盤面を cellW × cellH の矩形セルで全面に敷く。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const N = 36
  const cellW = w / N
  const cellH = h / N
  const idx = (x, y) => y * N + x
  const dx = [1, -1, 0, 0]
  const dy = [0, 0, 1, -1]

const dist = new Int32Array(N * N).fill(-1)
  const goal = idx((N / 2) | 0, (N / 2) | 0)
  dist[goal] = 0
  let front = [goal]

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

return () => {
    const next = []
    for (const cur of front) {
      const cx = cur % N
      const cy = (cur / N) | 0
      for (let k = 0; k < 4; k++) {
        const nx = cx + dx[k]
        const ny = cy + dy[k]
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue
        const ni = idx(nx, ny)
        if (dist[ni] !== -1) continue
        dist[ni] = dist[cur] + 1
        next.push(ni)
      }
    }
    front = next

for (let i = 0; i < N * N; i++) {
      if (dist[i] < 0) c.fillStyle = colors.paper
      else c.fillStyle = colors.tint(228 - Math.min(1, dist[i] / 44) * 180)
      c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 0.5, cellH + 0.5)
    }

c.fillStyle = colors.ink
    c.fillRect((goal % N) * cellW, ((goal / N) | 0) * cellH, cellW, cellH)
  }
}

中心から明るい四角の輪が太っていく。輪のかどが菱形なのは、上下左右の4方向にしか進まないから。横と縦の差を足したマンハッタン距離の菱形と、輪の形が一致する。壁がなければ BFS の距離はマンハッタン距離に重なる。

波が一段進むときは、波面の各マスから4つの隣を覗き、まだ塗っていないマスだけに「自分 + 1」を書き込む。

const ni = idx(nx, ny)
if (dist[ni] !== -1) continue // 先に塗られたマスには触れない
dist[ni] = dist[cur] + 1 // 親より1歩遠い
next.push(ni)

dist[ni] !== -1 で一度塗ったマスを二度塗らないので、各マスには最初に届いた波、最短の歩数だけが残る。隣の条件をひとつ足すと壁が効く。wall[ni] === 1 のマスを塞ぐと、波はそこへ入れず、開いた隙間だけを通って裏へ回り込む。

const wall = new Uint8Array(N * N)
  for (let i = 0; i < N * N; i++) wall[i] = Math.random() < 0.22 ? 1 : 0
  const goal = idx((N / 2) | 0, (N / 2) | 0)
  wall[goal] = 0

const dist = new Int32Array(N * N).fill(-1)
  dist[goal] = 0
  let front = [goal]

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

return () => {
    if (front.length > 0) {
      const next = []
      for (const cur of front) {
        const cx = cur % N
        const cy = (cur / N) | 0
        for (let k = 0; k < 4; k++) {
          const nx = cx + dx[k]
          const ny = cy + dy[k]
          if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue
          const ni = idx(nx, ny)
          if (wall[ni] === 1 || dist[ni] !== -1) continue
          dist[ni] = dist[cur] + 1
          next.push(ni)
        }
      }
      front = next
    }

for (let i = 0; i < N * N; i++) {
      if (wall[i] === 1) c.fillStyle = colors.tint(58)
      else if (dist[i] < 0) c.fillStyle = colors.paper
      else {
        const t = Math.min(1, dist[i] / 44)
        c.fillStyle = colors.tint(228 - t * 180)
      }
      c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 0.5, cellH + 0.5)
    }

c.fillStyle = colors.ink
    c.fillRect((goal % N) * cellW, ((goal / N) | 0) * cellH, cellW, cellH)
  }
}

明るい輪が壁の角でぐにゃりと曲がりながら裏へ回り込む。塗り終えると、各マスの濃淡がそのまま「ゴールまで本当に何歩か」になる。wall の密度 0.22 を上げると通れる隙間が痩せ、波が細い廊下を伝う。

距離だけでなく「どの隣から来たか」も覚えておくと、各マスに「ゴールへ近づく向き」が一本ずつ焼ける。その向きを矢印として読むのがフローフィールド。

フローフィールド。ゴールから一度だけ BFS（または重みつきのダイクストラ）で全マスの距離場を作り、各マスから距離の小さい隣へ向く単位ベクトルを焼き込んだ地図。動く点はこの矢印を読むだけで壁を回り込んでゴールへ集まる。経路を点ごとに解き直さないので、ゴールが一つで動く点が大群のとき、一匹ずつの A スターより計算が安い。RTS の群衆移動で使われる。

距離場の各マスで、最も距離の小さい隣の方向を vx, vy に焼く。点はその場の矢印を読み、向きへ一歩進むだけで壁を避けてゴールへ寄っていく。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const N = 30
  const cellW = w / N
  const cellH = h / N
  const idx = (x, y) => y * N + x
  const dx = [1, -1, 0, 0]
  const dy = [0, 0, 1, -1]

const wall = new Uint8Array(N * N)
  for (let i = 0; i < N * N; i++) wall[i] = Math.random() < 0.16 ? 1 : 0
  const goal = idx((N / 2) | 0, (N / 2) | 0)
  wall[goal] = 0

// ゴールから BFS で距離場を作る
  const dist = new Int32Array(N * N).fill(-1)
  dist[goal] = 0
  let front = [goal]
  while (front.length > 0) {
    const next = []
    for (const cur of front) {
      const cx = cur % N
      const cy = (cur / N) | 0
      for (let k = 0; k < 4; k++) {
        const nx = cx + dx[k]
        const ny = cy + dy[k]
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue
        const ni = idx(nx, ny)
        if (wall[ni] === 1 || dist[ni] !== -1) continue
        dist[ni] = dist[cur] + 1
        next.push(ni)
      }
    }
    front = next
  }

// 各マスに「距離が最小の隣」への向きを焼く
  const vx = new Float32Array(N * N)
  const vy = new Float32Array(N * N)
  for (let y = 0; y < N; y++) {
    for (let x = 0; x < N; x++) {
      const i = idx(x, y)
      if (wall[i] === 1 || dist[i] < 0) continue
      let bestD = dist[i]
      let bx = 0
      let by = 0
      for (let k = 0; k < 4; k++) {
        const nx = x + dx[k]
        const ny = y + dy[k]
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue
        const ni = idx(nx, ny)
        if (wall[ni] === 1 || dist[ni] < 0) continue
        if (dist[ni] < bestD) {
          bestD = dist[ni]
          bx = dx[k]
          by = dy[k]
        }
      }
      vx[i] = bx
      vy[i] = by
    }
  }

const spawn = () => {
    let gx = 0
    let gy = 0
    do {
      gx = (Math.random() * N) | 0
      gy = (Math.random() * N) | 0
    } while (wall[idx(gx, gy)] === 1)
    return { x: gx + 0.5, y: gy + 0.5 }
  }
  const agents = Array.from({ length: 240 }, spawn)

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

return () => {
    for (let i = 0; i < N * N; i++) {
      if (wall[i] === 1) c.fillStyle = colors.tint(58)
      else if (dist[i] < 0) c.fillStyle = colors.paper
      else c.fillStyle = colors.tint(232 - Math.min(1, dist[i] / 40) * 150)
      c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 0.5, cellH + 0.5)
    }

c.fillStyle = colors.ink
    for (const a of agents) {
      const ci = idx(a.x | 0, a.y | 0)
      a.x += vx[ci] * 0.08
      a.y += vy[ci] * 0.08
      if (dist[ci] <= 0) {
        const s = spawn()
        a.x = s.x
        a.y = s.y
      }
      c.fillRect(a.x * cellW - 1.5, a.y * cellH - 1.5, 3, 3)
    }
  }
}

点の大群が同じ距離場を読みながら、壁を回り込んでゴールの一点へ流れ込む。経路を一匹ずつ解いてはおらず、全員が同じ一枚の矢印地図を共有している。wall の密度を上げて隙間を狭めても、距離場が裏の通路を通る向きを各マスに持っているので、点は袋小路に入らず迂回路へ吸い寄せられる。