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

When you want to intelligently move characters in your game (or agents as they are called in AI circles), you have to solve two problems: how to reason about the level to find the destination, then how to move there. These two problems are tightly coupled, but quite different in nature. The problem of reasoning about the level is more global and static, in that it takes into account the whole scene. Moving to the destination is more local and dynamic, it only considers the direction to move and how to prevent collisions with other moving agents.

歩行可能エリア

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

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

経路探索

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

経路に沿って進む

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

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

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

障害物（Obstacle）を避ける

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

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

エージェントを動かす

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

この段階で、シミュレーションしたエージェントからアニメーションシステムに速度を提供して、ルートモーションを使用してキャラクターを移動させたり、ナビゲーションシステムにそれをさせることができます。

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

グローバルとローカル

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

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

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

2 種類の障害物（Obstacle）

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

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

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

Local collision avoidance can be often used to steer around sparsely scattered obstacles too. Since the algorithm is local, it will only consider the next immediate collisions, and cannot steer around traps or handle cases where an obstacle blocks a path. These cases can be solved using carving.

Describing OffMesh Links

The connections between the NavMesh polygons are described using links inside the pathfinding system. Sometimes it is necessary to let the agent navigate across places which are not walkable, for example, jumping over a fence, or traversing through a closed door. These cases need to know the location of the action.

These actions can be annotated using OffMesh Links which tell the pathfinder that a route exists through the specified link. This link can be later accessed when following the path, and the special action can be executed.