ゲームAIプログラミング

ゲームAIプログラミング

これは、実例で学ぶゲームAIプログラミング [ マット・バックランド ]の内容をkenmoが個人的にまとめたものです。

有限ステートマシン(Finite State Machine : FSM)

FSMとは

  • FSMは一種のデバイスで、すなわちデバイスのモデルである
  • いつでもとりかえることが可能な「有限個のステート」を持つ
  • 入力を処理することで、
    • あるステートから別のステートへの遷移を起こしたり
    • 出力を引き起こしたり
    • アクションを起こすことができる
  • 同時に取ることができるステートは「1つ」だけ

FSMの背後にある考え方は、

  • オブジェクトの行動を簡単に管理できるように、「チャンク」または「ステート」に分解する

ということ。

メリット

  • コードが素早く容易に書ける
  • デバッグが容易
  • 計算のオーバーヘッドがほとんどない
  • 直感的である
  • 柔軟性がある
コードが素早く容易に書ける

FSMを実装する方法はたくさんあり、そのほとんどが理にかなっていてシンプルである

デバッグが容易

簡単に管理できるチャンク(かたまり)に分割なので、おかしな動きをし始めたら、

ステートをトレースすることで簡単にデバッグができる。

計算のオーバーヘッドがほとんどない

基本はハードコーディングなので、CPU時間をあまり消費しない。

「もし~ならば~」の定型的な条件処理以外である、本当の意味の「思考」は行わない。

直感的である

「冷静」状態や「怒り」状態などのステート(状態)の概念は、人にとって自然で理解しやすい。

ゆえにプログラマ以外の人(プロデューサーやレベルデザイナー)にAIの設計に関する議論、

コミュニケーション、アイデアなどの改善をしやすくなる。

柔軟性がある

新しいステートの追加や、行動パターンの強化など、拡張が容易である。

また、ファジー理論やニューラルネットワークなど、他のテクニックを組み合わせることもできる。

実装例

  • 逃走
  • 巡回
  • 攻撃

という3つのステートを持つオブジェクトの実装例です。

 enum E_STATE {
 	STATE_RUNAWAY, // 逃走
 	STATE_PATROL,  // 巡回
 	STATE_ATTACK,  // 攻撃
 };
 void Actor::UpdateState(E_STATE state)
 {
 	switch(state)
 	{
 	case STATE_RUNAWAY:
 		逃走を実行();
 		if(安全)
 		{
 			ChangeState(STATE_PATROL);
 		}
 		break;
 	case STATE_PATROL:
 		巡回を実行();
 		if(敵が接近)
 		{
 			if(敵が強い)
 			{
	 			ChangeState(STATE_RUNAWAY);
 			}
 			else
 			{
	 			ChangeState(STATE_ATTACK);
 			}
 		}
 		break;
 	case STATE_ATTACK:
 		if(敵に負けそう)
 		{
 			ChangeState(STATE_RUNAWAY);
 		}
 		else
 		{
			攻撃実行();
 		}
 		break;
 	}
 }

一見、このアプローチが理にかなっているようですが、「ステート」や「条件」が増えるほど、スパゲッティコードになります。

(すでに巡回ステートのif文が、2つネストしている時点であやしいですよね)

状態遷移表

ステートと状態遷移(の条件)との作用を体系化するいい方法が「状態遷移表」です。

現在のステート条件 状態遷移
逃走 安全 巡回
攻撃 に負けそう 逃走
巡回 が接近 かつ が強い逃走
巡回 が接近 かつ が弱い攻撃

これは、先ほどのコードをステートと条件でマッピングしたものです。

これにより、フローが明確になるので、「ステート」や「条件」の追加による負荷を軽減することができます。

組み込み型のルール

もう一つの負荷を減らすいい方法が、

  • ステート自身の中に状態遷移の「ルール」を組み込む

ことです。

現在の実装は、巨大なswitch文によりダイレクトに状態遷移を制御していますが、

それを「関数ポインタ」または「Stateパターン」に置き換えることにより、

状態遷移の制御をそれぞれのステートに委譲することができます。

