【ゲームAI】基本的な経路探索

#概要
ゲームAIに関して勉強し始めたので，その備忘録．
本記事では基本的な経路探索について記述する．

本記事では，以下の手法について取り上げる．
●ランダムムーブメント
●ブレッドクラム経路探索
●ウェイポイントナビゲーション

なお，本記事では連続的なゲームを想定したサンプルを示す．
離散的なゲームでの上記手法も，考え方は同じである．

#参考書
ありきたりではあるが以下の書籍を用いた．
ゲーム開発者のためのAI入門
(サンプル)

#事前準備
ベクトル計算用の構造体，便利関数の準備と，
角度計算用のマクロの準備を行う．

//角度計算用マクロ.
#define L_PI		(3.1415f)
#define L_2PI		(6.2830f)
#define L_H_DEG		(180.0000f)
#define L_DEG		(360.0000f)
#define DEG2RAD(e) ((e)*(L_PI)/(L_H_DEG))
#define RAD2DEG(e) ((e)*(L_H_DEG)/(L_PI))
#define ADJUST_RAD(e) (((e)<(0.0000f))?(e)+(L_2PI):((e)>(L_2PI))?(e)-(L_2PI):(e))
#define ADJUST_DEG(e) (((e)<(0.0000f))?(e)+(L_DEG):((e)>(L_DEG))?(e)-(L_DEG):(e))

//ベクトル構造体.
#define VECTOR SVector2D<float>
template <class T>
struct SVector2D
{
	typedef T DataType;
	T x;
	T y;
	SVector2D(){ Init(); }
	void Init()
	{
		x = T();
		y = T();
	}
	SVector2D	operator +  ( const SVector2D& e ) const { SVector2D tmp; tmp.x = x + e.x; tmp.y = y + e.y; return tmp; }
	SVector2D&	operator += ( const SVector2D& e ){ x += e.x; y += e.y; return (*this); }
	SVector2D	operator -  ( const SVector2D& e ) const { SVector2D tmp; tmp.x = x - e.x; tmp.y = y - e.y; return tmp; }
	SVector2D&	operator -= ( const SVector2D& e ){ x -= e.x; y -= e.y; return (*this); }
	T			operator *  ( const SVector2D& e ) const { return ( x * e.x ) + ( y * e.y ); }
	SVector2D&	operator *= ( const int e ){ x *= e; y *= e; return (*this); }
	SVector2D&	operator *= ( const float e ){ x *= e; y *= e; return (*this); }
	SVector2D&	operator /= ( const int e ){ x /= e; y /= e; return (*this); }
	SVector2D&	operator /= ( const float e ){ x /= e; y /= e; return (*this); }
};

//数学関連の関数群.
namespace LMath
{
	VECTOR::DataType GetScalar( VECTOR vec )
	{
		return sqrtf( vec.x * vec.x + vec.y * vec.y );
	}

	VECTOR Normalize( VECTOR vec )
	{
		const VECTOR::DataType vecLen = GetScalar( vec );
		vec.x /= vecLen;
		vec.y /= vecLen;
		return vec;
	}

	VECTOR Normalize( VECTOR from, VECTOR to )
	{
		VECTOR tmp = to - from;
		return Normalize( tmp );
	}

	float GetRotateRad( const float from, const float to )
	{
		//角度候補1.
		const float dir1st		= ( to - from );
		const float dir1stVal	= fabsf( dir1st );

		//角度候補2.
		const float dir2ndVal	= ( L_2PI - dir1stVal );
		const float dir2nd		= ((dir1st>=0.0f)?-1.0f:1.0f) * dir2ndVal;
			
		//絶対値が小さい方を採用.
		return ( dir1stVal > dir2ndVal ) ? dir2nd : dir1st;
	}

	bool IsCollisionCircle( const VECTOR& pos1, const VECTOR& pos2, const float r )
	{
		VECTOR tmp = pos1 - pos2;
		return ( GetScalar( tmp ) < r );
	}
};

