2Dゲーム向けにA*(エースター)を再コーディングしたよー
先日のA*アルゴリズムの実装を、標準テンプレート抜きで書き直してみました。
以下プログラム。
#define WIDTH (25) #define HEIGHT (10) #define GX (15) #define GY (8) #define SX (3) #define SY (2) enum { SEARCH_NO_CHECK = 0, SEARCH_OPEN = 1, SEARCH_CLOSE = 2, }; typedef struct { int x; int y; } POINT; // 8方向のベクトル設定 POINT CheckMatrix[] = { { 0, 1 }, // 0 { -1, 1 }, // 1 { -1, 0 }, // 2 { -1, -1 }, // 3 { 0, -1 }, // 4 { 1, -1 }, // 5 { 1, 0 }, // 6 { 1, 1 }, // 7 }; typedef struct { int no; int chip; int status; int event_no; int cost; int SearchStatus; // 0:未調査 1:オープン 2:クローズ int parent; // 親の向き } mapcell; mapcell data[HEIGHT][WIDTH]; int def_data[HEIGHT][WIDTH] = { { 0, 0, 0, 0, 0, 0, 0,-1,0, 0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0,-1,0,-1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0,-1,0,-1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }, { 0,-1,-1,-1,-1, -1, 0,-1,0,-1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, -1, 0,-1,0,-1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, -1,-1,-1,0,-1, 0,0,0,0,-1, -1,-1,-1,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0,-1,0,-1, 0,0,0,0,-1, 0, 0, 0,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0,-1,0,-1, 0,0,0,0,-1, 0, 0,-1,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0,-1,0,-1, 0,0,0,0,-1, 0, 0,-1,0,0, 0,0,0,0,0, }, { 0, 0, 0, 0, 0, 0, 0, 0,0,-1, 0,0,0,0,-1, 0, 0,-1,0,0, 0,0,0,0,0, }, }; void ResetSearchStatus(void) { for(int h = 0; h < HEIGHT; h++){ for(int w = 0; w < WIDTH; w++){ data[h][w].cost = 0; data[h][w].SearchStatus = 0; } } return; } void SetDefault(void) { for(int h = 0; h < HEIGHT; h++){ for(int w = 0; w < WIDTH; w++){ data[h][w].status = def_data[h][w]; } } return; } void out(void) { for(int h = 0; h < HEIGHT; h++){ for(int w = 0; w < WIDTH; w++){ char ch = ' '; if(w == GX && h == GY) ch = '*'; if(w == SX && h == SY) ch = '@'; printf("%c", ch); if(data[h][w].status > 0) ch = 'o'; if(data[h][w].status < 0) ch = '#'; if(data[h][w].status == 0) ch = '.'; printf("%c", ch); } printf("\n"); } printf("OK.\n"); return; } // マンハッタン距離を斜め移動ありを考慮して求める int GetDistance(int from_x, int from_y, int to_x, int to_y) { int cx = from_x - to_x; int cy = from_y - to_y; if(cx < 0) cx *= -1; if(cy < 0) cy *= -1; // 推定移動コストを計算 if(cx < cy){ return (cx + (cy - cx)); }else{ return (cy + (cx - cy)); } } int BackTrace(int x, int y) { if(x == SX && y == SY) return 1; int parent_way = data[y][x].parent; return BackTrace( x + CheckMatrix[parent_way].x, y + CheckMatrix[parent_way].y ) + 1; } // A*で経路探査する int Search(int count){ int cost_min = 9999; int BackCost = 0; int CX = 0; int CY = 0; mapcell *n = NULL; // コストが最小のオープンノードを探す // TODO: ここを全マス探査しないようにすると、 // もっと早くなるかも for(int h = 0; h < HEIGHT; h++){ for(int w = 0; w < WIDTH; w++){ if(data[h][w].SearchStatus != SEARCH_OPEN)continue; if(GetDistance(w,h, GX, GY) > cost_min)continue; cost_min = GetDistance(w, h, GX, GY); n = &data[h][w]; CX = w; CY = h; } } // オープンノードがなければ終了(ゴールが見つからない) if(n == NULL) return -9; // ノードをクローズする n->SearchStatus = SEARCH_CLOSE; BackCost = BackTrace(CX, CY); for(int i = 0; i < 8; i++){ int check_x = CX + CheckMatrix[i].x; int check_y = CY + CheckMatrix[i].y; if(check_x < 0) continue; if(check_y < 0) continue; if(check_x >= WIDTH ) continue; if(check_y >= HEIGHT) continue; // 通れないところをよける if(data[check_y][check_x].status == -1) continue; int estimate_cost = BackCost + GetDistance(check_x, check_y, GX, GY) + 1; mapcell *cell = &data[check_y][check_x]; if(data[check_y][check_x].SearchStatus == SEARCH_NO_CHECK){ cell->parent = (i + 4) % 8; cell->SearchStatus = SEARCH_OPEN; }else if(estimate_cost < cell->cost){ cell->parent = (i + 4) % 8; cell->cost = estimate_cost; cell->SearchStatus = SEARCH_OPEN; } } // 見つかったら探索終了 if(CX == GX && CY == GY){ return -1; } return Search(count + 1); } void TraceRoute(int x, int y) { if(x == SX && y == SY){ printf("開始ノード>"); return; } POINT *parent_way = &CheckMatrix[data[y][x].parent]; data[y][x].status = 1; TraceRoute(x + parent_way->x, y + parent_way->y); if(x == GX && y == GY){ printf("ゴール\n"); return; }else{ printf("(%d,%d)>", x, y); } return; } int _tmain(int argc, _TCHAR* argv[]) { SetDefault(); ResetSearchStatus(); data[SY][SX].SearchStatus = SEARCH_OPEN; Search(0); TraceRoute(GX, GY); out(); return 0; }
ポイントはオープンリストとクローズリストをなくした事です。
いちいちリスト(std::mapだから正確にはマップ)の中を検索しなくても、
O(1)で検索済みかそうでないかが判断できるという。
当然ゴールからの最短経路の検索も、
配列を一発で参照できるので高速です。
どのぐらい速まったか
経路探査を5000回ループして、かかった時間を測定しました。
具体的には
- リスト破棄(配列の初期化)
- スタートノードの登録
- 検索
までをループ。
経路の確認はしませんでした。
まずは先日のコード。
驚きの86507ミリ秒。だいたい1分半。
遅すぎる!
1体敵キャラが動いたら17ミリ秒。
1/60秒(1フレーム)が16ミリ秒なので、完全に処理落ちします。
んで、作り替えたヤツ。
1195ミリ秒。
だいたい1秒。おおー70倍速くなった。
1体あたり0.2ミリ秒なので安心して使える!
というわけで
この処理をゲームに混ぜていきます!
主人公をワッサワッサ追いかける敵・・・!ハァハァ。
手前みそながら楽しみになってきた!
よろしくお願いします。