ナビゲーションメッシュ

ナビゲーションメッシュ（navmesh ）は、人工知能アプリケーションで使用される抽象データ構造であり、複雑な空間での経路探索においてエージェントを支援します。このアプローチは、少なくとも1980年代半ばからロボット工学の分野で知られており、メドウマップと呼ばれていました^{[1] 。そして2000年に}ビデオゲームのAIで普及しました。

説明

ナビゲーションメッシュは、環境のどの領域をエージェントが移動できるかを定義する 2 次元の凸多角形(ポリゴンメッシュ) の集合です。言い換えると、ゲーム内のキャラクターは、環境の一部である木、溶岩、その他の障害物に妨げられることなく、これらの領域内を自由に歩き回ることができます。隣接するポリゴンは、グラフで互いに接続されています。

これらのポリゴンの1つ内での経路探索は、ポリゴンが凸型で通過可能なため、直線で簡単に実行できます。メッシュ内のポリゴン間の経路探索は、A*などの多数のグラフ検索アルゴリズムの1つを使用して実行できます。^[2]ナビメッシュ上のエージェントは、環境の一部である障害物との計算コストの高い衝突検出チェックを回避できます。

2Dのような形式で移動可能領域を表現すると、本来は「真の」3D環境で実行する必要がある計算が簡素化されますが、2Dグリッドとは異なり、異なる高さで上下に重なり合う移動可能領域が可能になります。^[3]ナビゲーションメッシュ内のさまざまなサイズと形状のポリゴンは、通常のグリッドよりも高い精度で任意の環境を表現できます。^[4]

創造

ナビゲーションメッシュは、手動、自動、またはその両方の組み合わせで作成できます。ビデオゲームでは、レベルデザイナーがレベルエディターでナビメッシュのポリゴンを手動で定義する場合があります。このアプローチは非常に手間がかかります。^[5]あるいは、レベルジオメトリを入力として受け取り、ナビメッシュを自動的に出力するアプリケーションを作成することもできます。

一般的に、ナビメッシュによって表現される環境は静的であり、時間の経過とともに変化しないと考えられており、そのためナビメッシュはオフラインで作成でき、不変である。しかし、動的な環境におけるナビメッシュのオンライン更新についてはいくつかの調査が行われてきた。^[6]

歴史

ロボット工学では、このように連結された凸多角形を使用することは「メドウマッピング」と呼ばれており、^{[1] 1986年の}ロナルド・C・アーキンによる技術レポートで造語されました。^[7]

ビデオゲームの人工知能におけるナビゲーションメッシュは、通常、 Game Programming Gemsに掲載されたGreg Snookの2000年の記事「Simplified 3D Movement and Pathfinding Using Navigation Meshes」に由来するとされています。^{[8] 2001年に、JMP van Waverenは、}Quake III Arenaのボットに使用される「Area Awareness System」と呼ばれる、凸型で接続された3Dポリゴンを使用した同様の構造を説明しました。^[9]

注記

^ Tozour 2002、p.171より。
^ スヌーク2000、294-295頁。
^ スヌーク2000、289ページ。
^ ブランド2009、4ページ。
^ ブランド2009、10ページ。
^ ヴァン・トール、クック IV、ゲラルツ、2012.
^ アーキン 1986年。
^ ゴロデッツ 2013.
^ ヴァン・ウェイヴェレン、2001、p. 24〜46。

参考文献

Arkin, Ronald C. (1986)。「視覚ベースの自律ロボットの経路計画」(PDF) (技術レポート)。マサチューセッツ大学。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
Brand, Sandy (2009). 自律的に生成されたナビゲーションメッシュを使用した効率的な障害物回避(PDF) (修士論文). デルフト工科大学. 2015-06-09に閲覧。
Golodetz, Stuart (2013 年 10 月)。「構成空間での自動ナビゲーションメッシュ生成」。Overload . 117 . ACCU。
Snook, Greg (2000)。「ナビゲーションメッシュを使用した 3D 移動とパスファインディングの簡略化」。DeLoura, Mark (編)。ゲームプログラミングの宝石。Charles River Media。288 ～ 304 ページ。ISBN 1-58450-049-2。
Tozour, Paul (2002)。「ほぼ最適なナビゲーションメッシュの構築」。Rabin, Steve (編) 。AI ゲームプログラミングの知恵。Charles River Media。pp. 171–185。ISBN 1-58450-077-8。
van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2012). 「動的環境のためのナビゲーションメッシュ」(PDF) .コンピュータアニメーションと仮想世界. 23 (6). John Wiley & Sons: 535–546. doi :10.1002/cav.1468. S2CID 2996937 . 2015-06-09に取得。
van Waveren, JMP (2001-01-28). Quake III Arena Bot (PDF) (修士論文). デルフト工科大学.

外部リンク

UDK: ナビゲーションメッシュリファレンス
Unity: ナビゲーションの概要
ソースエンジン: ナビゲーションメッシュ
Urho3D: ナビゲーション
Godot エンジンナビゲーション
クライエンジンナビゲーションとAI

[FOOTNOTETozour2002171-1] Tozour 2002、p.171より。

[FOOTNOTESnook2000294–295-2] スヌーク2000、294-295頁。

[FOOTNOTESnook2000289-3] スヌーク2000、289ページ。

[FOOTNOTEBrand20094-4] ブランド2009、4ページ。

[FOOTNOTEBrand200910-5] ブランド2009、10ページ。

[FOOTNOTEvan_TollCook_IVGeraerts2012-6] ヴァン・トール、クック IV、ゲラルツ、2012.

[FOOTNOTEArkin1986-7] アーキン 1986年。

[FOOTNOTEGolodetz2013-8] ゴロデッツ 2013.

[FOOTNOTEvan_Waveren200124–46-9] ヴァン・ウェイヴェレン、2001、p. 24〜46。