Preface #
I’ve for a very long time been fascinated by the concept of procedural generation in games. There is something incredibly exciting in the endeavour of constructing a process that generates endless variety while adhering to certain design goals. Lately, I’ve been particularly obsessed with the methods used to generate dungeons in traditional grid-based roguelike games—you know, the ones that characteristically present themselves as blobs of ASCII characters on a terminal, leaving most of the graphics up to the player’s imagination. Throughout the genre’s existence of now over 40 years, many such methods have been developed, with the classic technique simply being described as follows:
- Start with a map full of wall cells.
- Generate a room at random coordinates with a random size, discarding if it would overlap with an existing room.
- Repeat Step 2 until a certain number of rooms have been placed (or a certain number of iterations).
- Connect the rooms using corridors.
This method generates neat rectangular rooms, and gives results similar to the dungeons in Rogue (the eponym of the genre) and Nethack. Since the rooms are often quite separated, step 4. is necessary and typically involves some form of pixelated line-drawing algorithm connecting the centers of the different rooms.
In addition to the fact that connecting the rooms is quite tricky, the main drawback of this algorithm is that generating maps with lots of rooms significantly increases the runtime, as it quickly becomes difficult to find empty areas by chance. While this frankly does not pose a challenge to modern hardware, it can still be undesirable for optimization reasons. To alleviate this problem, methods such as Binary Space Partitioning (BSP) and Tunneling algorithms have been devised. I won’t go into great detail with these; Josh Ge, the developer of Cogmind already has a fantastic blog post listing these methods with visual examples.
With my own roguelike game project, which has inconveniently been stuck in development hell since I started my Engineering degree back in 2022, I’ve been particularly wary about the design of the dungeon generator. In particular, I want the generator to fulfil the following criteria:
- The rooms should be minimally separated, preferably with walls that are only one cell thick.
- There should be a nice blend of rooms of various sizes and shapes, corridors and open areas. Maze-like structures are welcome.
- Corridors shouldn’t merely be room-to-room connectors, but rather form winding pathways with several doors leading directly into adjacent rooms.
- The generator script shouldn’t easily be able to ‘corner’ itself (in the sense that it is difficult to progress with room placement), and run in a relatively short time.
The Tunneling algorithm illustrated by Josh Ge in their blog post is by nature excellent at fulfilling the third criterion, since the tunneler digs out corridors and builds rooms in empty areas next to the corridor. However, depending on the desired end result, the algorithm may be very tricky to implement. For example, a naive room-placing function that simply checks if a new room of randomly selected size and shape would overlap an existing room has the same drawback as the basic algorithm; in order to get tightly packed rooms, the algorithm would have to run for a very long time. Furthermore, to ensure that the tunneler actually reaches the entire map, it will at least require out-of-bounds checking and ideally even a navigation heuristic that guides the tunneler towards large chunks of unexcavated wall.
In this article, I’m going to showcase a different, very simple approach to dungeon generation which can nevertheless be heavily customized and is capable of fulfilling all of my personal criteria above.
The Basic Generator #
Fundamentally, this dungeon generator is very similar to the classic method, placing rooms into the grid at random:
###############################################################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################........###########################################
############################........###########################################
############################........###########################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
##########......###############################################################
##########......###############################################################
##########......###############################################################
##########......###############################################################
##########......###############################################....############
##########......###############################################....############
##########......###############################################....############
###############################################################....############
###############################################################....############
###############################################.......#########....############
###############################################.......#########....############
###############################################.......#########################
###############################################.......#########################
###############################################.......#########################
###############################################.......#########################
#########.......###############################################################
#########.......###############################################################
#########.......###############################################################
#########.......###############################################################
###############################################################################
###############################################################################
###############################################################################However, when a room would be discarded due to overlapping with an existing room, we place it anyway and surround it with walls like so:
###############################################################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################........###########################################
############################........###########################################
############################........###########################################
###############################################################################
###############################################################################
###############################################################################
###############################################################################
##########......###############################################################
##########......###############################################################
##########......###############################################################
##########......###############################################################
##########......###############################################....############
##########......###############################################.###############
##########......###############################################.#........######
###############################################################.#........######
###############################################################.#........######
###############################################.......#########.#........######
###############################################.......#########.#........######
###############################################.......###########........######
###############################################.......#########################
###############################################.......#########################
###############################################.......#########################
#########.......###############################################################
#########.......###############################################################
#########.......###############################################################
#########.......###############################################################
###############################################################################
###############################################################################
###############################################################################This has a couple of important consequences. First and foremost, rooms that become partially covered attain irregular shapes, which was one of my design goals. Secondly, this actually allows us to simplify the algorithm. Since every room we place will be surrounded by walls anyway, we can simply ignore the overlap checking (which is by far the most complicated step of the process!) and construct all rooms using the same set of for loops. My crude Python implementation looks roughly like this:
import numpy as np
import random
MAP_SIZE_X = 79
MAP_SIZE_Y = 35
grid = np.zeros(shape=(MAP_SIZE_Y, MAP_SIZE_X), dtype=int)
def random_room(min_size: int, max_size: int, floor_tile: int = 0, wall_tile: int = 1):
size_x, size_y = (random.randint(min_size + 2, max_size + 2) for i in range(2))
pos_x, pos_y = (random.randint(0, MAP_SIZE_X - size_x), random.randint(0, MAP_SIZE_Y - size_y))
for x in range(pos_x, pos_x + size_x):
for y in range(pos_y, pos_y + size_y):
grid[y][x] = wall_tile
for x in range(pos_x + 1, pos_x + size_x - 1):
for y in range(pos_y + 1, pos_y + size_y - 1):
grid[y][x] = floor_tileIf we continue placing variable-size rooms a hundred or so more times—
for i in range(200):
random_room(3, 8)—we get a result like this:
###############################################################################
##########....################......#.......#######################........####
####..######..################......#.......#.#..###.##########################
#######....#..################......#.......#############...#####..#....#.....#
#.....#....##########......##########.......##########..#...#...#..#....#.....#
#...###....########.#......###.....##.......##..#....#..#...#...#.#########...#
#...#.#....###....#.#......###.....##.......##..#....#..#...#...#.#.......#...#
#...#.#....###....#.#......###.....##.......##..#....#..#...#...#.#.......#...#
#...#.#....###....#.#......#.########.......#####....####..########.......#####
#..####....###...##############..##############.#....#..#..#......#.......#..##
####..#....###...#..##......#.#..#...#.......####....#..####......#.......#..##
##################..##......#.#..#...##########.######..#..#......#.......#..##
#.......#...######..##......########.##########...###...#..#......#.......#..##
#.########..#.#.######......##.....#.####...###...#######..#......#.......#..##
#.#......######.#....#......##.....#.####...###...##..#....#......#########..##
#.#......#...####....#......##.....#.##.#...###########....#........#..########
###......#...#..#.#########.###########.#...#.#....#..#....##########.....#...#
###......#...#.##.#.......#############.#...#.#....#..############..#.....#...#
###......#...#.##.#.......####....#.##..#...#.#######..###########..#######...#
###......########.#.......#..#..###############.....#####...##...####...##....#
###......##.##.##.#########..#######.#.......##.....#.###...##...#####..#######
#######################......#.....############.....#.###...##########..##....#
#....######.......##..#......#.....##.......###.....#####...#........######...#
#....########.....##..#......#.....##.......###.....#.#######........#....#...#
#...##......#.....##..#......#.....##.......#########.##...##........#....#...#
#...##......###########......#.....##.......#################........#....#...#
######......#..##.....#......#.....###############....#.#..##........#....##..#
#...##......#..###############.....#...#.#......##....#.#..##........##########
#...##......#..#.......####........##########...##....#.#..##........#.#...####
#...##......#..#########..##########.#......###.##....#.#####........#.#...####
#...##......#####....#.......##......#......#.#.##....###.############.########
#...##......##..######.......##......#......#.#########...##..#..#.#####...####
#...#############.####.......##......#......#.########....##..####....#....####
###############...##########################################.....######....####
###############################################################################For an algorithm roughly a dozen lines of code long and without any if-statements, I personally find this quite remarkable. There is a lot in this layout that entices me from a player’s perspective; upon opening a door it is never obvious whether it will lead into a large open area or a cramped space, and to me this significantly enhances the exploration aspect. The attentive reader now asks me the question: What door?
So far, all rooms are completely enclosed and frankly, the process of actually connecting them with doors and hallways is a topic for a future article. For now, I’d like to focus on how the basic algorithm can be modified and extended to obtain different results.
Modifications #
The generator can place more objects than just rooms surrounded by walls. If we want to open up the map a little, we can, at the end of the script, add a couple of random rectangles of only floor tiles:
###############################################################################
##......############......########.....####################...#.....#..########
##......####################...###.....####..###....#.....#...#.....#..#...####
##......#.....##....#....###..####...####......#....#.....#...#######..########
##......#.....##....#....###..#........##......#....#.....#...#....#####.....##
##......#.....##....#....###..#........####..###..........#.########...#.....##
##......#......#....#....###..#........##.....##..........###......#...#.....##
##......#####..#....#...####..#........#########....#.....#.#......#...########
##......###..#.#....#...#..#..#........###.....##..########.#......#..........#
###########..#.#....#...#..####........###.....#...##..#....#......#..........#
##.....##.#....#....#####.....############.....#...##..#....#......##.........#
#########.##..###########........#.....###.....#...##..#....#.............#####
#...#.....#......#####..#........#.....#.#######...##..#######.....##........##
#...#.....##..#..#..##..#..#######.....##############.....####......#.#......##
#...#.....##..#..#####..#..#.....#######......#..#.########..#......#.###...###
#####.......#.#..#...#########...#....#.......#..###..#...#..#......###.......#
#####.......#.####...#..#....#...#....#.......#..###..#.......................#
##..#.......#.#.#########....#...#....#.......#..###..#..............####...###
##..#.......#.#.##.....##....#######..#################.##...........#.......##
##..#.......#.#.##..#####..........######.......#.....###...####.....#.......##
##..#.......######..#...#..........##..##.......#.....###...###......#.......##
##..#.......######..#..............##..##.......#.....#.#...#.....###........##
##..#########..######..............######.......#.....#.#................######
##......##.....#...#########.......#...##.......#....####...................###
##......##.....#......######.......#....#.......#....#..#...##...........#..###
###########...####....##...#.......#....##############..#...####.........#..###
##.########...#........#####.....###.....#..#####....#..#...#..#.....#...######
##.#......#####........#...#.......#.....#..##.##....#..#####..#.....#...#..###
##.#......#####........#...#.............#####.##....#.....#...#######...######
##.#......#####........#...#...........###.#.#.#.....#.....#...#...#.....#...##
##.#######.....########..########........#.#.###.....#.....#...#...#.....######
##.....#........#...###........###.......#.#.###.....#.....#...#...#.....######
##.....#........#####..........#...#.....###.###.....##########################
##.....###.......#######.......#...#######...###.....#######......#.....#######
###############################################################################The method can utilize multiple terrain types as well. To add irregular patches of e.g. water or grass, we can add functions creating such rectangles (or other shapes, but rectangles are the simplest) of those in the generator loop. To gain additional control, we can also specify exactly which tile types are replaced by ‘floor’ and which ones are replaced by ‘wall’. I got decent results by, at the end of the procedure, placing rectangles of water (symbolized by ≈ below) that alternate between replacing only floor tiles, replacing only wall tiles and replacing everything:
###############################################################################
###...####≈≈#.≈≈≈≈≈.#≈≈≈≈########≈≈≈≈≈≈.#..#......#..#..####.#....#############
###...#..#≈≈#.≈≈≈≈≈.#≈≈≈≈........≈≈≈≈≈≈.....###...#..#..####≈≈≈≈≈≈#...#########
#.....#..#≈≈#.≈≈≈≈≈.#≈≈≈≈≈≈≈≈≈...≈≈≈≈≈≈#......#..##≈≈≈≈.#..#≈≈≈≈≈≈#.........≈≈#
#.....#..#≈≈##≈≈≈≈≈###≈≈≈.......≈≈≈≈≈≈≈.......#..#.≈≈≈≈.#..#≈≈≈≈≈≈#.........≈≈#
#.....#..##...≈≈≈≈≈#.#...........≈≈≈≈≈≈.......####.≈≈≈≈##≈≈#≈≈≈≈≈≈#...#.....≈≈#
#≈≈...#####...≈≈≈≈≈#.#....#........#..........#..#.≈≈≈≈##≈≈#≈≈≈≈≈≈....##≈≈≈≈≈≈#
###...#..##....#...#.#....##≈#######..........#..#.≈≈≈≈..###.#.....#####≈≈≈≈≈≈#
#######..##≈≈≈≈#...#.#########≈≈≈≈≈≈≈≈........####...##..###.#.......##########
###...#####≈≈≈≈#...#.≈≈≈######......≈≈≈.......#..#...##..###############......#
###...#..##≈≈≈≈#...≈≈≈≈##....#......≈≈≈......#####...##..##....#.......#......#
#≈≈≈≈.#..##≈≈≈≈≈...≈≈≈≈≈#≈≈≈.#.#####≈≈≈#.........######.##≈#####≈≈≈....#......#
#.≈≈..#..###≈≈≈≈≈≈≈≈≈≈≈≈#≈≈≈≈###..≈≈≈≈≈####......≈....####≈#≈≈≈##≈≈....#......#
###≈≈≈≈..#≈#≈≈≈≈.≈≈≈#####≈≈≈≈###..≈≈...#.##......≈..≈≈####....≈≈#≈≈≈≈≈≈#......#
###≈≈≈≈#####..≈≈.≈≈≈#..≈#≈≈≈.#.#..≈≈...#.#≈≈≈≈≈.#####...##......########......#
###≈≈≈≈........≈.≈≈≈#..≈#≈≈≈.###.......#≈≈≈≈≈≈≈≈≈..#≈≈≈≈≈≈≈≈##..###..#≈≈≈≈....#
#####≈.........≈.≈≈≈#...######.#≈≈≈≈≈..#≈≈≈≈≈≈≈≈≈..#≈≈≈≈≈≈≈≈.....##############
#####≈.........#.##########.#..#≈≈≈≈≈..#≈≈≈≈≈≈≈≈≈..#≈≈..##.......###.#......###
#####≈...........#.##########..#.......##.≈≈≈≈≈≈≈...≈≈..####.....###≈#...≈≈≈≈≈#
###≈≈≈≈##........######.....####.......#..≈≈≈≈≈≈....≈≈..#.#........≈###########
##≈≈≈≈≈≈......#.############≈###########...###......≈≈..#.#........≈#...#######
##≈≈≈≈≈≈......#.#.#........#≈##...#........###..........#.#........≈#...#....##
###≈≈≈≈≈.....##.#.#........########........#.#####.....##.#........≈########≈##
##≈≈≈≈≈≈..≈≈≈≈≈.###.≈≈.....####.###........#.#....#....###.........≈##.....#.##
##≈###≈≈..≈≈≈≈≈≈#.#.≈≈.....#....###........########....#...........≈##.....#.##
##≈#≈#≈≈≈≈≈≈≈≈≈≈#.#.≈≈.....######.#.......≈########....#...........##≈.....#.##
##.#...≈≈.≈≈≈≈≈##.#........#..#.#.#.......≈###≈≈..#....#.......######≈.....#.##
####≈≈≈≈≈≈≈≈≈≈≈####........#..#.#.############≈≈..≈....###...#.....##≈.≈...#.##
###.≈≈≈≈≈≈≈≈≈≈≈####........#..###....#########≈≈..≈....#..#..#.....#.#.....#.##
###.≈≈≈≈≈≈≈....##≈##≈≈≈≈####..#.######.....≈≈#####≈....#..#..#.....###.....####
###.≈≈≈≈≈≈≈....##...≈≈≈≈......#......#########.##.≈....#..#..#.....###.....####
###.≈≈≈≈≈##....≈≈...≈≈≈≈......#......########..##.≈≈≈≈##..#..#####≈≈≈≈≈≈#######
###......##....##...≈≈≈≈###.......###########..##....≈#####....########...#####
####################≈≈≈≈..........######################.......################
###############################################################################To create a maze-like map full of corridors, we can nest a smaller room inside each generated ‘room’, effectively genererating each room with a corridor around it:
###############################################################################
##.#..........#.#################################################...#.....#####
##.#.########.####........######.#.........###############..#######.########..#
##.#.#......#.##.#.#############.#.#######.#.......#..##.#.##..################
##.#.#.....#####################.#.#.....#.#.#####.##.##########.....#.......##
####.#.....#.......#.........#.#.#.#.....#.#.#...#.##.#.......##.###.#######.##
#..#.#.....#.#######.#######.#.###.#.....############.#.#####.##########...#.##
#.##########.#.....#.#.....#.#.#.#############.....##.#.#...#.#####....#...#.##
#.#.....#..#.#.....#.#######.#.####..........##########.#...#.#...####.#...#.##
#.#.###.####.#######.........#.####.########.#...##...#.#...#.###.#..#.#...#.##
#.#.#.#.#..#.......###########.####.#......#.######.###.#####.#.#.#..#.#...#.##
#.#.#.#.################.#...#.######......#.#....#.#.#.......#.#.#..#.#####.##
#.#.#########.......#..#.#...#.#....########.######.#.###########.#..#.#.....##
###.##......#######.####.#####.####.#........###..#.#.....##......#..#.########
#.#.##.####.#.....#.#..#.......#..#.###############.#.....#########..#.####.#.#
#.#..#.#..#.#######.############..#.#######.......#.#######.##.#######.##.#.#.#
#.####.#..#.#.......##......#.#...#.###..##########.........##.........##.###.#
#.####.#..#.##########.######.#####.##########....###########################.#
#....#.####.##.#.#..##.#...##.......###......########.#...#.#.########......###
######......##.#.#####.#...############.####.##....##.#...#.####.....#.####.#.#
###..###########....##.#...#.#.......##.#..##########.#####.#..#.#####.#..#.#.#
###.#####.##...#############.##########.#..#........#.......#..#.#...#.#..#.###
###.#...#.#####.##........##.####.#.###.#..#.######.############.#####.#..#.###
###.#...#.#...#.##.######.####..#.##########.#....#.#..#.##.#..###...#.#..#.###
#.#.#...#.#...#.##.#....#.#..####.#........#.######.##.#.##.##.#.#.###.#..#.###
#.#.#####.#...#.##.#....#.##.#..#.#.########........##.#.#..##.#.#.#.#.#..#.###
#.#.......#...#.##.######.##.####.#.#......###########.#.#####.#.#.#.#.####.###
#.#############.##........##.#.##.#.#......#.#.#.#...#.#.#######.#.#.#......###
#.#.....#.#.....############.#.####.#......#.#.#.#####.###.....#.#.#.##########
#.#######.#########.##.#####.#.##.#.#......#.#.#.......##.####.#.#.#.....#.#.##
#.........#..#.#.##..#.......#.##.#.#......#.#.##########.#..#.#.#.#.....#.#.##
##############.#.#############.####.#......#.##########.#.####.###.#######.####
####.##.#......#.################.#.########.#####......#......###.........####
####..#.########.....##############..........###################.##############
###############################################################################What’s really cool about this method is that we can combine these different room functions in our generator script. For example, the following was generated by alternating between placing nested rooms and regular walled rooms, with the nested rooms having a 50% chance of not spawning the outermost wall. Finally, a couple of rooms without walls were added to create larger open areas:
###############################################################################
#############.....#....#......###################..........#............#######
###.......#.#..####.####......##.......#..###########...######.....#.......####
###.........#..#.......#.#######.#......###.........#........#...........#....#
###....................#.#....#..#..###...#.#######.#....................####.#
#######.....###.....####.#....#..#..#.#.###.#.....#.#.......#..#......#.....#.#
###.###................#.#....#..#..###..##.#.....#.#.....#.#..#......#.###.#.#
#######.......#........#.#....#..#.......########.#.##.#....#..#......#.#.#.#.#
####.....#.............###....#..#.#.#.###......###.##.#....#.........#.#.#.#.#
##########.....#........##....#....#.#.#####....#...##.#.####....######.#.#.#.#
#####..........#........##....#.##.###.....#....##########........#.....#.#.#.#
##.##.###......################.#......###.#....######...#....###.#.#...#.#.#.#
##.##.#.#.##.....#.#.#.#.....#######.#...#.#....#...##...#.#....#.####..###.#.#
##.##.#.#.##.....#.#.###.....#######.#...#.#....###.##...#.#....#.##.#......#.#
##.##.###.##.....#.###########.#####.#...#.#.##########..#.#....#.###########.#
##.##.....######......#.#...#...####.#...#.#..##......####.######.##....#...#.#
###########..........########......#.#...#.#...#......####........#####.#...#.#
########.#######...........##......#.#...#.#.###......#..###########..........#
##.....#.....#.#.....#####.##......#.#####.#.#.#####.....##.......####.######.#
#....###.###...#........##.##......#.......#.#..#.........#.......#..#.#....#.#
#......#.#.#...#........##.########...#########.#.......###.......#..#.######.#
#......#.#.#...#........##.#..........#.......###....#..#.#########..#........#
#......#.###...#........##.#..........#..####.#.#...##################......###
####....#....#.#........#..#..........##.#..#.#######.........#...#..#......###
###.....#....#.#........####......######.#..#.##...##.#######.#...##.#......#.#
###.#.....######........#.........###..#.#..#.##...##.#.....#.#...#..#......#.#
###.#.....#....#........####......###..#.#..#.##...##.#.....#.#...#..#......#.#
###.#.....#....##########.........###..#.#..#.##...##.#.....#.#####..#..#####.#
###.#.....#.....#.###..#####......#.#..#.####.##...##.#..........##..######.#.#
###.#.....#.....#.............#...#.#..#......##...##............##..####.###.#
###.#.#.#.#.....###############...###################............##.......#...#
###.#.#.###.....#........#........###....######.....#.#######....##.#...#.#####
###.###.#.#######........############....#....#######............##.#####.#.###
###.....#.#######........############....#...######################.......#####
###############################################################################When seeing a layout like this, I can already imagine what I want the decorator script to do. The small dead-ends could hide valuable loot or perhaps monsters, and large intact rooms could be locked behind keys scattered elsewhere in the dungeon. In my opinion, the layout above is nearly perfect, but I wanted to do something about the generator’s tendency to build isolated rooms completely surrounded by the same corridor.
The Swiss-Army Room #
The problem of isolated rooms arises because the basic room-nesting function always generates a full surrounding corridor. I solved this by creating a new room function, the most complicated one so far. It’s similar to the nested room function above, but with two major changes:
- The outermost wall is only placed on inner room floor tiles, not the outer ones. In practice, this connects the corridors together instead of blocking them off with walls each time a new room is placed.
- Instead of having a fixed corridor width of 1 on each side, the inner-room margin is randomized for each side. Possible values are 0 (no corridor), 2 (regular 1-cell corridor) or 3 (2-cell wide corridor). These values are assigned different weights as well.
In order to implement this, the grid must keep track of three different tile types: Floor tiles, wall tiles and corridor tiles. The corridor tiles are placed by the outer room function, and floor tiles are placed by the inner room function. The script looks like this:
corridor_weights = [0] * 2 + [2] * 2 + [3] * 1
def nested_room(min_size: int, max_size: int, floor_tile: int = 0, wall_tile: int = 1, corridor_tile: int = 2):
left, right, up, down = (random.choice(corridor_weights) for i in range(4))
size_x = random.randint(min_size, max_size) + left + right + 2
size_y = random.randint(min_size, max_size) + up + down + 2
pos_x, pos_y = (random.randint(0, MAP_SIZE_X - size_x), random.randint(0, MAP_SIZE_Y - size_y))
# Walls surrounding corridor
for x in range(pos_x, pos_x + size_x):
for y in range(pos_y, pos_y + size_y):
if grid[y][x] != corridor_tile:
grid[y][x] = wall_tile
# Corridor surrounding room
for x in range(pos_x + 1, pos_x + size_x - 1):
for y in range(pos_y + 1, pos_y + size_y - 1):
grid[y][x] = corridor_tile
# Walls surrounding room
for x in range(pos_x + left, pos_x + size_x - right):
for y in range(pos_y + up, pos_y + size_y - down):
grid[y][x] = wall_tile
# Room
for x in range(pos_x + left + 1, pos_x + size_x - right - 1):
for y in range(pos_y + up + 1, pos_y + size_y - down - 1):
grid[y][x] = floor_tile
for i in range(500):
nested_room(3, 7)Even using only this room type I was very happy with the results:
###############################################################################
######...........############.##...###..#..##..........######.#....#.##########
#######.#######..##.........########....####...#######.....#..#....#.##########
##...#..#########...........##.#...#.......#...#.....#.....#..#....#...#.....##
##...#..#.......#....#####..##.#...#######.#####.....########.#....#.#.#.....##
######..#.......#....##..#..##.#...#....##.#...#.....#......#.#....#.#.########
#.......#.......#.....#..#..#..#...#....##.#...#.....#......#.#....#.#.#.....##
#.#####.#.......#.##..#..#.....#...#....########.....#......#.########.########
#.#...#.#.......#.....#..#.....#####....##.#..#############.#.##.....##.......#
#.#...#.#########.#####..#..###....#....####.....##.......###.#.........#####.#
#.#...#...........#..##..#..#.#....#....#..#.....##..######.............#...#.#
#.########.##..####..#####..#.#.####....#..#..####...#....#......#####..#...#.#
#.##.....#.##..#.....#...#..#.############.#..#####..#....############..#...#.#
#.##.....#.##..#.....#...#..#...#.##.............##..#....#.............#...#.#
#.##.....#.############..#..#...#.##..#####.....###..#....#.............#######
#..#.....#............#..#..#...#.##..#...#.###.###..#....#.#########...##.#..#
#..#######.##.#########..#..#...#.##..#...#.#.#.###..#....#.#.......#......#..#
#..........##.#.......#..#..#####.#...#...#.#.#.###..#....#.#.......#.#########
##...########.#######.#..#..#.....##..#...#.#.#.###########.####....#.#....#..#
##.##########.......###..#..########..#...#########...#........######.#....####
#..######..##########....#..########..#...##....##########............#....####
#..........###......#............###########....#.#......#.####..######....#.##
#..........###......###.########..........#######.###....#.#..#..#....######.##
#.......####.#......###.#......#............#####...#....#.#..#..#....#......##
#.#######.##.#......#...#......#.########...#...#####....#.#..#..#....#####..##
#.#....##.####......#...#......#.#......#...#...#...########..##.######...#..##
#.#....##.#..#########..#......#.#......#...#...#...###.#......###.#.#....#..##
#.#....####..........#..#......#.#......##..#####...###.########.#.#.#....#..##
#.#######...........##..#......#.#......##..#...#...#.#........#.#.#.#....#...#
#...#...##.#####.##.##..#......#.#......##..#...#####.###.######.#.#.#....#...#
###.#....#.#...#....##.#########.#########..........#..##.#......#.#.#....#...#
##########.#...#.#####.###..............#############..#..#......###.######...#
#####.#..#.#...#.#.#.#.....#####...............#.......#..#......#.#..........#
##########.#...#.#.#.####....#####.#########...###################....#.#######
###############################################################################I can’t complain about the runtime either. The above (Python!) code runs in ~45 ms on my 2017 ThinkPad.
Summary #
In conclusion, this method is an exciting development in the genre of roguelikes, with applications in dungeon generation, terrain variation and more—I really had you there, didn’t I? For starters, I don’t even know if I’m the first to use this technique, but I have never seen it mentioned elsewhere which surprises me considering its simplicity, efficiency and flexibility. Since I couldn’t find any information about the method online, I will hereby refer to it as the Superimposition method, which can be summarized as follows:
Create functions that randomly replace existing chunks of the map with either pre-defined or randomly generated structures, optionally taking the existing tiles into consideration, and assemble these functions into a generator script following some procedure.
As stated before, this algorithm just provides a rough layout for the dungeon but it’s very flexible in doing so. For example, it’s possible to overlay pre-defined room layouts, requiring only that they do not overlap with the other special rooms to preserve their interiors. Since these rooms are typically few in number, the generator is not likely to get stuck trying to place them (unlike when attempting to fill the entire map with rooms that cannot overlap!)
As a thank you for reading this far, behold the complete 79x79 dungeon from the thumbnail, generated by 500 iterations of the room-sometimes-with-corridor function. What a labyrinth. I must say, the roundness of the top-left corner does bother me quite a bit. As do the diagonally opposed corner walls. Ugh, I’ll fix that later.
