【ゲームAI】迎撃アルゴリズム

#概要
ゲームAIに関して勉強し始めたので，その備忘録．
この記事では迎撃アルゴリズムについて示す．
迎撃アルゴリズムは，敵に対して待ち伏せ行動をする際に使用する経路探索アルゴリズムで，
敵の行動を元に移動先を予測して，その地点に向かって移動する．
実装内容は多種多様だと思うが，ここでは簡易な実装を示す．

なお，この記事では離散的なゲームを想定したサンプルを示す．
連続的なゲームでの迎撃アルゴリズムも，考え方は同じである．

また，この記事のサンプルでは，LOSアルゴリズムを使用している．
LOSアルゴリズムに関しては，以下の記事を参照してもらいたい．
【ゲームAI】LOSアルゴリズム

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

#迎撃アルゴリズム
##概要
原理は非常にシンプルなもので，
プレイヤー・敵の相対位置，相対速度から，接敵するまでの大体の時間を計算し，
その時間とプレイヤーの現在位置，現在速度から計算した地点を，
敵の移動先に設定してLOSアルゴリズムを走らせるというものである．

##サンプル

main.cpp

/*　　velP
 posP ●→　　●posF
	　＼
	　　＼
	　　　＼
	　　　　●↑velE
	      posE

	プレイヤー位置をposP，速度をvelP，
	敵位置をposE，速度をvelE，
	目標地点をposFとする．

	相対距離の計算式は以下
	d = posP - posE

	相対速度の計算式は以下
	v = velP - velE

	接近時間の計算式は以下
	t = d / v

	プレイヤーの到着予想地点は以下
	posF = posP + (velP * t)

	到着予測地点posFに向かってLOSアルゴリズムを適用すれば，
	待ち伏せ行動が可能になる．
*/
void UpdateIntercept( POINT& posP, POINT& velP, POINT& posE, POINT& velE )
{
	if( posP.x == 0 && posP.y == 0 ){ return; }

	//目標地点予測.
	POINT posF;
	{
		//相対距離.
		POINT dis;
		dis.x = posP.x - posE.x;
		dis.y = posP.y - posE.y;

		//相対速度.
		POINT vel;
		vel.x = velP.x - velE.x;
		vel.y = velP.y - velE.y;

		//接近時間.
		double time = 0;
		double distance = sqrt( dis.x * dis.x + dis.y * dis.y );
		double velcity	= sqrt( vel.x * vel.x + vel.y * vel.y );
		if( !( 0.000f <= velcity && velcity <= 0.000f ) ){
			time = distance / velcity;
			time = fabs( time );
		}

		//予測ポイントを目標地点に設定.
		posF.x = posP.x + (LONG)( (double)velP.x * time );
		posF.y = posP.y + (LONG)( (double)velP.y * time );
	}

	//LOSアルゴリズムを使って移動.
	UpdateBresenham( posE, posF );
}

今回はWindows.h内に定義されているPOINT構造体を二次元ベクトルとして利用している．
正直，自前の構造体を用意して，四則演算関連の演算子を定義して使えば，
途中の計算をもっとスマートにかけるはずである．

##解説
###考え方
基本的にサンプルに書いてある計算式通りである．

【接近時間】の計算に関しては，多少曖昧な所があると感じるだろう．
個人的にしっくりきた考え方は以下である．
1，【相対距離】を半径に，プレイヤーを中心にした円があるとする．
2，プレイヤーの現在の移動方向に，中心から弧に向かって直線を引く．
3，目標となる地点はその直線上にあるはずなので，【相対速度】を加味してあげて場所を確定する．
4，【相対速度】が大きければそれだけ手前が目標になるし，小さければ奥になる．
【相対速度】が小さいということは，速度差がないということなので，
目標地点が遠ざかるのは直感的に分かると思う．

###注意
【相対速度】は方向も加味する必要があるので，
プレイヤー，敵間で減算処理を施す時点では，ベクトルとして扱う必要がある．
この時点でスカラーにしたもので計算してしまうと，挙動がおかしくなるので注意．

また，相手の速度の方が速い場合などで正しく動作しないケースもあるので，
一定距離以上離れたら迎撃を中止する，などといった処理は必要になる．
2016/09/07追記
プレイヤー側の速度が速い場合に，迎撃としては正しく動作しない(迎撃に失敗する)ケースはあるが，
予測地点の計算自体は正しく行うことができる．
【相対速度】は絶対値を取って計算に使うので，敵側が速くてもプレイヤー側が速くても，
絶対値は同じになることがある．
ここだけ見ると，プレイヤー側の速度が速い場合に，予測地点がやたら手前になってしまうように
感じるが，実際には予測地点の計算時にプレイヤーの速度を加味しているため，ちゃんと奥になる．
迎撃失敗時に一定距離離れたら中止扱いにする，という処理はどちらにせよ必要になる．

#総括
簡単な手法の割には，それなりに賢く見えるので，
使い所は多い気もする．
銃弾やロケットなど，一度動き始めたら止められないものなどにはより有効だと思う．