【CEDEC2017】「Perception Tree ～Behavior Treeを応用したお手軽、柔軟な環境認識システム～」講演レポート

# 「Perception Tree ～Behavior Treeを応用したお手軽、柔軟な環境認識システム～」講演レポート

## 概要

このセッションはCEDEC2017、8/30の14:50~15:50に行われたものです。SNS公開可能と記載されていたため、本レポートは講演での口頭説明をしていた部分を付け加えつつ、資料と合わせて見返した時、内容がすぐわかるように講演内容をまとめたものとなります。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/effff6ee-f775-abc6-a694-466c29972af8.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/010741d8-ba20-0ddd-3850-3b8f210feb13.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/042276c6-305c-e004-7177-a8c0141148ca.png)

## ゲームAIエンジンの紹介

### ゲームAIエンジンとは

ゲーム内で使われる人工知能技術について処理を共通化し、効率的に扱えるようにしたシステム。一般的にはキャラクターAIはもちろん、自動生成AIやパラメータを自動調整するAIなど、AI技術を用いたもの全般がこのエンジンに入っているイメージ。

最近のゲームはオープンワールドなどで世界が広く複雑化する中で、全部人の手で作るのは難しくなって来ている。トリプルAと呼ばれるようなリッチなゲームの場合は、ゲームAIエンジンにどれほどの力を入れるかによってゲームのクオリティを左右するようになって来ている。

## ゲームAI特有の問題

描画や物理シミュレーションのような、ゲームで使用される他の技術と違って、ゲームAIは特有の問題が存在している。

### ドメイン依存性が高い

ゲームAIとゲームデザインは密接に絡んでいるため、ゲームによって求められる技術が異なってくる。例えば意思決定の技術にも、ステートマシンやビヘイビアツリー、プランニングやモンテカルロ法などが存在する。カジュアルなアクションゲームなら、ステートマシンやビヘイビアツリーが作りやすく、戦術的なコア向けアクションゲームだとプランニングの技術が必要になる。囲碁や将棋のようなボドゲAIはモンテカルロ法などが使われることが多い。

### ゲームエンジンへの依存

ゲームAIというのはそれ自体で完結するものではなく、アニメーションやサウンド、武器システムなどの外部システムを最終的には制御する必要がある。そのため、それらを内包しているゲームエンジンに依存しがちとなってしまい、従来はゲームタイトルごとに実装されることが多く、開発コストが高い要因になっていた。

### 総合

例えばゲーム向けのAIミドルウェアと聞いたとき、Havok AIのような経路探索ミドルウェアを思いつく人は多いが、その他のビヘイビアツリーなどを提供するミドルウェアは思いつかないことが多い。その原因が上記にあげている２つにあって、どうしても汎用的なものを提供しにくい。

ただし年々ゲームAIを使用することが多くなって来たので、このままにしておくわけにも行かず、株式会社バンダイナムコスタジオでは現在汎用的に使えるゲームAIエンジンを開発している。

## Munchkin

ゲームジャンル問わずに利用できることを目指した汎用的なゲームAIエンジンとなっている。既に実際の製品開発で利用中。また、会社によっては開発スタッフのスキルなどによってどのゲームエンジンを選択するかということが多くあるので、マルチエンジンに対応している。ただ、ゲームエンジンとの依存も減らしているため、JavaScriptで動作させることも可能。

従来はゲームタイトルごとにゲームAIを実装していたが、Munchkinを使用することで、共通の部分と、ゲームそれぞれで使う部分というところで分かれて、開発コストの削減が可能となった。そして余った余裕のところで、今まで手をつけることができなかった、より新しい技術にそれぞれのタイトルで挑戦をして、獲得した新しい技術をAIエンジンの方にフィードバックする。こうすることで、ゲームAIのエンジンが持つ能力が高くなってくると、様々なタイトルで高度なAI技術を簡単に利用できるようになる。このサイクルをし続けることで、世界に通用する新しい体験を生み出すことができると考えている。

## ゲームAIエンジンに既に存在するゲームAI技術

これは実装されて当然のBehavior Tree(2nd Generation)から、今Hotな話題の機械学習といった先端的なものまで幅広くサポートしている。

## エージェントアーキテクチャ

エンジンの中で使われているアーキテクチャとしては、一般的な三層構造となっている。

一番上にあるのが「Perception」という環境を認識するモジュールで、外部のオブジェクトの情報などを拾ってくる。