#ランダムムーブメント
##概要
目標地点に向かって真っ直ぐ進む経路探索．
これだけだとLOSアルゴリズムと同じだが，それに加えて，
視線上に障害物があった場合は，障害物を避けるように適当な方向に移動する．

##サンプル

void Update( const float nowVel, VECTOR& nowPos, const VECTOR& targetPos )
{
	const VECTOR	ray				= targetPos - nowPos;
	const VECTOR	rayNormalVec	= LMath::Normalize( ray );
	const float		rayScalar		= LMath::GetScalar( ray );
	const float		checkRange		= 20.0f;

	bool bRandomMove = false;

	VECTOR* obsArray = /*障害物位置リスト*/;
	const int obsNum = /*障害物位置リストサイズ*/;
	for( int i = 0; i < objNum; ++i ){
		//障害物との距離.
		VECTOR disObs = obsArray[i] - nowPos;

		//視線上への正射影.
		//(方向ベクトルが単位ベクトルじゃないと正しい長さは出ない).
		VECTOR checkProject = rayNormalVec;
		checkProject *= ( disObs * rayNormalVec );

		//正射影の方が長い場合は，そもそもチェック範囲に入っていないので無視.
		const float projectScalar = LMath::GetScalar( checkProject );
		if( rayScalar < projectScalar ){ continue; }

		//障害物周辺を向いていない場合も無視.
		if( !LMath::IsCollisionCircle( checkProject, disObs, checkRange ) ){
			continue;
		}

		bRandomMove = true;
		break;
	}

	float dir = ADJUST_RAD( atan2f( -rayNormalVec.y, rayNormalVec.x ) );
	if( bRandomMove ){
		//障害物があれば適当な方向にランダム移動する.
		const int angle = ( 60 );
		float displace = DEG2RAD( ( float  )( angle ) + ( float )( rand() % angle ) );
		if( rand() % 2 ){ displace *= -1.0f; }

		dir = ADJUST_RAD( dir + displace );
	}

	nowPos.x += nowVel * cosf( dir );
	nowPos.y += nowVel * -sinf( dir );
}

流石に完全ランダムだと，視線が通るまでに時間がかかるので，
左右±30度の範囲でランダムに値を決定するようにした．

##注意
障害物が大量にあってほぼ視線が通らないようなケース(大都会の街中など)では，
あまり賢い動きはしないので，別の方法を模索した方が良い．

##動作状況

##感想
賢く見せるためには，ランダム移動する部分をかなり工夫する必要があると思う．
使えるケースが思いつかない．

#ブレッドクラム経路探索
##概要
目標が通った箇所に**パンくず(ブレッドクラム)**を落とし，それを追跡する探索手法．
すでに目標が通った箇所なので，障害物などを気にする必要がない．
パンくずを発見できていない時の行動は，状況に応じて調整する．

##サンプル

#define BREAD_CRUMB_MAX_RANGE (60.0f)

//パンくずを落とす.目標が移動した時に呼び出す.
void DropBreadCrumb( const VECTOR& pos )
{
	//パンくず集合.
	VECTOR* breadArray = /*パンくず位置リスト*/;
	const int breadNum = /*パンくず位置リストサイズ*/;
	if( !( breadArray && ( breadNum > 0 ) ) ){ return; }

	//最近落としたパンくずより一定範囲離れていたらパンくずを落とす.
	if( LMath::IsCollisionCircle( breadArray[0], pos, BREAD_CRUMB_MAX_RANGE ) ){
		return;
	}

	//全パンくずの鮮度を更新.
	for( int i = breadNum - 1; i >= 1; --i ){
		breadArray[i] = breadArray[i-1];
	}

	//新しいパンくずを登録.
	breadArray[0] = pos;
}

