再帰関数を利用した幅優先探索

Question

map上で、プレイヤーの位置からゴールの位置までの道のりを探索するアルゴリズムを書いてみたのですが、プログラムを実行中に強制終了してしまいます。
どこでエラーになっているのか、どうすれば直るのかお教えください。

#include <iostream>
using namespace std;

constexpr int MAP_SIZE = 5;	// マップの縦横のサイズ

// mapを描画
void display(const int map[MAP_SIZE][MAP_SIZE]) {
	for (int y = 0; y < MAP_SIZE; y++) {
		for (int x = 0; x < MAP_SIZE; x++) {
			switch (map[y][x]) {
				case 0: cout << "＿"; break;
				case 1: cout << "■"; break;
				case 2: cout << "me"; break;
				case 3: cout << "◆"; break;
			}
		}
		cout << endl;
	}
}

// その場所が通過できる場所か
bool passMap(const int map[MAP_SIZE][MAP_SIZE], const int x, const int y) {
	if (0 <= x && x < MAP_SIZE && 0 <= y && y < MAP_SIZE) {
		switch (map[y][x]) {
			case 1: return false; break;	// ■のみ通過不可
			default: return true; break;
		}
	}
	return false;
}

// 問題のアルゴリズム
// ゴールまでの道のりを探索する　幅優先探索
bool searchRoute(const int map[MAP_SIZE][MAP_SIZE], int route[MAP_SIZE][MAP_SIZE], int sx, int sy, int gx, int gy) {
	if (!passMap(map, sx, sy)) return false;
	route[sy][sx] = 1;
	if (sx == gx && sy == gy) return true;
	if (searchRoute(map, route, sx, sy-1, gx, gy)) return true;
	if (searchRoute(map, route, sx, sy+1, gx, gy)) return true;
	if (searchRoute(map, route, sx-1, sy, gx, gy)) return true;
	if (searchRoute(map, route, sx+1, sy, gx, gy)) return true;
	route[sy][sx] = 0;
	return false;
}

int main() {
	// 0:道 1:壁 2:自分 3:ゴール
	int map[MAP_SIZE][MAP_SIZE] = {
		{0, 2, 0, 0, 0},
		{0, 0, 1, 0, 0},
		{0, 1, 0, 0, 0},
		{0, 0, 0, 1, 0},
		{0, 0, 1, 3, 0}
	};

	display(map);
	int route[MAP_SIZE][MAP_SIZE];	// 道のりを保存する配列
	for (int i = 0; i < MAP_SIZE; i++) {
		for (int j = 0; j < MAP_SIZE; j++)
			route[i][j] = 0;
	}
	searchRoute(map, route, 1, 0, 3, 4);
	cout << endl;
	display(route);

	return 0;
}

Comments

[dice142]

エラー文を質問文に追記してください。

[asobinin]

エラー文は出ません・・・
唐突に強制終了してしまいます。

Answer 1

確かに途中で、突然、止まるようですね。
ちょっと途中経過を出力してみたら、
sy の値が -1 になっています。

ソースを見直してみると、sx, sy の範囲チェックが無いですね。
きっとメモリを壊しているのでしょう。

[追記]
範囲外を除くようにしてみましたが、やはり、再帰が終わらないようです。
...と初期データを見ると、スタートから、スタートに戻ってくるループがある。
これを弾くようにしないと無限ループ。。正確には、同じ場所を二度通らないようにする必要があります。

passMap() の引数に route を追加し、最初のif 文の中を以下のようにして、動作を確認。
(searchRoute()にも範囲外チェック追加あり)

    if (0 <= x && x < MAP_SIZE && 0 <= y && y < MAP_SIZE) {
		return ((map[y][x] != 1) && (route[y][x] != 1));

遠回りなルートを通っていますが、一応、ゴールまで行くみたい。

Comments

[asobinin]

無事動作しました、ありがとうございます。
幅優先探索で、一度通った場所に戻ってこないようにするというところを忘れていたみたいですね・・・
この再帰関数では、最短のルートではなく、一番最初に見つかったルートを返すので最短ではない可能性がある + 関数の呼び出しコストが掛かってしまうため、コード量が少ないという利点はありますがゲームなどでは利用しづらいもののようです。もう少し工夫しなければ実践では使える場所が限定されてしまいそうです。

協力してくださった皆様、ありがとうございました。

Answer 2

再帰でメモリあふれてるのではないかと
searchRouteの終了条件確認したほうが良いと思いますね

Comments

[asobinin]

やはり再帰回数の問題なのかもしれません・・・
一度再帰を利用せずに探索関数を作ってみます。

[iwanote]

if (searchRoute(map, route, sx, sy-1, gx, gy)) return true;
if (searchRoute(map, route, sx, sy+1, gx, gy)) return true;
ここでループしてる可能性とかありませんか？

Answer 3

display 関数でもmain関数でも

cout << endl;

が何もコンソールに表示していないから、強制終了しているように勘違いしている可能性はありませんか？

Comments

[asobinin]

cout << endl;は単なる改行文字を出力しているだけです。
強制終了はsearchRouteの実行中に発生してしまいます。

[kts_h]

強制終了だというのは、何によって分かるのですか。

[asobinin]

実行すると、しばらくコンソールがフリーズした後、破壊されてしまいます。
何度試しても同じ結果でした。

[kts_h]

何が破壊されるのですか。現象を具体的に説明してもらえませんか。

[otn]

> 破壊されてしまいます。
コンソールが閉じてしまうという意味？ちょっと想像しがたいですが。

[otn]

主観を交えずに客観的な状況を書いてください。

[asobinin]

状況としましては、
実行→searchRouteの呼出(ここでフリーズすることは確認しました)→２~３秒コンソールがフリーズ→
ウィンドウが突然閉じるという流れです。
破壊というのは、exit(1)を呼び出したような、コンソールが異常終了してしまう状態のことを言っていました・・・
私も主観ですが、コンソールアプリケーションでは珍しいバグだと感じました。

[otn]

端末ウィンドウで、プログラムを起動して、そのプログラムがどうなろうが、端末まで閉じてしまうというのは非常に考えにくいです。OSはWindows? Linux? MacOS?
Linux/Macで、シェルから「exec プログラム名」で起動しているわけではないですよね？