Unityでの経路探索とAIに何を使うか

# はじめに
Unityで経路探索やAIを使うにあたって、
どんなものがあるのか？
どんな違いがあるのか？
どうやって使うのか？
を以下に絞って比較し、それぞれの簡単な使用方法を紹介します。

- 経路探索
  - Unity標準のNavMesh
  - A* Pathfinding Project
- AI
  - StateMachine（ImtStateMachine）
  - BehaviourTree（FluidBehaviorTree）

# どんなものがあるのか
### 経路探索
主に見かけるのは以下の2つです。

- **Unity標準のNavMesh**
  - Unityの標準機能なのでそのまま使えます。
  - キャラが通れる経路をメッシュ状に表現したものです。
- **A* Pathfinding Project**
  - NavMeshの他にも、GridGraph や PointGraph での経路探索もできるアセットです。
  - Pro版とFree版があります。

### AI
簡易なAIの手法として2つピックアップします。
（オープンワールドやMMOなどのスケールの大きいゲームでの複雑なAIでは、これらを組み合わせたり、別の手法にしたりといったアプローチが必要になると思われます。）

- **StateMachine**
  - ステート(状態)に応じて行動させて、ステートを切り替えていくことで様々な行動を表現します。  
  ![StateMachine簡易図.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/115246/b9d97bc0-72cd-b03a-4932-17bfc443c83b.png)
- **BehaviourTree**
  - 状況に応じた行動をTree状に表現して、Tree全体を都度走査して行動させます。  
  ![BehaviourTree簡易図.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/115246/ae73a4ae-0eca-92ab-f980-d5a606e721f9.png)

# どんな違いがあるのか
## 経路探索の比較
項目 | Unity標準のNavMesh | A* Pathfinding Project
--- | --- | ---
導入 | マップとなるオブジェクトをStatic（もしくはNavigation-Static）に設定。 | アセットのインポート。<br>Pathfinderコンポーネント追加。
Editorでの経路生成 | Window → AI → Navigation から設定してBake。 | 空オブジェクトにPathfinderコンポーネントを追加して、NavMesh/Grid/PointどれかのGraphを登録してScan。
動的な経路生成 | `NavMeshSurface.BuildNavMesh()`<br>（オブジェクトをStaticにする必要はない）<br>別途GitHubからコードを拾ってくる必要がある。 | `AstarPath.Scan()`<br>事前にPathfinderコンポーネントに空Graphの追加が必要。
移動経路のパス取得 | NavMeshAgent に計算させるか、パスのみ計算する。 | Seeker に計算させる。<br>Modifier コンポーネントを追加しておくとパスが自動補正される。
移動 | 取得したパスを辿るか、NavMeshAgentで移動。<br>NavMeshAgentでspeed類を0にして自動移動させないようにした場合でも、updatePositionをtrueにしておくとNavMesh範囲から外れないように移動させられる。 | 取得したパスを辿る。
障害物 | NavMeshObstacleを配置するとNavMeshが更新される。 | Collider.boundsを使用してGraphUpdateObjectを生成・反映すると更新される。<br>NavMesh用のNavmeshCut機能はPro版のみ。
経路設定のセーブ・ロード | BakeすることでNavMeshDataファイルを生成。<br>`NavMesh.AddNavMeshData()`でロード。<br>`NavMesh.RemoveNavMeshData()`で破棄。 | Pathfinderコンポーネントからセーブしてファイル生成。<br>`AstarPath.data.DeserializeGraphs()`でロード。<br>`AstarPath.data.RemoveGraph()`で破棄。

## AIの比較

項目 | StateMachine | BehaviourTree
--- | --- | ---
全体把握 | ステートが増えると全体像を把握しにくくなる。<br>特に遷移関係がややこしくなる。 | 全体像を把握しやすい。 
実行時の状態把握 | 現在の状態をContextに保持しておくなどして、CurrentStateTypeといった単一の情報で把握できる。 | 現在の状態を把握しづらい場合がある。<br>（各種状況が組み合ってTreeを走査するので、Stateなどの単一の情報で表現しづらい）<br>GUIでTree状態を見られれば全体像と同じく把握は容易。
実装 | ステートの追加にクラス自体の追加が必要となり、単純なステートだった場合は BehaviourTree と比較してコード記述が多くなる。 | 行動の追加に必要なコード量が、StateMachine と比較して少ない。<br>ただし、書き方によってはスパゲティになりやすい側面もある。
追加・修正 | 行動の追加・修正時に全体像を把握せずに、関連するステートのみ把握していれば十分な場合がある。 | 行動の追加・修正時に全体像を把握しないといけない場合がある。<br>（内部まで詳細に把握する必要は無いが、関連しない行動であっても、Tree上の優先度やどの状況での行動なのかの把握が必要になる場合がある）

