ナビゲーションメッシュ
コンテンツへジャンプ
ナビゲーションメッシュ（navmesh）は、人工知能アプリケーションにおいて、エージェントが複雑な空間を経路探索するのを支援するために使用される抽象データ構造です。このアプローチは、少なくとも1980年代半ばからロボット工学の分野で知られており、メドウマップと呼ばれていました[ 1 ] 。そして2000年にはビデオゲームのAI分野で普及しました。
説明
[編集]ナビゲーションメッシュは、2次元の凸多角形（ポリゴンメッシュ）の集合であり、エージェントが環境内のどの領域を移動できるかを定義します。言い換えれば、ゲーム内のキャラクターは、環境を構成する樹木、溶岩、その他の障害物に遮られることなく、これらの領域内を自由に移動できます。隣接するポリゴンはグラフで互いに接続されています。
これらのポリゴンは凸型で通過可能なため、ポリゴン内部の経路探索は直線上で簡単に行うことができます。メッシュ内のポリゴン間の経路探索は、 A* [ 2 ]などの多数のグラフ探索アルゴリズムのいずれかを用いて行うことができます。これにより、ナビメッシュ上のエージェントは、環境の一部である障害物との 計算コストの高い衝突検出チェックを回避できます。
2Dのような形式で移動可能領域を表現することで、「真の」3D環境で実行する必要がある計算が簡素化されますが、2Dグリッドとは異なり、異なる高さで上下に重なり合う移動可能領域が可能になります。[ 3 ]ナビゲーションメッシュ内の様々なサイズと形状のポリゴンは、通常のグリッドよりも高い精度で任意の環境を表現できます。[ 4 ]
創造
[編集]ナビゲーションメッシュは、手動でも自動でも、あるいはその両方を組み合わせて作成できます。ビデオゲームでは、レベルデザイナーがレベルエディタでナビメッシュのポリゴンを手動で定義することがあります。このアプローチは非常に手間がかかる場合があります。[ 5 ]あるいは、レベルジオメトリを入力として受け取り、ナビメッシュを自動的に出力するアプリケーションを作成することもできます。
ナビメッシュによって表現される環境は静的、つまり時間経過とともに変化しないものと一般的に想定されており、そのためナビメッシュはオフラインで作成でき、変更不可能である。しかしながら、動的な環境におけるナビメッシュのオンライン更新に関する研究もいくつか行われている。[ 6 ]
歴史
[編集]ロボット工学では、このように連結された凸多角形を使用することは「メドウマッピング」と呼ばれており、[ 1 ]これは1986年のロナルド・C・アーキンの技術レポートで造語された。[ 7 ]
ビデオゲームの人工知能におけるナビゲーションメッシュは、通常、2000年にGreg SnookがGame Programming Gemsに掲載した記事「Simplified 3D Movement and Pathfinding Using Navigation Meshes」に由来するとされています。[ 8 ] 2001年には、JMP van Waverenが凸型で連結された3Dポリゴンを用いた同様の構造を説明し、「エリアアウェアネスシステム」と名付け、Quake III Arenaのボットに使用されました。[ 9 ]
注記
[編集]- ^ a b トズール 2002年、171ページ。
- ^ スヌーク 2000、294～295頁。
- ^ スヌーク 2000、289ページ。
- ^ ブランド 2009、4ページ。
- ^ ブランド 2009、10ページ。
- ^ ヴァン・トール、クック IV、ゲラルツ、2012 年。
- ^ アーキン1986年。
- ^ ゴロデッツ 2013 .
- ^ ヴァン・ウェイヴェレン、2001、p. 24〜46。
参考文献
[編集]- アーキン、ロナルド・C. (1986). 「視覚ベースの自律ロボットのための経路計画」 (PDF) (技術レポート). マサチューセッツ大学.
{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です - Brand, Sandy (2009).自律的に生成されたナビゲーションメッシュを用いた効率的な障害物回避 (PDF) (修士論文). デルフト工科大学.オリジナル (PDF)から2015年6月10日にアーカイブ。 2015年6月9日閲覧。
- ゴロデッツ、スチュアート（2013年10月） 「コンフィギュレーション空間における自動ナビゲーションメッシュ生成」オーバーロード117ACCU
- スヌーク、グレッグ (2000). 「ナビゲーションメッシュを用いた簡略化された3D移動と経路探索」. マーク・デルーラ編著. 『ゲームプログラミングの宝石』 . チャールズ・リバー・メディア. pp. 288– 304. ISBN 1-58450-049-2。
- ポール・トズール（2002年）「ほぼ最適なナビゲーションメッシュの構築」ラビン・スティーブ編『AIゲームプログラミングの知恵』チャールズリバーメディア、 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年6月9日閲覧.
- van Waveren, JMP (2001-01-28). Quake III Arena Bot (PDF) (修士論文). デルフト工科大学.
外部リンク
[編集]
ナビゲーションメッシュ（navmesh）は、人工知能アプリケーションにおいて、エージェントが複雑な空間を経路探索するのを支援するために使用される抽象データ構造です。このアプローチは、少なくとも1980年代半ばからロボット工学の分野で知られており、メドウマップ[1]と呼ばれていました。そして2000年にはビデオゲームのAI分野で普及しました。
説明
ナビゲーションメッシュは、2次元の凸多角形（ポリゴンメッシュ）の集合であり、エージェントが環境内のどの領域を移動できるかを定義します。言い換えれば、ゲーム内のキャラクターは、環境を構成する樹木、溶岩、その他の障害物に遮られることなく、これらの領域内を自由に移動できます。隣接するポリゴンはグラフで互いに接続されています。
これらのポリゴンは凸型で通過可能なため、ポリゴン内部の経路探索は直線で簡単に行うことができます。メッシュ内のポリゴン間の経路探索は、 A* [2]などの多数のグラフ探索アルゴリズムのいずれかを用いて行うことができます。これにより、ナビメッシュ上のエージェントは、環境の一部である障害物との 計算コストの高い衝突検出チェックを回避できます。
2Dのような形式で移動可能領域を表現することで、「真の」3D環境で実行する必要がある計算が簡素化されますが、2Dグリッドとは異なり、異なる高さで上下に重なり合う移動可能領域が可能になります。[3]ナビゲーションメッシュ内の様々なサイズと形状のポリゴンは、通常のグリッドよりも高い精度で任意の環境を表現できます。[4]
創造
ナビゲーションメッシュは、手動でも自動でも、あるいはその両方を組み合わせて作成できます。ビデオゲームでは、レベルデザイナーがレベルエディタでナビメッシュのポリゴンを手動で定義することがあります。このアプローチは非常に手間がかかる場合があります。[5]あるいは、レベルジオメトリを入力として受け取り、ナビメッシュを自動的に出力するアプリケーションを作成することもできます。
ナビメッシュによって表現される環境は静的、つまり時間経過とともに変化しないものと一般的に想定されており、そのためナビメッシュはオフラインで作成でき、変更不可能である。しかしながら、動的な環境におけるナビメッシュのオンライン更新に関する研究もいくつか行われている。[6]
歴史
ロボット工学では、このように連結された凸多角形を使用することは「メドウマッピング」と呼ばれており、[1]ロナルド・C・アーキンによる1986年の技術レポートで造語されました。[7]
ビデオゲームの人工知能におけるナビゲーションメッシュは、通常、2000年にGreg SnookがGame Programming Gemsに掲載した記事「Simplified 3D Movement and Pathfinding Using Navigation Meshes」に由来するとされています。[8] 2001年には、JMP van Waverenが、 Quake III Arenaのボットに使用される「エリアアウェアネスシステム」と呼ばれる、凸型で連結された3Dポリゴンを使用した同様の構造を説明しました。[9]
注記
- ^ Tozour 2002、171ページより。
- ^ スヌーク 2000、294～295頁。
- ^ スヌーク 2000、289ページ。
- ^ ブランド2009、4ページ。
- ^ ブランド2009、10ページ。
- ^ ヴァン・トール、クック IV、ゲラルツ、2012.
- ^ アーキン 1986.
- ^ ゴロデッツ 2013.
- ^ ヴァン・ウェイヴェレン、2001、p. 24〜46。
参考文献
- アーキン、ロナルド・C. (1986). 「視覚ベースの自律ロボットのための経路計画」(PDF) (技術レポート). マサチューセッツ大学.
{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です - Brand, Sandy (2009). 自律的に生成されたナビゲーションメッシュを用いた効率的な障害物回避(PDF) (修士論文). デルフト工科大学. オリジナル(PDF)から2015年6月10日にアーカイブ。 2015年6月9日閲覧。
- ゴロデッツ、スチュアート（2013年10月）「コンフィギュレーション空間における自動ナビゲーションメッシュ生成」オーバーロード誌、117頁、ACCU。
- スヌーク、グレッグ (2000). 「ナビゲーションメッシュを用いた簡略化された3D移動と経路探索」. マーク・デルーラ編著. 『ゲームプログラミングの宝石』 . チャールズ・リバー・メディア. pp. 288– 304. ISBN 1-58450-049-2。
- ポール・トズール（2002年）「ほぼ最適なナビゲーションメッシュの構築」スティーブ・ラビン編『AIゲームプログラミングの知恵』チャールズリバーメディア、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年6月9日閲覧.
- van Waveren, JMP (2001-01-28). Quake III Arena Bot (PDF) (修士論文). デルフト工科大学.
外部リンク
- UDK: ナビゲーションメッシュリファレンス
- Unity: ナビゲーションの概要
- ソースエンジン: ナビゲーションメッシュ
- Urho3D: ナビゲーション
- Godotエンジンナビゲーション
- クライエンジンナビゲーションとAI
