shigureni.dev

探索で選ぶ — 経路と影響

判断のもうひとつの柱が探索。今この一歩でなく、ゴールまでの道のりそのものを先に解く。

A* は、スタートからゴールまでの最短路を引く探索。各マスに「ここまでの実コスト g」と「ゴールまでの推定 h」を持たせ、その和 f = g + h が最小のマスから順に開く。h がゴールの方向を教えるので、全方向へ均等に広がる幅優先より細くゴールへ伸びる。h が実際の距離を超えなければ（許容的）最短路を保証する。マンハッタン距離（縦横移動の格子でちょうど許容的）がよく使われる。

格子の各マスに状態を持たせる。開いたマス（open）、確定したマス（closed）、塞がれた壁、最終経路の四つ。毎フレーム open から f が最小のマスを一つ取り出し、隣の四マスを見て、より小さい g で来られるなら親を記録して open へ入れる。ゴールに着いたら親をたどって経路を復元する。塞がれたマスは濃く、開いたマスを中明度、確定を淡く、復元した経路を黒で塗り分ける。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const nx = 40
  const ny = 32
  const cellW = w / nx
  const cellH = h / ny
  const total = nx * ny

const off = [1, 0, -1, 0, 0, 1, 0, -1]
  const blocked = new Uint8Array(total)
  const state = new Uint8Array(total)
  const came = new Int32Array(total)
  const gScore = new Float64Array(total)
  const fScore = new Float64Array(total)
  const open = new Int32Array(total)
  const path = []
  let openLen = 0
  let start = 0
  let goal = 0
  let done = false
  let timer = 0

const heuristic = (i) =>
    Math.abs((i % nx) - (goal % nx)) + Math.abs(Math.floor(i / nx) - Math.floor(goal / nx))

const reset = () => {
    for (let i = 0; i < total; i++) blocked[i] = Math.random() < 0.26 ? 1 : 0
    state.fill(0)
    came.fill(-1)
    gScore.fill(1e9)
    start = Math.floor(Math.random() * 4) + nx * Math.floor(Math.random() * 4)
    goal = total - 1 - Math.floor(Math.random() * 4) - nx * Math.floor(Math.random() * 4)
    blocked[start] = 0
    blocked[goal] = 0
    open[0] = start
    openLen = 1
    state[start] = 1
    gScore[start] = 0
    fScore[start] = heuristic(start)
    done = false
    timer = 0
    path.length = 0
  }

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

return () => {
    if (done) {
      if (++timer > 120) reset()
    } else {
      for (let pass = 0; pass < 3 && openLen > 0 && !done; pass++) {
        let best = 0
        for (let i = 1; i < openLen; i++) {
          if (fScore[open[i]] < fScore[open[best]]) best = i
        }
        const cur = open[best]
        open[best] = open[--openLen]
        state[cur] = 2

if (cur === goal) {
          let p = goal
          while (p !== -1) {
            path.push(p)
            p = came[p]
          }
          done = true
          break
        }

for (let k = 0; k < 8; k += 2) {
          const ax = (cur % nx) + off[k]
          const ay = Math.floor(cur / nx) + off[k + 1]
          if (ax < 0 || ax >= nx || ay < 0 || ay >= ny) continue
          const ni = ax + ay * nx
          if (blocked[ni] === 1) continue
          const ng = gScore[cur] + 1
          if (ng >= gScore[ni]) continue
          came[ni] = cur
          gScore[ni] = ng
          fScore[ni] = ng + heuristic(ni)
          if (state[ni] !== 1 && openLen < total) open[openLen++] = ni
          state[ni] = 1
        }
      }
      if (openLen === 0) done = true
    }

for (let i = 0; i < total; i++) {
      if (blocked[i] === 1) c.fillStyle = colors.tint(58)
      else if (state[i] === 1) c.fillStyle = colors.tint(110)
      else if (state[i] === 2) c.fillStyle = colors.tint(204)
      else c.fillStyle = colors.paper
      c.fillRect((i % nx) * cellW, Math.floor(i / nx) * cellH, cellW + 1, cellH + 1)
    }

if (done) {
      c.fillStyle = colors.ink
      for (const i of path) {
        c.fillRect((i % nx) * cellW + 1, Math.floor(i / nx) * cellH + 1, cellW - 1, cellH - 1)
      }
    }
  }
}