//パンくずを元に位置と方向を決定する.
VECTOR g_targetBread;
void Update( VECTOR& nowPos, float& nowDir, const float nowVel )
{
	const float BREAD_COLLISION_RANGE = 15.0f;

	//すでに到着しているなら無効に.
	if( g_targetBread.x >= 0.0f && g_targetBread.y >= 0.0f )
	{
		if( LMath::IsCollisionCircle( g_targetBread, nowPos, BREAD_COLLISION_RANGE ) ){
			g_targetBread.x = g_targetBread.y = -1.0f;
		}
	}

	//目標パンくずがない場合は探す.
	if( !( g_targetBread.x >= 0.0f && g_targetBread.y >= 0.0f ) )
	{
		VECTOR* breadArray = /*パンくず位置リスト*/;
		const int breadNum = /*パンくず位置リストサイズ*/;
		for( int i = 0; i < breadNum; ++i ){
			VECTOR breadPos = breadArray[i];
			if( !( breadPos.x >= 0.0f && breadPos.y >= 0.0f ) ){ continue; }

			//範囲外のものは判定から外す.
			const float r = BREAD_CRUMB_MAX_RANGE + ( BREAD_COLLISION_RANGE * 2.0f );
			if( !LMath::IsCollisionCircle( breadPos, nowPos, r ) ){
				continue;
			}

			g_targetBread = breadPos;
			break;
		}
	}

	if( g_targetBread.x >= 0.0f && g_targetBread.y >= 0.0f ){
		//目標パンくずがあるならパンくずに向かう.
		
		//目標方向への方向ベクトル.
		VECTOR dirVec = LMath::Normalize( nowPos, g_targetBread );
		
		//角度に変換.
		nowDir = ADJUST_RAD( atan2f( -dirVec.y, dirVec.x ) );
	}
	else{
		//目標パンくずがないなら，ランダムで移動.

		//今の方向±30.0fの範囲をランダムで移動.
		const float angle = 30.0f;
		float displace = DEG2RAD( angle );
		if( rand() % 2 ){ displace *= -1.0f; }

		nowDir = ADJUST_RAD( nowDir + displace );
	}

	nowPos.x += nowVel * cosf( nowDir );
	nowPos.y += nowVel * -sinf( nowDir );
}

今回のサンプルでは，パンくずを発見できていない時の行動は，
その辺をうろつくようにしている．

##注意
パンくずは最新のものからチェックすることで，
古いものと新しいものが並んで落ちているような時に，新しいものを選択してくれる．
つまり，ただ追うだけではなく，可能ならショートカットするということである．
古いものからチェックすると，位置によっては古いパンくずに引っ張られる可能性がある．

##動作状況
パンの絵はGATAGさんのものを，使用させていただきました．

##感想
パンくずオブジェクトは，位置だけではなく，
色々な情報を含めることができるため，結構汎用性が高い．
実際に，CEDEC2016で発表されたLOST REAVERSにおけるAI Directorの試みにおいて，
AI用の情報として使用したという話が出た．
協調目的で敵が落としたり，マップに足跡を表示するために落としたり，色々使えそう．

#ウェイポイントナビゲーション
##概要
前もって，フィールドに経路上の地点情報(ウェイポイント)を埋め込んでおき，
目標地点に向かう時にウェイポイントを経由して移動する手法．

ウェイポイントは障害物に引っかからないように埋め込むため，
回避等は考えなくて良い．

##サンプル

#define WAY_POINT_MAX_NUM (20)
#define INF_COST (1 << 28)
int g_edgeCost[WAY_POINT_MAX_NUM ][WAY_POINT_MAX_NUM ];
int g_shortestPath[WAY_POINT_MAX_NUM ][WAY_POINT_MAX_NUM ];

