【ゲームAI】ポテンシャル関数

#概要
ゲームAIに関して勉強し始めたので，その備忘録．
本記事ではポテンシャル関数について記述する．

ポテンシャル関数に関する説明は，使用される分野によって多種多様である．
本記事では，分子動力学で用いられる，原子間距離に応じた相互作用力を求める関数を指す．
実装する関数はレナード・ジョーンズ・ポテンシャル関数である．

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

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

(どうでもいいが，この本のサンプルを取得する方法がわからない)
(書籍中に記述されているURLに飛んでもダメだった)
(できることならサンプルがほしいので，何か知っている方は教えてほしい．)

#レナード・ジョーンズ・ポテンシャル関数
##概要
以下の式を用いてることで，原子間のポテンシャルを計算できる．
(実際にはもっと複雑な式だが，ここではパラメータを少なくするために，ある程度まとめてある．)
U = -( A / r^n ) + ( B / r^m )
Uはポテンシャル，Aは引力の大きさ，Bは斥力の大きさ，
rは原子間距離，nは引力の減衰度合い，mは斥力の減衰度合い.

この式は，ポテンシャル曲線を表す簡易的なものであるため，
厳密な結果は得られない．しかし，大抵の場合はこの式だけで事足りるらしい．

調整するパラメータはA，B，n，mである．
AとBは各力の大きさである．目標に近づきたければAを大きくして，離れたければBを大きくする．
nとmは各力が影響を及ぼす範囲である．小さくすれば範囲は広がり，大きくすれば範囲は狭くなる．

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

//角度計算用マクロ.
#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 );
	}
};

##サンプル

//ポテンシャル関数のタイプ.
enum POTENTIAL_TYPE
{
	POTENTIAL_TYPE_TRACK = 0,
	POTENTIAL_TYPE_ESCAPE,
	POTENTIAL_TYPE_INTERCEPT,
	POTENTIAL_TYPE_SWARMING,
	POTENTIAL_TYPE_OBS_AVOID,
	POTENTIAL_TYPE_NUM,
	POTENTIAL_TYPE_INVALID = -1,
};
static bool IsValid( POTENTIAL_TYPE e ){ return ( 0 <= e && e < POTENTIAL_TYPE_NUM ); }

//ポテンシャル関数用パラメータ.
struct SParam
{
	float attraction;
	float repulsion;
	float atDamping;
	float reDamping;
};

//各ポテンシャル関数の具体的なパラメータ.
SParam g_param[POTENTIAL_TYPE_NUM] = 
{
	{ 50000.0f, 750000.0f, 2.0f, 3.0f },
	{ 0.0f, 40000.0f, 2.0f, 2.0f },
	{ 10000.0f, 40000.0f, 2.0f, 3.0f },
	{ 10000.0f, 50000.0f, 1.0f, 2.0f },
	{ 0.0f, 75000.0f, 1.0f, 2.0f },
};

/*
	レナード・ジョーンズ・ポテンシャル関数.
	
	物理学において，原子間の引力，斥力，ポテンシャルの関係を示す，
	以下の式がある．

	U = -( A / r^n ) + ( B / r^m )

	Uはポテンシャル，Aは引力の大きさ，Bは斥力の大きさ，
	rは原子間距離，nは引力の減衰度合い，mは斥力の減衰度合い.

	これらのパラメータを調整することで，
	追跡，逃避，迎撃，群れ行動，障害回避などを実現できる．

	迎撃，群れ行動，障害回避については，書籍にあるような，
	なめらかな動きにはならなかった．どこか間違いがあるらしい．

*/

#define VEL_BORDER				(0.01f)
#define SWARMING_RANGE_BORDER	(30.0f)
#define OBS_AVOID_RANGE_BORDER	(40.0f)

//レナード・ジョーンズ・ポテンシャル関数.
float GetPotensial( const SParam& param, const float r )
{
	return -( param.attraction / (float)pow( r, param.atDamping ) ) + ( param.repulsion / (float)pow( r, param.reDamping ) );
}

//パラメータ更新.
void UpdateParam( 
	POTENTIAL_TYPE type, 
	float& selfNextDir, 
	float& selfNextVel,
	const float& selfNowDir,
	const float& selfNowVel,
	const VECTOR& selfNowPos,
	const VECTOR& targetPos,
	const float border
	)
{
	//方向が自分向きであることに注意.
	VECTOR dirVec = selfNowPos - targetPos;
	const float r = LMath::GetScalar( dirVec );

	if( ( border >= 0.0f ) && ( r > border ) ){ return; }

	//ポテンシャル計算.
	const float potensial = GetPotensial( g_param[type], r );

	//ポテンシャルが閾値以上なので，方向と速度に影響を与える.
	if( fabsf( potensial ) >= VEL_BORDER ){
		float dir = ADJUST_RAD( atan2f( -dirVec.y, dirVec.x ) );
		if( potensial < 0.0f ){
			//引力が強いので目標に近づくように角度を反転.
			dir = ADJUST_RAD( dir + L_PI );
		}

		selfNextDir += LMath::GetRotateRad( selfNowDir, dir );
		selfNextVel += potensial - selfNowVel;
	}
}

