はじめに

この記事は裏Unreal Engine 4 (UE4) Advent Calendar 2016の10日目の記事です。

今回は「GOAP(Goal-Oriented Action Planning)」と呼ばれるシステムをUE4で組んでしまおうというものです。
環境はUE4.14でVisualStudio2015となっております。

2019-12-08：【UE4】GOAPシステムを作る最新版を投稿したのでこの記事は非推奨となりました。UE4でのGOAP実装に興味がある方はリンク先の記事を参照してください。

GOAPってなによ？

有名な実例では「F.E.A.R.」で用いられた技術で、日本語に直せば「ゴール指向アクションプランニング」です。
ゴール指向とは目標（ゴール）を達成するように行動をすることを言います。
アクションプランニングはそのままゴールへと向かう行動を順序よく組み立てることを言います。
つまり、GOAPは**「設定された目標を達成出来るように、順序よく自身の行動を組み立てる」システムと言えます。この順序よく行動を組み立てる**部分がGOAPが持つ一番の特徴であり、面白い部分だと思います。

目標と点在するアクション	導き出された行動順序

人間は意識的・無意識的にゴールを定め、プランニングを行い、ほとんどの場合導き出された一連の行動は最適化されています。
例えば「車で出かける」というゴールを定めた場合、「車のキーを持ち」->「車のドアを開け」->「車に乗り込み」->「エンジンを掛けて」->「出発」といった順序で目標を達成します。（もっと細かく列挙出来ますが、とりあえず簡単に考えます）
「車のキーを持ち」、「車のドアを開け」というのは上の図で示したように双方とも繋がってはおらず、実際には点在しているだけです。直接関係ないアクションも大量に混ざっています。（トイレに行く、ゲームをする等）
では点在するアクション群から一連の行動を求めるにはどうすれば良いのでしょうか。それは以下のようなパラメータが鍵を握ります。
「前提条件」と「効果」です。
「前提条件」とは行動を起こす前に必要な条件のことです。
続いて効果とは**行動を起こした後の状態の変化（効果）**の事をいいます。
GOAPのプランニングは「前提条件」と「効果」を繋ぎ合わせていく事で目標を達成するために必要な一連の行動を求めます。

今回はUnreal C++を使います

今まではUE4を使う場合、可能な限りBlueprintで実装するという自分ルールを適用していたのですが、お試しで書いたC++のコンソールアプリケーションでSTLや連想配列を結構使ってしまいBlueprintで同等の機能を実装するには手間がかかりすぎると判断し今回はUnreal C++で実装することにしました。

簡単な設計図

UGoapPlannerはエージェントから目標と現在の状態、実行可能なアクションを受け取り、目標を達成するように一連の行動を組み立てます。
UWorldStateは状態を表すクラスでアクセスメソッドやいくつかの便利メソッドを備えます。
UGoapNodeはUGoapPlanner内で活躍するクラスで行動を組み立てる際の探索アルゴリズムで用いられます。
UGoapActionは抽象クラスであり、これを継承してエージェントの振る舞いや前提条件、効果を定義します。
AGoapAgentは実際にフィールドに立つキャラクターです。UGoapPlannerとUGoapActionを継承したアクションを複数持っています。UGoapPlannerにはプランニングの命令を出し、渡された一連のアクションを元に必要ならば移動をし振る舞い、必要であればパラメータを変更します。

サンプルプロジェクトを上げています

こちらに簡易なサンプルプロジェクトをアップしてます。
UE4エディタとGOAP_TEST.slnを開いてVisualStudioの方を一度リビルドしてください。（ツールバーのBuild->ソリューションのリビルド)
Playボタンを押した際にOutput Logウィンドウに上から順に
output:PickupTool
output:ChopFirewood
output:DropFirewood
と表示されていればOKです。

リビルドせずに実行された方は
output:GOD
と表示されるはずです。

サンプルプロジェクトの内容は非常に単純でログ表示されるだけの退屈なものですが、GOAPのシステムは全て実装されています。エージェントはプログラマから与えられた目標を達成出来るように実行可能なアクション群から必要なアクションだけを取り上げ、順序よく組み立てています。
以降はGOAPシステムに実装されたクラスの解説です。
プロジェクトのコードと一緒に見ていただけると、より理解しやすいでしょう。

WorldState.h/cpp

最初に見ていくクラスはUWorldStateクラスです。

UPROPERTY()
	TMap<FString, bool> vars;

このメンバ変数は状態を保持するための連想配列です。
FString型のキーには状態名が入ります。例えば「毒状態か」「ドアを開けるための鍵は持っているか」「銃のマガジンには弾が込められているか」等です。
bool型の値には、そのまま状態名に対するYES・NOが入ります。YesならTRUE、NoならFALSEです。

int32 UWorldState::DistanceTo( const UWorldState* goal_state ) const
{
	int32 result = 0;

	for ( const auto& kv : goal_state->vars )
	{
		if ( !vars.Contains( kv.Key ) || vars[kv.Key] != kv.Value )
			++result;
	}

	return result;
}