### アセットの比較
AIに後述するアセット（ImtStateMachine, FluidBehaviorTree）を使用した場合における比較です。
（AIの比較と重複する部分もあります。）

項目 | ImtStateMachine | FluidBehaviorTree
--- | --- | ---
実装方法 | ステートごとにクラスを実装。 | 単一コードでツリーを実装。<br>Treeを部分的にパーツとして作成し、別のTreeに追加することも可能。 
行動の切り替え | 各ステートごとの遷移可否関係を設定しておく必要あり。<br>ステートを増やしたらその都度遷移関係の記述も必要。 | 毎フレームTree全体を走査して、都度現状に対応した行動を処理させる。
実行 | 現在のステートのクラスのみが実行される。 | 毎フレームTree全体を走査するため、不要なチェックが発生する場合がある。<br>Wait や Continue で Tree全体の走査ではなく行動を継続させることも可能。
全体把握 | GUI表示機能なし。<br>ステート遷移を矢印で表現するとしたら、ステートが増えるのに応じて矢印も増えるため全体の把握が難しくなる。<br>遷移可否の関係性は `ImtStateMachine.AddTransition()` をまとめて記載することで把握しやすくはできる。<br>ただし、ステートクラス側で遷移ガードができるため把握しづらくなる場合がある。 | 実行中にTreeをGUI表示可能。<br>（実行中のみ表示可能で、編集は不可。）<br>Treeを辿ることで、どの状況ならどの行動をするかを把握できる。<br>コード記述自体がTree状になるためGUIでなくても俯瞰での把握は難しくない。
実行時の状態把握 | CurrentStateType などを用意して現在のステートを把握できるようにすれば、エディタでも本番環境でもログ等ですぐ判別できる。<br>単一の状態として表現するため、今どの行動をしているのかは把握しやすい。 | エディタでの確認はTreeのGUI表示を見ることで可能。<br>実機環境用の確認機能はない。<br>実装するとしても、単一の状態としての表現ではなく全体の状況に応じて行動を選択するため、複数情報が必要。
キャッチアップ | 行動をクラスごとに切り替える作りであることが分かれば、理解は容易。<br>遷移関係の把握はステートが増えるごとにややこしくなるが、行動の実装・修正は単一ステートや関連ステートの一部のみの把握で済む場合もある。 | Sequence, Selector の組み合わせ方や優先順位の考慮が必要。<br>状況に応じて都度行動を変化させるため、全体像を把握しておかないと意図しない行動をさせてしまう場合がある。


# どうやって使うのか

## Unity標準のNavMesh
Window → AI → Navigation を開きます。

Objectタブを選択した状態で、Hierarchyからマップとなる床や壁のオブジェクトを選択すると、対象オブジェクトの設定を変更できます。
Navigation Static にチェックして、Navigation Area を床であれば Walkable, 壁であれば Not Walkable にします。

すべてのマップ用オブジェクトを設定したら、Bakeタブの中にあるBakeボタンを押してNavMeshを生成します。
SceneビューでBakeした結果を確認できます。

実行中にNavMeshを生成・更新するには、NavMeshComponentsという追加機能群が必要です。
https://github.com/Unity-Technologies/NavMeshComponents
NavMeshSurfaceコンポーネントを使用することで、動的生成が可能になります。

キャラクターなどの移動させたいオブジェクトに、NavMeshAgentコンポーネントを追加します。
`SetDestination()` で移動先座標を設定すると、自動で移動し始めます。

```cs
navMeshAgent.SetDestination(targetPosition);
```

または、移動経路となるパスのみを取得することもできます。

```cs
var navMeshPath = new NavMeshPath();
NavMesh.CalculatePath(myPosition, targetPosition, -1, navMeshPath);
// navMeshPath.corners に移動経路が入っています
```


## A* Pathfinding Project
Free版があるので、ダウンロードしてみて採用するかどうか検討できます。
https://arongranberg.com/astar/download
（Pro版の機能が不要であればFree版を採用することもできます。）

空オブジェクトを生成して、 Component → Pathfinding → Pathfinder でコンポーネントを追加します。

InspectorでAdd Mesh Graphから設定したいタイプを選択して追加し、Scanボタンで経路を生成します。
なお、NavMeshを使用する場合、Meshデータが必要となります。(アセット内にサンプルが入っています。)
GridGraphの場合は、NodeSize, Width, Depth等の数値設定のみで生成できます。
SceneビューでScanした結果を確認できます。

実行中にNavMeshやGridGraphを生成・更新するには、Inspectorで設定済みのNavGraphを取得して、設定を更新するなどしてからScanします。