そこで獲得した情報を元に、意思決定をするのが「Brain」。

意思決定結果を行動するのが「Action」である。

今回は「Perception」部分に着目する。

## ゲームAIにおける環境認識

ゲームAIが環境認識する方法は主に二種類存在する。

**Pull型**

隠れる場所を探したり、攻撃を行うのに有利な地点を探すといったような、エージェント自らが能動的に環境を調べて情報を取得する方法になる。

**Push型**

環境の方で発生した刺激を、エージェント持っているセンサーで受け取って発生源を認識する方法になる。人間でいうと五感に当たる。ゲームによってはそこに特殊な感覚も独自に追加される。

それぞれで、目的や処理の内容も違うので、ゲームAIの中では別々のシステムとして呼称することが多くなっている。

「Perception Tree」は主にPull型の環境認識を行い、Push型の方は一般的に「Sensory System」と呼ばれている。

### Push型(Sensory System)

エージェントは自分が持っているセンサーと、そのセンサーのパラメーター(視界等の情報)を、グローバルなところにあるSensory Systemに登録しておく。

キャラクターが移動したり、銃を発砲したりなどの音に関する刺激だったり、ダメージなどの痛みという刺激が発生した時に、その刺激をSensory Systemの方へ通知する。

Sensory Systemの方は、通知された刺激を受け取れるセンサーを探して来て、そのセンサーを持っているエージェントに通知を行う(イベントドリブン型)。

### Pull型

エージェントが自ら環境を調べるシステム。複雑な地形や多くの障害物がある環境でエージェントが行動する場合に、例えば射撃を行うとした時、ターゲットとの間に、障害物がない場所に移動して攻撃する必要がある。人間が今回どの椅子に座るかというのも個別で持っている評価軸に照らし合わせて選択している。

以前は、このようなAIを実装するのに、プログラムでハードコードしていた。そこで使う情報というのも、レベルの中に情報を一個一個埋め込んでいた。例えば、椅子に座るにも、椅子１つ１つに優先度をつけて、空いてる椅子の中で一番優先度が高い椅子に座る、というような感じだった。

ただしこれだと、ステージがどんどん複雑になって来ている現在では人手がいくらあっても足りなくなるので、データドリブンである程度自動で評価などを行えるようにするのが必要となっている。ここがゲームAIでホットなところになっている。

## データドリブンな認識

データドリブンでPull型のような認識を行うためには、主に３つのステップがある。

1. データソースを収集する。例えば視界内の敵を取得したり、環境中の歩けるところ(NavMesh)に評価を行う候補となるポイントをたくさん生成したりする。
1. フィルタリングする。例えば敵を発砲するのにも、ターゲットとの間に遮蔽物がないところに移動しないといけない。その場所を選ぶためにレイキャストを行い、間に障害物がないポイントだけをフィルタリングして候補として残しておくようにする。
1. スコアリング。候補として残った移動ポイントを自身の評価軸で評価を行い、どこに移動するのが望ましいのかを判断する。最終的に一番スコアが高いところを選ぶと、それぞれで実装した環境認識の方法が実行できる。

環境認識は上記３つのステップを組み合わせて定義するものとなっている。

データドリブンによる環境認識はCryENGINEが昔から実装を行なっていたところで、情報も広く公開されている。

## 旧AIエンジン

バンダイナムコスタジオでも、旧ゲームAIエンジンではCryENGINEのTactical Point System(TPS)を参考に実装していた。

先ほどの３つの処理をレイヤーとして実装し、複数のレイヤーの組み合わせと各レイヤーのパラメータ設定でAIの認識を定義していた。また、環境認識を実行するときは、レイヤーを上から順番に実行していた。

ただし旧ゲームAIエンジンでも問題点がいくつかあった。

事前に定義されたレイヤーを順番に実行するだけなので、例えばHPが高い時低い時のような状況に応じて、評価方法の一部を変えるなどの柔軟な対応が難しい。

また、環境認識を実行する時のシステムでは、生成した多くのポイントに対する評価を効率的に行う必要がある。それを行うには複雑な処理が必要で、システムの実装やメンテナンスのコストが高くなる。

環境認識の技術は比較的新しい技術。特に日本は最近になってビヘイビアツリーが広まって来た。ここでAIデザイナーにまた新しく環境認識のシステムを覚えてもらうのはラーニングコストが少し高くなっていた。