//グラフ生成.
void CreateGraph()
{
	//ウェイポイント生成.
	{
		VECTOR* waypointArray = /*ウェイポイント位置リスト*/;
		const int waypointNum = /*ウェイポイント位置リストサイズ*/
		const int POINT_NUM = 4;
		for( int i = 0; i < waypointNum; ++i ){
			VECTOR pos;
			pos.x = 50.0f + ( 100.0f * (float)(i % POINT_NUM) );
			pos.y = 50.0f + ( 100.0f * (float)(i / POINT_NUM) );
			waypointArray[i] = pos;
		}
	}

	//エッジを設定.
	{
		//初期化.
		for( int i = 0; i < WAY_POINT_MAX_NUM; ++i ){
			for( int j = 0; j < WAY_POINT_MAX_NUM; ++j ){
				g_edgeCost[i][j] = INF_COST;
			}
		}

		//自身へのコストはなし.
		for( int i = 0; i < WAY_POINT_MAX_NUM; ++i ){ g_edgeCost[i][i] = 0; }

		//手作業でエッジを設定.
		g_edgeCost[0][1] = g_edgeCost[1][0] = 1;
		g_edgeCost[1][2] = g_edgeCost[2][1] = 1;
		g_edgeCost[2][3] = g_edgeCost[3][2] = 2;
		
		g_edgeCost[0][4] = g_edgeCost[4][0] = 1;
		g_edgeCost[1][5] = g_edgeCost[5][1] = 2;
		g_edgeCost[2][6] = g_edgeCost[6][2] = 1;
		g_edgeCost[3][7] = g_edgeCost[7][3] = 1;

		g_edgeCost[4][5] = g_edgeCost[5][4] = 1;
		g_edgeCost[5][6] = g_edgeCost[6][5] = 2;
		g_edgeCost[6][7] = g_edgeCost[7][6] = 1;

		g_edgeCost[4][8] = g_edgeCost[8][4] = 1;
		g_edgeCost[5][9] = g_edgeCost[9][5] = 2;
		g_edgeCost[6][10] = g_edgeCost[10][6] = 1;
		g_edgeCost[7][11] = g_edgeCost[11][7] = 1;

		g_edgeCost[8][9] = g_edgeCost[9][8] = 2;
		g_edgeCost[9][10] = g_edgeCost[10][9] = 1;
		g_edgeCost[10][11] = g_edgeCost[11][10] = 3;

		g_edgeCost[8][12] = g_edgeCost[12][8] = 1;
		g_edgeCost[9][13] = g_edgeCost[13][9] = 1;
		g_edgeCost[10][14] = g_edgeCost[14][10] = 3;
		g_edgeCost[11][15] = g_edgeCost[15][11] = 1;

		g_edgeCost[12][13] = g_edgeCost[13][12] = 1;
		g_edgeCost[13][14] = g_edgeCost[14][13] = 1;
		g_edgeCost[14][15] = g_edgeCost[15][14] = 1;
	}

	//全点対最短経路を求める.
	{
		//エッジの状態をまんまコピー.
		for( int i = 0; i < WAY_POINT_MAX_NUM; ++i ){
			for( int j = 0; j < WAY_POINT_MAX_NUM; ++j ){
				g_shortestPath[i][j] = g_edgeCost[i][j];
			}
		}

		//ワーシャルフロイド.
		for( int k = 0; k < WAY_POINT_MAX_NUM; k++ ){
			for( int i = 0; i < WAY_POINT_MAX_NUM; i++ ){
				for( int j = 0; j < WAY_POINT_MAX_NUM; j++){
					const int newValue = g_shortestPath[i][k] + g_shortestPath[k][j];
					g_shortestPath[i][j] = min( g_shortestPath[i][j], newValue );
				}
			}
		}
	}
}

//次に行くウェイポイントを取得.
int GetNextNode( const int s, const int e )
{
	for( int i = 0; i < WAY_POINT_MAX_NUM; i++ ){
		if( i == s ){ continue; }
		if( g_edgeCost[s][i] + g_shortestPath[i][e] == g_shortestPath[s][e]) {
			return i;
		}
	}
	return -1;
}

int 	g_targetIndex;
VECTOR 	g_targetWayPoint;