DistanceTo関数はプランニング時の探索にヒューリスティックコストとして用いられます。
自身(UWorldStateのインスタンス）と目標の状態を比べて、どれほどの差があるかを求めます。

GoapAction.h/cpp

UGoapActionは初めの方の図で見せた前提条件と効果を持ち、それに加え実行時のコストも持っています。

bool UGoapAction::CheckPrecondition( const UWorldState* ws ) const
{
	for ( const auto& kv : preconditions )
	{
		if ( !ws->vars.Contains( kv.Key ) || ws->vars[kv.Key] != kv.Value )
			return false;
	}
	return true;
}

CheckPrecondition関数は引数で渡された状態を見て、前提条件をクリアしているかどうかを判定します。比較方法はDistanceTo関数と同様です。前提条件の持つ連想配列のキーが存在するかを調べ、存在していた場合は値を比較します。いずれかが異なった場合は前提条件をクリアしていないとしてFALSEを返します。

UWorldState* UGoapAction::ApplyEffects( const UWorldState* ws ) const
{
	UWorldState* temp = NewObject<UWorldState>();
	temp->vars = ws->vars;

	for ( const auto& kv : effects )
		temp->SetVariable( kv.Key, kv.Value );

	return temp;
}

ApplyEffects関数は引数で渡された状態をコピー、アクションが持つ効果を適用してコピーした方を返します。わざわざコピーする理由はGoapPlannerの項目で説明します。

GoapPlanner.h/cpp

UGoapPlannerクラスでは実際に目標に合わせてアクションを組み立てます。
その仕組は経路探索等にも使われている（むしろそちらでのほうが有名）Aアルゴリズムです。
Aアルゴリズムはグラフ探索アルゴリズムとも呼ばれています。Aアルゴリズムで調べるとほとんどの場合は道を探す用途で使われる事が多いですが、道でなくてもAで必須のヒューリスティックコストやGコスト等をうまく表現出来れば、今回のように行動でも最短の経路を調べる事が出来ます。

	if ( start->MeetsGoal( goal ) )
	{
		planActions = TArray<UGoapAction*>();
		return;
	}

Plan関数の最初は引数で渡されたエージェントの現在の状態が既に目標の状態に到達しているかをチェックします。
TRUEの場合、プランニングの必要は無いと判断し空の配列を渡して処理を終了します。

	open.Empty();
	close.Empty();
	known_nodes.Empty();

	UGoapNode* startNode = NewObject<UGoapNode>();
	startNode->IncrementID();
	startNode->ws = start;
	startNode->gCost = 0;
	startNode->hCost = CalculateHeuristic( start, goal );
	startNode->parent_id = 0;
	startNode->action = nullptr;

	known_nodes.Add( startNode->id, startNode );

	open.Add( startNode );

先のif文でFALSEだった場合はプランニングをする必要があるため、色々と準備をします。
StartNodeはほとんど内容は空っぽです。
known_nodesという探索済みのノードを格納する配列にStartNodeを格納します。
探索を始めるために一応open配列にも格納しておきます。

		UGoapNode* current = PopAndClose();

		if ( current->ws->MeetsGoal( goal ) )
		{
			do
			{
				planActions.Add( current->action );
				current = *known_nodes.Find( current->parent_id );
			} while ( current->parent_id != 0 );
			Algo::Reverse( planActions );
			return;
		}

PopAndClose関数でopen配列の先頭要素を取り出し計算済みのノードを格納するclose配列へ格納します。
次に取り出したノードの状態が目標の状態かをチェックします。
目標の状態であった場合、parent_idを辿りゴールノードからスタートノードへ戻りつつplanActionsへ格納していきます。

Algo::Reverse(planAcitons);

はEngineUtils.hにある便利関数です。
引数で渡された配列の順序を反転させます。

では、次に

for ( const auto action : actions )

以降の処理を見ていきます。
ここではエージェントが実行可能な全てのアクションに対し処理を行っていきます。

if ( action->CheckPrecondition( current->ws ) )

ループで取り出したアクションに対し、現在の状態で前提条件をクリアしているか確認します。
これがTRUEなら

UWorldState* possibility = action->ApplyEffects( current->ws );

ApplyEffects関数で現在の状態にアクションの効果を適用します。

if ( MemberOfClosed( possibility ) )
	continue;

適用した状態が既に計算済みのノードとしてClose配列に入っていれば、再度計算する必要は無いとして以降の処理を飛ばします。

UGoapNode* needle = MemberOfOpen( possibility );

適用した状態が計算中のノードとしてOpen配列に入っていれば、そのノードを取り出します。

if ( needle == nullptr )
{
	UGoapNode* found = NewObject<UGoapNode>();
	found->IncrementID();
	found->ws = possibility;
	found->gCost = current->gCost + action->cost;
	found->hCost = CalculateHeuristic( possibility, goal );
	found->parent_id = current->id;
	found->action = action;

	known_nodes.Add( found->id, found );

	AddToOpenList( found );
}

Open配列に渡した状態がOpenにもCloseにも無かった場合は、known_nodes配列とOpen配列にそれぞれ格納します。

else
{
	if ( (current->gCost + action->cost) < needle->gCost )
	{
		needle->parent_id = current->id;
		needle->gCost = current->gCost + action->cost;
		needle->hCost = CalculateHeuristic( possibility, goal );
		open.Sort();
	}
}

既に計算中のノードとしてOpen配列に格納されていた場合、needleが持つGコスト（スタートノードからこのノードまでのコスト）と現在計算しているノードのGコストとアクションの実行コストを足した数値と比べます。
needleが持つパラメータは「現時点で最短である」とされていたパラメータなので、ここでのIF文がTRUEだった場合、持っていたパラメータは最短では無いということでneedleが持つパラメータを更新します。

その２に続きます

その１ではUE_LOGで結果を表示するだけでしたが、その２ではプロジェクトに更に手を加えてフィールド上をアクションに応じて歩き回らせてみようと思います。

この記事に関して不明な点がありましたらTwitterの方にでも質問していただければと思います。

お疲れ様でした。