今回新しくAIエンジンを開発するにあたって、ビヘイビアツリーをうまく使ってこの辺の問題を解消しようと試みた。

## Behaviour Tree復習

Behaviour TreeはAIの意思決定をツリー状に表現する手法。

大きく分けて三種類のノードから構成されていて、ツリーのリーフに当たるところが**Taskノード**、ツリーの幹に当たる部分に**Compositeノード**と**Decoratorノード**が存在する。

### Taskノード

主に条件判定やアクションの実行を行うノードで、結果として成功か失敗かを返す。

例えば条件判定の場合は、残弾数はあるかどうかをチェックしたり、アクションの実行して射撃を行ったりする。

### Compositeノード

子ノードの実行を制御するためのノード。

このノードには以下の二種類が存在する。

- Sequence:子ノードを順番に実行するノード。全ての子ノードが成功した場合は、Sequenceノード自体が成功を返す。どこか１つで失敗すると、そこで処理を中断して、Sequenceノードは失敗を返す。
- Selector:子ノードの中から１つを選択するノード。子ノードが失敗すると次の子ノードに遷移する。全ての子ノードが失敗すると、Selectorノードも失敗を返す。どこかで成功すると、成功を返す。

### Decoratorノード

これは子ノードを１つしか持てない特別なノード。子ノードの動作をカスタマイズするために使用する。

例えば子ノードに射撃アクションがあり、Decoratorノードはrepeat 3という設定になっていたら、射撃を3回繰り返す。

## Perception Tree

Perception Tree専用ノードを追加している。

- Task:生成ノード、変更ノード、評価ノード
- Decorator:基準ノード
- Composite:クエリーノード

### 生成ノード

指定された間隔や大きさでポイントを生成するノード。

複数の生成ノードを組み合わせて複雑なポイントも生成できる。例えば、密度を低くした小さい円のポイント生成ノードと、密度を高くしたドーナツ上の円のポイント生成ノードを組み合わせるなど。

立体的なポイント生成も可能。これは空を飛ぶ敵や魔法攻撃のような特殊技があるときに便利。

### 変更ノード

生成したデータに何かしらの変更を加えるノード。主にデータを環境にマッチさせる目的で使用する。

レイキャストにヒットした場所にポイントを移動させるようなことをすると壁沿いにポイントの生成を行うこともできる。

### 評価ノード

生成したポイントをフィルタリングしたり、データの好ましさを評価してスコアリングしたりする。

### 基準ノード

これは生成ノードや評価ノードを実行する時に、基準を指定するためのノード。

例えば、生成ノードで同心円状にポイントを生成するにしても、どこを中心にするのか指定してあげる必要がある。評価ノードで、距離を元に評価する場合も、どことの距離かを設定する必要がある。

基準ノードは、複数の基準を提供することもできる。

例えばキャラクターを一定距離で離して配置したり移動させたりが可能。

### クエリーノード

子ノードとして、前述のノードを複数繋げることで一連のクエリーを定義するノード。

単純に結果を見るだけであれば、順番にそれぞれのノードを実行するだけだが、生成した大量の候補点に対して、レイキャストのような効果な処理を順次適応していくことになるため、処理負荷を抑えるための最適化がクエリーノードに入っている。

最適化方法として以下の３つが存在する。

#### 複数フレームへの分散(タイムスライス)

AIの処理では、1フレームで全ての処理を行う必要がない場合が多い。例えば人間の場合でも、何かの刺激を受けてからそれに反応するまでの単純な反応時間は200ms弱であると脳科学的に言われている。AIの行動を行う時も、これくらいの余裕を持たせたとしても、生物的に挙動がおかしく見えたりはしないので複数フレームに処理を分散してあげると負荷を下げることができる。

もともとBehaviour Treeは複数フレームに渡るキャラクターの振る舞いを記述するためのものなので、処理の分散というのはBehaviour Treeの機能でそのまま実現することが可能。

具体的な処理の方法としては、各ノードを実行した時に、そのノードが実行した処理量に応じてコストを返す。

これとは別に、AIに割くCPUガジェットに応じて、1フレームでどれだけのコストを許容するかを別途設定しておく。その設定されたコストの閾値を超えると、現在フレームでの処理は一旦中断して、残りの処理を次のフレームに持ち越す。

#### ノードの並べ替え

評価ノードはその順番を変えても結果には影響しないようになっている。

例えばレイキャストで自分から見える道だけを残すようにフィルタリングして、残ったデータに対して距離によるスコアをつけたとしても、その逆をした時との最終的な結果は変わらない。

