Random Dungeon

Random Dungeon Generator

Foreword

I wrote a random dungeon generator tutorial a few months ago, on my old blog. But since I moved to this new site, I decided to do a slightly better version of it.

This tutorial is aimed at people who are new to the world of random generation. The algorithm I will be describing generates passable dungeons that you can use in your roguelike or tabletop games but it leaves a lot of room for improvement.

If you have any questions, feel free to contact me on twitter.

Random Dungeon Generator (DEMO)

Algorithm

If you’re trained in the art of JavaScript, you can go have a look at the source in the demo. But for those of you who would like some extra help, let’s go through it now:

map = [];
for (var x = 0; x < map_size; x++) {
    map[x] = [];
    for (var y = 0; y < map_size; y++) {
        map[x][y] = 0;
    }
}

Create an empty 2-Dimensional array, the size of our map.

var room_count = Helpers.GetRandom(10, 20);
var min_size = 5;
var max_size = 15;

We use a helper function (included in the demo) to generate a random number for our room count and also define how small/large rooms can be.

for (var i = 0; i < room_count; i++) {
    var room = {};

    room.x = Helpers.GetRandom(1, map_size - max_size - 1);
    room.y = Helpers.GetRandom(1, map_size - max_size - 1);
    room.w = Helpers.GetRandom(min_size, max_size);
    room.h = Helpers.GetRandom(min_size, max_size);

    if (DoesCollide(room)) {
        i--;
        continue;
    }
    room.w--;
    room.h--;

    rooms.push(room);
}

This part generates random rooms and makes sure a generated room doesn’t collide with another one. We also decrease the room width and height by 1 so as to make sure that no two rooms are directly next to one another (making one big room).

SquashRooms();

I’ll go into this function a bit later. What it does is move all the rooms closer to one another to get rid of some avoidably large gaps.

for (i = 0; i < room_count; i++) {     
    var roomA = rooms[i];     
    var roomB = FindClosestRoom(roomA);     
    pointA = {         
        x: Helpers.GetRandom(roomA.x, roomA.x + roomA.w),         
        y: Helpers.GetRandom(roomA.y, roomA.y + roomA.h)     
    };     
    pointB = {         
        x: Helpers.GetRandom(roomB.x, roomB.x + roomB.w),         
        y: Helpers.GetRandom(roomB.y, roomB.y + roomB.h)     
    };     
    while ((pointB.x != pointA.x) || (pointB.y != pointA.y)) {         
        if (pointB.x != pointA.x) {             
            if (pointB.x > pointA.x) pointB.x--;
            else pointB.x++;
        } 
        else if (pointB.y != pointA.y) {
            if (pointB.y > pointA.y) pointB.y--;
            else pointB.y++;
        }

        map[pointB.x][pointB.y] = 1;
    }
}

Now we start building corridors between rooms that are near to one another. We choose a random point in each room and then move the second point towards the first one (in the while loop). We set each corridor tile to 1 which can later be interpreted by the dungeon drawing algorithm as such.

for (i = 0; i < room_count; i++) {
    var room = rooms[i];
    for (var x = room.x; x < room.x + room.w; x++) {
        for (var y = room.y; y < room.y + room.h; y++) {
            map[x][y] = 1;
        }
    }
}

Fairly straightforward. Here we iterate through all the rooms and set the tile to 1 for every tile within a room.

for (var x = 0; x < map_size; x++) {
    for (var y = 0; y < map_size; y++) {
        if (map[x][y] == 1) {
            for (var xx = x - 1; xx <= x + 1; xx++) {
                for (var yy = y - 1; yy <= y + 1; yy++) {
                    if (map[xx][yy] == 0) map[xx][yy] = 2;
                }
            }
        }
    }
}

This last part iterates through all the tiles in the map and if it finds a tile that is a floor (equal to 1) we check all the surrounding tiles for empty values. If we find an empty tile (that touches the floor) we build a wall (equal to 2).

That’s the whole algorithm! Lets have a quick look at the helper functions.

FindClosestRoom: function (room) {
    var mid = {
        x: room.x + (room.w / 2),
        y: room.y + (room.h / 2)
    };
    var closest = null;
    var closest_distance = 1000;
    for (var i = 0; i < this.rooms.length; i++) {
        var check = this.rooms[i];
        if (check == room) continue;
        var check_mid = {
            x: check.x + (check.w / 2),
            y: check.y + (check.h / 2)
        };
        var distance = Math.abs(mid.x - check_mid.x) + Math.abs(mid.y - check_mid.y);
        if (distance < closest_distance) {
            closest_distance = distance;
            closest = check;
        }
    }
    return closest;
}

This function calculates the midpoint of the room you give it and runs through all the other rooms, checking how far they are from it. The two variables declared (closest and closest_distance) keeps track of the closest room found so far and how close it is to our initial room.

You’ll notice I don’t use the Pythagorean Theorem to calculate the distance (square_root(delta_x_squared + delta_y squared)) but that would be overkill, we can do it like this and it’ll execute faster (not noticeably but we can feel superior regardless).

DoesCollide: function (room, ignore) {
    for (var i = 0; i < this.rooms.length; i++) {
        if (i == ignore) continue;
        var check = this.rooms[i];
        if (!((room.x + room.w < check.x) || (room.x > check.x + check.w) || (room.y + room.h < check.y) || (room.y > check.y + check.h))) 
            return true;
    }

    return false;
}

As the name implies, this function checks whether a room collides with any other room. It has a second parameter for the cases where the room we’re checking already lies in the room array and we need to ignore it (since it obviously collides with itself).

The long if uses de Morgan’s law to swap around an otherwise costly list of AND clauses. This technique is especially useful when writing collision tests that need to be performed in realtime.

SquashRooms: function () {
    for (var i = 0; i < 10; i++) {
        for (var j = 0; j < this.rooms.length; j++) {             
            var room = this.rooms[j];             
            while (true) {                 
                var old_position = {                     
                    x: room.x,                     
                    y: room.y                 
                };                 
                if (room.x > 1) room.x--;
                if (room.y > 1) room.y--;
                if ((room.x == 1) && (room.y == 1)) break;
                if (this.DoesCollide(room, j)) {
                    room.x = old_position.x;
                    room.y = old_position.y;
                    break;
                }
            }
        }
    }
}

Our final function! This function is very brute-forcey. It iterates through all the rooms and moves each room up and left, taking care not to let the room move onto the edge of the map (gotta leave space for walls). If it finds that moving a room has caused it to collide, we move it back to where it was and continue to the next room.

The whole process is done 10 times but less will also work. Decreasing the number will cause rooms to be further from one another (on average).

Conclusion

And that’s it! If you have any questions, feel free to drop me a tweet. You can see a similar algorithm to this in action in my roguelike, Morf.

One thought on “Random Dungeon Generator

  1. Pingback: Map Generator Plugin (Roguelike Articles) | Kiwi.JS HTML5 Game Engine

Comments are closed.