After wrestling with it for the past week, I’ve finally got a mostly functional random dungeon generator for my roguelike game Witherwyn. I hit several serious set backs (such as my algorithm predictably terminating only at infinity). The upside, is that the new algorithm produces topologically more interesting mazes than its rather naive predecessor.
Most roguelike map generators are diggers. This means that they work by initially filling up the entire map with walls and then they cut out rooms and corridors. Working this way guarantees that every cell in the dungeon is reachable from any other cell (a very desirable trait in any level for any game). My previous attempt at a random dungeon generator was made in 2001 and was intended to run on a TI-89 (which it did). I was using it in Witherwyn for a while. It worked by hollowing out a large room in the middle of the map, then it entered into a loop:
1. Find a wall that was exposed only on one face
2. Decide to try to put a room or corridor here
3. See if this feature will fit
4. If so, add it, other go to step 1.
After several hundred iterations, you would get a nice-looking map. However, all the maps it produced had a starfish topology – i.e. all paths between distant cells in the map went through the center.
For version two, I am using the much more complicated scheme outlined here. Basically the steps are:
1. Generate a dense perfect maze (no cycles, all points reachable) using Hunt and Kill (or Prim’s, or similar algorithm)
2. Sparsify the maze by iteratively filling in dead ends
3. Remove x% of the dead ends in the maze by intentionally adding cycles
4. Place rooms in smart places
I am still working on the room-placing step. It involves a double convolution – when I try to add a room to the map – I try to place it in all possible positions and then score those positions based on whether they would cause the room to intersect another room, or an existing corridor. The whole thing is a gigantic mess of nested for loops (6 of them, I think). It would never run on the 12 Mhz TI-89. Having gotten the damn thing to work, I’m declaring myself the Convolution Colonel.
Now all I have to figure out is the best way to add doors…
Witherwyn Google Count: 94
I once wrote a random dungeon generator for the TI-85/86. The dungeon levels were only 25×15 or so, so my algorithms was to take ten or so different 3×3 templates, e.g.
xx_
___
_xx
and randomly choose them to fill up the level. Surprisingly, interesting twisty passages and corridors and such resulted.
Personally I’d suggest adding rooms wherever you encounter one of those nice little twisty dead-end corridors. They look highly annoying, so it’d solve the trouble of where to put the rooms, and get rid of dead ends at the same time!
I made a girly-pink-frilly dress-up in javascript, I guess.