関数ポインタによる実装例

 void Actor::UpdateState()
 {
 	this->m_pFuncState(this); // ステートの関数ポインタを実行
 }
 void DoStateRunaway(Actor* pActor)
 {
 	// 逃走実行
 	if(pActor->安全())
 	{
 		ChangeState(pActor, DoStatePatrol);
 	}
 }
 void DoStatePatrol(Actor* pActor)
 {
 ・
 ・
 ・

Stateパターンによる実装
 /**
  * 状態基底クラス
  */
 class IState
 {
 public:
 	virtual void Execute(Actor* pActor) = 0;
 };
 
 /**
  * アクター
  */
 class Actor
 {
 private:
 	State* m_pCurrentState; // 現在の状態
 public:
 	void Update()
 	{
 		m_pCurrentState->Execute(this);
 	}
 	void ChangeState(const State* pNewState)
 	{
 		delete m_pCurrentState;
 		m_pCurrentState = pNewState;
 	}
 };
 
 /**
  * 逃走状態
  */
 class StateRunaway : public IState
 {
 public:
 	void Execute(Actor* pActor)
 	{
 		逃走を実行(pActor);
 		if(pActor->安全())
 		{
 			pActor->ChangeState(new StatePatrol());
 		}
 	}
 };
 
 /**
  * 巡回状態
  */
 class StatePatrol : public IState
 {
 ・
 ・
 ・

グローバルステートとステートブリップ

グローバルステート

ステート間に共通の処理がある場合、その処理をコピペするよりも、

「どこからでもアクセスできるステート」をあらかじめ生成しておき、

そのなかに共通の処理を埋め込んでおきます。

これをグローバルステータスと呼びます。

ステートブリップ

例えば、特定のステートにおいて遷移を行う場合、「直前に選ばれていたステート」に戻りたいとします。

そういった場合、そのステートに遷移する場合、「直前のステート」を保存しておくと、戻ることが簡単になります。

FSMにメッセージング機能を追加する

FSMが外部からメッセージを受け取って行動(イベント駆動)するようにする。

自律的に動くゲームエージェントの作成

自律エージェントとは

自律エージェントとは、環境内部に存在するシステムであり、かつ、

環境を知覚する環境の一部であり、

時間をかけて自分の意図を達成し、

エージェントが将来知覚するものに影響するように環境に対する働きかけを行う

自律エージェントの動作レイヤ

  • 行動選択
  • 操舵
  • 移動運動
行動選択

ゴール、プランの実行を「選択/決定」する。

  • 「ここへ行け」
  • 「A、BをやってCをやれ」

など。

操舵

ゴールを満たす、またはプランの実行をするために必要な「軌道を計算」する。

移動運動

操舵により計算された軌道を満たすために「移動」する。

操舵行動

  • 探索行動(Seek):目標位置の方向を向く
  • 逃走行動(Flee):目標位置から離れていく
  • 到着行動(Arrive):目標位置で優しく止まる
  • 追跡行動(Pursuit):目標の予測される移動先の方向を向く
  • 逃避行動(Evade):目標の予測される移動先から離れる
  • 徘徊行動(Wander):目標から一定の距離を徘徊する(目標の周りをぐるぐる回るなど)
  • 障害物回避行動(ObstacleAvoidance):経路上にある障害物を回避する
  • 壁回避行動(WallAvoidance):経路上にある壁を回避する
  • 介入行動(Interpose):2つの目標の間に介入する(ボスを守るシールドなど)
  • 隠身行動(Hide):目標からステルスして近づく
  • 経路追従行動(FollowPath):あらかじめ決められた経路を巡回する
  • オフセット追跡行動(OffsetPursuit):目標から一定の距離(オフセット)を取り続ける

グループ行動(フロッキング)

  • 結合行動(Separation)
  • 分離行動(Alignment)
  • 整列行動(Cohesion)


スクリプト言語

スクリプト言語を使うメリット

  • 初期化ファイル/設定ファイルから、素早く簡単に変数やゲームデータを読み込むことができる
  • 時間を節約し、生産性を上昇させることができる
  • 創造性を促進することができる
  • 拡張性を提供する

初期化ファイル/設定ファイルから、素早く簡単に変数やゲームデータを読み込むことができる

INIファイルのような初期化ファイル/設定ファイルを読み込む代わりに、

スクリプトファイルをロードして、値を設定することができるので、

専用の構文解析機を書く必要がなくなります。

時間を節約し、生産性を上昇させることができる

ゲームプロジェクトが大きくなるにつれて、プロジェクトをビルドするのに必要な時間も劇的に増加します。

1つのヘッダファイルに書いてある定数を修正しただけで、全コンパイルが必要となると、

膨大に時間を浪費してしまいます。

(実機に転送する必要があるような開発環境の場合は、特にそうですね)

少しだけ修正しても、結果を確認するのに時間がかかるということは、

修正をためらわせることとなり、ゲームの調整をやりにくくしてしまいます。

外部スクリプトが用意されていれば、コンパイルなしで修正が可能となるので、

時間が節約できて、より細かい調整が可能となります。

創造性を促進することができる

スクリプト言語は、C++のようなプログラム言語よりも高レベルで機能するため、

非プログラマーに対しても直感的な構文を提供します。

そのため、非プログラマーは、プログラマーの作業の妨げをすることなく、

ゲームデザイン・レベルデザインの調整を行えます。

レベルデザイナーは、ふっと思いついた革新的なアイデアを、

「それをやってもつまんないからヤダ」

とプログラマーに言われ、説得するための時間を浪費することなく、

そのアイデアを好きなだけ試すことができるわけです。

そして、さらによい効果を得るには、この仕組みをレベルデザインに興味のあるメンバー全員に解放することです。

それによりエンジンを用いて、この仕組みをいじり倒してもらえれば、レベルについての議論が活発となり、

メンバーの開発への参加意識(モラル)を高める効果を得ることができます。

拡張性を提供する

たいてい、製品としてのレベルは、多くのプレイヤーがクリア可能なレベルにチューニングされています。

しかし、それに物足りないプレイヤーは必ず存在します。

そういったプレイヤーがより深く楽しむための、レベルをエディットするための機能として、

スクリプトを公開することができます。

これは、コアユーザーに対する、大きなセールスポイントとなります。

Luaによる有限ステートマシンの実装

先ほどの逃走状態をLuaで実装するとこんな感じになります。

 State_Runaway = {} -- ステート関数テーブル
 
 -- 初期化関数
 State_Runaway["Init"] = function(pActor)
 	-- ロジックをここに入れる
 end
 
 -- メイン関数
 State_Runaway["Execute"] = function(pActor)
 	-- 逃走実行
 	if pActor:安全() then
 		pActor:GetFSM():ChangeState(STATE_PATROL)
 	end
 end
 
 -- 終了関数
 State_Runaway["Exit"] = function(pActor)
 	-- ロジックをここに入れる
 end

何に適用するか

  • アドベンチャーゲームのシナリオ制御や、会話イベントのメッセージ制御など
  • の行動パターン
  • ステージのフロー。アイテムの生成(たいていマップエディタで行ったほうが効率的だけれども)
  • アニメーションデモのスクリプト

複雑な演算(全オブジェクトを走査して評価値を計算するなど)は、大きな負荷となるので、スクリプト側ではやってはいけない。

スクリプト言語を使うデメリット

  • C言語であれば好きなところでウォッチしたりできるが、スクリプトではデバッグする機能がない
  • 構文エラーをチェックする機能が貧弱。またはない

ゴール駆動型エージェント

ゴールを実現するために必要な要素(サブゴール)に分解し、それぞれを順に満たすように行動するエージェント。

例:「剣を買う」というゴールを実現する

まず、ゴールを設定する。

  • 剣を買う

「剣を買う」ゴールを展開する。

  • 剣を買う
    • 金塊を手に入れる
    • 鍛冶屋に行く

さらに「金塊を手に入れる」サブゴールを展開する。

  • 剣を買う
    • 金塊を手に入れる
      • (金鉱への)経路をプランニングする
      • 経路をたどる
      • 金塊を拾う
    • 鍛冶屋に行く

さらに「経路をたどる」サブゴールを展開する。

  • 剣を買う
    • 金塊を手に入れる
      • (金鉱への)経路をプランニングする
      • 経路をたどる
        • エッジを移動する(1番目のウェイトポイント)
        • エッジを移動する(2番目のウェイトポイント)
        • エッジを移動する(3番目のウェイトポイント)
      • 金塊を拾う
    • 鍛冶屋に行く

ファジー理論

「遠い」「近い」「優しい」「しっかり」といった人間にしか理解できない曖昧なパラメータを、

擬似的にコンピュータが理解できるものにすること。

クリスプ集合

オブジェクトの境界を明確にするもの。

例えば、奇数・偶数のクリスプ集合は、

奇数 = {1,3,5,7,9,11,13,15}

偶数 = {2,4,6,8,10,12,14,16}

となります。

集合演算子

最もよく使うのが、和集合、共通集合、補集合です。

A = {1,2,3,4}

B = {3,5,7}

とすると、和集合A∪Bは、

A∪B = {1,2,3,4,3,5,7}

です。(OR演算ですね)

共通集合A∩Bは、

A∩B = {3}

です。(AND演算ですね)

補集合はその集合の逆元で、全体集合がA∪Bとすると、Aの補集合はBとなります。(NOT演算ですね)

A' = B

ファジー集合

クリスプ集合は、境界付近の値を正しく評価できない、という欠点があります。

例えば、

  • IQ 70~89 : 頭が悪い
  • IQ 90~109 : 普通
  • IQ 110~130 : 頭がいい

という集合に分類すると、IQ 109の人は、頭がいいはずなのですが、普通の人に分類されてしまいます。

ファジー集合では、「頭が悪い」「普通」「頭がいい」をメンバーと考え、

各メンバーへの帰属の度合いから、評価を行います。

例えば、

  • IQ 60~99 : 頭が悪い
  • IQ 80~119 : 普通
  • IQ 100~140 : 頭がいい

このように、各メンバーの判定を広めにとり、範囲の重複部分を作ります。

これにより、IQ 109の人は、おおよそ

  • 75%普通
  • 25%頭がいい

ということを推論することができます。

ファジー言語変数

ファジールール

ファジー推論

AI作成ガイドライン

AIを作成するについて、忘れてはならないこと。

  • 良いゲームのAIの解を作り出す正しい方法がたった「1つ」しかないということはほとんどありません。ある設計に全力を投じる前に、時間が許す限りできるだけ多くのさまざまな方法を実験してみてください
  • 何度もプレイテストを行い、「プレイテスターの声」に耳を傾けてください。可能であれば、「彼らのプレイ」を実際に見てください。メモ帳とペンを忘れないようにしてください
  • 1つか2つかのAIテクニックに魅了され、問題をなんとかそれらに適合するようにしてしまうという罠に落ちないようにしてください
  • 少なくとも、ゲームデザイナーやプロデューサーとだけでなく、みなさんのチームの他の人すべて(そう、アートデザイナーとさえも)とAIに関するブレストをしてください。これにより、みなさんが熟考すべき新しい、そしてひょっとしたら興奮するようなアイデアがいくつか生まれてくるでしょう
  • ゲームAIの設計は、繰り返し作業です。最初の1回で正しいものに到達するということはまずありません。複雑な問題の細部すべてを考えることは不可能です。最初の試みがうまくいかなくてもがっかりせずに、うまくいくまで我慢し、間違いから学び、デザインサイクルを繰り返し続けてください
  • ゲームAIに関連する話題を読むのに時間を惜しまないでください。このような話題を読んでいるときに、最も良いアイデアの多くが頭に浮かんでくるのです。認知科学、ロボット工学、哲学、心理学、社会科学、生物学、さらには軍事戦略までもがすべてみなさんが時間を費やす価値がある話題なのです
  • 極めて頭が良く、無敵を作ることが、ゲームAIのゴールではありません。良いAIとは、ゲームプレイを楽しくするAIのことです。このことはAIを作ることに没頭すると見落としがちです。プレイヤーを笑わせたり歓喜の声をあげさせたりするのがゲームAIの本当の目的なのです
  • プレイヤーNPCの頭を吹き飛ばすまでが、AIの寿命となります。どんなに最新のテクノロジーを利用したとしても、3秒で頭を飛ばされるのであれば、何の役にも立たないのです