shigureni.dev

毎フレーム解かない — 貪欲なナビ

マップ全体を相手にする探索は、敵が多いと全員ぶん毎フレーム回すのが重い。最短をいちいち解かず、今いるマスから標的にいちばん近づく隣へ一歩進むだけでも、追い詰める動きは出る。

標的へ近づく隣を毎歩選ぶだけのナビは greedy（貪欲法）の一種で、最短経路は保証しない。袋小路や凹んだ壁に正面から入ると、近づく隣が無くなって詰まる。Pac-Man の鬼はこれに近く、各鬼が標的マスを少しずつ変えて（自機の数マス先、自機と別の鬼の対称点など）追う・先回りするを撃ち分ける。来た方向への逆戻りを禁じる一手が、迷路で往復してハマるのを防ぐ。

壁を撒いた格子で、追手が一匹。各歩で四方の隣を見て、標的とのユークリッド距離がいちばん小さい隣へ進む。来た方向（rev[dir]）だけは候補から外す。標的は sin と cos でマップ上を漂わせている。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const N = 19
  const cellW = w / N
  const cellH = h / N
  const idx = (x, y) => y * N + x
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ]
  const rev = [1, 0, 3, 2]

const wall = new Uint8Array(N * N)
  for (let i = 0; i < N * N; i++) {
    const x = i % N
    const y = (i / N) | 0
    const edge = x === 0 || x === N - 1 || y === 0 || y === N - 1
    wall[i] = edge || Math.random() < 0.24 ? 1 : 0
  }
  const passable = (x, y) => x >= 0 && x < N && y >= 0 && y < N && wall[idx(x, y)] === 0

const chaser = { x: 3, y: 3, dir: 0 }
  const target = { x: 9, y: 9, t: 0 }

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

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

target.t += 0.03
    target.x = 1 + (((Math.sin(target.t) * 0.5 + 0.5) * (N - 2)) | 0)
    target.y = 1 + (((Math.cos(target.t * 0.7) * 0.5 + 0.5) * (N - 2)) | 0)

// 標的にいちばん近づく隣を選ぶ。来た方向だけは外す
    let bestDist = 1e9
    let next = chaser.dir
    for (let d = 0; d < 4; d++) {
      if (d === rev[chaser.dir]) continue
      const nx = chaser.x + dirs[d][0]
      const ny = chaser.y + dirs[d][1]
      if (passable(nx, ny) === false) continue
      const dist = Math.hypot(nx - target.x, ny - target.y)
      if (dist < bestDist) {
        bestDist = dist
        next = d
      }
    }
    if (bestDist < 1e9) {
      chaser.dir = next
      chaser.x += dirs[next][0]
      chaser.y += dirs[next][1]
    } else {
      chaser.dir = rev[chaser.dir] // 行き止まりなら引き返す
    }

c.fillStyle = colors.tint(58)
    for (let i = 0; i < N * N; i++) {
      if (wall[i] === 1) {
        c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 1, cellH + 1)
      }
    }

c.fillStyle = colors.tintAlpha(8, 0.4)
    c.fillRect(target.x * cellW, target.y * cellH, cellW, cellH)

c.fillStyle = colors.ink
    c.fillRect(
      chaser.x * cellW + cellW * 0.18,
      chaser.y * cellH + cellH * 0.18,
      cellW * 0.64,
      cellH * 0.64,
    )
  }
}

追手が標的の薄い四角を追って、壁の隙間を縫って進む。最短は解いていない。各歩で見るのは四方の距離だけで、見る範囲は手元の四マスに閉じている。標的が壁の裏へ回ると、追手は近づく隣を選び続けて壁に張り付き、隙間が見えるまで沿って動く。逆戻り禁止を外すと、行き止まりで一マスを往復してハマる。

