Grafo di visibilità
Un grafo i cui nodi sono gli spigoli degli ostacoli e i cui archi uniscono gli spigoli che si vedono: il cammino minimo al suo interno è il cammino minimo tra gli ostacoli.
Introdotto da Tomás Lozano-Pérez e Michael Wesley nel 1979 per la pianificazione del moto dei robot. Poiché in un piano pieno di ostacoli poligonali il cammino minimo corre sempre in linea retta tra spigoli di ostacoli, basta costruire il grafo con quegli spigoli ed eseguirvi A* o Dijkstra.
Il percorso aderisce strettamente agli spigoli: l'effetto è naturale, ma può servire un margine perché le unità non sfreghino il muro. Nel 3D complesso la navmesh ha in gran parte preso il sopravvento, ma in 2D il grafo di visibilità resiste.