はじめに
本ドキュメントはA*アルゴリズムについて記述したドキュメントである。
A*アルゴリズムとは
A*アルゴリズムとは昨年度のMIRS1404で実装予定であったが工数がかかりすぎると某先生の反対を受けお蔵入りになったアルゴリズムである。
要約するとスタートからゴールまで障害物をよけて進むアルゴリズムである。今回はCartesian座標系についてこれを適用する。
詳細については:https://ja.wikipedia.org/wiki/A*
MIRS2014の競技場の概図を以下に示す。
fig.1 競技場概図
上図のように競技場のタイルについて座標系を設定する。
そして座標をノードとし、それぞれのノードの上下左右をエッジで結べば模式的に競技場を無向グラフとして表現可能である。
今回はこれを利用してA*アルゴリズムを適用する。
これによりスタートからゴールまでの座標のみで移動経路を決定出来るため、シーケンスで動かすよりは自律移動している気分に浸れると思います。
実装例
C++による実装例とその実行結果を以下に示す。
Astar.cpp
/**
Copyright(c) 2015 d11120
Released under the MIT license
http ://opensource.org/licenses/mit-license.php
*/
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
enum State {
CLOSE, //0
SEMI_OPEN, //1
OPEN, //2
SEARCHED, //3
SEMI_SELECTED,//4
SELECTED, //5
FORBIDDEN, //6
};//end enum State
struct Anode {
State state;
int ActualCost;
int HeuristicCost;
int Score;
};//end struct Anode
void ChangeStateCL(Anode* np) {
if (np->state != FORBIDDEN) np->state = CLOSE;
}//end method ChangeStateC
void ChangeStateSO(Anode* np) {
if (np->state != FORBIDDEN) np->state = SEMI_OPEN;
}//end merhod ChangeStateSO
void ChangeStateOP(Anode* np) {
if (np->state != FORBIDDEN) np->state = OPEN;
}//end method ChangeStateOP
void ChangeStateFB(Anode* np) {
if (np->state != FORBIDDEN) np->state = FORBIDDEN;
}//end method ChangeStateFB
void ChangeStateSR(Anode* np) {
if (np->state != FORBIDDEN) np->state = SEARCHED;
}//end method ChangeStateS
void ChangeStateSS(Anode* np) {
if (np->state != FORBIDDEN) np->state = SEMI_SELECTED;
}//end method ChangeStateSS
void ChangeStateSL(Anode* np) {
if (np->state != FORBIDDEN) np->state = SELECTED;
}//end method ChangeStateSL
int search(Anode* np, int n, int x0, int y0, int ex, int ey) {
if (np->state != FORBIDDEN) {
np->ActualCost = n;
np->HeuristicCost = (abs(ex - x0) + abs(ey - y0));
np->Score = (np->ActualCost + np->HeuristicCost);
ChangeStateSR(np);
return np->Score;
}//end if
else return -1;
}//end function search
int main() {
int X, Y;
cout << "フィールドの広さを入力:(x y) => " << flush;
cin >> X >> Y;
Anode ** anode = new Anode*[X + 2];
for (int j = 0; j<X + 2; j++) {
anode[j] = new Anode[Y + 2];
}//end for j
for (int i = 0; i<X + 2; i++) {
for (int j = 0; j<Y + 2; j++) {
ChangeStateCL(&anode[i][j]);
anode[i][j].ActualCost = 0;
anode[i][j].HeuristicCost = 0;
anode[i][j].Score = 0;
}//end for j
}//end for i
for (int n = 0; n<X + 2; n++) {
ChangeStateFB(&anode[n][0]);
ChangeStateFB(&anode[n][Y + 1]);
}//end for n
for (int n = 0; n<Y + 2; n++) {
ChangeStateFB(&anode[0][n]);
ChangeStateFB(&anode[X + 1][n]);
}//end for n
int k;
cout << "ブロックの数を入力 => " << flush;
cin >> k;
for (int n = 0; n<k; n++) {
int fx, fy;
cout << "ブロックの座標を入力:(x y) => " << flush;
cin >> fx >> fy;
if (0<fx && fx <= X && 0<fy && fy <= Y) ChangeStateFB(&anode[fx][fy]);
}//end n
int x0, y0;
cout << "始点を入力:(x y) => " << flush;
cin >> x0 >> y0;
int ex, ey;
cout << "終点を入力:(x y) => " << flush;
cin >> ex >> ey;
int cnt = 0;
ChangeStateOP(&anode[x0][y0]);
do {
int i, j;cnt++;
for (i = 1; i <= X; i++) {
for (j = 1; j <= Y; j++) {
if (anode[i][j].state == OPEN) {
search(&anode[i][j], cnt, i, j, ex, ey);
if (anode[i - 1][j].state != SEARCHED) ChangeStateSO(&anode[i - 1][j]);//left
if (anode[i][j + 1].state != SEARCHED) ChangeStateSO(&anode[i][j + 1]);//up
if (anode[i + 1][j].state != SEARCHED) ChangeStateSO(&anode[i + 1][j]);//right
if (anode[i][j - 1].state != SEARCHED) ChangeStateSO(&anode[i][j - 1]);//down
}//end if
}//end for j
}//end for i
for (i = 1; i <= X; i++) {
for (j = 1; j <= Y; j++) {
if (anode[i][j].state == SEMI_OPEN) {
ChangeStateOP(&anode[i][j]);
}
}//end for j
}//end for i
} while (anode[ex][ey].state != SEARCHED);
cout << endl;
cout << "**start search**" << endl;
ChangeStateSS(&anode[ex][ey]);
for (int n = cnt; 0<n; n--) {
int i = 0, j = 0;
for (i = 1; i <= X; i++) {
for (j = 1; j <= Y; j++) {
if (anode[i][j].state == SEMI_SELECTED) {
ChangeStateSL(amp&anode[i][j]);
goto flagB;
}//end if
}//end for j
}//end for i
flagB:
cout << "-------(" << i << "," << j << ")-------" << endl;
vector<int> VtrScore;
vector<int> VtrActualCost;
if (anode[i - 1][j].state == SEARCHED && anode[i - 1][j].ActualCost == n - 1) {
VtrScore.push_back(anode[i - 1][j].Score);
VtrActualCost.push_back(anode[i - 1][j].ActualCost);
}//end if
if (anode[i][j + 1].state == SEARCHED && anode[i][j + 1].ActualCost == n - 1) {
VtrScore.push_back(anode[i][j + 1].Score);
VtrActualCost.push_back(anode[i][j + 1].ActualCost);
}//end if
if (anode[i + 1][j].state == SEARCHED && anode[i + 1][j].ActualCost == n - 1) {
VtrScore.push_back(anode[i + 1][j].Score);
VtrActualCost.push_back(anode[i + 1][j].ActualCost);
}//end if
if (anode[i][j - 1].state == SEARCHED && anode[i][j - 1].ActualCost == n - 1) {
VtrScore.push_back(anode[i][j - 1].Score);
VtrActualCost.push_back(anode[i][j - 1].ActualCost);
}//end if
if (!(VtrScore.empty()) && !(VtrActualCost.empty())) {
sort(VtrScore.begin(), VtrScore.end());
int minScore = VtrScore.front();
sort(VtrActualCost.begin(), VtrActualCost.end());
int minActualCost = VtrActualCost.front();
if (anode[i - 1][j].Score == minScore && anode[i - 1][j].ActualCost == minActualCost) {
ChangeStateSS(amp&anode[i - 1][j]);
}//end else if
else if (anode[i][j + 1].Score == minScore && anode[i][j + 1].ActualCost == minActualCost) {
ChangeStateSS(amp&anode[i][j + 1]);
}//end else if
else if (anode[i + 1][j].Score == minScore && anode[i + 1][j].ActualCost == minActualCost) {
ChangeStateSS(amp&anode[i + 1][j]);
}//end else if
else if (anode[i][j - 1].Score == minScore && anode[i][j - 1].ActualCost == minActualCost) {
ChangeStateSS(amp&anode[i][j - 1]);
}//end else if
else {
cout << "unexpected situation" << endl;
}//end else
}//end if
}//end for n
cout << "***end search***" << endl;
cout << endl;
for (int j = Y; 0<j; j--) {
for (int i = 1; i<X + 1; i++) {
if (anode[i][j].state == SELECTED) {
cout << "☆ " << flush;
}//end if
else if (anode[i][j].state == FORBIDDEN) {
cout << "■ " << flush;
}//end else if
else {
cout << "□ " << flush;
}//end else if
}//end for i
cout << endl;
}//end for j
for (int n = 0; n<X + 2; n++) {
delete[] anode[n];
}//end for n
delete[] anode;
return 0;
}
fig.2 実行結果
プログラム
以下にプログラムのリンクを示す。
Astar.cpp