```cs
var graph = AstarPath.active.graphs[0] as NavMeshGraph;
graph.sourceMesh = mesh;

AstarPath.active.Scan();
```

キャラクターなどの移動させたいオブジェクトに、Seekerコンポーネントを追加して、移動経路を取得できます。

```cs
astarSeeker.StartPath(myPosition, targetPosition, path =>
{
    if (!path.error)
    {
    	// path.vectorPath に移動経路が入っています
    }
});
```

### ImtStateMachine (StateMachine)
IceMilkTeaというフレームワークの一部として公開されている、ImtStateMachineを使用する例です。
https://github.com/Sinoa/IceMilkTea/blob/develop/Packages/IceMilkTea/Runtime/Core/UnitCode/PureCsharp/StateMachine.cs

参照用のメンバを用意しておきます。

```cs
public class StateMachineAi : MonoBehaviour
{
    // 各ステートクラスでの参照用
    Character character;

    // ステート遷移用ID
    enum TransitionEventId
    {
        Move,
        Attack,
    }
}
```

ステートごとの挙動を記述したクラスを作成します。

```cs
// 移動ステート
class MoveState : ImtStateMachine<StateMachineAi, TransitionEventId>.State
{
    protected override void Update()
    {
        Context.character.Move();

        // ターゲットに近づいたら攻撃ステートに遷移
        if (Context.character.IsNearTarget())
        {
            Context.stateMachine.SendEvent(TransitionEventId.Attack);
        }
    }
}
```

```cs
// 攻撃ステート
class AttackState : ImtStateMachine<StateMachineAi, TransitionEventId>.State
{
    protected override void Enter()
    {
        // ステート遷移時に攻撃開始
        Context.character.Attack();
    }

    protected override void Update()
    {
        // 攻撃が終わったら移動ステートに遷移
        if (!Context.character.IsAttacking())
        {
            Context.stateMachine.SendEvent(TransitionEventId.Move);
        }
    }
}
```
`Enter()`, `Update()` 以外にも、終了処理・特定時の遷移ガードといった機能もあります。

初期化として、StateMachineを生成して、ステートの遷移条件を設定します。

```cs
void Start()
{
	stateMachine = new ImtStateMachine<CasualEnemyStateMachineAi, TransitionEventId>(this);
	// 遷移条件の設定
	stateMachine.AddTransition<MoveState, AttackState>(TransitionEventId.Attack);
	stateMachine.AddTransition<AttackState, MoveState>(TransitionEventId.Move);
	stateMachine.SetStartState<MoveState>();
}
```

後は、ImtStateMachine.Update()を呼ぶことで、現在のステートのクラスのUpdateが動作します。

```cs
void Update()
{
    stateMachine.Update();
}
```


### FluidBehaviorTree (BehaviourTree)
GitHubで公開されているFluidBehaviorTreeを使用する例です。
https://github.com/ashblue/fluid-behavior-tree
コードからTreeを作成し、Editorでの実行中にTreeの状態をGUIで確認することができます。
（蛇足ですが、Behavior / Bihaviour の`u`が入るかどうかはアメリカ式かイギリス式かの違いで、意味は同じです。）

Treeを生成します。

```cs
void Start()
{
    tree = new BehaviorTreeBuilder(gameObject)
        .Selector()
            .Sequence("攻撃")
                .Condition(("攻撃していないか") => !character.IsAttaking())
                .Condition(("ターゲットとの距離判定") => character.IsNearTarget())
                .Do(() =>
                {
                    character.Attack();
                    return TaskStatus.Success;
                })
            .End()
            .Sequence("移動")
                .Condition(("攻撃していないか") => !character.IsAttaking())
                .Do(() =>
                {
                    character.Move();
                    return TaskStatus.Success;
                })
            .End()
        .End()
        .Build();
}
```
`Selector()`, `Sequence()`は子をすべて処理するけれど途中の成否によって処理を終了する仕組みで、
`Condition()`は条件判定、`Do()`は内包する処理を実行する仕組みです。
他にも、処理の待機／継続・成否の反転・Treeのパーツ化といった機能もあります。

後は、`BehaviorTree.Tick()`により、Treeを走査します。
`MonoBehaviour.Update()`で呼べば、毎フレーム走査することになります。

```cs
void Update()
{
    tree.Tick();
}
```

# 終わりに
結局の所どれを使えば良いのかは、ゲームの規模やジャンルによっても変わります。
いずれも一長一短あるため、GridGraphが使いたい、複雑なAIは不要、などの要望・状況に応じて選択できると良いかと思います。
Unityで経路探索・AIを実装したいけれどとりあえずどうしたらいいのか、といった方へのとっかかりとなることができれば幸いです。