フラッドフィル
種となる1点から、同じ色でつながった領域を塗りつぶす手法。ペイントツールの「バケツ」である。
1点を塗り替え、元の色を共有する隣接ピクセルへ広げていく。斜めを含めるかどうかは4近傍か8近傍かで決まる。素朴な再帰版は広い領域でスタックを使い果たすため、実際にはスキャンライン方式や、キュー・スタックを使う版が使われる。
同じアルゴリズムが、マインスイーパーの盤面開放、画像解析での連結成分のラベリング、手続き生成レベルでの部屋の判定にも使われる。理屈は単純だが、実装は例外だらけだ。とくに「同じ色」の線引きをどこでするかが厄介である。