ゲームの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;
}
}