距離の符号を反転すると、近づくのが遠ざかるに変わる。状態ごとに符号を切り替えると、一匹で追う・散る・逃げるを撃ち分けられる。state を 0 なら -dist（近づく）、1 なら +dist（遠ざかる）にして、タイマーで切り替える。2 では距離にランダムを混ぜて、ふらつきながら散る。

const spawn = () => {
    let x = 1 + ((Math.random() * (N - 2)) | 0)
    let y = 1 + ((Math.random() * (N - 2)) | 0)
    let guard = 0
    while (passable(x, y) === false && guard++ < 80) {
      x = 1 + ((Math.random() * (N - 2)) | 0)
      y = 1 + ((Math.random() * (N - 2)) | 0)
    }
    return { x, y, dir: 0, state: 0, timer: (Math.random() * 200) | 0 }
  }
  const ghosts = Array.from({ length: 4 }, spawn)
  const target = { x: 9, y: 9, t: 0 }

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

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

c.fillStyle = colors.tint(58)
    for (let i = 0; i < N * N; i++) {
      if (wall[i] === 1) {
        c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 1, cellH + 1)
      }
    }

target.t += 0.03
    target.x = 1 + (((Math.sin(target.t) * 0.5 + 0.5) * (N - 2)) | 0)
    target.y = 1 + (((Math.cos(target.t * 0.7) * 0.5 + 0.5) * (N - 2)) | 0)

for (const g of ghosts) {
      if (--g.timer <= 0) {
        g.state = (g.state + 1) % 3 // 追う→散る→逃げる→追う
        g.timer = g.state === 2 ? 90 : 150 + ((Math.random() * 200) | 0)
      }

let best = -1e9
      let next = g.dir
      for (let d = 0; d < 4; d++) {
        if (d === rev[g.dir]) continue
        const nx = g.x + dirs[d][0]
        const ny = g.y + dirs[d][1]
        if (passable(nx, ny) === false) continue
        const dist = Math.hypot(nx - target.x, ny - target.y)
        let score = g.state === 0 ? -dist : dist // 追うなら近い隣ほど高得点
        if (g.state === 2) score = -dist + Math.random() * 6
        if (score > best) {
          best = score
          next = d
        }
      }
      if (best > -1e9) {
        g.dir = next
        g.x += dirs[next][0]
        g.y += dirs[next][1]
      } else {
        g.dir = rev[g.dir]
      }

const px = g.x * cellW + cellW / 2
      const py = g.y * cellH + cellH / 2
      const rad = Math.min(cellW, cellH) * 0.36
      if (g.state === 2) {
        c.strokeStyle = colors.tint(28)
        c.lineWidth = 2
        c.strokeRect(px - rad, py - rad, rad * 2, rad * 2)
      } else {
        c.fillStyle = g.state === 0 ? colors.ink : colors.tint(120)
        c.beginPath()
        c.arc(px, py, rad, Math.PI, 0)
        c.lineTo(px + rad, py + rad)
        c.lineTo(px - rad, py + rad)
        c.closePath()
        c.fill()
      }
    }

c.fillStyle = colors.tintAlpha(8, 0.4)
    c.beginPath()
    c.arc(
      target.x * cellW + cellW / 2,
      target.y * cellH + cellH / 2,
      Math.min(cellW, cellH) * 0.24,
      0,
      6.283,
    )
    c.fill()
  }
}

濃い鬼が標的へ寄り、淡い鬼は逆に離れ、枠だけの鬼はふらつく。state の数字一つで符号が変わるだけで、同じ貪欲な一歩が追う動きにも散る動きにもなる。タイマーが切れるたびに役が入れ替わって、四匹がてんでに寄ったり離れたりする。score の式は四方の隣を比べて一番を選ぶだけで、盤の他のマスは一切読んでいない。

最短を保証する探索は盤全体を読む。貪欲なナビは手元の隣しか読まない。何匹を、どれだけの頻度で、どこまで正確に動かしたいかで、読む範囲を盤全体に取るか手元に絞るかが分かれる。