パス検索

概要 †

　パス検索とは、ナビゲーション・メッシュ上でプレイヤーおよびキャラクターAIの位置や可動範囲を検索し、必要に応じて移動の最短経路や予測経路を計算することができるアルゴリズムである。

歴史 †

　ゲーム内キャラクターの可動最短経路を計算する“パス検索”の先祖となる技術はグラフ理論と呼ばれ、1960年代にアメリカで電話交換網を広げていく際に使用された。
　離散空間において点と点をつなぐためのアルゴリズムは、「ダイクストラ法」やA* アルゴリズム呼ばれている。一方、ロボット技術においては、連続空間である現実世界を凸多角形のメッシュで囲み、その各中心にある点の連結データを取ることで、仮想の「離散空間」と見なして計算する技術が開発されていた。

　これらの技術は長らくゲーム業界では利用されてこなかったが、現在使われているナビゲーションAIの代表となるナビゲーション・メッシュとA* アルゴリズムを使用したパス検索を、本格的に3Dゲームに実装したのは2000年にリリースされた『Counter-Strike』（Valve Software／2000年）である。

　背景としては、ファミコンやスーパーファミコンの時代に簡易スクリプトで作られていたキャラクターAIは、自分の置かれている状況を十分に認識できるだけの知能が実装されてなかったため、ゲーム画面内の障害物に引っかかり動けなくなることがしばしばあったという課題があった。
　この問題はスーパーファミコンの時代にもあったが、3Dの大型ゲームの開発によって、いよいよ深刻なものとなった。その背景には、2Dゲームではキャラクターの行動範囲を制限するなどで問題が可視化されないようにしていたのが、3Dでは平面のマップ内の高低差や障害物が複雑に入り組むようになるため、人力で書くスクリプトで制御することの限界が生じたからである

　欧米のゲーム会社はこの課題に対し、テクノロジーによる解決策を模索した。2000年に刊行された技術書、『Game Programming Gems』 （Charles River Media; Book & CD edition。 リンク先は翻訳版。）「SECTION 3　人工知能」の「ナビゲーション メッシュによる3D移動とパス発見の単純化」で始めて“パス検索”という技術が紹介されたことをきっかけに、ゲーム開発者のあいだで徐々に普及し始めた。

3次元パス検索 †

　3次元パス検索システムは、ナビボリュームと呼ばれる立体を空間に敷き詰めることによって、パス検索を行う。

影響 †

　「ユーザーが見ているゲーム画面」と「ゲーム内のキャラクターが見ている光景」は異なる。
　パス検索の実装により、キャラクターはキャラクター自身から見たゲーム世界の状況を認識する知能を得た。キャラクターはかつてのようにひとつのエリアや経路に捕らわれることなく、ゲーム世界の中で自分自身が置かれた状況や環境を判断しながら、目的地にたどり着くことができるようになった。一方で、行動の自由を得たことと引き換えに、ゲームのキャラクターは、より高度に周囲を認識し、行動を決定する必要に迫られるようになった。

　このことはゲームデザインに求められるものの変化させることにもつながった。キャラクターAIの場所からの解放は、時間の解放にもつながったからである。

　自由に行動できるキャラクターAIは、より生き物らしく考えているように振る舞うことが期待されるし、移動が自由になるということは、思考においても長期的なスパンでのプランを作る能力が要求されるようになる。つまり時間と空間から解放されたAIには、より高度な思考と責任が求められるようになったのだ。

関連項目 †

ナビゲーションAI
ナビゲーション・メッシュ
ウェイポイントグラフ

参考文献 †

• 『人工知能の作り方』 （三宅陽一郎 著／技術評論社）
• 21世紀に“洋ゲー”でゲームAIが遂げた驚異の進化史。その「敗戦」から日本のゲーム業界が再び立ち上がるには？【AI開発者・三宅陽一郎氏インタビュー】 （電ファミニコゲーマー）
• AI最前線の現場から【スクウェア・エニックス】 ゲームそのものを認識するメタAI （ThinkIT）

AI wiki 記事一覧 †

はじめに †

• AIとは？
• このwikiの目的
• 使いかた

電ファミ関連記事 †