前線が壁を避けてゴールへ偏って伸び、着いた瞬間に黒い経路が一本残る。f でなく g だけで最小を取ると h が消えて、全方向へ均等に広がる幅優先になる。heuristic の戻り値を二倍三倍に膨らませると、ゴールへ一直線に突っ込んで探索は速くなるが、最短でない経路を引きうる。壁の密度 0.26 を上げると道が塞がって open が尽き、openLen === 0 で経路なしのまま打ち切る。

一匹なら A* でいい。同じゴールへ大群を向かわせるなら、全員ぶん A* を解くのは重い。ゴールから一度だけ距離を測って、各マスに「ゴールへ近づく向き」を焼いておく。

フローフィールド（流れ場）は、ゴールから幅優先で全マスの距離場を作り、各マスに「距離が一つ小さい隣へ向かう向き」を書き込んだもの。距離場の計算はゴール一点からの一回だけ。あとは何体のエージェントも、自分のいるマスの矢印を読むだけでゴールへ集まる。経路を個別に持たず一枚の場を共有するので、一対多のナビが探索一回ぶんで済む。

ゴールから幅優先で波を広げ、新しく到達したマスに「来た方向＝距離が減る向き」を矢印として記録する。距離が無限大のまま（壁に囲まれて届かない）マスには矢印が立たない。格子点ごとにその矢印を短い線で引き、ゴールを黒く塗る。エージェントを撒いて、各自が足元のマスの矢印を読んで一歩進む。

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

const wall = new Uint8Array(total)
  const dist = new Float32Array(total).fill(1e9)
  const fdx = new Float32Array(total)
  const fdy = new Float32Array(total)

const spawn = () => {
    for (let t = 0; t < 40; t++) {
      const x = Math.floor(Math.random() * nx)
      const y = Math.floor(Math.random() * ny)
      if (wall[idx(x, y)] === 0 && dist[idx(x, y)] < 1e9) {
        return { x: (x + 0.5) * cellW, y: (y + 0.5) * cellH }
      }
    }
    return { x: w / 2, y: h / 2 }
  }

let goalCell = build()
  const agents = Array.from({ length: 90 }, () => spawn())

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

return () => {
    c.fillStyle = colors.tintAlpha(238, 0.12)
    c.fillRect(0, 0, w, h)

c.strokeStyle = colors.tint(58)
    c.lineWidth = 1.5
    c.beginPath()
    for (let i = 0; i < total; i++) {
      if (dist[i] >= 1e9 || (fdx[i] === 0 && fdy[i] === 0)) continue
      const ox = ((i % nx) + 0.5) * cellW
      const oy = (Math.floor(i / nx) + 0.5) * cellH
      c.moveTo(ox, oy)
      c.lineTo(ox + fdx[i] * cellW * 0.42, oy + fdy[i] * cellH * 0.42)
    }
    c.stroke()

const gcx = (goalCell.gx + 0.5) * cellW
    const gcy = (goalCell.gy + 0.5) * cellH
    c.fillStyle = colors.ink
    c.fillRect(goalCell.gx * cellW + 1, goalCell.gy * cellH + 1, cellW - 2, cellH - 2)

c.fillStyle = colors.tint(28)
    for (const a of agents) {
      const cx = Math.min(nx - 1, Math.max(0, Math.floor(a.x / cellW)))
      const cy = Math.min(ny - 1, Math.max(0, Math.floor(a.y / cellH)))
      const i = idx(cx, cy)
      a.x += fdx[i] * cellW * 0.28
      a.y += fdy[i] * cellH * 0.28
      const arrived = Math.hypot(a.x - gcx, a.y - gcy) < cellW * 0.8
      if (arrived || (fdx[i] === 0 && fdy[i] === 0)) {
        const s = spawn()
        a.x = s.x
        a.y = s.y
      }
      c.fillRect(a.x - 1.5, a.y - 1.5, 3, 3)
    }
  }
}

矢印がゴールへ向かう流れの川になり、撒いた点が壁を回り込んで黒いマスへ吸い込まれる。点はゴールに着くか矢印のないマスに乗ると別の場所へ撒き直す。距離場は build の一回で作って固定し、各点は毎フレーム fdx, fdy を読むだけなので、点を 90 から増やしても計算量は撒いた数に比例して増えるだけになる。半透明の paper を毎フレーム上から塗っているので、点の通った跡が薄く尾を引く。

