The best way to search (if playing with connected stairs) is to go up and down and check the immediate vicinity: often there are staircase rooms with many stairs nearby. If thats not the case (no pun intended), rather than wander off in search of >, reroll the level.
So, basically the way you play is rather than playing on the 500x500 size map (or however big the map is), you play on a 30x30 size map.
Comment