Python Dungeon Generator

I designed the python dungeon generator after finding that there weren’t many python procedural level generators that were generic enough for use in any game engine/rendering set up. Those that did exist either weren’t very documented or lacked in features. So this aims to rectify that.

The generator can create rooms, corridors, mazes and cave systems and any mix of them. It contains a number of tools for generating content, searching through it and path finding along with a number of helper functions to support its use. It’s largely based on ideas in this article with my own bits and bobs thrown in to generalise its usage.

The generator is designed to be as robust as possible. While this allows you to abuse the various functions to get the result you want it also means that if you feed it junk it’ll spit out junk. It places few restrictions on the order that you need to call generator functions and provides plenty of customisation options. It has few dependencies on other python libraries, using only python’s random library.

I’ll detail its usage and how give examples of the dungeons it could generate. It looks like a lot, but it’s mostly pictures and code examples. Understanding how the generator works helps you get the most out of it. But for those who want to just grab the module and get stuck in can skip to the resources section at the end.

Getting Started

It really is this simple:

import dungeonGenerator

dungeon = dungeonGenerator.dungeonGenerator(31, 31)

You create a new instance of the dungeonGenerator class and pass to it the x and y size of the level/map you want to create. The performance of the generator functions is largely dependent on the size of the level/map you specify. You can fine tune its performance by balancing your level size with the size of the tiles you’re using. So if you’re generating dungeons on the fly rather than when the level is being loaded using a smaller map size can be offset with a bigger tile size in the game.

At the core of the generator is the grid (dungeonGenerator.grid[x][y]). This is a 2D python list that stores tile information. The tiles stored as integers, with each number representing a type of tile. The dungeonGenerator module specifies a number of constants for this:

dungeonGenerator.EMPTY = 0
dungeonGenerator.FLOOR = 1
dungeonGenerator.CORRIDOR = 2
dungeonGenerator.DOOR = 3
dungeonGenerator.DEADEND = 4
dungeonGenerator.WALL = 5
dungeonGenerator.OBSTACLE = 6
dungeonGenerator.CAVE = 7

EMPTY, WALL and OBSTACLE are all considered impassable by the generator (for things like path finding), while all other types can be traversed. Of course, you can provide your own tile constant values by changing them. But remember, put junk in, get junk out. Generally, it’s better (read: safer) to let the generator do it’s grid manipulations then apply your own.

Generator Functions

Rooms

rooms can be randomly generated by

dungeonGenerator.placeRandomRooms(minSize, maxSize, stepSize = 1, margin = 1, attempts = 500)

The first 2 parameters control the lower and upper bounds of the rooms to generate, the other parameters have default values and allow for finer control of the random generation. Step size control the steps that the room size grow in (cannot be lower than 1). A value of one would produce the range 1, 2, 3, 4, 5 etc, while a value of 2 would produce 1, 3, 5, 7, 9 etc. So by specifying an odd minimum and maximum size along with a step size of 2 you can get rooms of only odd sizes (or similarly, even ones should you wish). This is useful as it allows you to create rooms that line up with other features in the generated level.

Margin controls the distance that the rooms must be a part. By default this is 1, but could be set to 0 to produce rooms that touch (thus creating more interesting room shapes). Setting the margin to 3 will ensure that a corridor can always be carved between rooms.

placeRandomRooms() takes a brute force approach to placing rooms. Imaging a fist smashing jigsaw pieces together until it finds two pieces that fit. The attempts paramter controls the amount of smashing that can be done. High attempt values will take longer put provide more dense rooms, while lower values will be quicker put place few rooms. If you’ve already filled a lot of the grid with corridors and caves then increasing attempts will increase the likelihood of a room being placed (as will reducing the dimensions and margin).

It is possible to deterministically place a room by calling:

dungeonGenerator.placeRoom(startX, startY, roomWidth, roomHeight, ignoreOverlap = False)

