塗りつぶしの仕組み：隣のマスへ広がる処理

塗りつぶしは「隣へ広がる」を繰り返す処理

塗りつぶしを組み立てる材料は3つだけです。

• 盤面：マスの並びで、各マスは「塗れる」か「塗れない（壁）」のどちらかです。
• 開始マス：クリックされた場所です。
• 「隣」の定義：どのマスを隣と見なすかのルールです。

処理は次の流れになります。

1. 開始マスを塗り、「これから隣を調べるマス」の一覧に入れます。
2. 一覧からマスを1つ取り出します。
3. そのマスの隣を順に見て、盤面の内側にあり、まだ塗られておらず、壁でもないマスを塗って一覧に加えます。
4. 一覧が空になるまで2と3を繰り返します。

一覧の役割は「広がりの先端」を覚えておくことです。先端が壁や盤面の端にぶつかるたびに一覧は減り、広げる先がなくなった時点で処理は終わります。つまり「囲まれた内側だけが塗れる」のは、壁が先端を止めた結果です。内側と外側を見分ける特別な判定は存在しません。

「隣」の決め方で結果が変わる

隣の定義には主に2通りあります。

• 4方向、隣と見なすマス：上下左右の4マス、向いている場面：縦横にしか動けないゲーム、道や水路のつながり
• 8方向、隣と見なすマス：上下左右と斜めの8マス、向いている場面：斜めにも動ける駒、斜めの接触も「つながり」と見たい場面

同じ盤面でも、どちらを選ぶかで塗れる範囲が変わります。たとえば壁が斜めに並んで輪になっている場合、4方向では輪が閉じていると見なされて内側に色が留まります。8方向では斜めの隙間を通って外へ漏れます。

これはバグではなく、「つながっている」の定義の違いです。ゲームを作るときは、プレイヤーの移動規則と、判定に使う隣の定義をそろえる必要があります。縦横にしか歩けないキャラクターに8方向の判定を使うと、「歩いて行けないのに、つながっていると判定される」ずれが生じます。

最小のコードで広がり方を確かめる

次のコードは、4方向と8方向で塗れる範囲がどう違うかを並べて表示します。HTMLファイル1つに保存してブラウザで開けば動きます。. が空きマス、# が壁、* が塗られたマスです。

<pre id="out"></pre>
<script>
const map = ["..#....", ".#.#...", "..#....", "......."];
const H = map.length, W = map[0].length;
const D4 = [[1,0],[-1,0],[0,1],[0,-1]];
const D8 = D4.concat([[1,1],[1,-1],[-1,1],[-1,-1]]);
const copy = () => map.map(r => r.split(""));

function fill(g, r0, c0, dirs) {
  if (g[r0][c0] !== ".") return 0;
  let n = 1;
  const stack = [[r0, c0]];
  g[r0][c0] = "*";
  while (stack.length) {
    const [r, c] = stack.pop();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
      if (g[nr][nc] !== ".") continue;
      g[nr][nc] = "*";
      n++;
      stack.push([nr, nc]);
    }
  }
  return n;
}

function countAreas(dirs) {
  const g = copy();
  let areas = 0;
  for (let r = 0; r < H; r++)
    for (let c = 0; c < W; c++)
      if (fill(g, r, c, dirs) > 0) areas++;
  return areas;
}

let text = "";
for (const [name, dirs] of [["4方向", D4], ["8方向", D8]]) {
  const g = copy();
  const n = fill(g, 1, 2, dirs);
  text += name + ": 塗ったマス " + n + "\n";
  text += g.map(r => r.join("")).join("\n");
  text += "\n空き地の数: " + countAreas(dirs) + "\n\n";
}
document.getElementById("out").textContent = text;
</script>

開始マスは1行目・2列目（0から数えた位置）で、その上下左右はすべて壁です。実行する前に、4方向と8方向でそれぞれ何マス塗れるかを予想してみてください。予想と表示を照らし合わせれば、隣の定義がどう効くかを自分の目で確かめられます。あわせて、最後の「空き地の数」が4方向と8方向でどう変わるかも見てください。

起こりやすい誤り

