技術的サマリー：幾何学に基づくナビメッシュの検証——優先探索を伴うボクセルベース分析

問題定義

ナビゲーションメッシュ（ナビメッシュ）は、ビデオゲームにおけるノンプレイヤーキャラクター（NPC）の移動の基盤であり、歩行可能領域と接続性を定義する。しかし、大規模なゲーム開発において、環境は動的であり、地形、アセット、衝突幾何学は頻繁に変化する。その結果、ナビメッシュはこれらの変化と完全に同期して再生成されないことが多く、ナビゲーションデータと、基盤となる幾何学によって定義された実際の歩行可能空間との間にミスマッチが生じる。

既存の自動化された検証手法は、通常、エージェントベースの探索（例えば、世界を移動する強化学習エージェント）やランタイムの挙動分析に依存している。これらのアプローチは、エージェントが立ち往生したり目標に到達できなかったりするといった問題を間接的に推測するものであり、ナビゲーション表現が真の幾何学を正確に反映しているかを明示的に検証するものではない。さらに、これらの手法は計算コストが高く、自動化パイプラインへの統合が困難であり、ランタイムの失敗として即座に現れない構造的な不一致を検出できないことが多い。ランタイムシミュレーションに依存せず、ナビメッシュの正しさを直接検証するオフライン手法の欠如が存在する。

手法

本論文は、ナビメッシュ検証を幾何学の一貫性問題として扱うオフラインフレームワークを提案する。エージェントの挙動をシミュレートするのではなく、システムは環境の幾何学から歩行可能空間を独立して再構築し、エンジンによって生成されたナビメッシュと比較する。手法は以下の 3 つの主要コンポーネントで構成される。

1. ボクセルベースの歩行可能空間の再構築

システムは、ボクセルベースの表現を用いて、地形および衝突幾何学から直接、歩行可能空間の独立した参照を再構築する。

• ボクセル化: 地形の高さマップとアセットの衝突メッシュは、離散的な 3 次元グリッドのボクセルに変換される。
• 制約を考慮した分類: 各ボクセルは、ゲームエンジンの設定から導出されたナビゲーション制約（傾斜制限、ステップ高さ、エージェント半径、垂直クリアランス）に対して評価される。これらの制約を満たさないボクセルは破棄される。
• 接続グラフ: 残った歩行可能なボクセルは、近傍半径によって決定される隣接関係を持つグラフ $G_v = (V_w, E)$ を形成する。洪水充填アルゴリズムを用いて主要な連結成分を抽出し、孤立したアーティファクトを除去することで、幾何学に由来する到達可能性モデル $R_{vox}$ が得られる。

2. 学習に基づく優先探索

大規模なボクセル空間の網羅的な検証は計算的に不可能であるため、本フレームワークは探索を優先された探索問題として定式化する。

• 強化学習（RL）: ダブル深層 Q ネットワーク（DDQN）が、サンプリングプロセスを誘導するために訓練される。RL エージェントはナビゲーションをシミュレートするのではなく、不一致を含む可能性が高い領域を優先する方策を学習する。
• 状態と報酬: 状態には、局所的な幾何学的文脈、意味的重要性（パトロールルートやスポーンポイントへの近接性など）、および探索履歴が含まれる。報酬関数は、意味的に重要な領域への訪問を奨励し、冗長なステップや再訪問を罰する。
• 優先経験再生: 訓練プロセスは、高価値または構造的に複雑な領域に関連する遷移に焦点を当てる優先経験再生を使用し、収束を加速する。

3. 一貫性検証

RL 誘導の方策によってサンプリングされた各位置について：

• システムはエンジンにクエリを送信し、生成されたナビメッシュ上の到達可能性 ($R_{nav}$) を決定する。
• $R_{nav}$ を、幾何学に由来する到達可能性 $R_{vox}$ と比較する。
• 不一致 ($R_{nav} \neq R_{vox}$) は、潜在的な不一致を示すフラグとなる。
• ポストプロセッシング: 検出された不一致は、ボクセル離散化によって引き起こされる軽微なアーティファクトを除去し、構造的に重要な欠陥領域のみを保持するために、許容度ベースのフィルタリングおよび空間クラスタリング（連結成分分析）を受ける。

主要な貢献

1. 幾何学一貫性の定式化: 本論文は、幾何学に由来する歩行可能性とナビメッシュの接続性との直接比較としてナビメッシュ検証を定式化し、検証をエージェントの挙動およびランタイムシミュレーションから切り離す。
2. ボクセルベースの参照モデル: 生データである地形および衝突データから歩行可能空間を再構築する、制約を考慮したボクセルベースの表現を導入し、検証のための独立した真値（グラウンドトゥルース）として機能させる。
3. 学習に基づく探索: 本研究は、ナビゲーションシミュレーションではなく、探索の優先順位付けに強化学習を使用することを示す。このアプローチは、欠陥を含む可能性が高い領域にサンプリングを集中させることで検証効率を大幅に向上させ、均一サンプリングやヒューリスティックな重要性ベースのサンプリング戦略を上回る。
4. 生産対応パイプライン: 本フレームワークは、ゲームエンジン内に統合されたオフラインツールとして設計されており、並列処理が可能で、大規模かつ進化し続ける環境向けの自動化された QA ワークフローへの統合が可能である。

実験結果

本フレームワークは、Unity およびユービーアイソフトの Anvil エンジンの両方を使用して、複数の大規模な本番環境で評価された。

• 効率性: 学習に基づく優先戦略は、網羅的な走査（BFS/DFS）と比較して約45% 少ないサンプル数で、ヒューリスティックな重要性ベースのサンプリングと比較して24% 少ないサンプル数で、同様のカバレッジレベル（85% の重要性重み付きカバレッジ）を達成した。
• 検出: 検出率は手法間で比較的可能であった（約 87% から約 92.6% の範囲）が、提案された手法は、最も低いサンプル数（ベースラインの 55%）で最高検出率（92.6%）を達成した。
• 偽陽性: 優先 RL アプローチは、許容度ベースのフィルタリングおよびクラスタリングによるポストプロセッシングのおかげで、他の戦略と同等かそれ以下の偽陽性率（4.1%）を維持した。
• スケーラビリティ: 再構築および検証時間は、本番利用において実用的であることが示され、大規模な領域の完全な検証は 1〜7 分で完了した。

意義と主張

本論文は、このアプローチがナビメッシュの正しさを検証するための直接的、決定論的、かつ反復可能な手法を提供すると主張する。主に幾何学とエンジンクエリに依存するため、この手法は最小限の変更で異なるゲームエンジンに適応可能である。

その意義は、「エージェントの失敗を通じてバグを発見する」というパラダイムから、「幾何学比較を通じて構造的な一貫性を検証する」というパラダイムへの転換にある。これにより、エージェントが即座に立ち往生する原因とはならないが、ワールドデザインとナビゲーションデータ間の根本的なミスマッチを表すナビゲーションエラーの検出が可能となる。本フレームワークは、現代のオープンワールドゲーム開発の迅速なイテレーションサイクルに追従できる、スケーラブルで自動化された品質保証を可能にし、高価なランタイムシミュレーションを必要とせずに、ナビゲーションデータを進化し続けるゲーム環境と同期した状態に保つことを保証する。