フィルタリングでは無効なデータを削除できるので、これをスコアリングの前にやっておけば、全体の処理量を抑えることができる。

#### 不要な処理の削減

一番スコアが高いポイントを選ぶ場合、もしスコアリングが全てのデータに対して済んでいる場合は一番スコアが高い順からフィルタリングを実行していくと、１つフィルタリングをfalseしたものが見つかった時点で残りのデータを処理しなくても、既に選択するデータは確定しているので問題なく結果を得ることができる。

### 最適化方法がバッティングしている？

「ノードの並べ替え」ではスコアリングの前にフィルタリングを行っており、「不要な処理の削減」ではスコアリングの後にフィルタリングを行なっていた。

これは一見バッティングしているように見えるが、使い分けをすることで最適化を実現している。

つまり、処理負荷がさほど高くないフィルタリングの時は、全てのデータ2フィルタリングを行なったとしても誤差程度の違いしか出ないので、フィルタリングをスコアリングの前に持ってくる。

処理負荷が高いレイキャストのようなフィルタリングの場合は、スコアリングの後にフィルタリングを持ってきて、処理負荷の削減化を行なっている。

### ノードの並べ替え + 不要な処理の削減

スコアの上位から複数個を取得したい場合は、指定された個数を見たすまでフィルタリングを実行してあげる。

ランダムに取得したい場合は、スコアでソートするのではなく、ランダムにシャッフルするように変えて、一番上のデータからフィルタリングを実行すれば良い。

条件に合う全てのデータを取得したい場合は、フィルタリングは全てのデータに対して行わざる負えないので、スコアリングの前にフィルタリングをし、スコアリング時の対象となるデータ数を極力減らしておく。

## パスに沿ったポイント生成

複雑な環境の情報を元にポイントの生成や評価をしてあげると、高度なAIを作成できる。

その１つが、ゴールデンパス。ゲームAIではそこそこ有名。

### ゴールデンパス

これはある地点からある地点までのパスを経路探索で求めて、その結果のパスに沿ってポイントを生成するもの。

例えば、プレイヤーがいる場所から、プレイヤーが向かうべきチェックポイントまでの経路を探索して、その結果のパスに沿いつつ、一定の間隔でポイントを生成する。その生成したポイントのうち、プレイヤーに近すぎず遠すぎない位置にキャラクターを移動させるようなことをすると、プレイヤーを先導するようなコンパニオンキャラクターを作ることができる。

これもPerception Treeを使えば手軽に実現することができる。

ゴールデンパスでは、プレイヤーから見える位置に先導するキャラがいるかどうかもレイキャストで確認している。

また、パス検索をしているので、障害物がたくさんあるステージでもプレイヤーを先導することができる。

### 敵のスポーン

パス検索を敵のスポーンにも行うことで、敵を倒すだけで自然と進んで欲しい方向へ誘導できる。

敵の生成はプレイヤーから見えない進行方向の障害物の裏などに設定しておく。

この場合、パス検索を行って進路にあたるかどうかで敵の生成をしているため、プレイヤーの背後から敵が生成されることはない。

これならコンパニオンキャラクターも必要ない。

## オブジェクトの検索

複雑な地形内で戦術的な行動をすることは現在のAIで重要になっているが、それと同じくらい、環境中のオブジェクトを使うことも重要になっている。

例えばフィールドに設置された重火器を使用したり、フィールドに生えてる植物を食べて体力を回復したり…。

これらを行うために、生成ノードとして、指定した範囲に指定した種類のオブジェクトを検索して収集するノードを用意する。

ゲームAI技術として、AIが使用する情報や行動をオブジェクトに埋め込む、**スマートオブジェクト**という仕組みがある。

バンダイナムコスタジオでもスマートオブジェクトの仕組みは用意しているので、これとオブジェクト検索ノードを組み合わせることで、オブジェクトを効率的に利用したエージェントの振る舞いも簡単に実現することができている。

Perception Treeでは、オブジェクト自体もフィルタリングやスコアリングする。これを利用することでスマートオブジェクトの中でも有効で好ましいものを選択することができる。

ゴールデンパスによるプレイヤーの先導と組み合わせることで、より効果的に誘導が行える。

例えばゲームの進行で、有用なオブジェクトを見つけたら、そこまでエージェントが誘導してくれたり、プレイヤーにとって危険な罠がある場合、知らせるためにわざと罠に引っかかったりすることができる。

