複雑な障害物を迂回してゴールにたどり着きたい

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

複雑な障害物を迂回してゴールにたどり着きたい

#1

投稿記事 by 遊び人 » 6年前

お世話になっております。
ゲームのAI(Artificial incompetence)を作りたいと考えているのですが、目的地への移動がうまく出来ずにいます。
先に目的地へのルートを見つけた後でそれに沿って移動するという予定なのですが、
複雑な障害物がある場合、どのようなアルゴリズムを組めば良いのかわかりません(´・ω・`)
ご助言お願い致します。

プレイヤー(スタート地点)は上下左右に一マスずつ移動できます。

コード:

#include <iostream>
using namespace std;

constexpr int FIELD_SIZE = 6;

void Display(int field[FIELD_SIZE][FIELD_SIZE]);
bool Search(int map[FIELD_SIZE][FIELD_SIZE], int route[FIELD_SIZE][FIELD_SIZE], int start_x, int start_y, int goal_x, int goal_y);
bool CanPassField(int map[FIELD_SIZE][FIELD_SIZE], int x, int y, int distance);

int main() {
	int map[FIELD_SIZE][FIELD_SIZE] = {
		{ 0, 0, 0, 0, 0, 0 },
		{ 0, 1, 0, 0, 1, 0 },
		{ 2, 0, 1, 0, 0, 1 },
		{ 0, 0, 1, 1, 0, 0 },
		{ 0, 0, 0, 1, 0, 3 },
		{ 0, 1, 0, 0, 1, 0 },
	};
	int route[FIELD_SIZE][FIELD_SIZE];
	for (int i = 0; i < FIELD_SIZE; i++)
		for (int j = 0; j < FIELD_SIZE; j++)
			route[i][j] = 0;

	Display(map);
	cout << endl;
	if (Search(map, route, 0, 2, 5, 4) == true)
		Display(route);
	else
		cout << "ゴールへの道がありませんでした。" << endl;

	return 0;
}

// フィールドを描画する----------------------------------------------------------------------------
void Display(int field[FIELD_SIZE][FIELD_SIZE]) {
	int i, j;

	for (i = 0; i < FIELD_SIZE; i++) {
		for (j = 0; j < FIELD_SIZE; j++) {
			switch (field[i][j]) {
			case 0:
				cout << "□";	// 通過できる道
				break;
			case 1:
				cout << "■";	// 通過できない道
				break;
			case 2:
				cout << "S ";	// スタート(自分がいる場所)
				break;
			case 3:
				cout << "G ";	// 目的地
				break;
			default:
				cout << "  ";
				break;
			}
		}
		cout << endl;
	}
}

// 目的地へのルートを探索する----------------------------------------------------------------------
bool Search(int map[FIELD_SIZE][FIELD_SIZE], int route[FIELD_SIZE][FIELD_SIZE]
			, int start_x, int start_y, int goal_x, int goal_y) {
	int distance_x, distance_y;
	int now_x = start_x, now_y = start_y;	// 現在いる場所
	bool can_goal_flag = false;

	// スタートから目的地までの道にroute[y][x] = 1を代入する
	route[now_y][now_x] = 1;
	while (1) {
		// 通常移動
		if (now_y > goal_y && CanPassField(map, now_x, now_y, 0) == 0) {		// 上
			now_y--;
			route[now_y][now_x] = 1;
		}
		if (now_y < goal_y && CanPassField(map, now_x, now_y, 1) == 0) {		// 下
			now_y++;
			route[now_y][now_x] = 1;
		}
		if (now_x > goal_y && CanPassField(map, now_x, now_y, 2) == 0) {		// 左
			now_x--;
			route[now_y][now_x] = 1;
		}
		if (now_y < goal_y && CanPassField(map, now_x, now_y, 3) == 0) {		// 右
			now_x++;
			route[now_y][now_x] = 1;
		}

		// ゴールにたどり着いたらbreak
		if (route[goal_y][goal_x] == 1) {
			can_goal_flag = true;
			break;
		}
		// ゴールへの道がなかったらbreak
	}

	return can_goal_flag;
}

// 移動したい場所が通過できる場所か確認(distance 0:上 1:下 2:左 3:右)
// 戻り値-通れる:0 通れない:1 
bool CanPassField(int map[FIELD_SIZE][FIELD_SIZE], int x, int y, int distance) {
	switch (distance) {
	case 0:										// 上
		if (y > 0 && map[y - 1][x] != 1)
			return 0;
		else
			return 1;
		break;
	case 1:										// 下
		if (y < FIELD_SIZE - 1 && map[y + 1][x] != 1)
			return 0;
		else
			return 1;
		break;
	case 2:										// 左
		if (x > 0 && map[y][x - 1] != 1)
			return 0;
		else
			return 1;
		break;
	case 3:										// 右
		if (x < FIELD_SIZE - 1 && map[y][x + 1] != 1)
			return 0;
		else
			return 1;
		break;
	default:
		return 1;
	}
}

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

Re: 複雑な障害物を迂回してゴールにたどり着きたい

#2

投稿記事 by みけCAT » 6年前

例えば、幅優先探索をするといいと思います。

コード:

// 目的地へのルートを探索する----------------------------------------------------------------------
bool Search(int map[FIELD_SIZE][FIELD_SIZE], int route[FIELD_SIZE][FIELD_SIZE]
			, int start_x, int start_y, int goal_x, int goal_y) {
	static const int d[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 各方向の座標の差分
	struct queue_t {
		int x, y; // 座標
		int from_dir; // どっちに動いて来たか
	} queue[FIELD_SIZE * FIELD_SIZE]; // 探索場所を管理するキュー
	int queue_start, queue_end; // キューの情報

	int visited[FIELD_SIZE][FIELD_SIZE] = {{0}}; // その場所が探索済みか
	int from[FIELD_SIZE][FIELD_SIZE] = {{0}}; // その場所にどっちに動いて来たか

	// スタート地点を探索済みにする
	visited[start_y][start_x] = 1;
	from[start_y][start_x] = -1; // どっちからも来ていないことを表すダミーの値
	// キューを初期化する
	queue[0].x = start_x;
	queue[0].y = start_y;
	queue[0].from_dir = 0; // どっちからも来ていないが、探索に使うので適当な有効な方向を入れる
	queue_start = 0;
	queue_end = 1;

	// キューが空でなく、かつゴールにたどりついていない間繰り返す
	while (queue_start < queue_end && visited[goal_y][goal_x] == 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 (CanPassField(map, now_x, now_y, 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[goal_y][goal_x] == 0) return false;

	// スタートから目的地までの道にroute[y][x] = 1を代入する
	int now_x = goal_x, now_y = goal_y;
	route[now_y][now_x] = 1;
	while (now_x != start_x || now_y != start_y) {
		// 記録した方向をもとに、逆に移動する
		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;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

かずま

Re: 複雑な障害物を迂回してゴールにたどり着きたい

#3

投稿記事 by かずま » 6年前

再帰呼出しを使うやり方もあります。

コード:

#include <iostream>
using namespace std;
 
constexpr int FIELD_SIZE = 6;
 
void Display(int field[FIELD_SIZE][FIELD_SIZE])
{
    for (int i = 0; i < FIELD_SIZE; i++, endl(cout))
        for (int j = 0; j < FIELD_SIZE; j++)
            switch (field[i][j]) {
            case 0: cout << "□"; break; // 通過できる道
            case 1: cout << "■"; break; // 通過できない道
            case 2: cout << "S "; break; // スタート(自分がいる場所)
            case 3: cout << "G "; break; // 目的地
            default: cout << "  "; break;
            }
}
 
bool CanPassField(int map[FIELD_SIZE][FIELD_SIZE],
        int route[FIELD_SIZE][FIELD_SIZE], int x, int y)
{
    return x < 0 || x >= FIELD_SIZE || y < 0 || y >= FIELD_SIZE
        || map[y][x] == 1 || route[y][x] == 1;
}

bool Search(int map[FIELD_SIZE][FIELD_SIZE], int route[FIELD_SIZE][FIELD_SIZE],
        int x, int y, int goal_x, int goal_y)
{
    if (CanPassField(map, route, x, y)) return false;
    route[y][x] = 1;
    if (x == goal_x && y == goal_y) return true;
    if (Search(map, route, x, y-1, goal_x, goal_y)) return true;
    if (Search(map, route, x, y+1, goal_x, goal_y)) return true;
    if (Search(map, route, x-1, y, goal_x, goal_y)) return true;
    if (Search(map, route, x+1, y, goal_x, goal_y)) return true;
    route[y][x] = 0;
    return false;
}
 
int main()
{
    int map[FIELD_SIZE][FIELD_SIZE] = {
        { 0, 0, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 1, 0 },
        { 2, 0, 1, 0, 0, 1 },
        { 0, 0, 1, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 3 },
        { 0, 1, 0, 0, 1, 0 },
    };
    int route[FIELD_SIZE][FIELD_SIZE] = { 0 };
 
    Display(map);
    cout << endl;
    if (Search(map, route, 0, 2, 5, 4))
        Display(route);
    else
        cout << "ゴールへの道がありませんでした。\n";
}
最初に見つかったルートを返すので、
最短とはならないこともあります。

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

Re: 複雑な障害物を迂回してゴールにたどり着きたい

#4

投稿記事 by 遊び人 » 6年前

無事解決できました、ありがとうございます!
分かりやすくコメントを付けてくださいありがとうございます。
本格的なアルゴリズムというものを見たことがなかったので衝撃的でした。

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

Re: 複雑な障害物を迂回してゴールにたどり着きたい

#5

投稿記事 by 遊び人 » 6年前

再帰を用いると物凄くシンプルになりますね。
CanPassFieldの最適化もありがとうございます。
やっぱりswitchで長々と書くのは綺麗ではないですね。

返信

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