経緯
TerrariaやDQ Buildersなどで一定の条件を満たすと、壁やドアで囲まれた空間が部屋として認識され、プレイヤーにあるメリットを与えられますよね？
それを見ているうちに「部屋認識はどうやって出来たんだろう」と疑問が出てしまいました。
しかし、色々探したのですが、この機能についての文章や説明はあまりないのようです。
一番の疑問は「どうやって囲まれた空間を識別しているんだろう？」という点ですよね？
偶然、wikipediaで読んだflood fillアルゴリズムがここで使えそうので、今回はそれを使って実験してみました。
Flood fillとは
Flood fillは色々な画像編集ツール（例えば、windowsのペイント）にある「塗りつぶし」機能で使われているアルゴリズムです。
この機能を使ったことがある方は既に思い付いたと思いますが、クリックしたピクセルと繋がっている同じ色の区域しか色を塗らない機能です。
つまり、下図のような感じで、囲まれた空間を識別することが出来ます。
Flood fill、実はかなり簡単です。
パフォーマンス改善のため、バリエーションは大勢ありますが、今回は一番理解しやすい再帰を使っている方法で原理を説明します。
現在処理しているポイントをnといいます：
0. あるスタートポイントをnにします。
1. もしnが既に処理済みであれば、以下の処理を全部スキップして戻ります。
2. もしnが処理すべきポイントとして認識する条件（壁ではないこと、色が指定値であることなど）を満たせなければ、以下の処理を全部スキップして戻ります。
3. nを処理すべきポイントとして認識し、処理を行います（あるエリア（壁に囲まれた領域）に所属するポイントリストに追加、色を指定値に変更するなど）。
4. nを処理済みとマークします。
5. n下のポイントをnとして1から実行し直します。
6. n左のポイントをnとして1から実行し直します。
7. n上のポイントをnとして1から実行し直します。
8. n右のポイントをnとして1から実行し直します。
簡単なflood fill実装例
再帰を使って、実際のコードも非常に簡単です。
void FloodFill(Node node, Predicate<Node> shouldProcess, Action<Node> process)
{
if (node.IsProcessed) return;
if (!shouldProcess(node)) return;
process(node);
node.IsProcessed = true;
foreach (Node neighbour in node.Neighbours)
{
FloodFill(neighbour, shouldProcess, process);
}
}
部屋認識
では、部屋認識においてどうやってflood fillを応用するんでしょうか？
実はそれもとても簡単です。
上記のコードを使う場合、マップ上全部のポイントを一つずつnodeに入れ、shouldProcessに壁かどうかの判断ロジックを入れ、
processに応じるエリアのポイントリストに追加する・エリア情報を更新するロジックを入れて実行すればマップにあるエリアが全部識別されます。
その後、エリア毎に部屋として認識する条件（例えば、ライトがあるかどうか、エリアサイズが合っているかどうかなど）に満たしているかどうかをチェックすれば完了です。
例
void ScanForHouses(Map map)
{
List<Area> areas = new List<Area>();
foreach (Node node in map.Nodes)
{
Area area = null;
FloodFill(node, n => !n.IsWall, n =>
{
if (area == null) area = new Area();
area.Nodes.Add(n);
if (n.IsLight) area.LightCount++;
});
if (area != null) areas.Add(area);
}
foreach (Area area in areas)
{
// ライトが一つ以上、サイズが10～100間のエリアを部屋として認識します
area.IsHouse = area.LightCount > 0 && area.Nodes.Count > 10 && area.Nodes.Count < 100;
}
}
結論
案外簡単に部屋認識を実装できました。
もちろん、再帰でflood fillを実装するのがパフォーマンス的にいいとは言えません。Stack overflowする可能性もあります。
その場合、再帰ではなく、stackやqueueを使ってflood fillを実装すれば大体解決出来ます。どちらも結構簡単です。
もっと詳しいの話や他の実装バリエーションを知りたい方はレファレンスを読めばいいと思います。基本的な原理が変わることがありません。