This function enables you to specify the starting position and the height and width of the room. The bool ignoreOverlap controls whether the room should be placed regardless of if it disrupts other tiles or not. This function is useful for ensuring that there is always a room you know the position of (like for placing a player. It could also be used to create a ‘bridge’ between generated dungeons.

Here’s some examples:

When a room is created a new instance of the class dungeonRoom is created, which is a container for the rooms starting X, Y positions and it’s height and width. This instance is stored in the list dungeonGenerator.rooms so that you can fetch and manipulate rooms later. The dungeonRoom class has the attributes dungeonRoom.x, dungeonRoom.y, dungeonRoom.height, dungeonRoom.width. Note, changing these won’t actually update dungeonGenerator.grid, you need to do that yourself.

Generally, better results are gained by placing rooms first then generating connecting corridors. However, more sparse layouts can be achieved by generating corridors first, culling them back then trying to place rooms (although a higher attempts value is probably needed).

Corridors and Mazes

Corridors and mazes are generated by calling:

dungeonGenerator.generateCorridors(mode = 'r', x = None, y = None):

x and y are starting points in the grid to begin generating a maze/corridor. If none is provided it’ll pick a point at random that’s not occupied by another tile. It is generated using the growing tree algorithm (based on this article) and allows you to specify how the next tile to branch out to is chosen. This is determined by the parameter mode, and through this you can control the ‘look’ of the generated maze/corridor. There are 4 possible modes:

‘r’ – random cell, produces short, straight sections with lots of ‘spine’ like offshoots
‘l’ – last cell added, produces windy, meandering mazes/corridors
‘m’ – middle cell, favours straight lines with spines towards the ends
‘f’ – first cell in the list, produces straight lines with no offshoots

The tiles generated by this function are added to dungeonGenerator.corridors, which is a list holding the X, and Y grid positions of all the corridor tiles generated. This is useful for finding dead ends and processing corridors separately later.

The image below shows the 4 different patterns on their own, with rooms and with dead ends culled:

The generator’s rules prevent it from creating diagonal sections or a corridor/maze coming within 1 tile of any other tile. It comes to an end once it’s ran out of tiles to explore. This means it is possible to have regions of a map that do not contain any corridors. These regions tend to occur with small room margins (less than 3), even-numbered room sizes, mixing in caves and manually placed rooms that cut off sections. To work around this, you can keep calling generateCorridors() until there are no remaining empty spaces, using the convenient findEmptySpace(distance) function:

from dungeonGenerator import dungeonGenerator

dm = dungeonGenerator(91, 91)

dm.placeRoom(41, 0, 10, 91, True)
dm.placeRoom(0, 41, 91, 10, True)
dm.placeRandomRooms(7, 9, 2, 1, 1000)

x, y = dm.findEmptySpace(3)
while x:
    dm.generateCorridors('f', x, y)
    x, y = dm.findEmptySpace(3)

dungeonGenerator.findEmptySpace() returns the x and y co-ordinates of the first empty space in the grid it finds. The distance value is how far the space has to be away from anything to be considered empty, this value cannot be lower than 1. If it cannot find any empty spaces it will return (None, None).

Caves

More organic shapes, or cave-like structures can be created by calling the cave generator (based on this):

dungeonGenerator.generateCaves(p = 45, smoothing = 4):

p is the probability of an empty tile becoming a cave tile. Values over 45 tend to produce one large cavern, while values below 35 create small islands of cave. Lower values of smoothing will create more jagged looking sections, while increasing creates rounder sections, values greater than 4 have little effect.

The cave generator can be used in conjunction with rooms and corridors. But some care needs to be taken. Generally, its best to form cave sections first, with a p value of around 30-40 then generate the rooms and corridors, which gives isolated cave sections you can join up to the corridors:

But you can do it the over way round. This way gives you cave sections that spill into the rooms and corridors:

However, you’ll need to join up the rooms and corridors first and then prune the dead ends (see next section), otherwise the grid will largely be made up of corridors and there will be no space for caves to form.

Alternatively, the cave generator function can be used entirely on its own to create a cave level. Or any combination that takes your fancy!

Joining it all together

Once you’ve got your rooms, corridors and caves sorted its time to join things together. We’ll start with the simple case of joining rooms and corridors. Simply call:

dungeonGenerator.connectAllRooms(extraDoorChance)

Which will connect each room to a corridor, cave section or another room with a door tile (the orange ones in the example images). The parameter extraDoorChance controls the likelihood of a room having more than one door (all rooms are guaranteed to have one door).

This method pretty much guarantees all rooms are joined to the corridors/other rooms so long as your rooms are well-spaced (a margin of 3 or more will suffice). All generated door tiles are added to the list dungeonGenerator.doors and stores the X and Y locations on the grid as a tuple, in case you want to cycle through the doors later.

If you’ve got a tight room spacing but lots of placed corridors chances are reasonably good the whole thing will be connected. But sometimes this will not be the case. Also the above method will not connect cave sections to each other. In these instances we need to find the unconnected areas and force a connection. For instance:

can be fixed with:

import dungeonGenerator

dm = dungeonGenerator.dungeonGenerator(91, 91)

dm.placeRandomRooms(5, 15, 1, 1, 3000)
dm.generateCorridors('l')
dm.connectAllRooms(0)
dm.pruneDeadends(50)

#join unconnected areas
unconnected = dm.findUnconnectedAreas()
dm.joinUnconnectedAreas(unconnected)

Producing:

dungeonGenerator.findUnconnectedAreas() returns a list of lists of tiles that are disconnected. dungeonGenerator.joinUnconnectedAreas(unconnectedAreas) takes that list and joins them.

This is a brute force approach to connecting parts of the level together. It’s looks for the shortest possible straight connection between areas and carves a path between them. It doesn’t add the connections to dungeonGenerator.doors since it doesn’t generate any door tiles, but the corridors it adds will be appended to dungeonGenerator.corridors. It won’t always produce the most attractive of results, but the majority of the time you’ll be fine. If you just wanted straight connections between rooms/caves then you could skip calling generateCorridors() and connectAllRooms() and use findUnconnectedAreas() and joinUnconnectedAreas().

Another approach is to find disconnected areas and then remove them. This is particularly handy for cleaning up small islands created by the cave generator:

import dungeonGenerator

dm = dungeonGenerator.dungeonGenerator(91, 91)
dm.generateCaves(40, 4)
unconnected = dm.findUnconnectedAreas()
for area in unconnected:
    if len(area) < 35:
        for x, y in area:
            dm.grid[x][y] = dungeonGenerator.EMPTY

It’s worth noting that after this operation you need to call dungeonGenerator.findUnconnectedAreas() again since you will need to update the list of disconnected areas. This approach leaves more room to place rooms, corridors and connect the whole thing together:

import dungeonGenerator

dm = dungeonGenerator.dungeonGenerator(91, 91)
dm.generateCaves(40, 4)
# clear away small islands
unconnected = dm.findUnconnectedAreas()
for area in unconnected:
    if len(area) < 35:
        for x, y in area:
            dm.grid[x][y] = EMPTY
# generate rooms and corridors
dm.placeRandomRooms(5, 9, 1, 1, 2000)
x, y = dm.findEmptySpace(3)
while x:
    dm.generateCorridors('l', x, y)
    x, y = dm.findEmptySpace(3)
# join it all together
dm.connectAllRooms(0)
unconnected = dm.findUnconnectedAreas()
dm.joinUnconnectedAreas(unconnected)
dm.pruneDeadends(70)

Finally, a level with lots of dead ends wouldn’t be much fun to explore, so the generator provides functions for dealing with this:

dungeonGenerator.pruneDeadends(amount)

It takes the amount of pruning iterations to do. Each iteration it removes all the current dead ends in the level. In removing one dead end the tile that was touching it becomes a dead end, which would then be removed in the next iteration and so forth. This function also updates dungeonGenerator.deadends – a list containing the X,Y positions of all the dead ends.

It works on the rule that a corridor tile that only touches one other tile must be a dead end. So calling it before dungeonGenerator.connectAllRooms() cull corridors surrounding rooms potentially leaving disconnected areas (see above on how to handle this). But is a useful way to to clear back corridors to make space for rooms if you wanted to generate corridors first and then rooms:

import dungeonGenerator
# generate level
dm = dungeonGenerator.dungeonGenerator(91, 91)

dm.generateCorridors()
dm.pruneDeadends(30)
dm.placeRandomRooms(9, 12, 1, 1, 2000)
dm.connectAllRooms(30)
unconnected = dm.findUnconnectedAreas()
dm.joinUnconnectedAreas(unconnected)

It also possible to clear all the dead ends in a level:

import dungeonGenerator
# generate level
dm = dungeonGenerator.dungeonGenerator(51, 51)
dm.placeRandomRooms(5, 13, 2, 3, 1000)
dm.generateCorridors('l')
dm.connectAllRooms(30)

#clear all dead ends
dm.findDeadends()
while dm.deadends:
    dm.pruneDeadends(1)

The method dungeonGenerator.findDeadends() searches through all the corridors and stores all the found dead ends in dungeonGenerator.deadends. This is handy if you wanted to place some treasure in the dead ends for the player to find.

Helper functions and everything else

dungeonGenerator comes with a whole host of helper functions. Most of these are used internally, but there are a few you might want to use (we’ve already covered quite a few).

dungeonGenerator.findNeighbours(x, y)
dungeonGenerator.findNeighboursDirect(x, y)

Both are generator functions that allow you to iterate over all of a tiles neighbours (findNeighbours) or just the north, south, east and west neighbours (findNeighboursDirect). They both take an X and Y grid co-ordinate to search from.

for nx, ny, in dm.findNeighbours(x, y):
    dm.grid[nx][ny] ... do something with them

For quickly replacing tiles you can use the flood fill function, which fills all directly connected tiles:

dungeonGenerator.floodFill(x, y, fillWith, tilesToFill = [], grid = None):

It takes the X and Y grid co-ordinates to start filling from and the tile constant to fill with. If the tile constant is the same as the tile you’re trying to fill then it wont work (since it’s already Filled!).

import dungeonGenerator

dm = dungeonGenerator.dungeonGenerator(51, 51)
dm.generateCorridors()

x, y = dm.corridors[0]
dm.floodFill(x, y, dungeonGenerator.CORRIDORS) # will not work
dm.floodFill(x, y, dungeonGenerator.FLOOR) # will work

floodFill also has 2 optional parameters. The first is tilesToFile, where you can pass a list of the tile constants you want to filled. If this is omitted or None then all connected tiles will be filled. So if you wanted the flood fill to only affect corridor and door tiles:

import dungeonGenerator

myNewTileConstant = 8

dm = dungeonGenerator.dungeonGenerator(51, 51)
dm.placeRandomRooms(5, 9, 2, 3, 500)
dm.connectAllRooms(20)
dm.generateCorridors()

x, y = dm.corridors[0]
dm.floodFill(x, y, myNewTileConstant [dungeonGenerator.CORRIDOR, dungeonGenerator.DOOR])

The second is grid. By default, the flood fill directly manipulates dungeonGenerator.grid but there are times when this is not helpful. For instance, findUnconnectedAreas() uses flood fill to find distinct areas, but if it changed the grid then the tile layout would be wrong. So you can pass it your own 2D list to use, such as a deep copy of dungeonGenerator.grid.

dungeonGenerator also provides a function for wrapping all the generated tiles with wall tiles:

dungeonGenerator.placeWalls()

Generally it makes sense to call this last, since no other function can traverse a wall tile leaving parts disconnected. However, combined with floodFill it can be abused to widen paths:

import dungeonGenerator

dm = dungeonGenerator.dungeonGenerator(91, 91)
dm.generateCorridors()
dm.pruneDeadends(20)

dm.placeWalls()
x, y = dm.corridors[1]
dm.floodFill(x, y, CORRIDOR)

dm.placeRandomRooms(4, 9, 1, 1, 3000)
dm.connectAllRooms(30)
unconnected = dm.findUnconnectedAreas()
dm.joinUnconnectedAreas(unconnected)

Finally, we have the path finding functions.

dungeonGenerator.constructNavGraph()
dungeonGenerator.findPath(startX, startY, endX, endY)

Before you can find a path a navigation graph needs to be constructed by calling constructNavGraph, which catalogues how the tiles link together. If you make any changes to the level you will need to re-construct the navigation graph by calling this function again.

Then you can find a path between two points on the dungeonGenerator.grid using findPath() and passing the start X,Y and end X,Y co-ordinates. This function returns a list of X,Y tuples forming a path between the two points. It’s important to note that all co-ordinates are dungeonGenerator.grid co-ordinates. Therefore in game applications you’ll need to convert your game world co-ordinates into grid co-ordinates and vice-versa. This is easily accomplished by using integer division:

startX = objectGameWorldXPos // gameTileSize
startX = objectGameWorldYPos // gameTileSize

This isn’t entirely accurate though. How you choose to round the game object’s world position prior to division will affect which grid tile the object is considered to be on. This will produce better results:

def roundNearestInt(i, base = 2):
    """Returns nearest multiple of base"""
    return int(base * round(i/base))

startX = roundNearestInt(objectGameWorldXPos) // gameTileSize
startX = roundNearestInt(objectGameWorldYPos) // gameTileSize

Converting tile grid co-ordinates to game world co-ordinates is as simple as multiplying the co-ordinates by the game tile size

Rendering the map

In order to be able to see you’re generated level you need a way to render it out. The dungeonGenerator is renderer independent. It’s as simple as iterating over dungeonGenerator.grid and then calling what ever engine/set up specific rendering code you’re using. Then all you have to do is multiply the tiles x,y co-ordinates in the grid by the tile size in the game world to get the objects position in the game world.

There are two ways to do this. The first is looping over dungeonGenerator.grid:

for x in range(dungeonGenerator.width):
    for y in range(dungeonGenerator.height):
        if dungeonGenerator.grid[x][y] == dungeonGenerator.FLOOR:
            render(floorTile)
            floorTile.xPosition = x * tileSize
            floorTile.yPosition = y * tileSize
        and so forth...

Alternatively, the dungeonGenerator class is designed to be iterated over, returning the current tiles x,y positions in the grid and it’s value:

for x, y, tile in dungeonGenerator:
    if tile == dungeonGenerator.FLOOR:
        render(floorTile)
        floorTile.xPosition = x * tileSize
        floorTile.yPosition = y * tileSize
    and so forth...

In pygame it might look something like this:

import pygame
import dungeonGenerator

tileSize = 16
levelSize = 51

screen = pygame.display.set_mode((levelSize * tileSize, levelSize * tileSize))
spriteSheet = pygame.image.load('testSprites.png').convert()

floorRect = pygame.Rect(0, 0, tileSize, tileSize)
floorTile = spriteSheet.subsurface(floorRect)

wallRect = pygame.Rect(tileSize*3, 0, tileSize, tileSize)
wallTile = spriteSheet.subsurface(wallRect)

facingWallRect = pygame.Rect(tileSize*2, 0, tileSize, tileSize)
facingWallTile = spriteSheet.subsurface(facingWallRect)

boxRect = pygame.Rect(tileSize*1, 0, tileSize, tileSize)
boxTile = spriteSheet.subsurface(boxRect)

doorRect = pygame.Rect(tileSize*4, 0, tileSize, tileSize)
doorTile = spriteSheet.subsurface(doorRect)

doorSideRect = pygame.Rect(tileSize*5, 0, tileSize, tileSize)
doorSideTile = spriteSheet.subsurface(doorSideRect)

d = dungeonGenerator.dungeonGenerator(levelSize, levelSize)
d.placeRandomRooms(5, 11, 2, 4, 500)
d.generateCorridors()
d.connectAllRooms(30)
d.pruneDeadends(20)
d.placeWalls()

for x, y, tile in d:
    if tile == dungeonGenerator.FLOOR:
        screen.blit(floorTile, (x*tileSize, y*tileSize))
    elif tile == dungeonGenerator.CORRIDOR:
        screen.blit(floorTile, (x*tileSize, y*tileSize))
    elif tile == dungeonGenerator.DOOR:
        # rotate the door tile accordingly
        # no need to check bounds since a door tile will never be against the edge
        if d.grid[x+1][y] == dungeonGenerator.WALL:
            screen.blit(doorTile, (x*tileSize, y*tileSize))
        else:
            screen.blit(doorSideTile, (x*tileSize, y*tileSize))
    elif tile == dungeonGenerator.WALL:
        # if the wall tile is facing us lets render a different one
        if y == levelSize-1 or d.grid[x][y+1] != dungeonGenerator.WALL:
            screen.blit(facingWallTile, (x*tileSize, y*tileSize))
        else:
            screen.blit(wallTile, (x*tileSize, y*tileSize))

for de in d.deadends:
    screen.blit(boxTile, (de[0] * tileSize, de[1] * tileSize))

pygame.display.flip()

In Blender it’s even less lines:

import dungeonGenerator
import bge
from random import choice

scene = bge.logic.getCurrentScene()
spacing = 4

d = dungeonGenerator.dungeonGenerator(51, 51)
d.placeRoom(1, 1, 3, 3)
d.placeRandomRooms(3, 11, 2, 3, 500)
d.generateCorridors('f')
d.connectAllRooms(40)
d.pruneDeadends(30)
d.placeWalls()

for x, y, c in d:
    if c == dungeonGenerator.FLOOR:
        ob = scene.addObject(choice(['Floor2', 'Floor3']))
        ob.worldPosition.y = y * spacing
        ob.worldPosition.x = x * spacing
        ob.worldOrientation = [0, 0, choice([0, 1.5708, 3.1415, -1.5708])]
    elif c == dungeonGenerator.CORRIDOR:
        ob = scene.addObject('Floor')
        ob.worldPosition.y = y * spacing
        ob.worldPosition.x = x * spacing
    elif c == dungeonGenerator.DOOR:
        ob = scene.addObject('Door')
        ob.worldPosition.y = y * spacing
        ob.worldPosition.x = x * spacing
    elif c == dungeonGenerator.WALL:
        ob = scene.addObject('Wall1')
        ob.worldPosition.y = y * spacing
        ob.worldPosition.x = x * spacing
        ob.worldOrientation = [0, 0, choice([0, 1.5708, 3.1415, -1.5708])]

Final Words

It’s not the fastest generator in the world but I think it’s got a high enough level of customisation and flexibility to make up for it. This gives it plenty of scope to be used in different projects. For instance, you could use placeRandomRooms() for generating cities/towns instead of typical room-corridor maps. Or perhaps use it to procedurally generate interiors for buildings.

It is possible to rewrite some of the methods using more python libraries, like itertools and collections, which would probably improve some of the implementations and performance. But would mean extra things to include in any games distributed with it.

For more complex tile map arrangements, like tile render culling for example, then it is probably better to define your own tile class. Implementing this is fairly straightforward and require few modifcations to the module. Just replace all self.grid[x][y] = CONSTANT references with self.grid[x][y] = myTileClass(params). So long as your tile class provides it’s own comparators (specifically __eq__ and __ne__)  everything should work as expected.

As always, leave your feedback in the comments and share some of the levels you’ve made with this.

Resources

dungeonGenerator.py original

dungeonGenerator.py none-square dungeons fix

Blender example file – note, the dungeon generator works well in the BGE, but the generator was not built specifically for the BGE. So mixing in blender specific python with the generation code wont work.

There’s more examples and discussion on using the generator in blender on this BA thread.

~ by Jay on January 15, 2016.