# Random Dungeon Generator

posted in: Uncategorized | 3

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.

### 3 Responses

1. ##### Ashley

First off, thanks for taking the time to post this code. I’m a student and found this extremely helpful while figuring out how to design my first dungeon! That being said, it appears that your code leads to rooms or sections of rooms being unreachable by the rest of the dungeon. Running your demo a few times, it gets disconnected rooms fairly often as there doesn’t appear to be anything checking that all the rooms are in fact connected by corridors. Being quite new to this sort of thing, do you have any suggestions for ensuring that all of the rooms are reachable by some sort of path through rooms and corridors? Any help or advice would be greatly appreciated!

• Hi there. I left that part out to keep the algorithm as simple as possible. The ‘simplest’ way to fix this would be to use a flood fill algorithm:

1. Find the first open tile
2. Call a recursive function on that tile that sets any open tile (value 1) to another value that isn’t used yet (like 3)
3. When the recursive function is done, check to see if there are any open tiles left (value 1)
4. If there are open tiles left, it means there are disconnected areas: rerun the generator
5. Repeat process until you build a fully connected map

Good luck!

2. ##### Bryan Jarrie

Hi, I’m currently using RPG Maker MV & was wondering if this would work with it since it uses javascript plugins? I’ve tried asking everyone on the RPG Maker forums but no one seems to want to do it because of how tedious it is. I desperately need this so any help would be greatly appreciated.