• TOP>
  • パス検索

パス検索

概要

 パス検索とは、ナビゲーション・メッシュ上でプレイヤーおよびキャラクター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次元パス検索システムは、ナビボリュームと呼ばれる立体を空間に敷き詰めることによって、パス検索を行う。

スクリーンショット 2017-11-17 14.06.17

影響

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

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

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

関連項目

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

参考文献

AI wiki 記事一覧

はじめに

電ファミ関連記事

コメント

ゲスト
コメントを入力する。
投稿前に利用規約をご確認ください。
ゲスト

コメントの投稿が完了した時点で、本サービスの利用規約に同意したものとさせていただきます。

アクセスランキング

編集メンバー参加申請

こちらの申請フォームより、Wikiの管理人へ参加申請をしてください。

管理人が申請を承認すると、編集メンバーに参加できます。

編集メンバーの詳細はこちらから。

あなたのアカウント ゲスト
サイト名 ゲームAI用語辞典
メッセージ ※メッセージは100文字以内で入力してください。
編集メンバー参加申請

編集に参加するにはログインが必要です。

ゲームAI用語辞典へようこそ!

{{isNeedLogin ? 'この機能のご利用には、Twitterでログインをお願いします。' : 'ログインはTwitterのアカウント連携で行います。'}}
※勝手にツイートすることはありません。