Grafo de visibilidad
Un grafo cuyos nodos son las esquinas de los obstáculos y cuyas aristas unen esquinas que se ven entre sí — el camino más corto a través de él es el camino más corto esquivando los obstáculos.
Introducido por Tomás Lozano-Pérez y Michael Wesley en 1979 para la planificación de movimiento de robots. Como un camino más corto en un plano lleno de obstáculos poligonales siempre va en línea recta entre esquinas de obstáculos, basta con construir el grafo a partir de esas esquinas y ejecutar A* o Dijkstra sobre él.
El camino se ciñe mucho a las esquinas, lo que se ve natural pero puede necesitar un margen para que las unidades no rocen la pared. En 3D complejo, el navmesh se ha impuesto en gran medida, pero en 2D el grafo de visibilidad sigue vivo.