【UE4】HTNを実装してみた


#はじめに
この記事はUnreal Engine 4 (UE4) Advent Calendar 2019 その２の18日目の記事です。そしてUE4アドカレ「勉強してみましたシリーズ」の最終回です。
GOAPの記事を書いた勢いでHTNについても勉強してみたのでここでまとめてみようと思います。

#HTNとは
**Hierarchical 
Task 
Network**
の頭文字を取ってHTNです。日本語では**「階層型タスクネットワーク」**と（HTNプランナーとも）呼ばれます。

この技術は意思決定アルゴリズムの内、[タスクベース](https://wiki.denfaminicogamer.jp/ai_wiki/意思決定アルゴリズム#content_1001_5)に該当します。タスクベースは**ある抽象的なタスク**からどんどん**タスクを分解**していき最終的に**具体的な小さなタスク**を求め、そこから一連のアクションを導き出します。この時、抽象的なタスクを**コンポジットタスク（Composite Task）**と呼び、具体的なタスクを**プリミティブタスク（Primitive Taskも）**と呼びます。


#HTNで登場する用語たち
HTNの詳細な説明に入る前にHTNで頻出する重要な用語を紹介します。ここで出てくるいくつかの単語は[GOAPの記事](https://qiita.com/Dv7Pavilion/items/788e9074ef97087c4780)でも出てきます。

- **World State（世界の状態）**
    - 文字通り世界の状態を表すデータ。例えば＜状態名、真理値＞と表される。（＜HasOre, True＞は**（AIは）鉱石を持っている**と同義）
    - 有名なホラーFPS：**F.E.A.R.**では真理値の部分を列挙型であったりオブジェクトのポインタだったりする。
    - この**世界**という言葉は第三者からみたゲーム世界とAI本人から見たゲーム世界のどちらの意味でも使われる。


- **Preconditions（前提条件）**
    - あるタスクを実行するために満たしておくべき条件
    - 例：プレイヤーのもとへ移動する場合の前提条件として「プレイヤーを視認している」必要がある

- **Effects（効果）**
    - 世界に与える状態のこと
    - 例：鉱石を拾うタスクの効果として＜HasOre、True＞をWorld Stateへ与える

- **Primitive Task（プリミティブタスク）**
    - HTNで登場する2つのタスクの１つ。最も具体的なタスクでありAIが実行するアクションを持つ。
    - Primitive Taskは他のタスクを持つことは出来ない。
    - ツリー構造でいう**葉**に該当する。
    - 役割としてはGOAPのアクションと同じ。よってタスクを実行するための**前提条件**、**効果**を持つ。（しかし前提条件の実装は必須ではない）
    - GOAPのアクションと異なる点として**Operator**と呼ばれるアクションを持つ。（Operatorについては後述する）
    - 例：AからBへの移動、他オブジェクトへの攻撃、防御、等々

```cpp
// 擬似コード（Exploring HTN Planners through Example より）
Primitive Task [TaskName(term1, term2,...)]
    Preconditions [Condition1, Condition2, …]//有っても、無くてもよい
    Operator [OperatorName(term1, term2,...)]
    Effects [WorldState op value, WorldState = value, WorldState += value]//optional

// 少し具体的な例
Primitive Task [SprintToEnemy] // エネミーに向かって走る
    Preconditions [WsHasEnemy == true] // 前提条件は「敵を認知しているか？」
    Operator [NavigateTo(EnemyLoc, Speed_Fast)] // 実際の行動（Enemy LocにSpeed_Fastの速さで移動する）
    Effects [WsLocation = EnemyLoc, WsIsTired = true] // 現在地はEnemy Locであり疲れている状態を世界に与える
```

- **Composite Task（複合タスク）**
    - **Hierarchical（階層）**と名を持つ所以。Composite TaskやPrimitive Taskを持つことができる。（これらを**Subtasks**（詳細は後述）と呼ぶ）
    - ツリー構造でいう**枝**に該当する
    - **Methods**と呼ばれるComposite Taskの分解ルートを決める条件を持つ
    - 例：プレイヤーを倒すComposite Taskの場合、サブタスクとして「プレイヤーへの移動」「プレイヤーへの攻撃」を持つ

```cpp
// 擬似コード（Exploring HTN Planners through Example より）
Compound Task [TaskName(term1, term2,...)]
    Method 0 [Condition1, Condition2,...]
        Subtasks [task1(term1, term2,...). task2(term1,term2,...),...]
    Method 1 [Condition1, Condition2,...]
        Subtasks [task1(term1, term2,...). task2(term1,term2,...),...]

// 少し具体的な例
Compound Task [AttackEnemy]  // 敵を攻撃する
    Method 0 [WsHasTreeTrunk == true] // 前提条件「木の棍棒を所持しているか？」
        Subtasks [NavigateTo(EnemyLoc). DoTrunkSlam()] // 前提条件を満たしている時に展開できるサブタスク（「EnemyLocに移動」して、「攻撃」する）
    Method 1 [WsHasTreeTrunk == false] // 前提条件「木の棍棒は未所持か？」
        Subtasks [LiftBoulderFromGround(). ThrowBoulderAt(EnemyLoc)] // 「丸石を拾う」「EnemyLocに丸石を投げる」
```

- **Methods**
    - Composite Taskの分解ルートを示す。
    - 例：<Has Ore, True>の場合、Subtasks_Aを展開。条件を満たさない場合はSubtasks_Bを展開。

<img width=50% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/72fb936b-587a-a385-2294-5f8ee1900c8e.png">

    
- **Operator（オペレータ）**
    - 実際にAIが行うアクション。Primitive TaskはこのOperatorを実行してAIを世界で行動させる。
    - 例：実際にAI Move Toノードを定義したMove To等

- **Subtasks**
    - Composite Taskが持つ他の（もしくは自身の）Composite TaskやPrimitive Taskのリスト
    - Methodsに沿ってComposite Taskを分解していきSubtasksを得る

- **Domain（ドメイン）**
    - Composite TaskやPrimitive Taskを保持する。


#HTNプランニングの外観
HTNプランニングの全体のイメージとしては[Exploring HTN Planners through Example](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf)にある図が非常にわかりやすいです。

World StateはAIが持つSensors（UE4でいうAI PerceptionやPawn Sensingコンポーネントのこと）によって常に更新されます。PlannerはDomainに保持されている各Composite TaskをMethodsによって分解し、分解するべきComposite Taskが無くなった時点でのPrimitive Taskを一連のアクションとして返します。Plan Runner（ここではAI自身）は一連のアクションを実行しPrimitive Taskが持つEffectをWorld Stateへ適用します。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/f998d17f-c02e-6355-082c-df4aaf5ee482.png">

#GOAPとの違い

HTNについてのひと通りの説明が終わったところで、もう１つのプランニングを用いた意思決定アルゴリズムである**GOAP**との違いを紹介していきます。

####GOAPによるプランニング
GOAPでのプランニングは**A＊による経路探索**によって実現されます。
HTNでいうところの「Primitive Task」と「Operator」両方の機能を備えた**Action**を定義しDomainに放り込まれ、A＊によって各アクションの前提条件と効果を連鎖的につなぎ合わせることで一連のアクションを導き出します。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/37ef3119-36cd-0f9b-79c0-ef157a25ceec.png">

####HTN
HTNでのプランニングは**[深さ優先探索（Depth First Search, DFS）](https://ja.wikipedia.org/wiki/深さ優先探索)による経路探索**によって実現されます。
Composite TaskをMethodに基づいて分解を行い、Primitive Taskが出現するとそのPrimitive Taskが持つ効果をWorld Stateへと適用し実行リストへと格納されます。この時点で未だ分解されていないComposite Taskがあれば再び分解を行います。これを未分解のComposite Taskが無くなるまで繰り返します。
このComposite Taskの分解と出現したPrimitive Taskが持つ効果の適用を繰り返し、必要なComposite Taskを分解し尽くしたときに目標を達成するための一連のアクションが手に入ります。

以下の画像ではSubtasksの数字順にPrimitive Taskが出現します。Composite TaskであるPickup Oreの目標を達成するには
MoveTo(ToolStorage) -> Pickup(Tool) -> MoveTo(Mine) -> Pickup(Ore)
という順番にタスクを実行すれば良いことになります。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/dfa396fc-bce2-dd08-b67b-f53da1d8f481.png">


もう1つ分かりやすい図として[Exploring HTN Planners through Example](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf)にある図も載せておきます。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/8effbd37-a9bf-64fa-9a5b-e79a055711fc.png">


#プロジェクトはこちら
いつものようにOneDriveにてプロジェクトを配布しています。Unreal C++を使用しているのでVisual Studioの導入が必要だと思われます。

UE4バージョン：4.23.1
Visual Studio Community 2019 - Version 16.1.3
https://1drv.ms/u/s!Au-8FqgREBKZiTZ2QD6o4Z4FE0Ss?e=CBCrxs

#プログラム解説
ここの実装は@yhaseさんの[lua_planner](https://github.com/yhase7/lua_planner)と[Exploring HTN Planners through Example](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf)を参考にしました。

##C++側
###HTNBaseTasks.h/cpp
これらのファイルにはHTNに必要な各タスクが定義されています。最初にPrimitive Taskのクラスから見ていきます。

Primitive Taskは前提条件と2種類の効果を持ちます。Expected Effectsは**「プランニング時にのみ考慮される効果」**、つまり「このタスクを実行するときはこういう状態になっていて欲しいな～」という期待を込めた効果を表します。Effectsは**「実世界に影響を与える効果」**を表します。このように効果を2種類に分けることによりOperator実行中に何らかの理由によって世界の状態が変化した場合に再プランニングで対処することが出来るようになります。（2種類の効果の実装は[Exploring HTN Planners through Example](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf)を参考にしました）

プロジェクトの実装ではPrimitive Taskが所持できるOperatorは１つのみです。[『LEFT ALIVE』で採用されたHTNを用いたゲームAIとは？](https://www.gamebusiness.jp/article/2019/10/28/16360.html)で紹介されているプロジェクトでは複数のOperatorを設定でき同時に実行できるようにしていますがUE4ではBP側にSequenceという並行処理のノードがあるのでこれで代用出来るのではと思いOperator１つのみの実装としました。

```cpp
UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNPrimitiveTask : public UHTNTaskBase
{
	GENERATED_BODY()
private:
protected:
	UPROPERTY(EditDefaultsOnly, Category = "HTN")
		TSubclassOf<UHTNOperator> OperatorClasses;
	UPROPERTY(EditDefaultsOnly, Category = "HTN")
		FHTNWorldState Preconditions;
	UPROPERTY(EditDefaultsOnly, Category = "HTN")
		FHTNWorldState ExpectedEffects;

	UPROPERTY()
		UHTNOperator* Operator;			// 実際のアクション
	UPROPERTY()
		FHTNWorldState Effects;

	// 実世界に影響を与える効果はBP側で定義する。（「何個集めたときにTRUEにする」みたいなことをしたいので）
	UFUNCTION(BlueprintImplementableEvent, BlueprintCallable, Category = "HTN")
		void DefineEffects(FHTNWorldState& WS, class AAIController* OwnerController, APawn* ControlledPawn);

public:
	virtual void Initialize() override;
	// Expected EffectsをWorld Stateに適用する。（プランニング時にのみ呼ばれる）
	virtual void ApplyExpectedEffects(FHTNWorldState& WS) { WS.Update(ExpectedEffects); }

	// EffectsをWorld Stateに適用する（Operator実行後に呼ばれる）
	virtual void ApplyEffects(FHTNWorldState& WS, class AAIController* OwnerController, APawn* ControlledPawn) 
	{ 
		DefineEffects(Effects, OwnerController, ControlledPawn);  
		WS.Update(Effects); 
	}

	// 前提条件のチェック
	virtual bool CheckPreconditions(const FHTNWorldState& WS);

	UHTNOperator* GetOperator() const { return Operator; }
};
```

---

Composite Taskはほとんどやることが無くComposite Taskを分解するためのMethodや分解した結果を保持するSubtasks配列を持つくらいです。

```cpp
UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNCompositeTask : public UHTNTaskBase
{
	GENERATED_BODY()
private:
	void ClearSubtasks() { Subtasks.Empty(); }
protected:
	UPROPERTY(EditDefaultsOnly, Category = "HTN")
		TArray<TSubclassOf<UHTNMethod>> MethodClasses;

	UPROPERTY()
		TArray<UHTNMethod*> Methods;
	UPROPERTY()
		TArray<FString> Subtasks;
public:
	virtual void Initialize() override;

	// StartIndex番目のMethodを実行し、Composite Taskを分解する
	bool FindSatisfiedMethod(const FHTNWorldState& WS, int StartIndex = 0);

	const TArray<FString>& GetSubtasks() const { return Subtasks; }
};
```

###HTNMethodsOperators.h/cpp
ここではComposite Taskの分解ルートを示す**Methodクラス**と実際にAIの振る舞いが定義される**Operatorクラス**が定義されます。MethodクラスはBP側の実装が肝なのでここでは省略します。

OperatorクラスはAIが実際にゲーム世界での振る舞いを定義する場所なので多くの機能がBP側に公開されています。このクラスの実装はBehavior TreeのTaskノードの実装を参考にしました。
ReceiveExecuteActionには実際の振る舞いを定義します。よってMove Toノード等を配置する場所はこの関数内（BP側でイベントとして定義）になります。Behavior TreeのTaskノードと同様にReceiveExecuteActionでアクションを実行し終えたタイミングでFinishExecute関数を呼ぶ必要があります。これによってOperationの実行は成功、失敗、何らかの理由で中断されたかを知ることが出来ます。この結果はアクターにアタッチするHTNComponentで活用されます。（FInishExecute関数が呼ばれなかったときは「実行中」と判断されます）

```cpp
enum class EOperationResult
{
	Success,
	Failed,
	Aborted,
	InProgress,
};

UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNOperator : public UObject
{
	GENERATED_BODY()
private:
protected:
	EOperationResult Result;
	bool bActive;
	UFUNCTION(BlueprintImplementableEvent, Category = "HTN")
		void ReceiveInitializeAction(class AAIController* OwnerController, class APawn* ControlledPawn);
	UFUNCTION(BlueprintImplementableEvent, Category = "HTN")
		void ReceiveExecuteAction(class AAIController* OwnerController, class APawn* ControlledPawn);
	UFUNCTION(BlueprintCallable, Category = "HTN")
		void FinishExecute(bool bSuccess) { Result = bSuccess ? EOperationResult::Success : EOperationResult::Failed; }
	UFUNCTION(BlueprintCallable, Category = "HTN")
		void FinishAbort() { Result = EOperationResult::Aborted; }
public:
	UHTNOperator()
	{
		Result = EOperationResult::InProgress;
	}

	void Initialize(class AAIController* OwnerController, class APawn* ControlledPawn)
	{
		bActive = true;
		Result = EOperationResult::InProgress;
		ReceiveInitializeAction(OwnerController, ControlledPawn);
	}

	void Execute(class AAIController* OwnerController, class APawn* ControlledPawn)
	{
		Result = EOperationResult::InProgress;
		ReceiveExecuteAction(OwnerController, ControlledPawn);
	}

	void Terminate() { bActive = false; }
	EOperationResult GetResult() const { return Result; }
	bool IsActivated()const { return bActive; }
};
```

###HTNPlanner.h/cpp
HTNによるプランニングはこれらのファイルで実装されます。DomainについてはPrimitive TaskやComposite Taskを保持するだけのクラスなので説明は省略します。

UHTNPlannerはプラン生成の他に深さ優先探索で用いられるバックトラックのための機能がいくつか備わっています。
PSがプランナーの探索状態を表し、ResorePointsがバックトラックに用いるスタックです。RecordDecompositionOfTask関数で現在のプランナーの状態のコピーを取りスタックへ格納します。RestoreToLastMethodIndexAndTasksToProcess関数とRestoreToLastDecomposedTask関数はどちらもプランナーの状態を過去へと戻します。

```cpp
UCLASS()
class HTNPLANNINGEXAMPLE_API UHTNPlanner : public UObject
{
	GENERATED_BODY()
private:

private:
	UPROPERTY()
		TArray<FPlannerState> RestorePoints;
	UPROPERTY()
		FPlannerState PS;

	// 復元ポイントを作成＆スタックにプッシュ
	void RecordDecompositionOfTask() { RestorePoints.Add(PS); }
	// Method IndexとTasks To Processのデータのみ復元
	void RestoreToLastMethodIndexAndTasksToProcess()
	{
		// Pop()で末尾要素を取り出して削除
		FPlannerState RestorePS = RestorePoints.Pop();
		PS.CurrentTask = RestorePS.CurrentTask;
		PS.MethodIndex = RestorePS.MethodIndex;
		PS.TasksToProcess = RestorePS.TasksToProcess;
	}
	// プランナーの状態を全て復元
	void RestoreToLastDecomposedTask() { PS = RestorePoints.Pop(); }
	// 復元できるかチェック
	bool CanRollBack() const { return RestorePoints.Num() > 0; }

protected:
public:
	void GeneratePlan(const FHTNWorldState& InitialState, const UHTNDomain* Domain, FString RootTaskName,  TArray<UHTNPrimitiveTask*>& OutPrimitiveActions);

};
```

---

プランを生成するGeneratePlan関数を見ていきます。全てのコードを一度に載っけると少々長めなので分割しながら説明します。

タスクを探索中のタスクを表すTasksToProcessから取り出した直後のコードです。こちらでは取り出したタスクがComposite Taskかをチェックします。
Composite Taskだった場合、FindSatisfiedMethod関数を実行してWorld StateとMethod Indexに応じたSubtasksがBP側にて生成されます。返り値がTRUE、つまり無事にSubtasksが生成された場合、その時点でのプランナーの状態をスタックへ保存します。ここがアクション経路の分岐点なので進んだルートの先でプランが成立しなかった場合はバックトラックによりこの時点に戻ることが出来ます。

```cpp
		// 取り出したタスクは「Composite」？
		UHTNCompositeTask* const Composite = Domain->GetComposite(PS.CurrentTask);
		if (Composite)
		{
			// MethodIndexに応じたMethodを実行して分解する。
			if (Composite->FindSatisfiedMethod(PS.WorldState, PS.MethodIndex))
			{
				RecordDecompositionOfTask();
				PS.MethodIndex = 0;
				// 分解した結果を取得
				TArray<FString> Subtasks = Composite->GetSubtasks();
				// 取得したSubtasksは探索中のタスクリストの先頭に挿入される
				PS.TasksToProcess.Insert(Subtasks, 0);
			}
			// 「条件が合わずに分解出来なかった」 or 「実行するMethodが無かった」場合はバックトラックする
			else if (CanRollBack())
			{
				RestoreToLastMethodIndexAndTasksToProcess();
				PS.MethodIndex++;
				PS.TasksToProcess.Insert(PS.CurrentTask, 0);
			}
			continue;
		}

```

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/9a54acc3-c8bb-c944-1f77-0574d49b4701.png">


---

取り出したタスクがPrimitive Taskの場合、現時点でのWorld Stateで前提条件のチェックを行います。前提条件をクリアした場合、ApplyExpectedEffectsによりプランニング時にのみ適用される効果をWorld Stateへ適用し出力されるプランへと組み込まれます。前提条件をクリアできなかった場合はバックトラックが実行されます。

```cpp
		// 取り出したタスクは「Primitive」？
		UHTNPrimitiveTask* const Primitive = Domain->GetPrimitive(PS.CurrentTask);
		if (Primitive)
		{
			// 前提条件のチェック
			if (Primitive->CheckPreconditions(PS.WorldState))
			{
				// World Stateに適用（実世界には影響しない）
				Primitive->ApplyExpectedEffects(PS.WorldState);
				// 最終的なプランに加える
				PS.FinalPrimitives.Add(Primitive);
			}
			// バックトラックします
			else if (CanRollBack())
			{
				RestoreToLastDecomposedTask();
				PS.TasksToProcess.Add(PS.CurrentTask);
			}
			continue;
		}
```

---

Composite TaskやPrimitive Taskを取り出したときの動作を繰り返し、探索中のタスクのリストであるTasksToProcessが空っぽになったら**「プランが無事に生成できた」**となり出力されます。

##BP側
###BP_Composite_ホニャララ
UHTNCompositeTaskの派生BPはかなり単純で使用するMethodのクラスとタスク名を指定するだけです。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/b13222b7-a4ba-1599-6b45-4643a6ad4d43.png">

##BP_Primitive_ホニャララ
UHTNPrimitiveTaskの派生BPでは実際の振る舞いを定義したOperatorクラス、期待される効果であるExpected Effects、タスク名、実世界に適用するEffectsを定義しています。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/8033ae61-64ac-e729-ab64-0153789aaa9b.png">

BP_Primitive_DropOreでは条件を用いてWorld Stateの値を設定しています。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/3c54916c-95b3-9f82-f934-8d1eb25e7901.png">

###BP_Operator_ホニャララ
以下の図はBP_Operator_MoveToでの処理です。名前が表す通りAIの移動処理を実装しています。
Receive Execute Actionでは移動処理を実行していますが目的に到達する前に次のタスクへ遷移してしまわないようにFinish Executeを呼んでいません。よってこのOperatorはInProgressを返すので次のTickでもこのOperatorが呼ばれます。
Receive Initialize ActionでHTNComponentを所持するPawnの参照からイベントディスパッチャを取り出しバインドします。このイベントディスパッチャは移動が終了したときに呼び出されますのでバインドしたイベントではFinish Executeを呼び出し引数にTrueを与えます。ここで初めてこのOperatorは処理を完全に終了することが出来ます。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/8d63c769-7164-a287-6645-13875f9efc91.png">

###BP_Method_ホニャララ
以下の図はBP_Method_CorrectOreの一部を切り取ったものです。
World StateによってSubtasksに与えられる内容が異なります。Has ToolがFalseの場合は採掘道具を取得するComposite TaskがSubtasksとして与えられますがその他にもCompositeCorrectOreが指定されています。CompositeCorrectOreはBP_Method_CorrectOreを持つBP_Composite_CorrectOreのことですのでこれは再帰を意味しています。

図では枠で囲まれて右上に数字が書かれていますが、これはSubtasksに分解される順番を示しています。
Has ToolがFalseの場合はCompositePickupToolの中身が分解されPrimitive TaskであるPickupToolが出現するので、このPickupToolのExpected Effectsを適用します。CompositeCorrectOreがあるので再びCompositeCorrectOreが分解されますが、今度はHas ToolがTrueになっているので一段下のHas OreがFalseの場合の分解に移ります。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/a250fa30-4f63-d207-9c96-59e6c7a99b0d.png">

以下の図はBP_Method_CorrectOreの全分解ルートを示したものです。

<img width=70% src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104467/c8997653-77cf-0b7e-9743-91c32b41a43d.png">


#HTNのいいところ
プロジェクトの説明をひと通り終えたところでHTNの利点を紹介します。

- **直感的な記述が可能**
    - 大きなタスクを分解して小さなタスクの集合とする考えは人間にとっても非常に自然で馴染み深い意思決定方法。
    - Behavior Treeと比べるとAIの行動についての表現力は高いと言える。

- **実装は結構シンプル**
    - HTNプランニングシステム自体はそれほど複雑な作りではないので組み込みやすい。

- **実行速度が早い**
    - 急激な環境の変化が無い場合は一度のプラン生成をするだけなので意思決定時の負荷は低いと言える。
    - プランニング自体もソートを用いるA＊アルゴリズムと比べると処理速度が早い。（もちろんComposite Taskの複雑さによる）



#おわりに
UE4アドカレ「勉強してみましたシリーズ」最終回でした。
HTNは思っていた以上に実装しやすくGOAPと比べると直感的にAIの振る舞いを記述出来るのでサンプル作成は結構楽しかったです。ですがUE4にビルトインされているBehavior Treeと比べるとグラフィカルなツールが無いので全体の見通しは少し悪いですね。あとデバッグもしづらいです。
しかし[プレイヤーに反応するだけのAIはもう古い！ゲームAIへのプランニング技術の導入](https://cedil.cesa.or.jp/cedil_sessions/view/1476)で解説されているようにHTNプランニングによって生成されたプランをBehavior Treeとして出力する方法もあるようです。これならグラフィカルなツールが無い＆デバッグしづらい問題も一気に解決できそうな気がします。


#余談：UE4にはHTNの公式プラグインがあるよ
UE4には標準でHTNを実装したプラグインが備わっています。
Epic GamesのAI Tech LeadのMieszko Zielinskiさんのツイートでは「フォートナイト：世界を救え」や「Paragon」でも使われたようです。

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">I&#39;d also like to add that our C++ side has HTN plugin and a generic A* implementation (used in FN:StW and Paragon). We also have an extensive AI debugging toolset (vislog, gameplay debugger, bt debugger). Not to mention two avoidance implementations! ;)</p>&mdash; Mieszko Zielinski (@MieszkoZ) <a href="https://twitter.com/MieszkoZ/status/1192150856411598848?ref_src=twsrc%5Etfw">November 6, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

---

公式プラグイン版HTNですが
C:\Program Files\Epic Games\UE_バージョン名\Engine\Plugins\AI\HTNPlanner
にあります。
UE4.23.1をインストール自分の環境では
C:\Program Files\Epic Games\UE_4.23\Engine\Plugins\AI\HTNPlanner
にありました。

しかし上記にあるHTNプラグインはHTNの実装は確認出来ますが使い方については特に書かれていません。GitHubにてダウンロードできるUE4のソースコード内ではHTNプラグインの自動化テストが記述されているのでそちらからある程度使い方について見当が付くと思います。
GitHub上では
[リリース版ブランチ/Engine/Plugins/AI/HTNPlanner/Source/HTNTestSuite/Private/HTNTest.cpp](https://github.com/EpicGames/UnrealEngine/blob/release/Engine/Plugins/AI/HTNPlanner/Source/HTNTestSuite/Private/HTNTest.cpp)
にて自動化テストが記述されています。

もしクローンしたUE4をお持ちの場合[UE4 VisualStudioを使ってエンジンをデバッグする](http://unrealengine.hatenablog.com/entry/2014/08/22/215802)を参考にエンジンをデバッグ出来る状態にしたプロジェクトをC++テンプレートで作成します。上記の自動化テストが記述されたファイルのどこかにブレークポイントを配置しPluginの
「Built-In -> AI -> HTN Plunner」「Built-In -> Testing -> EditorTests」
を有効にします。続いてSession FrontendのAutomationタブを開きHTNの自動化テストを実行すればブレークポイントで停止するので自由にステップ実行で処理を確認することが出来ます。


#参考資料
- 実例で学ぶゲームAIプログラミング 第９章 ゴール駆動型エージェントの行動
    - タイトルでは「ゴール駆動型」となっていますが内容はHTNプランニングとほぼ同じです。

- http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf
    - 本文中でも度々登場したHTNについての解説と実例。かなり参考になる。

- https://www.gamebusiness.jp/article/2019/10/28/16360.html
    - つい最近行われたHTNを採用したゲームAIについてのポストモーテム。いろいろな課題が挙げられている。

- https://hasht.hatenablog.com/entry/2019/06/24/202237
    - GOAP記事でもお世話になったhasht氏によるHTNについての記事

- http://igda.sakura.ne.jp/sblo_files/ai-igdajp/GDC2010/GDC2010_Report_ForRT_ymiyake.pdf
    - HTNを用いた商用ゲームで有名な例の１つであるKillZone2についての解説

- https://www.guerrilla-games.com/read/killzone-2-multiplayer-bots
    - ゲリラゲームズにて公開されているKillZone2の発表資料

- https://aiandgames.com/cybertron-intel/
    - HTNが用いられた商用ゲームの１つTRANSFORMERS: FALL OF CYBERTRON（日本語版は無し？）についての解説。
    - このページを掲載している「AI&Games」は文字通りゲームとゲームAIについて詳しい考察をしているのでGoogle翻訳等を駆使してちょこちょこ読むと楽しい。

- https://arxiv.org/pdf/1106.4869.pdf
    - HTNの派生でありHTNをよりシンプルなものとした「Simple Hierarchical Orderd Planner 2：SHOP2」の論文

- https://www.reddit.com/r/gamedev/comments/1ozugf/whats_the_difference_between_behavior_trees_and/ccxce8h/
    - Behavior TreeとHTNの違いについての質問。GOAPについても述べられている。

- https://stackoverflow.com/questions/50771965/hierarchical-task-network-htn-in-ai
    - HTNとは何なのか？についての質問とその回答

- https://blog.inductorsoftware.com/blog/htnoverview
    - HTNの概要についてまとめたブログ

- http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter04_Behavior_Selection_Algorithms.pdf
    - HTNとは直接関係が無いがいくつかあるゲームAIの意思決定方法の選び方について書かれたもの。意思決定方法の全体像を掴むのには最適かも。