Visibility Graphs and Cell Decomposition
Before sampling planners, there were two classic ways to turn a map into a graph. A visibility graph links every pair of obstacle corners that can see each other, and gives the truly shortest path, though it hugs the obstacles. Cell decomposition splits free space into simple cells and connects neighbors, giving safer but longer paths.
Drag the start and goal.
Two roadmaps
The visibility graph has a node at every obstacle corner, plus the start and goal, and an edge between any two nodes whose straight connecting line crosses no obstacle. Its shortest path is the shortest possible path in the plane, because a shortest path only ever bends at obstacle corners.
Cell decomposition splits space into cells, here by a quadtree that keeps splitting any cell that is partly blocked, until a size limit. Free cells become nodes, joined when they touch.
What to notice
The visibility path grazes the obstacle corners, so a real robot would need the obstacles inflated by its radius first. The cell path keeps away from walls but is longer and jagged, and with too little detail, narrow gaps get lost because their cells count as blocked. Both scale badly to many dimensions, which is why arms use sampling planners.