ナビゲーションシステムの内部的なしくみ

ゲーム内のキャラクターにインテリジェントに（AI 用語でいえば「エージェントとして」）移動させたい場合、直面する問題は 2 つ存在します。すなわちレベルにおいて目的地をどのように_判断_し特定させるか、そしてどのやってキャラクターをそこまで_移動_させるか、です。この 2 つの点は強い関連性を持つものの、その中身は大きく異なります。なぜなら「目的地の判断」はレベル全体に対する静的な問題であり、シーン全体への考慮が求められる一方で、「目的地へ移動」はより局地的かつ動的なもので、進む方向や、他の移動中エージェントとの衝突回避などを中心に考慮が必要になるからです。

歩行可能エリア

ゲームシーン中の歩行可能エリアは、ナビゲーションシステム内に独自データとして保持されます。歩行可能エリアは、シーン内でエージェントが立ち止まったり移動したりできる場所を定義するものです。Unity 上ではエージェントは円柱として示されます。歩行可能エリアはシーン内でジオメトリから自動的に生成されます。この際、まずエージェントが立てる場所がテストされ、立てると確認された場所が接続されていき、シーンのジオメトリ表面を覆います。この表面部分のことを、ナビゲーションメッシュ（短縮して NavMesh: ナビメッシュとも）と呼びます。

NavMesh はこの表面部分を凸ポリゴンとして格納します。凸ポリゴンを利用する理由は、ポリゴン内の任意の 2 点間に障害物(Obstacle)がないことが確定しているためです。またポリゴンの境界線以外にも、周囲のポリゴンとの位置関係も記録されます。これにより、歩行可能エリアが判定されます。

経路探索

シーン中の 2 点間を結ぶ経路を探索するには、出発地点と目的地点をそれぞれの地点にもっとも近いポリゴンにマッピングする必要があります。次に、出発地点から検索を始め、目的地点ポリゴンに到達するまで近傍ポリゴンを進んでいきます。この際の経路を追跡することで、出発地点から目的地点までを結ぶルートが発見されます。探索に使用される主要なアルゴリズムには A*（A-star）と呼ばれるものがあり、Unity ではこれを採用しています。

経路に沿って進む

スタートから移動先のポリゴンへのパスが記述された一連のポリゴンを corridor(廊下)といいます。次の目に見える廊下の曲がり角に向かうことでエージェントは移動先に到達します。もしあなたがシーン内で1つのエージェントが動くだけのシンプルなゲームを作ろうとしているのなら、キャラクターは一挙に廊下のすべてのコーナーを見つけ、角を結ぶ線分に沿って移動するようにアニメーション化されます。

同時に移動する複数のエージェントを扱う場合、彼らはお互いを避けるために元のパスから外れる必要があります。線分から成るパスを使用してこのようなズレを補正しようとすると、すぐに難解になりエラーを引き起こしてしまいます。

各フレーム内のエージェントの動きは非常に小さいので、多少回り道をする必要があってもポリゴンのつながりを使って廊下を修正することができます。その後すぐに、次の見える曲がり角に向かいます。

障害物（Obstacle）を避ける

ステアリング理論は目的地に到達するために必要な方向や速さ(速度)を計算して次の曲がり角の座標を求めます。この速度を用いることで他のエージェントとの衝突を実現できます。

障害物回避は、望みの方向への移動と、他のエージェントやナビゲーションメッシュの縁などとの将来的な衝突の平均から、速さを変えます。 Unity は reciprocal velocity obstacles (RVO) を用いて衝突を予測し、回避します。

エージェントを動かす

最後に、操縦と障害物回避を行った後で、最終的な速度が計算されます。 Unity では、エージェントは簡単な動的モデルでシミュレートされます。また、より自然でスムーズな動きを実現するために、加速も考慮します。

この段階において、キャラクターを動かしたり、ナビゲーションシステムにそのキャラクターを注意させるために、シミュレートしたエージェントからメカニムアニメーションシステムに速度を与える事ができるようになります。

エージェントがどちらかの方法を使って動くと、シミュレートされたエージェントの位置が動き、ナビメッシュに拘束されます。この最後の工程はちょっとしたものですが、ナビゲーションを強固なものにするために、とても重要です。

グローバルとローカル

ナビゲーションを理解するうえで最も重要な事の一つに、ナビゲーションの「グローバルとローカルの違い」があります。

グローバルナビゲーションは、ワールド中の走路を探すために使われます。ワールド中のパスを探すのは、非常に多くのメモリと計算量を必要とするコストの高い操作です。

パスとして描画されるポリゴンの線形リストは、操作を行うために柔軟なデータ構造となっており、エージェントの位置が動きをローカルで調整することができます。ローカルナビゲーションは、他のエージェントや動いているオブジェクトを衝突を考慮せずに次の移動位置まで移動する方法を見つけようとします。

2 種類の障害物（Obstacle）

ナビゲーションを使う多くのアプリケーションでは、他のエージェントよりもむしろ他のタイプの障害物を必要とします。シューター型やドライビングのゲームでは普通、籠や樽などが必要になります。障害物はローカルの障害物回避か、グローバルの経路探索を使って、操作することができます。

障害物が動く時は、ローカルの障害物回避を使って最適な操作が行われます。この場合、エージェントは障害物を予知して避ける事が可能です。障害物が静止していて、全エージェントのパスをブロックすると考えられる場合、障害物はグローバルのナビゲーションに影響を与えます。それこそが、ナビゲーションメッシュなのです。

ナビメッシュに変更を加える事を carving と呼びます。障害物のどの部分がナビメッシュに接触したかを探索し、、ナビメッシュに穴を開ける工程です。この計算にはコストがかかるので、衝突回避を利用して障害物を操作した方が良いです。

ローカルでの衝突回避は、まばらに配置された障害物の回避にも使う事があります。アルゴリズムがローカルなため、次にくる障害物の事だけしか考慮できず、トラップを回避したり、障害物が通り道をブロックしている状況を扱う事はできません。そのような状況では、 carving を使えば解決する事ができます。

Off-mesh Links について

NavMesh ポリゴンのつながりは、経路探索システム内のリンクを使って表されます。時にエージェントは歩けない場所を横切って移動する必要があります。例えばフェンスを飛び越えたり、閉まっているドアを通過するといった場合です。このような場合、アクションをする位置を知っておく必要があります。

これらのアクションには、指定したリンクを通るルートが存在する事を経路探索に伝える Off-Mesh Links を使って、注を付ける事ができます。このリンクには、経路を辿った後でアクセスする事ができるので、そこで特別なアクションが実行されます。