Hey everyone! For the past few years, I've been addicted to a specific category of games known as roguelikes. One of my favorite aspect of this genre is that the world tends to be randomly generated each play through making the games have much more replayability. I also find that procedural content generation is an extremely interesting computer science problem, so I figured I'd write a post about generating a game world procedurally. I'll be writing the code in Java, which can easily be translated to a number of other languages. We'll be generating one of the most traditional roguelike elements - a dungeon. Our dungeon will be fairly simple, containing a set of rooms connected by tunnels. The end result will generate dungeons which can be represented like :

Before we get started, we'll need to define a utility function for generating a random integer within a given range. I've provided a simple utility class here which makes use of the java.util.Random class in Java to generate pseudorandom numbers. One important thing to discuss here is the seed used. A pseudorandom number generator is deterministic - given a certain input, you will always have the same output. This is really neat because it means that if we keep track of the state of the random number generator when building a level, we can rebuild it by simply resetting the state of the RNG to the original state. This saves us a ton of space when saving levels ;) Also, to keep things simple we will build an array of integers representing the map with the first dimension being the X value and the second being the Y. Each element will contain one of the following values: 0 for wall or 1 for floor. This can easily be changed to return an enum value or whatever you please.

Let's begin! Our first step will be to carve out the rooms. In order to do this, we 1) fill our room with wall tiles, 2) split the map into a grid, and finally 3) randomly select cells of the grid to contain rooms, filling them with floor tiles. Of course the rooms will have a random size as well as have some deviations in order to generate a map which isn't too boring. First we'll create a basic Room class in order to hold data. Although best practice is generally to have class members be private, in this case it's acceptable to just access them directly rather then to operate through getters and setteres. Having a Room class is a useful step for the future as we can then add special attributes to rooms (like a dark room) as well as have different types of rooms (like circular rooms).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package lbaw.map;
/**
 * A basic rectangular room.
 * @author Dominic Charley-Roy
 *
 */
public class Room {
    public int x;
    public int y;
    public int width;
    public int height;
    public Room(int x, int y, int width, int height) {
        super();
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }
    public void place(int[][] tiles) {
        // Fill the room with floor tiles. Offsets are necessary
        // for walls.
        for (int xP = x + 1; xP < x + width - 1; xP++)
            for (int yP = y + 1; yP < y + height - 1; yP++)
                tiles[xP][yP] = 1;
    }
}

We can now build our Map utility class which will take care of building rooms based on a few constants. First we will generate the number of rooms to place. Once we have that, for each room we will randomly place it in an unused grid cell (remember we said we were splitting the map into a grid) and generate a width and height for it. We will store the list of rooms in a List in order to make tunnelling easier later on. I also declared a few constants for generation information - go ahead and tinker around with them and see what you get!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package lbaw.map;

import java.util.ArrayList;
import java.util.List;
import lbaw.util.Util;

public class MapBuilder {
    private static final int MAX_ROOM_WIDTH = 10;
    private static final int MAX_ROOM_HEIGHT = 8;
    private static final int MIN_ROOM_WIDTH = 5;
    private static final int MIN_ROOM_HEIGHT = 4;
    // The following ratios determine the number of rooms to place 
    // based on the total possible number of rooms.
    private static final double MIN_ROOM_RATIO = 0.3;
    private static final double MAX_ROOM_RATIO = 0.7; 
    public static int[][] buildMap(int width, int height) {
        int[][] tiles = new int[width][height];
        // clear the map
        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++)
                tiles[x][y] = 0;
        // Build the rooms and tunnels
        List<Room> rooms = placeRooms(tiles);
        placeTunnels(tiles, rooms);
        return tiles;
    }
    private static List<Room> placeRooms(int[][] tiles) {
        int mapWidth = tiles.length, mapHeight = tiles[0].length;
        int roomsAcross = mapWidth / MAX_ROOM_WIDTH, roomsDown = mapHeight
                / MAX_ROOM_HEIGHT;
        int maxRooms = roomsAcross * roomsDown;
        // use an array of booleans to represent which rooms have been used
        boolean[] usedRooms = new boolean[maxRooms];
        // generate the number of total rooms based on the ratios
        int totalRooms = Util.rand((int) (maxRooms * MIN_ROOM_RATIO),
                (int) (maxRooms * MAX_ROOM_RATIO));
        // generate the rooms
        List<Room> rooms = new ArrayList<Room>(totalRooms);
        Room room;
        int roomCell;
        int width, height, x, y;
        for (int i = 0; i < totalRooms; i++) {
            // keep generating a room cell until we find an unused one
            do {
                roomCell = Util.rand(0, maxRooms - 1);
            } while (usedRooms[roomCell]);
            usedRooms[roomCell] = true;
            // generate room width and height
            width = Util.rand(MIN_ROOM_WIDTH, MAX_ROOM_WIDTH);
            height = Util.rand(MIN_ROOM_HEIGHT, MAX_ROOM_HEIGHT);
            // generate x and y position based on cell x and y. we also
            // generate a random offset with the remaining space in the cell
            // in order to create less square levels.
            x = (roomCell % roomsAcross) * MAX_ROOM_WIDTH;
            x += Util.rand(0, MAX_ROOM_WIDTH - width);
            y = (roomCell / roomsAcross) * MAX_ROOM_HEIGHT;
            y += Util.rand(0, MAX_ROOM_HEIGHT - height);
            room = new Room(x, y, width, height);
            room.place(tiles);
            rooms.add(room);
        }
        return rooms;
    }
    private static void placeTunnels(int[][] tiles, List<Room> rooms) {
        // We will carve the tunnels here.
    }
}

