【ゲームAI】パターンムーブメント

#概要
ゲームAIに関して勉強し始めたので，その備忘録．
この記事ではパターンムーブメントについて記述する．

なお，この記事では離散的なゲームを想定したサンプルを示す．
連続的なゲームでのパターンムーブメントも，考え方は同じである．

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

#パターンムーブメント
##概要
パターンムーブメントとは，用意したデータを参照して，
一定のパターンでオブジェクトを行動させる手法のことである．

実装内容は多種多様だと思うが，ここでは，
簡易な外部データを読み込んで，その通りに行動する方法を示す．

外部データは，以下の構成になっている．
●行動データ
●パターンデータ

各データに関して解説した後，実際に読み込んだデータをどう反映するかを示す．

##行動データ
###データ構成

/*
データ構造：
{行動名,速度,方向}

リスト内容：
停止
前進
後進
半左回り
半右回り
左回り
右回り
*/

7
{stop,0,0}
{forward,1,0}
{backward,-1,0}
{halfturnleft,0,45}
{halfturnright,0,-45}
{turnleft,0,90}
{turnright,0,-90}

データ内容は非常に簡易的なものである．
行動名は，この後取り上げるパターンデータにおいて，
行動を指定する際に使われる．いわばユニークな識別子である．
速度，方向以外にも必要な場合は，適宜カンマ区切りで追加していくことになるが，
その場合はプログラム側の修正も必要になる．
ただし，パラメータの追加ではなく，行動の追加であれば，プログラムの修正は必要ない．

###データ読み込み

//データパース用引数タイプ.
enum ARG_TYPE
{
	ARG_TYPE_START = 0,
	ARG_TYPE_STR,
	ARG_TYPE_INT_1,
	ARG_TYPE_INT_2,
	ARG_TYPE_END,
	ARG_TYPE_NUM,
	ARG_TYPE_INVALID = -1,
};

//行動データ.
struct SActionData
{
	enum{ ACTION_NAME_MAX = 100, };
	char	actionName[ ACTION_NAME_MAX ];
	int		vel;
	int		dir;
	SActionData(){ Init(); }
	void Init()
	{
		memset( actionName, '\0', sizeof( char ) * ACTION_NAME_MAX );
		vel = dir = 0;
	}
};
SActionData*	g_actionList;
int				g_actionListNum;

/*
	データ構造は以下の通り.
	N //アクション総数.
	{actionName,vel,dir}
	.
	.
	.
	
	また，コメントアウトで句切られた箇所に関しては，
	読み込みを無視するようになっている.
*/
#include <string>
#include <iostream>
#include <fstream>
void LoadAction()
{
	g_actionList = NULL;
	g_actionListNum = 0;

	//定義ファイルを開く.
	std::ifstream input;
	{
		std::string str( /*ファイルパス*/ );
		input.open( str.data(), std::ios::in );
	}

	if( input.fail() ){ return; }

	//アクションデータ.
	{
		bool	bCommentOut = false;
		int		index		= 0;
		while( true ){
			if( input.eof() ){ break; }

			std::string str;
			std::getline( input, str );

			if( strcmp( str.data(), "" ) == 0 ){
				continue;
			}
			else if( strcmp( str.data(), "\n" ) == 0 ){
				continue;
			}
			else if( strcmp( str.data(), "/*" ) == 0 ){
				bCommentOut = true;
				continue;
			}
			else if( strcmp( str.data(), "*/" ) == 0 ){
				bCommentOut = false;
				continue;
			}

			if( bCommentOut ){ continue; }

			char c = str.data()[0];
			if( c == '{' ){
				//データ本体.
				if( index >= g_actionListNum ){ break; }

				SActionData* pData = &g_actionList[index];
				ARG_TYPE type = ARG_TYPE_START;
				int strIndex = 0;
				bool bMinus = false;
				for( unsigned int i = 0; i < str.size(); ++i ){
					if( str[i] == '{' || str[i] == ',' || str[i] == '}' ){
						//引数タイプの更新.
						switch( type )
						{
						case ARG_TYPE_START:	type = ARG_TYPE_STR;				break;
						case ARG_TYPE_STR:		type = ARG_TYPE_INT_1;				break;
						case ARG_TYPE_INT_1:	if( bMinus ){ pData->vel *= -1; }	type = ARG_TYPE_INT_2;	break;
						case ARG_TYPE_INT_2:	if( bMinus ){ pData->dir *= -1; }	type = ARG_TYPE_END; 	break;
						};
						strIndex	= 0;
						bMinus		= false;
					}
					else{
						//各引数の更新.
						if( type != ARG_TYPE_STR && str[i] == '-' ){ bMinus = true; continue; }
						
						switch( type )
						{
						case ARG_TYPE_STR:		pData->actionName[strIndex++] = str[i];			break;
						case ARG_TYPE_INT_1:	pData->vel *= 10;	pData->vel += str[i] - '0';	break;
						case ARG_TYPE_INT_2:	pData->dir *= 10;	pData->dir += str[i] - '0';	break;
						};
					}
				}

				index++;
			}
			else{
				//データ総数.
				sscanf_s( str.data(), "%d", &g_actionListNum );
				g_actionList = new SActionData[ g_actionListNum ];
			}
		}
	}
}

基本的に，データ構成を元にパースしているだけである．
(もうちょっとスマートに書けると思ったが…)

##パターンデータ
###データ構成

/*
データ構造：
[パターン名,行動数]
{
行動名,時間
行動名,時間
.
.
.
}

リスト内容：
矩形
ジグザグ

*/

2

[rect,2]
{
forward,5
turnleft,1
}

[ziguzagu,4]
{
halfturnleft,1
forward,1
halfturnright,1
forward,1
}

パターンデータは，行動データの組み合わせとして構成されている．
こちらに関しても，パラメータを追加する場合にはプログラムの修正が必要だが，
パターンを追加する場合はプログラムの修正は不要である．

###データ読み込み

//パターンデータ.
struct SPatternData
{
	enum{ PATTERN_NAME_MAX = 100, };
	char			patternName[ PATTERN_NAME_MAX ];
	SActionData*	actionData;
	int*			actionTime;
	int				actionNum;
	int				actionIndex;
	SPatternData(){ Init(); }
	~SPatternData(){ Term(); }
	void Init()
	{
		memset( patternName, '\0', sizeof( char ) * PATTERN_NAME_MAX );
		actionData = NULL;
		actionTime = NULL;
		actionNum	= 0;
		actionIndex = -1;
	}
	void Term()
	{
		if( actionData ){ delete [] actionData; actionData = NULL; }
		if( actionTime ){ delete [] actionTime; actionTime = NULL; }
	}
	SActionData* GetAt( int index ){ return &actionData[ index ]; }
	SActionData* GetNow(){ return GetAt( actionIndex ); }
};
SPatternData*	g_patternList;
int				g_patternListNum;

/*
	データ構造は以下の通り.
	N //パターン総数.
	[patternName,actionNum]
	{
	actionName,time
	.
	.
	.
	}
	.
	.
	.
	
	また，コメントアウトで句切られた箇所に関しては，
	読み込みを無視するようになっている.
*/
void LoadPattern()
{
	g_patternList = NULL;
	g_patternListNum = 0;

	//定義ファイルを開く.
	std::ifstream input;
	{
		std::string str( /*ファイルパス*/ );
		input.open( str.data(), std::ios::in );
	}

	if( input.fail() ){ return; }

	//パターンデータ.
	{
		bool	bCommentOut = false;
		bool	bDataIn		= false;
		int		ptnIndex	= 0;
		int		actIndex	= 0;
		while( true ){
			if( input.eof() ){ break; }

			std::string str;
			std::getline( input, str );

			if( strcmp( str.data(), "" ) == 0 ){
				continue;
			}
			else if( strcmp( str.data(), "\n" ) == 0 ){
				continue;
			}
			else if( strcmp( str.data(), "/*" ) == 0 ){
				bCommentOut = true;		continue;
			}
			else if( strcmp( str.data(), "*/" ) == 0 ){
				bCommentOut = false;	continue;
			}

			if( bCommentOut ){ continue; }

			if( strcmp( str.data(), "{" ) == 0 ){
				if( ptnIndex >= g_patternListNum ){ break; }
				bDataIn	= true;
				actIndex = 0;
				continue;
			}
			else if( strcmp( str.data(), "}" ) == 0 ){
				bDataIn = false;
				ptnIndex++;
				continue;
			}

			if( bDataIn ){
				SPatternData* pData = &g_patternList[ptnIndex];
				
				//アクションデータ情報取得.
				char	buf[ SActionData::ACTION_NAME_MAX] = {};
				int		time		= 0;
				int		strIndex	= 0;
				ARG_TYPE type = ARG_TYPE_STR;
				for( unsigned int i = 0; i < str.size(); ++i ){
					if( str[i] == ',' ){
						//引数タイプの更新.
						switch( type )
						{
						case ARG_TYPE_STR:		type = ARG_TYPE_INT_1;	break;
						case ARG_TYPE_INT_1:	type = ARG_TYPE_END;	break;
						};
						strIndex = 0;
					}
					else{
						//各引数の更新.
						switch( type )
						{
						case ARG_TYPE_STR:		buf[strIndex++] = str[i];			break;
						case ARG_TYPE_INT_1:	time *= 10;	time += str[i] - '0';	break;
						};
					}
				}

				//アクションリストから該当データをコピー.
				for( int i = 0; i < g_actionListNum; ++i ){
					if( strcmp( buf, g_actionList[i].actionName ) == 0 ){
						pData->actionData[actIndex] = g_actionList[i];
					}
				}
				pData->actionTime[actIndex] = time;

				actIndex++;
			}
			else{
				char c = str.data()[0];
				if( c == '[' ){
					SPatternData* pData = &g_patternList[ptnIndex];

					//パターン名とアクション総数を取得.
					int strIndex = 0;
					ARG_TYPE type = ARG_TYPE_START;
					for( unsigned int i = 0; i < str.size(); ++i ){
						if( str[i] == '[' || str[i] == ',' || str[i] == ']' ){
							//引数タイプの更新.
							switch( type )
							{
							case ARG_TYPE_START:	type = ARG_TYPE_STR;	break;
							case ARG_TYPE_STR:		type = ARG_TYPE_INT_1;	break;
							case ARG_TYPE_INT_1:	type = ARG_TYPE_END;	break;
							};
							strIndex = 0;
						}
						else{
							//各引数の更新.
							switch( type )
							{
							case ARG_TYPE_STR:		pData->patternName[strIndex++] = str[i];					break;
							case ARG_TYPE_INT_1:	pData->actionNum *= 10;	pData->actionNum += str[i] - '0';	break;
							};
						}
					}

					//アクション総数を元にアクションデータ用のバッファを取得.
					pData->actionData = new SActionData[ pData->actionNum ];
					pData->actionTime = new int[ pData->actionNum ];
				}
				else{
					//パターン総数を取得.
					sscanf_s( str.data(), "%d", &g_patternListNum );
					g_patternList = new SPatternData[ g_patternListNum ];
				}
			}			
		}
	}
}

こちらもデータ構成に合わせてパースしているだけである．
(ひどく汚い…標準ライブラリの文字列関連について詳しい人なら，もっと綺麗に書けるはず．)

##データ反映

//方向.
enum ST_DIR
{
	ST_DIR_RIGHT = 0,
	ST_DIR_UP_RIGHT,
	ST_DIR_UP,
	ST_DIR_LEFT_UP,
	ST_DIR_LEFT,
	ST_DIR_DOWN_LEFT,
	ST_DIR_DOWN,
	ST_DIR_RIGHT_DOWN,
	ST_DIR_NUM,
	ST_DIR_INVALID = -1,
};
#define DEV_ANGLE 45
#define MAX_ANGLE 360

/*
	読み込み済みのデータを参照して，一定のパターンでオブジェクトを動かす．
	パターン変更の条件は，状況に応じて要調整．
*/
void Update( POINT& pos )
{
	static int vel = 0;
	static int dir = 0;
	static int time = 0;
	static int patternIndex = 0;

	//パターン変更決定.
	{
		if( /*パターン変更のための条件*/ ){
			SPatternData* pData = &g_patternList[ patternIndex ];
			pData->actionIndex = -1;
			patternIndex = ( patternIndex + 1 ) % g_patternListNum;
			time = 0;
		}
	}

	//パターン更新.
	{
		SPatternData* pPtnData = &g_patternList[ patternIndex ];

		//行動時間が終わったので行動の更新.
		if( time <= 0 )
		{
			//インデックスを進める.
			pPtnData->actionIndex = ( pPtnData->actionIndex + 1 ) % pPtnData->actionNum;

			//アクションデータを元にデータに反映する.
			SActionData* pActData = pPtnData->GetAt( pPtnData->actionIndex );
			time	= pPtnData->actionTime[ pPtnData->actionIndex ];
			vel		= pActData->vel;
			dir		= ( dir + pActData->dir + MAX_ANGLE ) % MAX_ANGLE;
		}

		//セットされている行動の実行.
		{
			//方向ベクトル.
			static const int dx[ST_DIR_NUM] = { 1, 1, 0, -1, -1, -1, 0, 1 };
			static const int dy[ST_DIR_NUM] = { 0, -1, -1, -1, 0, 1, 1, 1 };

			//方向.
			ST_DIR stdir = (ST_DIR)(dir / DEV_ANGLE);
			
			//位置を更新.
			pos.x += dx[dir] * vel;
			pos.y += dy[dir] * vel;

			//行動時間を減らす.
			time--;
		}
	}
}

やっていることは以下の通り．
1，特定の条件を満たしたら，パターンを変更する．
2，設定されている行動時間が終わったら，設定されているパターンを元に行動を変更する．
3，設定されている行動を元に位置を変える．

データを読み込んだ時点でほぼ全ての作業は終わっていて，
実際にデータを反映する部分は，そこまでやることはない．
ただし，これはあくまで簡易な外部データを用いているからであり，
外部データで指定するパラメータが増えれば，その分だけコード量も増える．

##注意
外部データとソースコード，両方にデータ構成に関するコメントを載せたのは，
データ構成を更新した時に一方のみしか更新していない，といったことがないようにである．
更新忘れがあるかどうかをコメントで判定できる．

外部データは，できる限り細かい単位に分けるよう心がける必要がある．
データを色々作り終えてからデータ構成を変える，となると，
修正コストが高く付いてしまうからだ．
粗いものを細かくするよりも，細かいものを粗くまとめる方が，
圧倒的にコストは安く済む．

#総括
流行り，というより一般的になりつつある，データドリブン形式の手法である．
プログラムを変えることなく行動を変えられるのは，非常に有用だと思う．
ただし，最近のゲーム業界では，データが膨大になりすぎて人による管理が難しくなる，
という問題も出ている．
上手くプロシージャルな手法と組み合わせる運用が必要になるだろう．