これによって、よりレベルデザイナの意図に沿ったプレイヤーの誘導ができるようになる。

また、キャラクターが様々なオブジェクトに反応することで、表現力が増し、キャラクターが生き生きとして見える効果もある。

## Sensory Systemとの連携

Perception TreeではSensory Systemとの連携も行える。

Sensory Systemで知覚した対象に対して処理を行うノードを提供することで実現している。

ターゲットの選択もセンサーの種類やパラメータ、何を基準に評価するか、などをノードベースで行える。

エージェントごとに、選択アルゴリズムを変えたいとか、調整したい時も楽にできるようになっている。

## Behaviour Treeの機能活用

Behaviour Treeがベースとなっているので、その機能をそのまま活用できる。

### Selectorノード

旧AIエンジンの問題であった、柔軟な対応ができないという部分に対して、Selectorノードを使用すれば、自分の状況に応じてクエリー内容の一部を変更することができる。

例えば、HPの高さによってターゲットにする相手を変更したり。

オプションの機能で、複雑な環境でキャラクターが行動する場合に、クエリーで結果が得られないようなレアケースが出てくることがある。

クエリーのところで処理の最適化が入っているとはいえ、レアケース対応のためだけに、生成するポイントは増やしたくない。

なのでクエリーが失敗した時だけ(つまりレアケースの時だけ)、別のクエリーを実行できる。

### Blackboardへのアクセス

Behaviour TreeではBlackboardを使用して色んな処理をしている。

Perception TreeでもBlackboardに格納された値を使用して、条件の判定や基準の設定を行うことができる。

Blackboardは色んなゲームAIの中で使われているものなので、他の技術との連携もしやすくなる。

### サブツリーの実行

Behaviour Treeの場合、よく用いられるトリックとしては、特定のミッションや場所などではキャラクターの汎用な振る舞いではなく、固有の振る舞いをしてほしいことがある。これを行うために、１つのBehaviour Treeの中にミッション固有の行動を入れてしまうのはメンテナンスがしにくくなるため避けるべき。

その代わり、Behaviour Treeの中に１つ枠を空けておき、レベルスクリプトなどの外部から実行してほしいツリーを指定して実行してもらうことができる。

これらはPerception Treeでも同様のことができる。

## Sequence

Sequenceを使ったクエリーを多段階クエリーと呼ぶ。

クエリーを実行する時に、別のクエリーの結果を利用したい場合がある。

例えばオブジェクトを検索してそのオブジェクトの周囲にポイントを生成するようなことはこれが使える。

クエリーノードではポイントが一個でも見つかった場合は成功が返るようになっているので、Sequenceノードの下クエリーノードを繋げてあげると、一個のクエリーが成功するともう一個別のクエリーを実行するようなことができる。

## まとめ

旧ゲームAIエンジンで起きていた問題点に関して以下のような対応ができた。

- 状況に応じた評価式の変更など、柔軟な対応が難しい：Selectorノードを使用した分岐が可能。
- システムの実装、メンテコストが高い：エディタ、ランタイム共に多くをBehaviour Treeと共有しているので楽。
- AIデザイナのラーニングコストが高い：Behaviour Treeが使えれば、最小限のラーニングで済む。

またPerception Treeの機能面では、現世代での一般的な環境認識システムでできることは全てサポートしている。それに加えて、分岐や多段階クエリーのような既存のシステムでは対応されていないこともPerception Treeでは対応されている。ゲーム独自のカスタムなロジック(ゲーム独自の評価方法や基準提供など)もノードを追加するだけで可能。拡張性もあるので汎用のゲームAIエンジンとして使いやすくなっている。

Perception Treeで複雑な環境認識の定義を環境認識のシステム内で完結できる。なので、今までであれば、意思決定側で環境認識の仕方を変更していたところに関して冗長な記述が少なくなり、保守性が高まる。

AIが持っている認識の仕方をデータドリブンで作っていくことができるので、複雑で戦略的な振る舞いも効率的に作成できるようになった。

## 感想

大手ゲーム会社では自社でゲームAIエンジンを開発しているのは驚きでした。しかし、確かに汎用的なものが存在していない状態で開発を進めるのはコスパが悪いと感じるので、Perception Treeが使える状態になったのはとても素晴らしいことだと感じました。ゲームAIエンジンに関しては知らないことが多かったので勉強になりました。