//位置更新.
void Update( VECTOR* nowPos, const float nowDir, const float nowVel, const VECTOR targetPos )
{
	if( g_targetIndex < 0 ){
		//最初のウェイポイントが見つかっていないので，直近のウェイポイントを探す.
		g_targetIndex		= SearchNearestPoint( nowPos );
		g_targetWayPoint	= GetWayPointPos( g_targetIndex );
	}
	else{
		//目標のウェイポイントは見つかっている．

		const float RANGE_MAX = 15.0f;
		if( LMath::IsCollisionCircle( g_targetWayPoint, nowPos, RANGE_MAX ) ){
			//すでに到着しているので，次のウェイポイントを探す.
			const int playerPoint = SearchNearestPoint( targetPos);
			g_targetIndex		= GetNextNode( g_targetIndex, playerPoint );
			g_targetWayPoint	= GetWayPointPos( g_targetIndex );
		}
	}

	if( g_targetWayPoint.x >= 0.0f && g_targetWayPoint.y >= 0.0f ){
		//目標地点が有効なら，そこに向かう.
		
		VECTOR dirVec = LMath::Normalize( nowPos, g_targetWayPoint );

		nowDir = ADJUST_RAD( atan2f( -dirVec.y, dirVec.x ) );

		nowPos.x += nowVel * cosf( nowDir );
		nowPos.y += nowVel * -sinf( nowDir );
	}

	obj->SetNextPos( nowPos );
}

//指定位置から一番近いウェイポイントを探す.
int SearchNearestPoint( const VECTOR& pos )
{
	VECTOR* waypointArray = /*ウェイポイント位置リスト*/;
	const int waypointNum = /*ウェイポイント位置リストサイズ*/;
	if( !( waypointArray && ( waypointNum > 0 ) ) ){ return -1; }

	//距離で直近かどうか判断.
	int		nextPoint	= -1;
	float	minDistance = (float)(1 << 30);
	for( int i = 0; i < waypointNum; ++i ){
		const float distance = LMath::GetScalar( waypointArray[i] - pos );
		if( distance > minDistance ){ continue; }
		minDistance = distance;
		nextPoint	= i;
	}

	return nextPoint;
}

//ウェイポイントの位置を取得.
VECTOR	GetWayPointPos( const int& index )
{
	VECTOR tmp;
	tmp.x = tmp.y = -1.0f;

	VECTOR* waypointArray = /*ウェイポイント位置リスト*/;
	const int waypointNum = /*ウェイポイント位置リストサイズ*/;
	if( !( waypointArray && ( waypointNum > 0 ) ) ){ return tmp; }

	if( 0 > index || index >= waypointNum ){ return tmp; }

	return waypointArray[index];
}

コストデータは外部データにすべきだが，今回はハードコーディングした．

最短経路計算はワーシャル-フロイド法を使用した．
経路復元ができるなら，ダイクストラでもベルマンフォードでもSPFAでも何でも良い．
なお，次回記事にて，より効率的な最短経路計算であるA*アルゴリズムを紹介する予定である．

##注意
コストデータは，充分に大きい初期値を設定する必要がある．
ただし，最短経路計算時に加算処理があるので，オーバーフローしないように注意．
また，各ウェイポイントにおいて，自身へのコストは0に設定する必要がある．

##動作状況

草むらっぽい絵で句切られているウェイポイント間のコストは高く設定してある．
そのため，遠回りした方が最短になると判断している．

##感想
単純な仕組みではあるものの，結構賢く見える．
今回はウェイポイントの生成やコストの設定を静的に行っているが，
最近のゲーム業界では，動的に行っているようだ．
その際には，ナビゲーションメッシュなどを参照して，障害物がないことを保証する．
また，CEDEC2016で発表されたキャラクターの人工知能のための戦術位置解析システムによれば，
ウェイポイントの動的生成を使用して，より高度で汎用的な位置解析を行っているとのこと.
現在のゲームAI技術において，かなり使用されている手法である．

#紹介だけ
##ウォールトレーシング
現在の方向を基準に，左方，前方，右方，後方という順に移動先をチェックし，
移動できる方向があれば，そちらに移動するという手法．

広い空間が大量の小部屋で区切られている，といったケースにおいて，
壁沿いに移動することで，全小部屋を訪問できるという強みがある．

ただし，最初に配置された場所が壁沿いじゃない場合は，
まず壁沿いに移動する手段が必要になる．

また，壁が繋がっていない場所があるケースなど，全訪問できないケースもある．

#総括
経路探索の紹介だったが，パンくずやウェイポイントなど，
経路探索以外にも活用できる概念もあるので，しっかり活用していく必要がありそう．