Dungeon Generation

The focus this week has been on dungeon generation.

Up till this week I had been using a BSP to generate the level, but I was unsatisfied with this due to the lack of control I had over it. Furthermore a problem with the algorithms I could find posted online again had the same issue. So I set out to create a new algorithm with the following constraints:

1. Should allow control over the rooms to be included. For example 2 stair rooms, 1 large vault and 3 minor vaults.

2. Should fill the remaining space with random rooms.

3. Should connect everything up.

With these steps in mind I came up with this:

The algorithm is based around 'docking' rooms to one of the four corners of a space. The space is then divided into two parts (based on the room's size), and the algorithm is called recursively on the subparts. The strength of this is that you can specify a list of rooms to be included, dock those in the spaces they will fit, then fill the rest with random rooms.

Example:


Starting with:

###############

###############

###############

###############

###############

###############

###############


Placing a single room:
...
...
...

You pick the NE corner, making the grid look like:
###############

###########...#

###########...#

###########...#

###############

###############

###############


Then the remaining space gets seperated as follows:
1111111111#####

1111111111#...#

1111111111#...#

1111111111#...#

1111111111#####

111111111122222

111111111122222

Where 1 and 2 are the two different zones created.

You can then run the algorithm on zone 1 and zone 2.

Using offsets and random sizes for the random rooms (and picking random corners) the resulting grid gets filled with rooms.

You can then place the doors and connect the rooms via corridors (I use a reduced delauney triangulation to find the pairs of doors to connect, then connect them by using A* to find a path).

Examples of the final output:

##################################################
##################################################
####...............###############################
####.#############.#######.......#################
####.#tBBbt#tbbBt#.#######.......+.########....###
####.#bcTcb#bcTcb#.#######.......#.########....###
####.#B.c.b#B6c6B#.#######.......#.########....###
####.#b...b#B...b#.#######.......#.########....###
####.#b...b#B...b#.#######.......#.########....+.#
####.#b...B#B...b#.###############.########....#.#
####.#B...B#b...b#.###############.########....#.#
####.#t...t#t...t#.##############..########....#.#
####.###.#####.###.############....#############.#
####.#...........#.##########...##.#############.#
####.#t.........t#.########...####.############..#
####.######.######.########.######.#########.....#
####......#+#......########.######.#########.###.#
###########........................########..###.#
###########..##########.#+########.######...####.#
############............#.......##...##...######.#
############.####+###.###.......##.#.##.########.#
############.#......#.###.......##.#..#.########.#
#####...####.#......#.###.......##......########.#
#####.>.+....#......#.###.......##..#+##########.#
#####...#.####......#.###.......##.##.........##.#
#########.####......#.###.......#..##.........##.#
#########.###########.###.......#.###.........##.#
#########.###########.###########.###.........##.#
#########.###########.###########.###.........##.#
#########.###########.###########.###.........##.#
#########.###########.###########.##############.#
#########.###########.###########.##############.#
#########.###########.###########.##############.#
#########.###########.###########.##############.#
#########...#########.............##############.#
###########.#########..#########################.#
###.......#.#########..#.........####..........#.#
###.......#.#########..#.........####..........+.#
###.......#.##......#..#.........####..........#.#
###.......#.##......#..#.........####..........#.#
###.......+.##......#..#.........####..........#.#
###.......#.##......#..#.........####..........#.#
###.......#.##......#..#.........####..........#.#
###.......#.##......#..+.........####..........#.#
###.......#.##......+..#.........####..........#.#
###########.##......#..#.........####..........#.#
###########..########..#########################.#
###########......................................#
##################################################
##################################################

Drawbacks:
The resulting map can tend to look quite 'gridlike' (though greater ranges for padding and room size will reduce this tendency).

The map space is not used efficiently (though in most cases, you dont want to pack the map too tightly, so its not the biggest issue).

If the grid is too small the rooms may not be able to be placed (Can brute force by increasing the size of the grid then regenerating, repeat until everything fits).


The way I use it is to have a level description that defines 'required' rooms and 'optional' rooms (with some guide for how to pick the optional ones, like Pick 2 from this list). So when creating a level I create a list of rooms to be added, created from all the 'Required' rooms, all the rooms selected from 'Optional' and any rooms added by the game (like stairs connecting to the previous room). Then using the algorithm all these rooms can be added to the grid, and the remaining space filled in with random stuff.

This algorithm seems to fit all my criteria, and so far I have been very happy with it.