When I use this algorithm to generate rooms, and I plug the values into my roguelike engine, I get something similar to this. Looking good so far! Now let's get these rooms connected. This is why we kept track of the rooms we added in a list. Essentially we will connect each room to the previous and to the next. In order to tunnel, we will keep track of the distance in both the x direction and y direction from the center of both rooms, and repeatedly add segments of random length in both direction until we finally hit the center. Let's replace the placeTunnels method with the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private static void placeTunnels(int[][] tiles, List<Room> rooms) {
    int deltaX, deltaY, deltaXSign, deltaYSign;
    int currentX, currentY;
    boolean movingInX;
    int carver, carveLength;
    Room currentRoom, goalRoom;
    // iterate through each room apart the last, tunnelling
    Iterator<Room> iterator = rooms.iterator();
    currentRoom = iterator.next();
    while (iterator.hasNext()) {
        goalRoom = iterator.next();
        // calculate the starting position and distance remaining
        // based on the center of the two rooms
        currentX = currentRoom.x + (currentRoom.width / 2);
        currentY = currentRoom.y + (currentRoom.height / 2);
        deltaX = (goalRoom.x + (goalRoom.width / 2)) - currentX;
        deltaY = (goalRoom.y + (goalRoom.height / 2)) - currentY;
        // determine sign to carve in for both directions
        if (deltaX == 0) deltaXSign = 1;
        else deltaXSign = (int)(deltaX / Math.abs(deltaX)); 
        if (deltaY == 0) deltaYSign = 1;
        else deltaYSign = (int)(deltaY / Math.abs(deltaY));
        // iterate until we only have 1 direction left
        while (!(deltaX == 0 && deltaY == 0)) {
            // randomly choose a direction
            movingInX = Util.rand(0, 1) == 1;
            // if we are at 0 of current side, switch direction
            if (movingInX && deltaX == 0) movingInX = false;
            if (!movingInX && deltaY == 0) movingInX = true;
            // carve a random length
            carveLength = Util.rand(1, (int)(Math.abs(movingInX ? deltaX : deltaY)));
            for (carver = 0; carver < carveLength; carver++) {
                if (movingInX) currentX += deltaXSign * 1;
                else currentY += deltaYSign * 1;
                tiles[currentX][currentY] = 1;
            }
            // update deltas
            if (movingInX) deltaX -= deltaXSign * carveLength;
            else deltaY -= deltaYSign * carveLength;
        }
        currentRoom = goalRoom;
    }
}

And now your dungeon will be navigable! The advantage of using the list is that it ensures all rooms are connected. You can now do plenty of interesting things like have hidden tunnels, different types of rooms, etc. Another nice aspect is that tunnels tend to crisscross as the rooms wont necessarily be in cell order, making the level less linear.

I hope that you enjoyed this little bite of procedural content generation! Feel free to post any questions you may have. Thanks for reading and see you next time,

Dominic

PS: Check out this link if you're curious about procedural generation and this link if you're curious about roguelike development.