shigureni.dev

ゴールの方へ細く伸びる — A スター

ダイクストラは全方向へ平等に広がる。ゴールがどっちにあろうと、距離の近い順に律儀に確定していく。ゴールまでの見当（ヒューリスティック）を持っているなら、ゴールから遠ざかる方向の探索は後回しにできる。

確定済みのコスト g に、ゴールまでの見当 h を足した f を見て、f の小さいマスから優先して開く。g だけ見るのがダイクストラ、g + h で先を急ぐのが A スター。見る量がひとつ増えただけで、枠組みは同じ。

A スター。g + h を評価値にして探索する経路アルゴリズム。g はスタートから今のマスまでの確定済みコスト、h はそのマスからゴールまでの見積もり（ヒューリスティック）で、f = g + h を最小化する向きにマスを開く。h が実際のコストを決して上回らない（admissible・許容的）かぎり、最短経路になる。マンハッタン距離やチェビシェフ距離は壁を無視して測るので許容的になる。h を常に 0 にすると f = g となりダイクストラに一致し、g を無視して h だけ見ると貪欲最良優先探索（greedy best-first）になる。A スターはその中間に位置する。Hart, Nilsson, Raphael が 1968 年に定式化した。

未確定のマスから、ダイクストラは g の最小を選んでいた。A スターは g + h の最小に変える。h はゴールまでのマンハッタン距離、横の差と縦の差を足したもの。これだけで、選ばれるマスがゴールの方角へ傾く。

// 未確定(open)の中から f = g + h が最小のマスを選ぶ
let bi = 0
for (let i = 1; i < open.length; i++) {
  const fi = gScore[open[i]] + hCost(open[i]) // g に見当 h を足す
  if (fi < gScore[open[bi]] + hCost(open[bi])) bi = i
}

hCost を 0 にすれば f = g に戻り、選び方はダイクストラと同じになる。h を足したぶん、ゴールから逸れたマスの f が底上げされて後回しになる。マスは未踏 / open（縁に並んで待つ）/ closed（確定済み）の3つの状態を行き来する。open は f が最小のものから取り出し、開いたら closed に移す。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const N = 34
  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.2 ? 1 : 0
  const start = idx(2, 2)
  const goal = idx(N - 3, N - 3)
  wall[start] = 0
  wall[goal] = 0

const gScore = new Float32Array(N * N).fill(1e9)
  const state = new Uint8Array(N * N) // 0:未踏 1:open 2:closed
  gScore[start] = 0
  let open = [start]
  state[start] = 1

// ゴールまでの見当（マンハッタン距離）
  const hCost = (i) => Math.abs((i % N) - (goal % N)) + Math.abs(((i / N) | 0) - ((goal / N) | 0))
  let done = false

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

return () => {
    for (let step = 0; step < 3 && open.length > 0 && !done; step++) {
      // f = g + h が最小の open を取り出す
      let bi = 0
      for (let i = 1; i < open.length; i++) {
        const fi = gScore[open[i]] + hCost(open[i])
        const fb = gScore[open[bi]] + hCost(open[bi])
        if (fi < fb) bi = i
      }
      const cur = open[bi]
      open[bi] = open[open.length - 1]
      open.pop()
      state[cur] = 2
      if (cur === goal) {
        done = true
        break
      }
      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) continue
        const ng = gScore[cur] + 1
        if (ng >= gScore[ni]) continue
        gScore[ni] = ng
        if (state[ni] !== 1) {
          open.push(ni)
          state[ni] = 1
        }
      }
    }

for (let i = 0; i < N * N; i++) {
      if (wall[i] === 1) c.fillStyle = colors.tint(58)
      else if (state[i] === 1)
        c.fillStyle = colors.tint(120) // 探索の縁(open)
      else if (state[i] === 2)
        c.fillStyle = colors.tint(205) // 確定(closed)
      else c.fillStyle = colors.paper
      c.fillRect((i % N) * cellW, ((i / N) | 0) * cellH, cellW + 0.5, cellH + 0.5)
    }

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

確定済み（明るいマス）の広がりが、全方向の円ではなく、スタートからゴールへ細く傾いて伸びる。見当 h がゴールから逸れる方向の f を底上げして後回しにするので、無駄な方角をあまり開かない。hCost(i) を 0 にすると f = g になってダイクストラと同じ選び方に戻り、確定の塗りがまた全方向の円に広がる。壁（暗いマス）に当たると open の縁がそこで途切れ、開いた隙間を縫ってゴール側へ回り込む。

来た道を一マスごとに覚えておくと、ゴールに届いた瞬間その親をスタートまで遡って経路の線が引ける。確定（明るい）と探索の縁（中間調）と壁（暗い）の3つの濃淡に、遡った経路を最も暗い線で重ねると、細い探索の帯の中に一本の道が浮かぶ。

見当を本当の距離より大きく見積もると（weighted A スター）、探索はもっと細く速くなる代わりに、最短である保証は崩れる。h に掛ける係数が、速さと最適さのつまみになる。