shigureni.dev

ナビゲーション — フローフィールド

ゴールを一つ決めて、そこから全マスへ「あと何歩か」を測る。各マスに、ゴールへ一歩近づく隣の向きを矢印として置く。大群のキャラはそれぞれ足元の矢印を辿るだけで、壁を回り込んで一斉にゴールへ集まる。一体ごとに最短路を解かず、距離場を一回焼いて全員で共有する。

フローフィールド（ベクトルフィールドパスファインディング）は、ゴールから幅優先探索で距離場を作り、各マスの勾配を進行方向にした地図。一体ごとに A* を解くと群衆の規模ぶんコストが増えるが、ゴールが一つなら距離場を一度焼くだけで全員ぶんの経路が決まる。RTS の集団移動に使われる。距離の測り方を BFS（一歩=1）からダイクストラ（地形コスト付き）に替えると、沼を避けて道を通る重みつきの流れになる。

ゴールから波を流す。ゴールのマスに歩数 0 を置き、上下左右の隣の床へ一歩ずつ歩数を書き込みながら、まだ未到達の床だけを次の層へ積む。壁にぶつかると波はそこで止まり、壁の裏へは別の経路から回り込む。歩数を明るさに焼くと、ゴール（黒い升）の近くが暗く、遠いほど明るいグラデーションになる。

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

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

// ゴールから BFS。dist[i] = ゴールからの歩数（未到達は 1e9 のまま）
  const dist = new Float32Array(N * N).fill(1e9)
  dist[goal] = 0
  let queue = [goal]
  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 (wall[ni] === 1 || dist[ni] <= d) continue
        dist[ni] = d
        if (d > far) 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 (wall[i] === 1) continue
        if (dist[i] >= 1e9)
          c.fillStyle = colors.tint(70) // 壁で孤立した床
        else c.fillStyle = colors.tint(30 + (dist[i] / far) * 200)
        c.fillRect(x * cellW, y * cellH, cellW + 1, cellH + 1)
      }
    }
    c.fillStyle = colors.ink
    c.fillRect((goal % N) * cellW + 1, ((goal / N) | 0) * cellH + 1, cellW - 2, cellH - 2)
  }
}

明るさの段がそのまま、ゴールまでの距離の等高線になる。同じ歩数の床が帯になって、ゴールを囲む輪のように並ぶ。波が回り込めなかった孤立床は暗いまま残る。

距離場に、向きを一緒に記録する。あるマスへ初めて波が届いたとき、どの隣から来たかを書き留める。その来た方向の逆——隣へ戻る向きが、ゴールへ近づく矢印になる。波を流すループの中で歩数を書くのと同じ行で、隣の座標 − 自分の座標 を向きとして溜める。全マスにこの矢印を引くと、画面いっぱいに流れの分布が立つ。

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

const dist = new Float32Array(N * N).fill(1e9)
  const flowX = new Float32Array(N * N)
  const flowY = new Float32Array(N * N)
  dist[goal] = 0
  let queue = [goal]
  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 (wall[ni] === 1 || dist[ni] <= d) continue
        dist[ni] = d
        flowX[ni] = cx - nx // 来た隣へ戻る向き = ゴール側
        flowY[ni] = cy - ny
        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 (wall[i] !== 1) continue
        c.fillStyle = colors.tint(150) // 壁
        c.fillRect(x * cellW, y * cellH, cellW + 1, cellH + 1)
      }
    }
    c.strokeStyle = colors.tint(40)
    c.lineWidth = 2
    c.beginPath()
    for (let i = 0; i < N * N; i++) {
      if (dist[i] >= 1e9) continue
      if (flowX[i] === 0 && flowY[i] === 0) continue
      const ox = (i % N) * cellW + cellW / 2
      const oy = ((i / N) | 0) * cellH + cellH / 2
      c.moveTo(ox, oy)
      c.lineTo(ox + flowX[i] * cellW * 0.4, oy + flowY[i] * cellH * 0.4)
    }
    c.stroke()
    c.fillStyle = colors.ink
    c.fillRect((goal % N) * cellW + 1, ((goal / N) | 0) * cellH + 1, cellW - 2, cellH - 2)
  }
}

矢印がゴール（黒い升）へ向かって渦を巻くように収束し、壁（灰色）の周りでは迂回するように向きが曲がる。床ごとに、自分の真上に来る経路が一本決まっている。

この矢印の上をキャラに歩かせる。一体の足元のマスを x / cellW、y / cellH で割り出し、そのマスの矢印 flowX, flowY を速度に足す。それを毎フレーム繰り返すと、どこから出発しても矢印を辿ってゴールへ吸い込まれる。ゴールに着いた粒は別の床へ撒き直して、群れが流れ続ける。

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

const dist = new Float32Array(N * N).fill(1e9)
  const flowX = new Float32Array(N * N)
  const flowY = new Float32Array(N * N)
  dist[goal] = 0
  let queue = [goal]
  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 (wall[ni] === 1 || dist[ni] <= d) continue
        dist[ni] = d
        flowX[ni] = cx - nx
        flowY[ni] = cy - ny
        layer.push(ni)
      }
    }
    queue = layer
  }

const goalX = (goal % N) * cellW + cellW / 2
  const goalY = ((goal / N) | 0) * cellH + cellH / 2

// ゴールに届く床のどこかから湧かせる
  const spawn = () => {
    for (let t = 0; t < 40; t++) {
      const x = (Math.random() * N) | 0
      const y = (Math.random() * N) | 0
      const i = idx(x, y)
      if (wall[i] === 0 && dist[i] < 1e9)
        return { x: x * cellW + cellW / 2, y: y * cellH + cellH / 2 }
    }
    return { x: goalX, y: goalY }
  }

const agents = Array.from({ length: 220 }, () => spawn())

return () => {
    c.fillStyle = colors.tintAlpha(238, 0.1)
    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 (wall[i] !== 1) continue
        c.fillStyle = colors.tint(150)
        c.fillRect(x * cellW, y * cellH, cellW + 1, cellH + 1)
      }
    }

c.fillStyle = colors.ink
    c.fillRect((goal % N) * cellW + 1, ((goal / N) | 0) * cellH + 1, cellW - 2, cellH - 2)

c.fillStyle = colors.tint(28)
    for (const a of agents) {
      const cx = Math.min(N - 1, Math.max(0, (a.x / cellW) | 0))
      const cy = Math.min(N - 1, Math.max(0, (a.y / cellH) | 0))
      const i = idx(cx, cy)
      a.x += flowX[i] * cellW * 0.2 // 足元の矢印を速度に
      a.y += flowY[i] * cellH * 0.2
      const arrived = Math.hypot(a.x - goalX, a.y - goalY) < cellW * 0.7
      if (arrived || (flowX[i] === 0 && flowY[i] === 0)) {
        const s = spawn()
        a.x = s.x
        a.y = s.y
      }
      c.fillRect(a.x - 2, a.y - 2, 4, 4)
    }
  }
}

撒いた点が矢印の筋に沿って流れ、壁を回り込みながらゴール（黒い升）へ集まる。半透明の paper を毎フレーム上から塗っているので、通り道が尾を引いて経路の束が見える。一体ごとに経路を解く処理はどこにもなく、全員が同じ flowX, flowY を読むだけで道が決まる。一点から波を流して歩数を測る BFS の距離場に、来た向きの記録を一行足すと、そのまま大群のナビゲーションになる。