shigureni.dev

地面に重みをつける — ダイクストラ

一歩のコストをマスごとに変える。沼は通れるが手間がかかる、舗装路は速い。一歩 1 で数える幅優先のままだと、コストの違うマスを一段ずつの輪では扱えない。未確定のマスのうち、いま分かっている中でいちばん距離の小さいものから順に確定していく。

ダイクストラ法。辺に重み（コスト）のあるグラフで始点からの最短距離を求める。Edsger Dijkstra が 1959 年に発表した。確定済みの集合を一つずつ広げ、毎回「未確定で距離最小の頂点」を確定する。確定した頂点の距離はそれ以上短くならない——重みが非負なら、より遠い頂点を経由して短くなることがないため。隣の距離は 現在の距離 + 入る辺の重み で更新する。すべての重みが 1 のとき、距離最小の頂点を選ぶ操作は同じ距離の輪を一斉に広げる幅優先探索に一致する。

地面の重みを場として作る。sin と cos の積でなだらかな帯を描き、しきい値を越えたマスを沼として 8、ほかを 1 にする。マスごとにコストが違う。

const swamp = Math.sin(x * 0.5) * Math.cos(y * 0.4)
cost[idx(x, y)] = swamp > 0.45 ? 8 : 1 // 沼は1歩8ぶんの手間

波の進め方が変わる。コストが違うと、次に塗るべきマスが波面のどこにあるか定まらない。未確定のマスから距離が最小のものを一つ選んで確定し、その隣を更新する。隣を更新するとき足すのは 1 ではなく入る先のコスト。

done[best] = 1 // 最小距離のマスを確定
for (let k = 0; k < 4; k++) {
  const ni = idx(nx, ny)
  const nd = dist[best] + cost[ni] // 入る先のコストぶん遠い
  if (nd < dist[ni]) dist[ni] = nd // より短ければ書き換える
}

最小を選んで確定し、隣を見直す。この繰り返しで、距離が近い順に決まる。

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 cost = new Float32Array(N * N)
  for (let y = 0; y < N; y++) {
    for (let x = 0; x < N; x++) {
      const swamp = Math.sin(x * 0.5) * Math.cos(y * 0.4)
      cost[idx(x, y)] = swamp > 0.45 ? 8 : 1
    }
  }
  const goal = idx(4, (N / 2) | 0)

const dist = new Float32Array(N * N).fill(1e9)
  dist[goal] = 0
  const done = new Uint8Array(N * N)
  let settled = false

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

return () => {
    // 毎フレーム、未確定で最小距離のマスを少しずつ確定する
    for (let step = 0; step < 12 && !settled; step++) {
      let best = -1
      let bestD = 1e9
      for (let i = 0; i < N * N; i++) {
        if (done[i] === 0 && dist[i] < bestD) {
          bestD = dist[i]
          best = i
        }
      }
      if (best < 0) {
        settled = true
        break
      }
      done[best] = 1
      const cx = best % N
      const cy = (best / 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)
        const nd = dist[best] + cost[ni] // 入る先のコストを足す
        if (nd < dist[ni]) dist[ni] = nd
      }
    }

for (let i = 0; i < N * N; i++) {
      const swamp = cost[i] > 1
      if (dist[i] >= 1e9) c.fillStyle = swamp ? colors.tint(150) : colors.paper
      else {
        const t = Math.min(1, dist[i] / 90)
        c.fillStyle = colors.tint(232 - t * 190)
      }
      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)
  }
}

塗り終えた濃淡は、沼の帯のところで等しいコストの輪がきゅっと詰まる。手間がかかる地面ほど少し進むだけで距離（明度）が一気に落ち、輪の間隔が狭くなる。cost を全部 1 に戻すと、距離最小を選ぶ操作が同じ距離の輪を一斉に広げる幅優先と一致して、同心円に戻る。