IT用語集 › AI & 機械学習 › 可視グラフ
ノードが障害物の角、エッジが互いに見通せる角同士を結ぶグラフ。そこでの最短経路が、障害物を避ける最短経路になる。
1979年にトマス・ロサノ＝ペレスとマイケル・ウェズリーがロボットの動作計画のために導入した。多角形の障害物が並ぶ平面では、最短経路は必ず障害物の角と角の間を直線で進むため、それらの角からグラフを作り、A*やダイクストラ法を走らせれば足りる。
経路は角すれすれを通るので自然に見えるが、ユニットが壁をこすらないよう余白が必要になることがある。複雑な3Dではナビメッシュがほぼ主流になったが、2Dでは可視グラフが今も現役である。