• 塗る前に一覧へ入れてしまう：取り出したときに塗る書き方だと、同じマスが一覧に何度も入り、処理が重くなります。上のコードは一覧に入れる時点で塗って、二重に入ることを防いでいます。
• 盤面の端の確認を忘れる：範囲外の添字を読むと、エラーになるか、undefined との比較で意図しない動きになります。
• 自然に再帰で書いて深くなりすぎる：広い盤面で関数が自分自身を呼び続けると、ブラウザの呼び出し上限に達することがあります。上のように自前の一覧（スタック）を使えば避けられます。
• 塗った結果で元の盤面を壊す：判定だけしたいのに元データを塗りつぶすと、次の判定が狂います。上のコードのように、コピーに対して塗るのが安全です。

領域判定・連結判定・距離測定は同じ型の変形

塗りつぶしの骨組みは、少し変えるだけで別の問題を解きます。

• 連結判定：二点AとBがつながっているかを知るには、Aから塗って、Bが塗られたかを見ます。壁で隔てられていれば、Bは塗られません。
• 領域の数え上げ：盤面を端から走査し、未処理の空きマスに出会うたびに塗りつぶして、その回数を数えます。上のコードの countAreas がこの形で、島の数や部屋の数にそのまま使えます。
• 囲まれた領域の判定：盤面の外側の縁から塗りを始め、塗れなかった空きマスを「囲まれた内側」と見なします。陣取り系のゲームで「相手の石に完全に囲まれた場所」を探す考え方と同じ型です。
• 距離の測定：一覧の取り出し順を「先に入れたものから」に変えると、開始点に近いマスから順に広がります。各マスに「開始点から何歩目で届いたか」を記録すれば、最短の歩数が求まります。これは幅優先探索と呼ばれる方法で、上のコードのスタックを先入れ先出しの待ち行列に替えるだけで試せます。

塗れる範囲そのものは、スタックでも待ち行列でも変わりません。変わるのは広がる順番だけです。順番に意味を持たせたいとき（距離が欲しいとき）は待ち行列、範囲だけ分かればよいときはどちらでも構いません。

公式作品の設計から読み取れること

確認済みの仕様だけを手がかりに、この考え方が関わりそうな点を整理します。以下は「設計から読み取れること」であり、内部の実装を断定するものではありません。

潮だまりは、引き潮で浅瀬に海藻3つ、砂地に小石2つを置き、潮を切り替えて観察する作品です。8種の生きものが「上下左右の隣接条件」で現れると案内されています。ここから読み取れるのは、判定の単位が4方向の隣であり、斜めは含まないという点です。先ほどの表でいえば、4方向を採用した設計にあたります。条件が隣り合うマスだけで決まるのか、連なりまで考慮するのかは、作品を開いて置き方を変えながら確かめてください。

潮目のオセロには、返る石のプレビューがあります。オセロは石を置いたときに、8方向それぞれで相手の石を挟めるかを調べるゲームです。ここでの処理は塗りつぶしのように面で広がるのではなく、各方向へ一直線に進んで止まる形です。出発点が「8方向の隣」である点は塗りつぶしと共通で、広がり方が面か直線かが違います。置く前に結果を見せるプレビューがあることから、置く前の盤面で結果を計算できる作りであることが読み取れます。

月夜の配達には「残り最短距離」の表示があり、かたちのあいだには「次の一手のヒント（最短とは限らない）」があります。距離を求める方法として前節の幅優先探索が典型ですが、これらの作品が実際にどう計算しているかは案内されていません。両作品を遊びながら、表示される距離やヒントが一手ごとにどう変わるかを観察し、「隣へ広がる」考え方と結びつけてみてください。かたちのあいだでヒントが最短とは限らないと明記されている点は、手法の選び方に幅があることを示しています。

次の行動

まず上のコードを保存して実行し、4方向と8方向の結果を予想と照らし合わせてください。次に、stack.pop() を queue.shift() に替え、各マスに歩数を記録する形に書き換えて、開始点からの距離を表示してみてください。最後に潮だまりや月夜の配達を開き、隣の定義や距離の表示が遊びにどう効いているかを確かめてみてください。