Graph Search to Navigation

Visit every reachable node once with one loop and a frontier. Take from the front and it ripples out in layers; take from the back, marking nodes as they come off, and it plunges down a branch.

Settle the nearest node, relax its edges, repeat. A heap keeps the nearest at hand, a stale entry is skipped, and every settled distance is final because no edge is negative. BFS, ordered by distance.

Dijkstra with a compass: rank the open set by the cost so far plus an estimate of the cost to go. An estimate that never overstates keeps the path optimal in fewer expansions; overstate it, it errs.

Cut the floor into cells, block the ones a wall touches, merge the rest into convex rectangles, and join neighbours with portals: the graph of rooms and doors a game agent plans its route over.

A* where the nodes are rooms and the edges are doors: cost a room by the walk to the door it was entered through, estimate the rest as a straight line, and get back a corridor, not yet a path.

Pull a string tight through the corridor's doors: a funnel narrows to each door's ends, leaves a corner where it would cross itself, and yields the shortest path in the corridor, radius included.