Dungeon Generation

[roddy]

One of the most interesting aspects of the old "Roguelike" games are their dungeon building algorithms. Every time you descend into the depths of the dark cave or the gloomy catacombs, you're faced with a new, automatically generated setting. There are rooms of treasure, long corridors filled with traps, hidden rooms, and so forth.

Dungeon generation, I would hazard to say, is one of the most fascinating problems in computer science, not only because of how common it is in game development, but because of the sheer scope of the problem. It is, at its heart, a purely decision-based situation. Should this tile be a wall or a floor? Are all the rooms connected? No? How do I connect them? Where should I put the door? Where do I put the traps?

There are many different algorithms out there that focus on this problem. Some are rooted in cellular biology and artificial life that create some very cool looking cave-like structures with irregularly shaped rooms. Others produce honest-to-god mazes and labyrinths of winding corridors and few open spaces.

Today we are going to focus on a very simple dungeon generation program that will build the dungeon itself, but not place anything in it. Doors, traps, stairs, monsters, and treasures will not fall within the scope of this program. Even the dungeon itself will be rather simplistic: it will consist of square or rectangular rooms, and corridors.

Java Code

Before we begin, we need to consider some constraints for our dungeon, namely: dimensions. We need to decide on the maximum and minimum dimensions of our dungeon. I've decided to limit my dungeon to being at most 50x50, and at minimum 10x10.
private static final int MAX_X = 50;
private static final int MAX_Y = 50;
private static final int MIN_X = 10;
private static final int MIN_Y = 10;
There are two other constraints we need to consider: minimum corridor and room sizes. Corridors that are two spaces long are rather useless, as is a 1x1 room. So we need to define some more constants:
private static final int MIN_CORRIDOR_LENGTH = 3;
private static final int MIN_ROOM_LENGTH = 3;
Now we are almost ready to start coding the Dungeon. First, however, we need to do a little set-up regarding terrain.

