合計 昨日 今日

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

[このトピックは解決済みです]

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: 遊び人
[URL]
かけだし(1,486 ポイント)
Date: 2018年1月04日(木) 02:33
No: 1
(OFFLINE)

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

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

プレイヤー(スタート地点)は上下左右に一マスずつ移動できます。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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;
    }
}

Name: みけCAT
[URL]
伝説なるハッカー(690,092 ポイント)
Date: 2018年1月04日(木) 06:56
No: 2
(ONLINE)

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

例えば、幅優先探索をするといいと思います。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 目的地へのルートを探索する----------------------------------------------------------------------
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で殴ればいい!(死亡フラグ)

Name: かずま
[URL]
Date: 2018年1月04日(木) 19:16
No: 3
(OFFLINE)

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

再帰呼出しを使うやり方もあります。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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";
}

最初に見つかったルートを返すので、
最短とはならないこともあります。

Name: 遊び人
[URL]
かけだし(1,486 ポイント)
Date: 2018年1月04日(木) 19:19
No: 4
(OFFLINE)

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

[解決!]

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

Name: 遊び人
[URL]
かけだし(1,486 ポイント)
Date: 2018年1月04日(木) 19:24
No: 5
(OFFLINE)

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

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


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[16人]