ゲーム AI の設計 (その 2) – 知覚とパス検索

この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Designing Artificial Intelligence for Games (Part 2)」(http://software.intel.com/en-us/articles/designing-artificial-intelligence-for-games-part-2/) の日本語参考訳です。

知覚とパス検索

前の記事 (その 1) では、AI を使用するエンティティーに関連する人工知能研究として、インテリジェント・エージェントの基本的な決定を管理する方法について説明しました。

この記事では、主人公 (またはモンスターなどのゲームのエンティティー) に決定を行うための情報を与えます。インテリジェント・エージェントは、ゲーム世界で注目する位置ポイントを識別して、そこにたどり着く方法を見つける必要があります。これらの方法を最適化する手法を示し、マルチスレッド化のための構成方法を説明します。

この記事では、現実の人工知能 (AI) についても説明します。インテリジェント・エージェントはすべて、その環境を知覚する基本的な能力と、その世界の中をナビゲートして移動する何らかの手段を持つ必要があります。エンティティーも、(アプローチは異なっても) 同じことを行う必要があります。すべてがうまく高速に動作することを確認するため、工夫することもできます。

AI はどのように知覚するか

ゲームによってはエージェントに任意の決定を行わせるだけで十分ですが、エージェントにそれ以上を求める場合にはどうすればいいのでしょうか。エージェントが適切な決定を行うには、その周りで何が行われているかを知る必要があるでしょう。

AI ロボットのアプリケーションでは、ロボットが人間のように周りの世界を知覚する能力を備えることを可能にするため、コンピューター・ビジョンの分野ではさまざまな研究が行われています。その洗練度はゲーム世界に必要な知覚レベルを凌駕しています。

ゲームの仮想世界は、現実世界の AI ロボットよりも非常に有利です。なぜなら、ゲーム世界では、すべての要素が分かっており、ゲーム内のどこかに、その世界に存在する要素を含むリストがあるからです。あらゆる条件でリストを検索し、エージェントがより意味のある決定を下すのに必要な情報を直ちに得ることができます。

視覚

エンティティーの視覚を欺くことは、エージェントに知覚能力を与える最も基本的なレベルです。セットの範囲内のすべての項目についてエンティティーのリストを検索することで、この処理を行えます。エージェントが注目する最初の項目を取得するか、範囲内の項目のリストを取得することで、エージェントはその状況で最適な決定を下すことができます。

このセットアップは単純なゲームでは問題ありませんが、スパイゲームやファーストパーソン・シューター (FPS、シューティング・ゲーム) のようなより複雑なゲームでは、エージェントは「見た」ものを選択する必要があります。エージェントが後ろを警戒しなくて良いのであれば、視界の外にある情報をより分けることができます。これは、次のような計算で実現できます。

エージェントの位置からターゲットの位置を引いて、エージェントとエンティティー間のベクトルを計算します。
そのベクトルと、エージェントが見ている方向の角度を計算します。(値がベクトルになっていない場合、その値も計算します。)
角度の絶対値がエージェントにあらかじめ設定されている視界の角度よりも大きい場合、エンティティーはエージェントの視界に入りません。

より複雑なゲームでは、何かの影に隠れているプレイヤーやほかのエンティティーを考慮する必要があります。この種のゲームでは、レイ・トレーシング (レイ・キャスティング と呼ばれることもあります) によって、ターゲットをブロックしているものがないか確認します。

レイ・トレーシングは、あるポイントから設定した方向へ光線を追跡して、何かと交差するかどうかを確認する数学的な手法です。ゲームエンジンが提供するレイ・トレーシング機能が何を行っているか確認したい場合は、「Two Brains Are Better Than One」(http://software.intel.com/en-us/articles/two-brains-are-better-than-one/) を参照してください。

前の手法ではターゲットの中心に何かがあることは分かりますが、エージェントを思いとどまらせるには十分でないかもしれません。ターゲットは障害物の後ろに隠れ、頭だけを出している可能性もあります。ターゲットの特定のポイントに対して複数のレイ・トレーシングを使用することによって、ターゲットを攻撃できるかどうかだけではなく、ターゲットを攻撃できる場所を決定できます。

聴覚

一見すると、音と視界には違いがないように思えます。エンティティーを見ることができるのであれば、音も聞くことができるはずです。エージェントは見つけたエンティティーが視界から消えるまでその行動をすべて検出できます。しかし、エージェントに聴覚を追加することで、より効果的に視界を認識できるようになります。エンティティーが知覚レベルとして出すノイズを追跡することは、ステルスゲームの鍵です。

視界と同じように、近くのエンティティーのリストを取得する必要があります。単純な距離チェックによってリストを取得できますが、リストの情報をより分ける方法は異なります。

エンティティーの行動アクションすべてに関連する音レベルを設定する必要があります。音レベルはあらかじめ設定する (ゲームバランスの最適化) か、アクションに基づいて音響効果を設定する (臨場感は増すが不要) ことができます。生成された音がしきい値内であれば、エージェントはそのエンティティーを知覚します。

障害物を考慮する場合は、その環境でレイ・トレーシングを行って音の障害物を確認することで、さらにリストからより分けることができます。完全に防音の材料というのはほとんどないため、どのような基準でリストからエンティティーを取り除くのか、考慮する必要があります。

ほかの感覚

エージェントに視覚と聴覚を持たせるために必要な基本的な機能は、ほかの感覚をシミュレートする際にも流用できます。設計レベルでゲームに追加できると思われるその他の感覚のリストを次に示します。

嗅覚。インテリジェント・エージェントが匂いでプレイヤーを追跡するというアイデアは、Call of Duty 4* (コールオブデューティ 4) などの最近のゲームで追加されました。ゲームに嗅覚を追加することは比較的容易です。ゲームの各エンティティーに、個別の匂いの番号と強さを割り当てるだけです。匂いの強さによって 2 つの要因 (匂いの半径と後に残される匂いの跡のサイズ) が決まります。
アクティブなプレイヤー・エンティティーは、さまざまな理由から (詳細は後述)、最後のいくつかの位置を保持しています。その理由の 1 つは匂いです。プレイヤー・エンティティーが跡を更新すると、跡は「冷たく」なり、匂いの強さは弱くなります。匂いのあるエージェントが更新された場合、音と同じように匂い (の半径と壁) を確認する必要があります。匂いに気付くかどうかは、エンティティーの跡を確認したときの、匂いの強さとエージェントの嗅覚によって決まります。
レーダー。一部のゲームではプレイヤーにレーダーが付いていることがあります。レーダーの追加はさらに容易です。必要なのは、単純な半径チェックだけです。反応があった場合、AI は内容を確認します。チームゲームでは、レーダーを使用することでゲームがさらに面白くなります。チーム単位の AI にするには、各チームでレーダーに反応したエンティティーを集めたレーダーリストが必要です。チームのメンバーはそれぞれ、そのリストに対して半径チェックを行い、チームが反応するかどうかを決定します。
チームは、レーダー装置を使用して (Enemy Territory: Quake Wars* “エネミーテリトリー: クエイクウォーズ” などのゲームで採用されています)、メンバーのレーダーの「反応」をすべてリストに追加します。チームとしてリストを持つことで、単独行動しているメンバーも、ほかのメンバーと同じ情報を持つことができます。
触覚。この感覚はゲームエンジンの衝突システムに自動的に含まれているため、新しく追加する必要はありません。インテリジェント・エージェントが損傷や衝突イベントに反応することを確認するだけで済みます。
味覚。この感覚をどのようにゲーム内に追加すればいいのか、現時点ではいいアイデアは浮かびません。おそらく匂いと似たものになるでしょうが、エージェントが見つけたものを「味わう」ようにする必要があるでしょう。

我々はゲーム世界でさまざまなことを感じることができますが、エージェントが何かを感じるようにするには、エージェントが見ることができるものを指定して、見たものを認識できるようにエージェントを設定する必要があります。何を見ているか認識できれば、エージェントはエンティティーを管理する規則に基づいて、見たものに反応することができます。

一時エンティティー

パーティクル、デカール、特殊効果などと呼ばれる一時エンティティーは、ゲーム世界の視覚効果です。全体的なクラス構造が定義するエンティティーに似ていますが、一時エンティティーは、ゲーム世界のほかのエンティティーとは異なり、考えたり、反応したり、対話することはありません。一時エンティティーは、少しの間だけゲーム世界に視覚効果を追加して、消えていきます。例えば、弾道、煙、火花、血痕、足跡などに使用されます。

一時エンティティーの性質として、処理はほとんど行われず、(非常に単純な衝突を除いて) 衝突の検出も行われません。しかし、一部の一時エンティティーはプレイヤーに何かを気付かせる視覚的な手掛かりを与えます (例えば、弾痕や焼け跡は戦闘があったことを示し、雪の中の足跡はターゲットの捕捉につながります)。インテリジェント・エージェントでも同じ手掛かりを使用することはできないのでしょうか。

その方法は 2 つあります。一時エンティティー・システムにレイ・トレーシングを追加する方法 (この場合、一時エンティティー・システムの意味はなくなります) と、一時エンティティーの近くに空のエンティティーを追加する方法です。

この空のエンティティーには考える能力も関連するグラフィックもありませんが、エージェントはこのエンティティーを検出できます。そして、エージェントに知性を与える情報を伝えます。例えば、床に大量の血のデカールを追加するときに、エージェントに何かがおかしいことを知らせる不可視のエンティティーも追加するのです。もうお分かりでしょうが、足跡にも同じ方法を使用できます。

障害物

多くのシューティング・ゲームで、攻撃を防ぐことができる障害物がある場合、エージェントは何もない場所に敵から丸見えの状態で立つ代わりに、障害物に身を隠す行動をとります。この処理は、これまで説明した処理とは異なる特殊なケースです。エージェントは隠れることができる障害物があるかどうかをどうやって判断すればいいのでしょうか。

Penny Arcade* の敵 AI と障害物処理の風刺漫画

この処理では、その世界にあるものから障害物を決定する方法と、その世界のエンティティーから隠れるのに適切な場所を決定する方法の、2 つの方法について考える必要があります。エンティティーが攻撃を防ぐことができるかどうか判断するには、エンティティーと障害物のサイズを比較する簡単なチェックを実行します。次に、エンティティーが後ろに隠れることができるかどうか確認する必要があります。

そのためには、敵と障害物の位置の違いから光線を作成します。この光線を使用して障害物の後ろが (敵から見て) 安全かどうかを判断した後、その場所をエージェントの次のターゲットにします。風刺漫画のように可燃物の背後に隠れるのはいかがなものでしょう。少なくとも適切な場所ではないですよね。

ここで、エージェントは緑の星の場所が攻撃を受けない安全な場所だと判断している

AI ナビゲーション

これまでは、AI がどのように決定を下しているか、(より良い決定を下すために) 何が起きているかをどのように知ることができるのか詳しく説明しました。ここでは、AI がどのように決定を下すことができるのか、地点 A から地点 B に移動する方法を、例を基に考えてみましょう。ゲームの性質やパフォーマンスのレベルに応じて、いくつかの異なるアプローチを説明します。

クラッシュ・アンド・ターン

クラッシュ・アンド・ターンは、エンティティーの移動方法の中でも最も基本的な方法の 1 つです。具体的に説明しましょう。

ターゲットの向きに移動します。
壁にぶつかったら、ターゲットに最も近くなるように向きを変えます。特に良い選択肢がない場合は、ランダムに選択します。

このアプローチは単純なゲームではうまく動作します。実際に、モンスターがプレイヤーを捜す方法として、非常に多くのゲームで使用されています。クラッシュ・アンド・ターンでは、でこぼこの壁やコーナーがあるとエンティティーが動けなくなってしまうため、何でもすり抜けるゾンビとして移動するゲームや土地に起伏のないゲームで使用するのが理想的です。

エージェントがより賢く移動する必要があるゲームでは、単純なクラッシュ・アンド・ターンを拡張して、エージェントがより多くのメモリーを使用できるようにします。エージェントがすでに移動した場所を把握できれば、向きについてより意味のある決定を下すことができるようになります。どの向きもだめな場合、エージェントは引き返して異なる選択を行います。このように、エージェントはターゲットへのパスを規則正しく調査します。具体的に説明しましょう。

ターゲットに向かって移動します。
分岐点に達したら選択を行います。
行き止まりだった場合、最後に選択を行った場所に戻って別の選択を行います。
すべてのパスを調査してもだめだった場合はギブアップします。

このアプローチは、処理が軽いため、ゲームの速度を低下させることなく、大量の処理を行うことが可能です。また、マルチスレッド化にも適しています。ただし、各エージェントがマップ全体の可能なパスを調べるため、大量の空間スペースを浪費します。

幸い、エージェントが共有メモリーでパスを調べるようにすることで、この浪費を回避できます。このアプローチでは、さらにスレッド化によって競合が発生する場合があるため、個別のモジュールでエンティティーのパスを管理し、移動する際にすべてのエージェントはリクエストを送り、新しいパスが見つかった際にはそのパスを送るようにします。そして、パス・マップ・モジュールで受け取ったリクエスト/パスを解析して競合を回避します。

パス検索

クラッシュ・アンド・ターンによるパスマップの生成は、マップの変更に対応する優れた方法です。ストラテジー・ゲームでは、ユニットが状況を把握するのをプレイヤーはのんびり待ってくれません。これらのパスマップは巨大になるため、パスマップから正しいパスを検索することはボトルネックになります。そこでパス検索の出番です。

パス検索は、ゲーム開発で基本的に解決済みの問題といえるでしょう。オリジナルの Starcraft* (スタークラフト) (Blizzard Entertainment*) のような古いゲームは、大きく複雑なマップのパスをすべて検索できるように大量のゲーム・エンティティーを制御していました。

そのパス検索では、グラフ (ここではマップ) の任意の 2 点間の最適なパスを発見する、’A*’ (エースターと読みます) と呼ばれるアルゴリズムが使用されていました。オンライン検索を行うと、F、G、H のような記述語を使用するアルゴリズムが見つかるでしょう。ここで簡単に説明しましょう。

始めに、チェックしていないノードのリスト (Unchecked) とチェックしたノードのリスト (Checked) の 2 つのリストをセットアップする必要があります。リストはそれぞれ、位置ノード、ゴールまでの推定距離、その親 (このノードをリストに追加したノード) への参照で構成されます。リストの初期状態は空です。

次に、開始位置を Unchecked リストに追加します。親はありません。その後、以下のようなアルゴリズムに従ってリストを更新します。

リストから最も良さそうなノードを選択します。
そのノードがゴールの場合、処理は完了です。
そのノードがゴールでない場合、そのノードを Checked リストに追加します。
そのノードに隣接する各ノードについて以下の操作を行います。
- ノードが移動不可の場合、ノードを無視します。
- ノードがすでに (Checked または Unchecked) リストにある場合、ノードを無視します。
- ほかはすべて、このノードを親として設定し、ゴールまでの距離を推定して (簡単な距離チェックで十分です)、Unchecked リストに追加します。

エンティティーがゴールに到達したら、親がないノード (開始ノード) まで親をさかのぼることで、パスを構築できます。これにより、エンティティーがその後辿るべき最適なパスが分かります。そして、この手順はエージェントに指示が与えられた場合や、移動を自力で決定する場合にのみ必要なため、マルチスレッド化による恩恵を受けることができます。

エージェントは、AI のパフォーマンスに影響を与えることなく、パス探索スレッドにリクエストを送り、パスが発見されたらパスを取得することができます。ほとんどの状況で、システムは迅速に結果を得ることができますが、パスリクエストの負荷が大きい場合、エージェントはそのまま待つかクラッシュ・アンド・ターン手法を使用して正しい向きに進み始めます。

マップが非常に大きい場合、システムはマップを複数の領域に分割して、領域間 (または中間地点) のすべてのパスをあらかじめ計算しておきます。この場合、パス・ファインダーは最良のパスを調べるだけで、直ちに結果を返すことができます。パス・マップ・スレッドは、マップ上の変更 (プレイヤーが壁を作成した場合など) を監視して、必要に応じてパスチェックを再実行します。各スレッドは、ゲームのほかの部分のパフォーマンスに影響を与えることなくアルゴリズムを処理できます。

パス検索サブシステムでは、マルチスレッド化によりシステムのパフォーマンス向上が期待できます。この手法は、リアルタイム・ストラテジー (RTS) ゲームや一意のパスを検索する大量のエンティティーを含むシステムでよく利用されます。異なるスレッドで同時に複数のパスが検索されることがあるので、システムは発見されたパスを把握しておかなければなりません。そうでないと、同じパスを 2 回以上 (無駄に) 発見することになります。

コード例

C 言語で A* を実装した例を紹介します。サポート関数は、例を単純にするため、また異なる実装スタイルに合わせて変更する必要があるため、この例には含まれていません。ゲームレイアウトは単純な格子状のタイルで、各タイルは移動可能または移動不可になっています。この例では隣接するタイルにしか移動できないようになっていますが、多少の変更を加えることで、対角線上への移動を許可したり、六角タイルのゲームレイアウトにすることも可能です。

    /*Get Path will return -1 on failure or a number on distance to path
    if a path is found, the array pointed to by path will be set with the path in Points*/
    int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
    {
        int u,i,p;
        memset(&Checked,0,sizeof(Checked));
        memset(&Unchecked,0,sizeof(Unchecked));
        Unchecked[0].s.x = sx;
        Unchecked[0].s.y = sy;
        Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
        Unchecked[0].p.x = -1;
        Unchecked[0].p.y = -1;
        Unchecked[0].used = 1;
        Unchecked[0].steps = 0;

上記のセクションでは、Checked および Unchecked リストを初期化して、Unchecked リストに開始ノードを追加しています。このセットを使用して、残りのアルゴリズムはループ内で実行できます。

    do {
	    u = GetBestUnchecked();
	    /*add */
	    AddtoList(Checked,Unchecked[u]);
	    if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
	    {
		    break;
	    }

上記のセクションでは、ゴールに最も近い Unchecked リストのノードを調べています。GetBestUnchecked() は、各ノードのゴールまでの推定距離を確認する関数です。そのタイルがゴールの場合、ループを終了して処理を完了します。

以下のコードでは、X と Y 方向の両方からゴールまでの推定距離を調べ、その距離を加えて最終的な距離を計算しています。ここで必要なのは相対距離であり、正確な距離ではないため、ピタゴラスの定理 (a^2 + b^2 = c^2) などを使用して計算する必要はありません。プロセッサーは、乗算 (や除算) よりも加算や減算を高速に処理することができます。このセクションは何度も実行されるため、最適化が鍵になります。

    /*tile to the left*/
    if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
    {
		if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
		/*make sure we don't repeat a search*/
		{
			if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
			NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
		}
    }

上記のセクションでは、現在のノードの左側のタイルを確認しています。そのタイルが Checked または Unchecked リストにない場合、リストに追加しようとします。TileValid() も、ゲームに合わせて変更する必要がある関数です。TileValid() のチェックをパスすると、新しいタイルを Unchecked リストに追加する NewToList() が呼び出されます。次の 3 つのセクションも同じプロセスを行いますが、方向が異なります (右、上、下)。

    /*tile to the right*/
    if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
    {
		if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
		/*make sure we don't repeat a search*/
		{
			if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
				NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
		}
    }
    /*tile below*/
    if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
    {
		if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
		/*make sure we don't repeat a search*/
		{
		    if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
			    NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
		}
    }
    /*tile above*/
    if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
    {
		if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
		/*make sure we don't repeat a search*/
		{
			if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
			    NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
		}
    }
    memset(&Unchecked[u],0,sizeof(PNode));

この反復作業で最後に行うことは、Unchecked リストから現在のノードを削除することです。これでタイルを再度確認する必要がなくなります。

    }
    while(1);

コードの最後の部分では、Checked リストのゴールから逆に追跡を行って、パスを作成します。パスの各ノードには親ノードの情報があるため、開始位置に戻るパスを常に見つけることができます。最終的なパスが見つかると、関数は新しいパスの長さを返します。

		IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
		p = Checked[u].steps;
		if(path != NULL)
		{
			for(i = (p - 1);i >= 0;i--)
			{
				path[i].x = Checked[u].s.x;
				path[i].y = Checked[u].s.y;
				IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
			}
		}
		return p;
    }

まとめ

インテリジェント・エージェントは、まわりの世界を観察する必要があります。単純な範囲チェックやレイ・トレーシングを使用して、視覚や聴覚のようなアイデアに関連する観察を迅速に行うことで、ゲームの展開とともにエージェントが人間と同じような決定を下せるようになります。

エージェントは、ゴールを念頭において進む方向を決める必要があります。クラッシュ・アンド・ターンのような迅速な手法は短期間の単純なマップに適しています。より複雑なゲームでは、マップを分析して最適なパスを検索する必要があります。ゲームをマルチスレッド化して、大量のエンティティーや複雑なマップを含む場合でもスムーズに実行されるようにすることで、パス検索を最適化することができます。

著者紹介

Donald “DJ” Kehoe: ニュージャージー工科大学の IT プログラムのインストラクターとして、ゲーム開発を分業化し、多くのプログラムのコース (ゲーム・アーキテクチャー、プログラミング、レベルデザイン) や、ゲームと 3D グラフィックスを統合したコースを教えています。現在は、ゲームと仮想世界を利用して神経と筋肉のリハビリテーションの効果を高める研究で、生物工学の博士号取得を目指しています。

インテル® ソフトウェア製品のパフォーマンス/最適化に関する詳細は、最適化に関する注意事項 (英語) を参照してください。

知覚とパス検索

AI はどのように知覚するか

AI ナビゲーション

コード例

まとめ

関連記事

著者紹介