C言語でのFlood Fill実装 #Flood-Fill

経緯:

C言語で３Dゲームを実装しました。
その実装のなかでFlood Fillが有効的な手段だと思い、調べてみたのですがC言語でFlood Fillを実装している記事がなかったので簡単にまとめました。

＜やりたいこと＞
以下のようなmapを読み取り、このmap通りに３Dゲームを描写する。

(補足：１が壁。０が移動可能。Pがplayerの位置。)

上記のような縦と横が揃っている長方形のmapは
① 1行ずつreadで読み込む
② 2行目以降、1行目との長さが同じ、かつmapが１で囲まれているか

を判定し、実現できました。

しかし、


        1111111111111111111111111
        1000000000110000000000001
        1011000001110000000000001
        1001000000000000000000001
111111111011000001110000000000001
100000000011000001110111111111111
11110111111111011100000010001
11110111111111011101010010001
11000000110101011100000010001
10000000000000001100000010001
10000000000000001101010010001
11000001110101011111011110P0111
11110111 1110101 101111010001
11111111 1111111 111111111111

上記のようなmapではうまくmapが読み取れずエラーとして処理されてしまっていました。本来であれば上記のmapは１で囲まれているため正常に起動してほしいです。
そこで思いついたのがFlood fillのアルゴリズムを使用する方法でした。

方法としては
①playerの位置から塗りつぶしを始める
②塗りつぶした箇所は他の記号でマーク
③1が来たら壁なのでそれ以降（mapの外）は塗りつぶさない

という手順でした。

flood fillアルゴリズム実装:

では実際にどういう実装にしたのか記載していきます。


typedef struct s_flood_fill
{
	char	**map;
	int		num_rows;
	int		num_cols;
	bool	is_enclosed;
}	t_flood_fill;

構造体定義１：
flood_fill:マップ（二次元配列）、マップの行数と列数、領域が完全に囲まれているかどうかを示すフラグを含む。

typedef struct s_point {
	double	x;
	double	y;
}	t_point;

構造体定義２：
t_point player_pos: プレイヤーの現在位置を表す構造体。xとy座標を持つ。

void	flood_fill(t_flood_fill *data, int x, int y)
{
	if (x < 0 || y < 0 || data->num_rows <= x || data->num_cols <= y)
	{
		data->is_enclosed = false;
		return ;
	}
	if (data->map[y][x] != '0')
		return ;
	data->map[y][x] = '*';
	flood_fill(data, x + 1, y);
	flood_fill(data, x - 1, y);
	flood_fill(data, x, y + 1);
	flood_fill(data, x, y - 1);
}

flood_fill関数の引数:

上記で定義したflood_fill構造体、int x, int y: 現在の探索位置（マップ上のx座標とy座標）を引数にとる関数を作成。

アルゴリズムの動作:

境界条件のチェック: 関数はまず、現在の探索位置がマップの範囲外であるかどうかを確認。範囲外の場合は、領域が完全に囲まれていないことを意味するので、data->is_enclosedフラグをfalseに設定し、関数を終了。
対象外のセルのチェック: 探索位置がマップの範囲内である場合、そのセルが既に塗りつぶされているか、塗りつぶし対象外であるかをチェック。対象外であれば、そのセルの処理をスキップし、関数を終了。
セルの塗りつぶし: 対象のセル（'0'で表されるセル）を見つけた場合、それを別の値（私は'*'に指定）に変更して、セルが塗りつぶされたことをマーク。
隣り合うセルの探索: 現在のセルを塗りつぶした後、再帰的に上下左右の隣接セルに対してflood fillを実行。

void	perform_flood_fill(t_flood_fill *data,
		t_point player_pos, char player_char)
{
	data->map[(int)player_pos.y][(int)player_pos.x] = '0';
	flood_fill(data, (int)player_pos.x, (int)player_pos.y);
	data->map[(int)player_pos.y][(int)player_pos.x] = player_char;
	if (!data->is_enclosed)
		error_message("Map is not fully enclosed by walls ('1').");
}

perform_flood_fill関数の引数:

上記で定義したflood_fill構造体, t_point構造体,char player_char: プレイヤーをマップ上で表す文字を引数にとる関数を作成。

関数の動作:

プレイヤー位置の初期化: プレイヤーの現在位置にあるマップのセルを一時的に'0'に設定。（これにより、flood fillアルゴリズムがこの位置から開始して、連続する領域を塗りつぶすことができる。）
flood fillの実行: flood_fill関数を呼び出して、プレイヤーの位置から連続する領域を塗りつぶす。
（マップ内の連続する'0'のセルを探索し、それらを'*'などの別の値でマーク。）
プレイヤー位置の復元: flood fillの実行後、プレイヤーの位置にあるセルの値をplayer_charに戻して、プレイヤーの位置をマップ上に再描画。
⇧戻すことを忘れずに！
領域の完全な囲まれ具合のチェック: flood_fill関数の実行中にマップの端に達するなどして領域が完全に囲まれていないことが判明した場合、data->is_enclosedフラグがfalseに設定される。（エラー処理）

このような流れで長方形に限らず様々なmapに対応した3Dゲームを実装することができました。
最後までお読みいただきありがとうございました！

注意点：
再帰的なアプローチはスタックオーバーフローを引き起こす可能性があるので、非常に大きなマップでの使用には適していません。
（実際に1000×1000などの大きなデータを入れるとセグフォしました。。。）
スタックを使用しない反復的なアプローチや、再帰の深さを制限する方法を検討する必要があると思います。