void Update( VECTOR& pos, float& dir, float& vel )
{
	static const bool bTrack		= false;
	static const bool bEscape		= false;
	static const bool bIntercept	= false;
	static const bool bSwarming		= false;
	static const bool bObsAvoid		= false;

	const VECTOR nowPos = pos;	
	const float nowDir = dir;
	const float nowVel = vel;

	//追跡.
	if( bTrack )
	{
		VECTOR targetPos = /*追い駆けたい対象*/;
		UpdateParam( POTENTIAL_TYPE_TRACK, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );		
	}

	//逃避.
	if( bEscape )
	{
		VECTOR targetPos = /*逃げたい対象*/;
		UpdateParam( POTENTIAL_TYPE_ESCAPE, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );
	}

	//迎撃.
	if( bIntercept )
	{
		VECTOR targetPos = /*迎撃したい対象*/;
		UpdateParam( POTENTIAL_TYPE_INTERCEPT, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );
	}

	//群れ.
	if( bSwarming )
	{
		VECTOR* posArray = /*動的モジュールの位置リスト*/;
		const int posNum = /*動的モジュールのリストサイズ*/;
		for( int i = 0; i < posNum; ++i ){
			VECTOR targetPos = posArray[i];
			UpdateParam( POTENTIAL_TYPE_SWARMING, dir, vel, nowDir, nowVel, nowPos, targetPos, SWARMING_RANGE_BORDER );
		}
	}

	//障害回避.
	if( bObsAvoid )
	{
		VECTOR* posArray = /*障害物の位置リスト*/;
		const int posNum = /*障害物のリストサイズ*/;
		for( int i = 0; i < posNum; ++i ){
			VECTOR targetPos = posArray[i];
			UpdateParam( POTENTIAL_TYPE_OBS_AVOID, dir, vel, nowDir, nowVel, nowPos, targetPos, OBS_AVOID_RANGE_BORDER );
		}
	}

	//0～L_2PIの範囲に入るように調整.
	while( (dir < 0.000f) || (dir > L_2PI) ){
		dir = ADJUST_RAD( dir );
	}

	//最大速度は1.0f.
	vel = min( fabsf( vel ), 1.0f );

	pos.x += vel * cosf( dir );
	pos.y += vel * -sinf( dir );
}

基本的に，公式通りポテンシャルを計算し，
適用するだけである．

ポテンシャルが正である場合は斥力が強く，
負である場合は引力が強い．

今回のサンプルでは，ポテンシャルの絶対値を速度に，
ポテンシャルの符号を向きに反映させている．

ポテンシャル計算を組み合わせることで，色々な動作をさせることができる．

##注意
コード上では，各行動をboolで分岐させているが，
実際に使う場合は，外部データに任せる，ステートで管理する，など，
状況に応じて変化するようにした方が良い．

上記サンプルはどこかバグがあるらしく，
参考書籍のように滑らかな動作をしなかった．
上記コードを使用する場合は，しっかり動作を確認してから使用してほしい．

#動作状況
手元のビジュアライザで動作確認をしてみた．
障害回避と群れ行動があまり綺麗にできていない．
おそらくバグだとは思うが，書籍通りに実装してみると，
こうなってしまう気はする…

##追跡＋逃避

一定以上近づいたら，その距離を保とうとする．
すごい追っかけファンだけど一定の理性はあるファン，みたいなのを
再現する時に使える．

##追跡＋障害回避

ちょっと賢いストーカー．
でも，障害物に引っかかる馬鹿なストーカー．

##群れ＋障害回避

この群れ行動は，フロッキングではなく，スウォーミングという．
鳥や魚の群れではなく，蜂や蛾の群れに近い運動をする．
二人組ができると安定したり，三人組になるとモニョモニョしたり，
原子感が出ている気もする．

#総括
簡単な式で色々な状況に対応できるというのは強力だと思う．
が，直感的ではないパラメータをいじる必要があったり，
求めている動きにするための試行錯誤が大量に必要だったりと，
コストがかさむ可能性は否めない．
使いどころをしっかり考える必要がある．