Push: Ctrl+Y

 技術で遊んで ときどき進む

ゲームAI 解説してみた

ゲームAI調査:BDIアーキテクチャ(BehaviorTree・HTNプランニング)

ゲームAIのアーキテクチャの最新情報(?)を調べてみました。

前回シリーズでゲームAIについてやってみたわけですが、いかんせん本が出版されたのが2007年と古いので、最新的にはどうなっているのか気になって調査開始しました。検索するのに微妙に難航したので、ここにメモ的まとめを置いておきたいと思います。

 

資料

資料は色々探した結果、ここが一番充実していました。

日本最大のゲーム開発者向けカンファレンス:CEDECの資料がここに格納されていたので、そこからキーワード取ってたどっていった感じです。

参考になった記事も羅列しておきます。

 

ステート駆動エージェントの問題点

前回解説したステート駆動エージェントですが、やってみた感想としても全体像は見えにくくなるなあという気持ちはしていました。調べていてもステートが多くなると管理しきれなくなってしまうという話は結構出ていて、その問題点を解消するために他の手法が編み出されたという流れっぽいです。ちなみに簡単なゲームならば今でもステート駆動エージェントで作られているらしいです。

 

BDIアーキテクチャでゲームAI

1991年、哲学者:Bradmanが提唱した「意図の理論」という、人間ってこういう感じだよね、をモデル化したのが自律・合理的エージェントのモデルがBDIアーキテクチャです。エージェントが内部に持つ信念・願望から作られる意図により、エージェントの動作を決定します。動作手順はこんな感じ。

  1. 内部パラメータ(信念・願望)から目標を決定し、達成手段の候補を求める
  2. 達成手段の候補の中から、実際に行う手段を熟考して決定(意図
  3. 決定した手段を実行
  4. 外部からの知覚により、信念・願望を更新

これをゲームAIに落とし込むと、必要な要素は以下になります。

  • BehaviorTree(内部パラメータから目標を決定する)
  • HTNプランナ(達成手段の候補:HTNドメインから実際に行う手段を決定)
  • Perception(外部からの知覚)

・・知らない単語ばっかきた。。ひとつひとつまとめていきます。
ちなみに、BehaviorTreeとHTNプランナはそれひとつでもAIとしての動作(目標を決定して達成手段を実行する)を担保できますが、掛け合わせるとデメリットを補いあっていい感じになるので、このような役割分担になっています。

 

BehaviorTree

これは階層型ステート駆動マシン(HFSM)に近い(?)として、存在はいちおう知っていました。2007年あたりにゲーム業界に一気に広まった技術らしい。

参考サイト:

 

全体像

エージェントの行動をツリー探索(木構造)で決定していく方法で、全体を俯瞰しやすく拡張と再利用が容易なのが特徴です。各々のノードを実行・その結果をステータスとして親に返却していく感じです。そのノードとステータスの種類が色々あって、そこを理解できればBehaviorTreeは掴めたな!って感じかなあと思います。

 

ノードの種類

大きく分けると、

  • 条件判定
  • 実際の行動(Action)

がノードになりえます。さらにその振る舞いによって、

  • Action(実際の行動:木構造でいうLeaf)
  • Decorator(子ノードを一つだけ持ち、その子ノードの動作をカスタマイズする)
    • EX1:条件判定(通ったら子が返すステータスを返却)
    • EX2:子ノードをx回繰り返す
  • Sequence(複数の子ノードを順番に実行)
    • EX:位置を移動する => 待機する
  • Selector(成功する子ノードにぶつかるまで実行)
    • EX:位置Aに移動する(失敗) => 位置Bに移動する(成功)
  • Parallel(複数タスクを並行して行う)
    • EX1:競合しないアクション(叫びながら武器を変える、とか)
    • EX2:グループの行動

などなど、他にもあるけど代表的なのはこんな感じで分けられます。英語だけど、このサイト(GitHub:Behavior-Trees)とか参考になります。

 

ステータス

ノードが返却するのがステータスです。普通に

  • Success(成功)
  • Failuer(失敗)
  • Running(実行中)
  • Ready(初期値)

は必須としても、他独自ステータスを作ってもいい感じなのかなと思いました。(作りすぎると複雑になるので少ないに越したことはないと思うが)

 

HTNプランニング

1977年あたりからある技術。
プランニングするゲームAIは熟考型AIとも言われ、目の前の状況に場当たり的に答えを出す条件反射型AIとは違って、首尾一貫した動作(なんか考えてるっぽい動き)になるのが特徴です。もちろん熟考するとその分負荷がかかるのですが、HTNプランニングはその時間をいい感じに削減できるプランニング方法だと言えそう。

余談ですが、熟考型として他にSTRIPSというプランニング方法があります。
グラフ探索を用いるパターンですが、HTNと比べてあまり直感的ではなく複雑になりがちという欠点があるらしい。詳しくはここでは省略します。。

 

全体像

行動を、

  • 複合タスク(抽象的なタスク:方法を選択するときに条件分岐の基になるような単位)
    • EX:地点AからBに行く => 飛行機で行く・電車で行く・歩いていく
      • (お金がたくさんあれば飛行機/そこそこなら電車/なければ歩き、という条件分岐ができる)
  • プリミティブタスク(具体的なタスク:行動の最小単位)
    • EX:航空券を買う・飛行機に乗る・きっぷを買う・・・

に分割することにより、行動の最適解を素早く発見する手法。人が計画するときの思考に近い形なので、かなり理解しやすい方法です。手順は、

  1. ゴールをリストに追加
  2. リストがなくなるまでA〜Cを繰り返す
    1. リストからタスクを取り出す
    2. 複合タスクの場合 => 現在の状態(ステート)からサブタスクを選択し、リストに追加
    3. プリミティブタスクの場合 => 現在の状態(ステート)をアップデートし、プランに自身を追加
  3. プランを返却

という感じで、最後に返却されたプランにはゴールに至るための道筋が並んでいるやったー!という按配です。

参考サイト:

直感的に分かりやすくて良い。

 

BehaviorTree × HTNプランニング ≒ BDIアーキテクチャの実現

一つだけとってもいい感じのシステムになりそうな気がしますが、掛け合わせると良いことあるんです。

BehaviorTreeのデメリット:

  • 複雑なAIを作ろうとするとツリーが巨大になって開発困難
  • 一度に実行するノード数が多いと処理負荷

HTNプランニングのデメリット:

  • 全体像がわかりにくい
  • 自動的に最適解を選んでしまうので、演出的な行動をさせにくい
  • 大量のタスクが作成されると、細かい調整をするのが難しい

これを掛け合わせて

  • 目標の決定をBehaviorTree
  • 実際の行動の決定をHTNプランニング

とすれば、柔軟な対応が可能になります。
さらに、演出的行動をさせたい場合はBehaviorTreeの方で非同期ツリーを作成しておき、割込みさせるという方法で実現できてしまいます。

この方式では、Perception(BehaviorTreeに渡される情報)とBehaviorTree自身のバリエーションにより、各エージェントにバリエーションをもたらすことができます。これもなんか人間っぽい。

あとは実装面、

  • BehaviorTreeを再利用できるようにパーツにして、柔軟にリンクする
  • HTNプランニングとBehaviorTreeのどちらでやるのが良いかを考えながら作っていく
  • 実際の行動は同じでも、作成された意図によってアクションをちょっと変える(「移動」でも隠れるための移動と攻撃するための移動では違うアクションになる)

などなど、工夫しながらやっていくと良いみたいです。

 

まとめ

なんとなくイメージはつかめた&工夫しがいがあって楽しそう。
細かいところは実際のところ使ってみないとまだ分からないので、次は実装やってみようかなと思います。

 

-ゲームAI, 解説してみた
-

おすすめの記事

1
React + Redux入門① - Reduxの概念を理解

React+Reduxでサイトを作っているので、復習がてら「検索画面を作成する」 ...

2
React + Redux + D3.js アニメーション:ドラッグ&ドロップでキングスライムを作った

はい、今回は要素のドラッグ&ドロップを中心に作ってみました。 Mater ...