My personal solution would be to generate rooms lazily so that each room always has an entrance and exit.
I think a minimap would be cool but maybe not necessary. You could get away with some kind of exit indicator.
