幅優先探索で発生するメモリエラー

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
遊び人
記事: 42
登録日時: 2年前

幅優先探索で発生するメモリエラー

#1

投稿記事 by 遊び人 » 5ヶ月前

viewtopic.php?f=3&t=19902
過去にこちらでみけCAT様にご回答いただいたアルゴリズムを元に再び幅優先探索を作成したのですが、とあるところで「expression vector subscript out of range」のエラーが出てしまいます。
既にご回答いただいているので、自分の力で解決したかったのですが、一行一行デバッグをかけても、何故ここでエラーが発生しているのか私ではわかりませんでした・・・
またお力をお貸しください。

プレイヤーを追いかける敵のルートを探すのに使用しています。
OS:Windows10 コンパイラ:Visual Studio 2017

コード:

//chaser.cpp----------------------------------------------------------
// ルート初期化
void Chaser::initRoute(int msize_x, int msize_y) {
	for (int i = 0; i < msize_y; i++)
		for (int j = 0; j < msize_x; j++)
			route[i][j] = 0;
}

// ルートを算出
bool Chaser::search(int chaser_mx, int chaser_my, int player_mx, int player_my, const Map &map) {
	static std::vector<std::vector<int>> visited; // その場所が探索済みか
	static std::vector<std::vector<int>> from; // その場所にどっちに動いて来たか
	static bool init_flag = true;		
	if (init_flag) {	// 最初のみ実行する
		visited.resize(map.sizeY());
		from.resize(map.sizeY());
		for (int i = 0; i < map.sizeY(); i++) {
			visited[i].resize(map.sizeX());
			from[i].resize(map.sizeX());
		}
		init_flag = false;
	}
	struct queue_t {	// 探索場所を管理するキュー
		int x;
		int y;
		int from_dir;
	};

	//if (chase_flag) {
		// データを初期化
		initRoute(map.sizeX(), map.sizeY());
		for (int i = 0; i < map.sizeY(); i++) {
			std::fill(visited[i].begin(), visited[i].end(), 0);
			std::fill(from[i].begin(), from[i].end(), 0);
		}

		static const int d[4][2] = { { 0, -1 },{ 0, 1 },{ -1, 0 },{ 1, 0 } }; // 各方向の座標の差分
		std::vector<queue_t> queue(map.sizeX() * map.sizeY());
		int queue_start, queue_end; // キューの情報

		for (int i = 0; i < map.sizeY(); i++) {
			for (int j = 0; j < map.sizeX(); j++) {
				visited[i][j] = 0;
				from[i][j] = 0;
			}
		}
													  // スタート地点を探索済みにする
		visited[chaser_my][chaser_mx] = 1;
		from[chaser_my][chaser_mx] = -1; // どっちからも来ていないことを表すダミーの値
									 // キューを初期化する
		queue[0].x = chaser_mx;
		queue[0].y = chaser_my;
		queue[0].from_dir = 0; // どっちからも来ていないが、探索に使うので適当な有効な方向を入れる
		queue_start = 0;
		queue_end = 1;

		// キューが空でなく、かつゴールにたどりついていない間繰り返す
		while (queue_start < queue_end && visited[player_my][player_mx] == 0) {
			int now_x = queue[queue_start].x;
			int now_y = queue[queue_start].y;
			int now_from_dir = queue[queue_start].from_dir;
			queue_start++; // デキューする
						   // 各方向について探索する
			for (int i = 0; i < 4; i++) {
				int next_dir = (now_from_dir + i) % 4; // 移動した方向を優先して探索する
				int next_x = now_x + d[next_dir][0];
				int next_y = now_y + d[next_dir][1];
				// その方向に行けて、かつまだ行っていないなら
				if (map.passMap(chaser_mx + d[next_dir][1], chaser_my + d[next_dir][0]) && visited[next_y][next_x] == 0) {		// ←ここでエラー
					visited[next_y][next_x] = 1; // 行ったことにする
					from[next_y][next_x] = next_dir; // その時の方向を記録する
													 // エンキューする
					queue[queue_end].x = next_x;
					queue[queue_end].y = next_y;
					queue[queue_end].from_dir = next_dir;
					queue_end++;
				}
			}
		}
		// ゴールにたどりついていないならば、諦める
		if (visited[player_my][player_mx] == 0) return false;

		// スタートから目的地までの道にroute[y][x] = 1を代入する
		int now_x = player_mx, now_y = player_my;
		route[now_y][now_x] = 1;
		while (now_x != chaser_mx || now_y != chaser_my) {
			//記録した方向をもとに、逆に移動する
			int dir = from[now_y][now_x]; // now_xを書き換えるので、方向を記録しておかないとダメ
			now_x -= d[dir][0];
			now_y -= d[dir][1];
			route[now_y][now_x] = 1;
		}
		
		return true;
	//}
	return false;
}

//map.cpp-------------------------------------------------------------
// そのマップを通過できるか
bool Map::passMap(int x, int y) const {
	if (0 <= x && x < map_size_x && 0 <= y && y < map_size_y) {
		switch (map[y][x]) {
		case GRASS_ID:
		case CAVE_ID:
		case BRICK_ID:
		case GOAL_ID:
			return true;	// 通れる
		case GRASS_BLOCK_ID:
		case CAVE_BLOCK_ID:
		case BRICK_BLOCK_ID:
			return false;	// 通れない
		}
	}
	return false;
}

アバター
みけCAT
記事: 6190
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: 幅優先探索で発生するメモリエラー

#2

投稿記事 by みけCAT » 5ヶ月前

  • visitedおよびfromの初期化(リサイズ)を最初しかしていないので、
    小さいマップについて探索したあとに大きいマップについて探索すると不都合を起こします。
    毎回初期化するか、前回の探索とサイズが変わっていたら初期化するようにするといいでしょう。
  • 「ここでエラー」の行において、行こうとしている座標とは関係ない座標をmap.passMapに渡しているので、
    正常に行けるかどうか(ここに範囲外かどうかも含まれている)を判定できず、範囲外に行ってしまう原因になります。
    行こうとしているのは(x, y) = (next_x, next_y)なので、この座標をmap.passMapに渡すべきです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

遊び人
記事: 42
登録日時: 2年前

Re: 幅優先探索で発生するメモリエラー

#3

投稿記事 by 遊び人 » 5ヶ月前

next_x,yの存在を忘れて、謎の座標を渡しておりました・・・
まだまだ精進が足りないようです。

返信

“C言語何でも質問掲示板” へ戻る