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ミリ秒なので安心して使える！

というわけで

　この処理をゲームに混ぜていきます！
　主人公をワッサワッサ追いかける敵・・・！ハァハァ。
　手前みそながら楽しみになってきた！
　
　よろしくお願いします。