ひとことで
キャラクターが歩ける床を、凸多角形（三角形など）の集まりとして表したものです。広い部屋は大きな多角形 1 つで済むので、同じ範囲を細かい格子で表すよりノードがずっと少なく、A* の探索が速くなります。多角形の中なら、どこに立っても、どの方向へまっすぐ歩いても外に出ないことが保証されるので、経路は「通る多角形の列」の中で自由に引けます。Unity、Unreal Engine、Godot など多くのエンジンが標準で使っています。
ゲームでの使いどころ
- 3D のアクションや RPG の敵・仲間の移動：坂や段差、複数の階をまたぐ地形でも、歩ける面だけをつなげて経路を探す。
- キャラクターの大きさごとのメッシュ：人間用、大型の敵用など、通れる幅に合わせて別々のナビメッシュを作る。
- オフメッシュリンク：はしご、ジャンプ、扉など、床でつながっていない場所どうしを特別な辺でつなぐ。
- 動的な障害物：置かれた箱や壊れた橋を、その部分だけ作り直して反映する（タイルごとの再ベイク）。
しくみ
作る（ベイク）：レベルのメッシュから、歩ける面を取り出します。代表的な Recast では、
- シーンをボクセルに分け、上が空いていて傾きが緩い面を「歩ける」とします。
- 壁からキャラクターの半径の分だけ歩ける範囲を縮めます（エロージョン）。
- 歩ける範囲を領域に分け、輪郭を多角形にして、凸多角形に分割します。
デモでは、長方形の障害物を半径の分だけ広げ、その角と辺上の点をドロネー分割して、障害物の中の三角形を捨てています。
探す：多角形をノード、共有する辺（ポータル）を隣り合う関係として、A* で「通る多角形の列（回廊）」を求めます。コストは多角形の中心どうし、あるいはポータルの中点どうしの距離で近似します。
経路を引く：回廊の中で、角をかすめる最短の折れ線をファネル法で求めます。多角形の中心を結ぶだけだとジグザグになるためです。
実装のポイント
- 半径で縮める：ナビメッシュをキャラクターの半径だけ縮めておけば、経路の計算では「点」として扱えます。角をかすめる経路でも、体が壁にめり込みません。
- 地面への投影：経路は多角形の上の点なので、坂や段差では、実際の地面の高さに合わせて足元の高さを求め直します。
- 点がメッシュの外：クリックした点がちょうど障害物の上だった場合などは、いちばん近い多角形の上の点に寄せてから探します。
- 歩き方との組み合わせ：ナビメッシュが決めるのは大まかな道筋です。実際の移動は、次の曲がり角へ向かう操舵と、ほかのキャラクターとの回避（ORCA）で決めます。
つまずきやすい点
- 細長い三角形：三角形の形が悪いと、多角形の中心を結んだコストが実際の距離とずれ、遠回りの回廊を選ぶことがあります。ファネル法で経路自体は整いますが、回廊の選び方には影響します。
- 半径の違うキャラクター：小さなキャラクター用のメッシュを大きなキャラクターに使うと、狭い隙間に入り込んで引っかかります。
- 動く床や扉：ナビメッシュは基本的に止まった地形用です。動くものは障害物として別に避けるか、その部分を作り直します。
デモで試すこと
- 青い三角形の集まりがナビメッシュです。柱や壁の周りは、キャラクターの半径の分だけ床が削られています。床をクリックすると、黄色の回廊が選ばれ、赤い経路に沿ってキャラクターが歩きます。
- 「キャラクターの半径」を大きくすると、柱の周りの削られる幅が広がり、狭い通路がふさがって遠回りになります。
- 「同じ範囲を格子で表すと」を入れると、同じ範囲を 0.25 刻みの格子にした場合のノード数と比べられます。三角形の数の方がずっと少ないことを確かめてください。
- 「三角形の重心を結ぶ」に切り替えると、回廊の中をジグザグに進む不自然な経路になります。