道を引くのとは別に、盤面全体の「どちらが優勢か」を場で持てる。各ユニットが周りへ影響を撒いて、味方はプラス、敵はマイナス。足し合わせた符号が、その地点を今どちらが支配しているかになる。

影響マップ（influence map）は、各ユニットから距離とともに減衰する影響値を撒いて格子に足し込んだ場。陣営ごとに符号を逆にすると、値の正負がその地点の支配勢力、値が 0 を横切る線が前線になる。減衰には距離の二乗に反比例する strength / d² をよく使う。この場を A* のコストに足し込むと、敵の濃い所を避ける臆病なルートも、突っ切る強気なルートも、混ぜる重み一つで連続的に作れる。

ユニットを画面に散らし、味方と敵で符号を分ける。壁で跳ね返りながら漂わせる。格子の各マスで全ユニットからの sign * strength / (距離² + soften) を足して場を作る。soften はユニット直上で値が発散しないための下駄。値の絶対値を明るさに写し、強い所ほど濃く塗る。隣のマスと符号が変わる境目（積が負）を黒で縁取ると、前線が浮く。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const nx = 64
  const ny = 52
  const cellW = w / nx
  const cellH = h / ny
  const speed = w / 240
  const soften = (w / 19.2) * (w / 19.2)
  const strength = 9000 * (w / 384) * (w / 384)

const count = 6
  const units = Array.from({ length: count }, (_unit, i) => ({
    x: Math.random() * w,
    y: Math.random() * h,
    vx: (Math.random() - 0.5) * 2 * speed,
    vy: (Math.random() - 0.5) * 2 * speed,
    sign: i % 2 === 0 ? 1 : -1,
  }))
  const field = new Float32Array(nx * ny)

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

return () => {
    for (const u of units) {
      u.x += u.vx
      u.y += u.vy
      if (u.x < 0 || u.x >= w) {
        u.vx = -u.vx
        u.x = Math.max(0, Math.min(w - 1, u.x))
      }
      if (u.y < 0 || u.y >= h) {
        u.vy = -u.vy
        u.y = Math.max(0, Math.min(h - 1, u.y))
      }
    }

for (let gy = 0; gy < ny; gy++) {
      for (let gx = 0; gx < nx; gx++) {
        const px = (gx + 0.5) * cellW
        const py = (gy + 0.5) * cellH
        let sum = 0
        for (const u of units) {
          const ddx = px - u.x
          const ddy = py - u.y
          const d2 = ddx * ddx + ddy * ddy + soften
          sum += (u.sign * strength) / d2
        }
        field[gy * nx + gx] = sum
      }
    }

for (let gy = 0; gy < ny; gy++) {
      for (let gx = 0; gx < nx; gx++) {
        const v = field[gy * nx + gx]
        const mag = Math.min(1, Math.abs(v))
        c.fillStyle = colors.tint(Math.round(238 - mag * 200))
        c.fillRect(gx * cellW, gy * cellH, cellW + 1, cellH + 1)
      }
    }

c.fillStyle = colors.ink
    for (let gy = 0; gy < ny; gy++) {
      for (let gx = 0; gx < nx; gx++) {
        const v = field[gy * nx + gx]
        const r = gx < nx - 1 ? field[gy * nx + gx + 1] : v
        const d = gy < ny - 1 ? field[(gy + 1) * nx + gx] : v
        if (v * r < 0 || v * d < 0) {
          c.fillRect(gx * cellW, gy * cellH, cellW + 1, cellH + 1)
        }
      }
    }
  }
}

各ユニットの周りに濃い染みができ、味方と敵の染みがぶつかる谷間に黒い前線が走る。ユニットが動くと前線がぬるりと動き、味方が固まった側へ押し込まれる。strength / d² の二乗を一乗 strength / d に変えると影響が遠くまで届いて前線がぼやけ、soften を小さくするとユニット直上が鋭く尖る。隣との積が負のマスだけ黒くしているので、線は値がちょうど 0 になる等値線をなぞる。判断の材料が、点でなく一枚の場に乗る。