Synlighetsgraf
En graf där noderna är hindrens hörn och kanterna kopplar hörn som ser varandra — kortaste vägen genom den är kortaste vägen förbi hindren.
Introducerad av Tomás Lozano-Pérez och Michael Wesley 1979 för robotars rörelseplanering. Eftersom en kortaste bana i ett plan med polygonhinder alltid går rakt mellan hinderhörn räcker det att bygga grafen av hörnen och köra A* eller Dijkstra över den.
Banan hugger tätt om hörnen, vilket ser naturligt ut men kan behöva marginal så enheter inte skrapar i väggen. I komplex 3D har navmesh i stort tagit över, men i 2D lever synlighetsgrafen kvar.