Roguelikes are rather known for their text-based interfaces, with the little @ symbol representing the character, a fullstop (.) representing a floor or other "walkable" area, and a pound (#) representing a wall. There are plenty of other characters out there, most of which are superfluous at this time.

In order to keep track of what terrain is where, we are going to define an enum. We could, in all truth, actually do this by defining two int constants (FLOOR = 0, WALL = 1) or even two boolean constants, but I've chosen to use an enum for future expansion. What if I wanted to add stone walls, or wooden floors? My enum will include two types of wall, for the sake of argument.
package castle.dungeon;

public enum Terrain {
    DIRT("."),
    DIRT_WALL("#"),
    STONE_WALL("#");

    private String symbol = null;
    private Terrain(String symbol) {
        this.symbol = symbol;
    }
    @Override public String toString() {
        return this.symbol;
    }
    public boolean isWall() {
        return (this.equals(Terrain.DIRT_WALL)) ||
        (this.equals(Terrain.STONE_WALL));
    }
}

The reason that Terrain includes the isWall() method is so that I can query an unknown Terrain and ask it, are you a wall, or can I walk on you? Theoretically it would be better to have an isUnwalkable() method instead, but currently our only unwalkable terrains are walls, so it will do.

Now we're ready to begin the actual Dungeon class. We we include two constructors: a default that will create a Dungeon at the maximum dimensions, and one that takes a length and a width for custom dimensions. The constructors will need to check the provided dimensions against the maximum/minimum constraints we defined previously.

Additionally, we will need the constructors to initialize a two-dimensional Terrain array, which will keep track of what Terrain is at what position. The array will be initialized to Terrain.DIRT_WALL.
private int x, y;
private Terrain[][] dungeonMap;

public Dungeon() {
    this(MAX_X, MAX_Y);
}

public Dungeon(int x, int y) {
    x = (x > MAX_X || x < MIN_X) ? MAX_X : x;
    y = (y > MAX_Y || y < MIN_Y) ? MAX_Y : y;
    init(x, y);
}

private void init(int x, int y) {
    this.x = x;
    this.y = y;
    dungeonMap = new Terrain[this.x][this.y];

    for (int i = 0; i < dungeonMap.length; i++) {
        for (int j = 0; j < dungeonMap[i].length; j++) {
            dungeonMap[i][j] = DIRT_WALL;
        }
    }
}

The next thing we'll need to do is write our build() method to do the actual dungeon building. But before we can do that, we need to think a little bit about what exactly our algorithm is going to do, how it's going to do it, and how it's going to know when to stop.

Building dungeons

It would be very simple to write two methods called buildRoom and buildCorridor, feed them the appropriate variables, and say go. Build me a dungeon.

But how will the program know where to build the room or the corridor? How will it decide the dimensions of the room, or the length of the corridor? How will it know whether it should build a room, or build a corridor?

And, most importantly, how will it know when to stop?

Busyness

I started with this last question and decided to define a property called "busyness." Not business, like a company, but busyness, like "how busy is this map so far?"

I defined busyness to be a ratio of "walkable" tiles (ie: floor) to "unwalkable" tiles (ie: walls). So if I have a 10x10 map with a 5x5 room, I have 25 walkable tiles to 100 unwalkable tiles, or a busyness of 0.25.

In order for this approach to work, we need to determine a minimum acceptable busyness threshold. Then the algorithm will keep creating rooms and corridors until that threshold is met or exceeded.

For my algorithm, I determined that 0.55 was a good minimum threshold. You may wish to set yours higher for maps with more rooms/corridors, or lower for fewer.

You should note that a busyness threshold of 1.0 is 100% walkable; that is, a map with no walls. Likewise, a busyness threshold of 0.0 represents a map with no floors and 100% walls. Busyness should probably range between 0.3 and 0.7.

private static final double BUSYNESS_THRESHOLD = 0.55;
private double busyness;

private void evaluateBusyness() {
    int walkable = 0;
    int unwalkable = 0;
    for (int row = 0; row < dungeonMap.length; row++) {
        for (int col = 0; col < dungeonMap[row].length;
        col++) {
            if (dungeonMap[row][col].isWall()) {
                unwalkable++;
            } else {
                walkable++;
            }
        }
    }
    busyness = (1.0*walkable) / unwalkable;
}

The evaluateBusyness() method will need to be called every time something new (whether a corridor or a room) is drawn on the map.

Building corridors

In our dungeon, a corridor is simply a long, straight walkable path that is exactly one tile wide. It can go in any direction, including diagonally. But because I'm not a big fan of the road to nowhere (the concept, not the song), we need to make sure that the corridor starts from a place that is already walkable.

Our buildCorridor method, therefore, will need to take a number of parameters:

• x and y, the coordinates of the initial tile


• the length of the corridor


• the direction to build the corridor

Of course, the first thing we'll need to do is check constraints, making sure that x and y are valid coordinates for our specific dungeon, and then the provided length is not less than our specified minimum length.

But what if the provided length is too long? We have three options:

1. Abort. Exit the buildCorridor method and let the algorithm try building something else.


2. Use the minimum. Replace the target length with the default minimum length we defined previously.


3. The longest possible. Build the longest possible corridor that still meets all acceptable criteria, even it if never quite makes the target length.

For the sake of keeping the algorithm from running quite so long, I've decided to go with the third option.

The final criteria is direction, which I have chosen to model using two ints: directionX and directionY. Each of these variables should be able to have the value of -1, 0, or 1. A corridor going straight up would have directionX=0 and directionY=-1. A corridor going straight left would have directionX=-1 and directionY=0. A corridor going diagonally down and to the right would be directionX=1 and directionY=1.

We now have enough to start building our method.
private void buildCorridor (final int x, final int y, final int directionX, final int directionY, int length) {
First we need to check that our initial coordinates are valid.
if (x <= 0 || y <= 0 || x >= MAX_X || y >= MAX_Y) {
    return;
}
We also need to make sure that the provided length is at least the minimum length, that the initial tile (x,y) is "walkable" (see discussion above about roads to nowhere), and that the direction is valid.
if (length < MIN_CORRIDOR_LENGTH) {
    return;
}
if (dungeonMap[x][y].isWall()) {
    return;
}
if (directionX == 0 && directionY == 0) {
    return;
}
if (directionX > 2 || directionX < -2 || directionY > 2 || directionY < -2) {
    return;
}
Yes, it is possible to combine all of these if-statements into a single big "check if everything is ok"-type conditional, but this sort of separation of purposes makes it easier to debug.

Now that we know that our initial position is valid, and that our proposed direction and lengths are acceptable, we can start mapping out the potential path of our corridor.

First, we need to determine that the minimum-length corridor can be placed with these defined parameters. At the same time, we need to determine that this corridor has not already been build -- that is: other than the initial (x,y) tile, and possibly the last tile, are all of the remaining tiles "unwalkable?"

To do this, I've defined two "helper" variables, positionX and positionY which are merely references to the tile currently being checked at any given point in time.
int positionX = x;
int positionY = y;
for (int i = 0; i < MIN_CORRIDOR_LENGTH; i++) {
    positionX += directionX;
    positionY += directionY;
    if (positionX <= 0 || positionX >= MAX_X || positionY <= 0 || positionY >= MAX_Y) {
        return;
    } else if (!dungeonMap[positionX][positionY].isWall()) {
        return;
    }
}
Now that we know that we can, at the least, place the minimum-length corridor, we should check to see if we can place the full-length corridor. At the same time, should we find that we cannot place the full-length corridor, we need to save the actual maximum length corridor that we can place.
int actualLength = length;
for (int i = MIN_CORRIDOR_LENGTH; i < length; i++) {
    positionX += directionX;
    positionY += directionY;
    if (positionX <= 0 || positionX >= MAX_X || positionY <= 0 || positionY >= MAX_Y) {
        actualLength = i-1;
        i = length;
    }
}
So now that actualLength is storing the potential maximum length of our corridor, lets go back over it and make sure that it's all currently "unwalkable," except, potentially, the final tile.
positionX = x;
positionY = y;
for (int i = 0; i < actualLength-1; i++) {
    positionX += directionX;
    positionY += directionY;
    if (!dungeonMap[positionX][positionY].isWall()) {
        actualLength = i;
    }
}
Now we know exactly the length of the corridor we can build. So let's go ahead and build it.
positionX = x;
positionY = y;
for (int i = 0; i <= actualLength; i++) {
    dungeonMap[positionX][positionY] = Terrain.DIRT;
    positionX += directionX;
    positionY += directionY;
}

Building rooms

Building rooms is rather much simpler than building corridors. Instead of having to worry about minimum, maximum, and actual lengths, all we need to worry about is our starting coordinates (x,y), and the width and height of the room. When it comes to building rooms, the position (x,y) refers to the tile at the top-left of the room.

The first thing we need to do is check our constraints. x and y must be valid, and both width and length must be longer than the MIN_ROOM_LENGTH constant. Additionally, the sum of x+width must not exceed this.x, which is the actually width of the overall dungeon. (That is, the room cannot extend past the boundaries of the dungeon itself.)
if (x <= 0 || y <= 0 || width < MIN_ROOM_LENGTH || height < MIN_ROOM_LENGTH || (x + width >= this.x) || (y + height >= this.y)) {
    return;
}
Now we need to check that every potential room tile is currently "unwalkable" (that is, a wall.) However, since we want to allow entrances and exits from a room, we are not going to check the outermost tiles.
for (int row = x+1; row < x+width; row++) {
    for (int col = y+1; col < y + height; col++) {
        if (!dungeonMap[row][col].isWall()) {
            return;
        }
    }
}
Since we don't check the outermost tiles of the potential room, we're running the risk of having two rooms overlap into a sort of massive room. For that reason, we're going to go back and count how many spaces do overlap. This way, we can set a constraint and say, "OK, you're allowed some entrances, but no more than 4." If there is an overlap of any kind, it will be of a maximum of 4 spaces.
int entranceCount = 0;
for (int row = x; row <= x+width; row++) {
    for (int col = y; col <= y+height; col++) {
        if (!dungeonMap[row][col].isWall()) {
            entranceCount++;
        }
    }
}
if (entranceCount > 4) {
    return;
}
Now we have determined that this is an adequate place for a new room, so let's build it.
for (int row = x; row <= x+width; row++) {
    for (int col = y; col <= y+height; col++) {
        if (dungeonMap[row][col].isWall()) {
            dungeonMap[row][col] = Terrain.DIRT;
        }
    }
}

Choosing what to build

So we've got two methods to build corridors and rooms, and a while-loop that runs as follows:
while(busyness < BUSYNESS_THRESHOLD) {
    build();
    evaluateBusyness();
}
But what exactly is build(), and how does it determine what exactly it should be building, and where? You've probably already guessed that build() is the method that calls the buildCorridor and buildRoom methods.

Since we want this to be somewhat random -- that is, every time we create a Dungeon we want a different layout -- we're going to use the random number generator provided in java.util.Random. Random has three useful methods that we're going to make use of: nextInt(), nextInt(n), and nextDouble(). I've instantiated an instance of Random within the init method:
private Random r;
private void init() {
    // ...
    r = new Random();
    // ...
}
The first thing the build method will need to determine is: what tile are we going to use as our starting point for whatever-it-is that we're building.
int x = r.nextInt(this.x);
int y = r.nextInt(this.y);
This will choose a random number between 0, inclusive, and this.x (or this.y), exclusive. Recall that this.x and this.y refer to the actually dimensions of the overall dungeon.

Next we need to decide whether to build a corridor or a room. This could be done in many ways, depending on whether we want equal chances for corridors and rooms to be build, or weighted chances, or whatnot. Consider, however, that if you decide you want to build corridors 75% of the time and rooms the remaining 25%, you will not actually end up with 75% corridors. This is because of the numerous "failure" states available for the buildRoom and buildCorridor methods.

I've decided that the way I'm going to go about choosing is to choose a number between 0 and 2. If the number is 0, I will build a corridor. If the number is 1 or 2, I will build a room. (This is roughly equivalent to a 33% chance for corridors, 66% chance for rooms. Rooms have a lot of ways they can go wrong, so...)
int pick = r.nextInt(3);
switch(pick) {
    case 0:
        // corridor
        break;
    default:
        // room
        break;
}
Let's say we rolled a 0, so we're building a corridor. The buildCorridor takes five variables: the (x,y) coordinates of the initial tile, the x- and y-directions, and the target length.

We already know x and y, so let's move on to directionX and directionY. You may (or may not) recall that these should range from -1 to 1. So let's fire up the old random number generator, call nextInt(3) and subtract 1. Of course, we don't want directionX = directionY = 0; this would mean that there is no direction, and therefore no movement. So, a quick trap to recalculate should that be the case:
int directionX, directionY;
do {
    int directionX = r.nextInt(3) - 1; // -1 -> 1
    int directionY = r.nextInt(3) - 1; // -1 -> 1
} while (directionX == 0 && directionY == 0);
Now to calculate length. This one's a bit tricky, because we'll need to give the random number generator a constraint. The question is: which one? A corridor that runs the full length of the map is cool, as is one that runs the full width, or the full diagonal. But those lengths might be all different sizes. I made a design decision here and decided to have the maximum length be the longest dimension -- length or width.
int length = r.nextInt(this.x > this.y ? this.x : this.y);
This is enough information to be able to call buildCorridor:
buildCorridor(x, y, directionX, directionY, length);
Now the other option: building a room. Rooms are much simpler than corridors since we only need two random numbers: width and height. (If we had shapes other than rectangular rooms, we'd need to pick that too here; but we don't.)
int width = r.nextInt(this.x/2);
int height = r.nextInt(this.y/2);
buildRoom(x,y,width,height);
Note that since we trap for directionX = directionY = 0 within the build method, in addition to not allowing directionX or directionY to have any values other than -1, 0, or 1, that we can now remove one of the failure states from the buildCorridor method, which will save us some calculation time.

Final code


/* This work is licensed under the Creative Commons
 * Attribution 3.0 Unported License. To view a copy of this
 * license, visit http://creativecommons.org/licenses/by/3.0/
 * or send a letter to Creative Commons, 171 Second Street,
 * Suite 300, San Francisco, California, 94105, USA.
*/
package castle.dungeon;
import java.util.Random;

/**
 * A simple dungeon generation class. (6 July 2010)
 * @author Roddy of the Frozen Peas
 * (roddyofthefrozenpeas@gmail.com)
 **/
public class Dungeon {
    public static void main(String[] args) {
        Dungeon x = new Dungeon();
        System.out.println(x);
    }
    
    private static final int MAX_X = 50;
    private static final int MAX_Y = 50;
    private static final int MIN_X = 10;
    private static final int MIN_Y = 10;
    private static final int MIN_CORRIDOR_LENGTH = 3;
    private static final int MIN_ROOM_LENGTH = 3;
    private static final double BUSYNESS_THRESHOLD = 0.55;
    
    private double busyness;
    private int x;
    private int y;
    
    private Terrain[][] dungeonMap;
    private Random r;
    
    public Dungeon() {
        init(MAX_X, MAX_Y);
    }
    public Dungeon(int x, int yl) {
        x = (x <= MAX_X && x >= MIN_X) ? x : MAX_X;
        y = (y <= MAX_Y && y >= MIN_Y) ? y : MAX_Y;
        init(x, y);
    }
    private void init(int x, int y) {
        this.x = x;
        this.y = y;
        dungeonMap = new Terrain[this.x][this.y];
        for (int i = 0; i < this.x; i++) {
            for (int j = 0; j < this.y; j++) {
                dungeonMap[i][j] = Terrain.DIRT_WALL;
            }
        }
        r = new Random();
        busyness = 0.0;
        while (busyness < BUSYNESS_THRESHOLD) {
            build();
            evaluateBusyness();
        }
    }
    private void build() {
        int x = r.nextInt(this.x);
        int y = r.nextInt(this.y);
        switch(r.nextInt(3)) {
            case 0: // corridor
                int directionX, directionY;
                do {
                    directionX = r.nextInt(3) - 1; // -1 -> 1
                    directionY = r.nextInt(3) - 1; // -1 -> 1
                } while (directionX == 0 && directionY == 0);
                int length = r.nextInt(this.x > this.y ?
                this.x : this.y);
                buildCorridor(x, y, directionX, directionY,
                length);
                break;
            default: // room
                int width = r.nextInt(this.x/2);
                int height = r.nextInt(this.y/2);
                buildRoom(x,y,width);
                break;
        }
    }
    private void evaluateBusyness() {
        int walkable = 0;
        int unwalkable = 0;
        for (int row = 0; row < dungeonMap.length; row++) {
            for (int col = 0; col < dungeonMap[row].length;
            col++) {
                if (dungeonMap[row][col].isWall()) {
                    unwalkable++;
                } else {
                    walkable++;
                }
            }
        }
        busyness = (1.0*walkable) / unwalkable;
    }
    private void buildCorridor (final int x, final int y,
    final int directionX, final int directionY, int length) {
        if (x <= 0 || y <= 0 || x >= MAX_X || y >= MAX_Y) {
            return;
        }
        if (length < MIN_CORRIDOR_LENGTH) {
            return;
        }
        if (dungeonMap[x][y].isWall()) {
            return;
        }        
        int positionX = x;
        int positionY = y;
        for (int i = 0; i < MIN_CORRIDOR_LENGTH; i++) {
            positionX += directionX;
            positionY += directionY;
            if (positionX <= 0 || positionX >= this.x
            || positionY <= 0 || positionY >= this.y) {
                return;
            } else if
            (!dungeonMap[positionX][positionY].isWall()
            && i < MIN_CORRIDOR_LENGTH-1) {
                return;
            }
        }
        int actualLength = length;
        for (int i = MIN_CORRIDOR_LENGTH; i < length; i++) {
            positionX += directionX;
            positionY += directionY;
            if (positionX <= 0 || positionX >= this.x
            || positionY <= 0 || positionY >= this.y) {
                actualLength = i-1;
                i = length;
            }
        }
        positionX = x;
        positionY = y;
        for (int i = 0; i < actualLength-1; i++) {
            positionX += directionX;
            positionY += directionY;
            if (!dungeonMap[positionX][positionY].isWall()) {
                actualLength = i;
            }
        }
        positionX = x;
        positionY = y;
        for (int i = 0; i <= actualLength; i++) {
            dungeonMap[positionX][positionY] = Terrain.DIRT;
            positionX += directionX;
            positionY += directionY;
        }
    }
    private void buildRoom(int x, int y, int width,
    int height) {
        if (x <= 0 || y <= 0 || width < MIN_ROOM_LENGTH
        || height < MIN_ROOM_LENGTH || (x + width >= MAX_X)
        || (y + height >= MAX_Y)) {
            return;
        }
        for (int row = x+1; row < x+width; row++) {
            for (int col = y+1; col < y + height; col++) {
                if (!dungeonMap[row][col].isWall()) {
                    return;
                }
            }
        }
        int entranceCount = 0;
        for (int row = x; row <= x+width; row++) {
            for (int col = y; col <= y+height; col++) {
                if (!dungeonMap[row][col].isWall()) {
                    entranceCount++;
                }
            }
        }
        if (entranceCount > 4) {
            return;
        }
        for (int row = x; row <= x+width; row++) {
            for (int col = y; col <= y+height; col++) {
                if (dungeonMap[row][col].isWall()) {
                    dungeonMap[row][col] = Terrain.DIRT;
                }
            }
        }
    }

    // GETTERS AND SETTERS //
    @Override public String toString() {
        StringBuffer sb = new StringBuffer();
        for (int row = 0; row < x; row++) {
            for (Terrain t : dungeonMap[row]) {
                sb.append(t.toString());
            }
            sb.append("\n");
        }
        return sb.toString();
    }
    public int getX() {
        return x;
    }
    protected void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    protected void setY(int y) {
        this.y = y;
    }
    public Terrain[][] getDungeonMap() {
        return dungeonMap;
    }
    protected void setDungeonMap(Terrain[][] dungeonMap) {
        this.dungeonMap = dungeonMap;
    }
}

Notes

This is a very, very simple dungeon generation program. It is very rough and rather efficient, but it can be broken very easily. The busyness concept, for example, can easily cause an infinite loop if set too high. There are no constraints to promote connectivity; using this algorithm will, 9 times out of 10, leave you with rooms that are unattached to anything else.

But this is not intended to be the bestest dungeon generating algorithm evar. Rather, this is meant to be an exercise. Now that you have a basic dungeon generating framework, what can you do with it to make it better?

Can this be used in its current form in a game? Of course. If you put some sort of teleporting mechanism in, you can easily get to unattached rooms. Or trapdoors from other floors could fall into them -- now that's something of a unique trap. You'll need to tweak some things here or there, but it is feasible.

Important: This work is licensed under the Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

You are allowed to use this code, and derive your own from it, in commercial products (or otherwise), IF AND ONLY IF you leave the attribution to Roddy of the Frozen Peas (roddyofthefrozenpeas@gmail.com). Please see the specifics.

Other articles in this series

1. Dungeon generation (this article)


2. Extending the dungeon


3. Connected dungeons