Lazythunk

Dungeon Generation in Epic Dungeons in Space

Desired Dungeon Layout

I'm working on a space-fantasy roguelike titled Epic Dungeons in Space™ I wanted to try something different from the style of dungeon generation used in rogues like Nethack or Angband. What I enjoy most about roguelikes is the sense of anticipation the player feels when discovering a new room. So I want to pack my dungeons with as many rooms as possible — no long corridors or searching around for doorways.

Controlled Randomness

In EDIS my map is represented by a grid of cells. Areas such as rooms are represented by a Rect. A Rect is an object containing at least an x, y, width and height. First I start with a Rect equal to the dimensions of my map, I'll represent these like rooms you would see in an ASCII roguelike:

+------+
|......|
|......|
|......|
+------+

Then I randomly select a vertical or horizontal split inside the Rect. For example with a vertical split, the area marked with ? would be potential areas for creating a new split:

+-????-+     +---+--+    +---+   +--+
|.????.|     |...|..|    |...|   |..|
|.????.| ->  |...|..| -> |...| & |..|
|.????.|     |...|..|    |...|   |..|
+-????-+     +---+--+    +---+   +--+

Notice that the new Rects should overlap since they share a wall. Keep spliting each new Rect recursively until all Rects are down to a desired minimum room size. If we overlayed these on a map it would look like this:

+----+-------+--------+---+-----+--------+-----+
|....|.......|........|...|.....|........|.....|
|....|.......|........|...|.....|........|.....|
|....|.......|........|...|.....|........|.....|
|....|.......|........|...+-----+........|.....|
+----+-----+-+---+----+...|.....|........|.....|
|..........|.....|....+___+.....+-------++-----+
|..........|.....|....|...|.....|.......|......|
|..........|.....|....|...+-----+.......|......|
|..........|.....|....|...|.....|.......|......|
+-----+----+----++----+...|.....|.......|......|
|.....|.........|.....+---++----++----+-+------+
|.....|.........|.....|....|.....|....|........|
|.....+---------+.....|....|.....|....|........|
|.....|.........|.....|....|.....|....|........|
+-----+.........+-----+....|.....|....+--------+
|.....+----+----+.....+----+----++----+........|
|.....|....|....|.....|.........|.....|........|
|.....|....|....|.....|.........|.....|........|
|.....|....|....|.....|.........|.....|........|
|.....|....|....|.....|.........|.....|........|
+-----+----+----+-----+---------------+--------+

Not bad! You can see the structure is there but, it isn't too interesting unless you're trying to create a Borg cube.

This is the best part to fine tune for your tastes. There are a lot of fun variables to mess with: minimum room size, median split tolerance, vertical vs. horizontal split weight etc. Along the way, you'll want to collect all of the smallest Rects into an array for the other stages of processing.

Pre-processing Neighbors

With the list of smallests Rects we'll need to figure out which rooms are potential neighbors and save those on each Rect. My map is a grid of cells, each Rect represents some area of cells and if there are enough overlapping cells I can determine which Rects are neighbors of each other. The algorithm I used for this is:

current for each rect
  r for each rect
    skip if r is already in current neighbor list
    if r overlaps current -- a fast test against x/y width/height
      shared = shared cells in current and r
      if length of shared > 1
        add r to current neighbor list
        add current to r neighbor list

Neighbors must share at least 2 cells, for example the first case here would be invalid but the second would be the minimum required for passing between rooms using a Manhattan distance.

+--+      +--+
|..|      |..|
+--+--+   +-++-+
   |..|     |..|
   +--+     +--+

Remove Rooms

Now that all the Rects know their neighbors we can start creating a more interesting map. To make things seem less uniform, I'm going to remove Rects until we have only a few connected rooms left. In psuedo-code again:

  while under max removed rects
    remove a random rect
    if remaining rects are not connected
      add removed back

We can use a flood fill algorithm to check that the remaining Rects are still connected after removal:

connected = []
open = []

add a starting rect to open

while open is not empty
  current = remove from open
  add current to connected
  neighbor for current neighbors
    if neighbor not in connected or open
      add neighbor to open

The remaining rects should equal the length of connected If we apply this a few times to the example map:

     +-------+--------+---+     +--------+-----+
     |.......|........|...|     |........|.....|
     |.......|........|...|     |........|.....|
     |.......|........|...|     |........|.....|
     |.......|........|...|     |........|.....|
     +-------+---+----+...|     |........|.....|
                 |....+___+     +-------++-----+
                 |....|...|     |.......|       
                 |....|...+-----+.......|       
                 |....|...|.....|.......|       
+-----+---------++----+...|.....|.......|       
|.....|.........|     +---++----++----+-+------+
|.....|.........|     |....|.....|    |........|
|.....+---------+     |....|.....|    |........|
|.....|.........|     |....|.....|    |........|
+-----+.........+-----+....|.....|    +--------+
      +----+----+.....+----+----++----+........|
      |....|    |.....|         |.....|........|
      |....|    |.....|         |.....|........|
      |....|    |.....|         |.....|........|
      |....|    |.....|         |.....|........|
      +----+    +-----+         ------+--------+

Which is pretty good without any adjustment. Smaller room size and more removals will create more interesting maze-like patterns (and you could also apply a maze generator on top of this structure.) Here's an example of this in action using existing code from EDIS: