I don't know how they actually did it but conceptually I thought about it as traversing the map's segments depth first in 2D starting at one edge of the viewport & the currently occupied polygon. Simple, and allows freedom like overlapping rooms, but would go sideways in cases like the one you describe.