ナビメッシュ（NavMesh）完全ガイド：基本概念から生成・動的対応・実装まで
エバープレイ編集部ナビメッシュ（NavMesh）とは何か
ナビメッシュ（Navigation Mesh、略してNavMesh）は、主にゲームやシミュレーション、ロボティクス分野で用いられる経路探索のための空間表現です。連続する歩行可能領域を多角形（多くは凸ポリゴンや三角形）の集合として表現し、エージェント（キャラクターやロボット）はこのメッシュ上で最短経路やコスト最小経路を求めて移動します。グリッドベース（タイルやボクセル）よりも表現効率が良く、自然な経路や滑らかな回避挙動を実現しやすい点が特徴です。
基本概念と構造
- ポリゴン単位の表現：ナビメッシュは歩行可能領域をポリゴン（多角形）の集合として表し、ポリゴン同士は共有するエッジで隣接関係を持ちます。多くの実装ではポリゴンを「ノード」として扱い、隣接ノード間の通行可能性をエッジとして考えます。
- 凸性の重要性：凸ポリゴンであれば、ポリゴン内の任意の2点間は直線で結べるため、内部での経路計算が簡単になります。そのため生成工程で凸化や三角分割が行われることが多いです。
- 階層性とレイヤー：大規模なマップではヒエラルキー（大きな領域→小さな領域）を持たせたり、上下階層（橋や階段）を分けて扱うことで探索の効率化を図ります。
ナビメッシュ生成の流れ（代表的な手法）
商用エンジンやライブラリでは、環境から自動的にナビメッシュを「ベイク（bake）」する機能が備わっています。代表的な生成工程は次のようになります。
- ジオメトリ抽出：シーン内のコリジョンやメッシュから「歩行可能」と見なすジオメトリを抽出します。
- ボクセル化（Voxelization）：空間を細かいセルに分割し、歩行可能領域をボクセル単位でマークします。これにより複雑な形状を整数グリッドで扱いやすくします。
- 輪郭抽出（Contour tracing）：ボクセル領域の外形を輪郭として抽出します。
- ポリゴン化と簡略化（Polygonization / Simplification）：輪郭を多角形に変換し、必要に応じて頂点数を削減して多角形群を得ます。
- トポロジー処理：穴や孤立領域の処理、隣接関係の計算、オフメッシュリンク（ジャンプや梯子など特殊移動経路）の追加などを行います。
この一連の工程は、オープンソースのRecast（Mikko Mononen作）などで実装されています。Recastではパラメータとして cellSize や cellHeight 、agentHeight、agentRadius、agentMaxClimb、maxSlope、regionMinSize、edgeMaxError といった設定があり、これらを調整して生成結果の品質と精度を制御します。
経路探索アルゴリズムと経路の滑らか化
- グラフ探索（A*）：ナビメッシュのポリゴンをノード、ポリゴン間の通行可能なエッジを辺としてグラフ化し、A*などの探索アルゴリズムでポリゴン列（通過領域）を求めます（A*の原理については一般的な参考文献を参照ください）。
- ファネルアルゴリズム（Funnel）：通過するポリゴン間の共通エッジ（ポータル）を用いて、経路の頂点列を最適化（ポータル間を直線的に結んだ最短路を求める）します。これにより「クネクネ」した通路ではなく、より滑らかで自然な経路が得られます。
- コストと領域属性：特定領域にコストを付けて避けさせたり（泥地は遅くなるなど）、通行不可領域や優先領域を指定できます。探索はこれらのコストを考慮した重み付きA*で行います。
動的環境への対応
屋内の扉開閉や移動障害物、破壊可能オブジェクトなど、実行時に環境が変化する場合は静的なナビメッシュだけでは不十分です。代表的な対応手法は次の通りです。
- カービング（Carving）：NavMesh上から障害物分の領域を切り抜く手法。UnityのNavMeshObstacleのCarve機能などが該当します。動的に現れる障害物を即座に反映できますが、頻繁な更新はコストが高くなります。
- 部分的再ベイク（Incremental/Rebake）：変更があった領域だけを再生成する手法。Recastベースの実装や商用ミドルウェアでは増分更新機能があるものもあります。
- 経路再計画（Replanning）：局所的な回避ロジック（ローカル・アボイダンス）と組み合わせ、長計画はNavMesh、短期回避は別アルゴリズムに任せる混成戦略が一般的です。
局所回避と群衆（Crowd）シミュレーション
ナビメッシュはグローバル経路を提供しますが、エージェント同士の衝突回避や混雑を扱うには局所回避アルゴリズムが必要です。代表的な技術に Reciprocal Velocity Obstacles (RVO) や DetourCrowd（Detourの群衆モジュール）があります。これらは各エージェントの速度ベクトルを互いに調整して衝突を未然に避けます。大人数の群衆シミュレーションでは、NavMeshを高レベル経路に使い、RVO等で低レベルの動作を補う構成が一般的です。
主要な実装例とツール
- Recast & Detour：オープンソースの代表実装で、ナビメッシュ生成（Recast）と経路探索（Detour）、群衆モジュール（DetourCrowd）を提供します。ゲーム開発コミュニティで広く利用されています。
- Unity：Unity の NavMesh システムはエディタでベイク可能で、NavMeshAgent、NavMeshObstacle、OffMeshLink などのコンポーネントを提供します。拡張用の NavMeshComponents は GitHub で公開されています。
- Unreal Engine：Unreal のナビゲーションシステムは Recast ベースで実装されており、ナビメッシュのベイク、動的ボリューム、ナビメッシュレイヤーなどをサポートします。
- RVO2 などのローカル回避ライブラリ：局所回避に特化したライブラリはナビメッシュと組み合わせて用いられます。
実務上の注意点とベストプラクティス
- エージェントパラメータを正しく設定する：agentRadius（半径）、agentHeight（高さ）、maxClimb（段差許容）、maxSlope（上り斜度）等は現実のエージェントを想定して正確に設定してください。これらは生成結果に大きく影響します。
- ベイク解像度のトレードオフ：cellSize や contour simplification の設定は生成時間とメモリ、形状精度のトレードオフです。広大なマップでは階層化や領域分割を検討してください。
- オフメッシュリンクの活用：ジャンプ、登攀、梯子、テレポート等の特殊移動はオフメッシュリンクで定義し、経路探索時に考慮させます。
- 動的要素の扱い：頻繁に移動する障害物はNavMeshの再構築コストが高くなるため、動的障害物はローカル回避や一時的な経路再計画で処理するのが実用的です。
- テストと可視化：視覚的にナビメッシュやポータル、経路を表示して問題箇所（到達不能領域、細すぎる通路など）を検出します。多くのエンジンはデバッグ可視化ツールを提供します。
応用例
- ゲーム（NPCのナビゲーション、群衆表現）
- ロボティクス（屋内移動ロボットの経路計画）— ただしロボットでは3D障害やセンシングを考慮した補完が必要
- 建築や都市シミュレーション、群衆解析（避難経路解析など）
- AR/VR環境でのエージェント挙動やユーザー導線の設計
よくある落とし穴とトラブルシューティング
- 狭すぎる通路や接触しているコリジョンが原因で期待したナビ領域が切り離される。
- スロープや階段の扱いを誤ると歩行不能エリアが発生する。maxSlope と maxClimb の設定を見直す。
- 動的障害物のCarvingを乱用すると再生成コストでフレームレートが落ちる。頻度や半径を制限するかローカル回避に切り替える。
- 経路が「壁に張り付く」ように見える場合は、ファネル後のパススムージングやウェイポイントのオフセット（マージン）を利用する。
まとめ
ナビメッシュは、効率的で表現力の高い経路探索基盤として、ゲーム開発のみならずシミュレーションやロボティクス分野でも広く採用されています。重要なのは単にナビメッシュを生成することではなく、エージェント特性に合わせたパラメータ設計、動的要素との連携（ローカル回避や部分再ベイク）、そしてデバッグ/可視化を通じて実運用に耐える品質を作り込むことです。オープンソースの Recast & Detour や、Unity / Unreal の実装を学び、実際の環境でチューニングを重ねることが最短の近道です。
参考文献
- Recast & Detour（GitHub） — ナビメッシュ生成と経路探索の代表的オープンソース実装
- Unity Manual: Navigation (NavMesh) — Unity のナビゲーションシステムの公式ドキュメント
- Unity NavMeshComponents（GitHub） — カスタムベイクや拡張を提供する公式拡張群
- Unreal Engine: Navigation System — Unreal のナビゲーションに関する公式ドキュメント（Recastベース）
- RVO2（Reciprocal Velocity Obstacles） — 局所回避アルゴリズムとライブラリ
- A* search algorithm（Wikipedia） — 経路探索アルゴリズムの基礎
投稿者プロフィール
