Dungeon Generator Algorithm: Part I
I've finished developing the dungeon generator for Aeldan, and while the algorithms used are trivial to implement, the steps to arrive at a quality final map are not straightforward. This article will guide you through them, without going into specifics from image generation or special parameters.
Above: a randomly generated dungeon map.
Step 1: Map and Room sizes
Choose a predefined set of values for your map and room sizes. It is not possible to fit ten 3x3 rooms in a 6x6 area. The wider the area and the smaller the rooms, the more sparse your dungeon will feel. The values below are taken directly from Aeldan's generator:
10 rooms: 20x20 map, rooms varying between 5 and 2 in both width and height (max filled space of 62%)
20 rooms: 30x28 map, rooms varying between 5 and 3 in width, 5 and 2 in height (max filled space of 60%)
The larger your rooms, the lower the maximum occupancy ratio you should aim for. Rooms that are too large have the potential to block large areas, and as you'll see in the next step, you want as much leeway as possible.
Step Two: Generate rooms
At these relatively small sizes (the largest map is US ratio 50, for 3,366 squares), memory is cheap. Keep a bi-dimensional array corresponding to all possible x and y coordinates and assign them a value of 0, or empty. An empty square is one that contains nothing, and this is what all the squares should be initialized to.
Next, loop through rooms. You want to create 10 (or as many as you want) rooms and position them in our array (keeping a separate copy of their positions). Generate a possible room (random x (rx) and y (ry) position, random width, random height), then iterate through all the possible squares your room takes up (all x values between rx and rx + width, for all y values between your ry and ry+height) making sure they are 0. If so, perfect: set all those values to the room number (1 for the first, 2 for the second, etc), and generate a new room. If not, generate new values. Loop until you have your desired number of rooms: some may not be possible to generate at all (like our 6x6 example containing ten 3x3 rooms) so be sure to halt generation after a few (1,500?) iterations.
Step 3: Growing paths
The Procedural Content Generation Wiki is an amazing resource. You'll find the Growing Tree Algorithm for creating mazes in this page. What this algorithm does, in very basic terms, is pick a randomized square, consider it a path, then add all the squares around it (diagonals excluded) to a list of "exposed" squares. In every iteration, it'll take a random exposed square, count the "path" squares around it, set it to "wall" or "path" depending on the number of path squares, and add the squares that this new exploration exposes to the exposed list.
If that sounds complicated, read it again. It's actually rather simple: each step the algorithm evaluates only one square, and it may expand the path once in a random direction, or close off a square that already has two paths around it, preventing loops. The end result is a matrix of walls and paths, very useful for what we're doing here.
We already have a matrix (a bi-dimensional array) we are keeping with the status of the rooms. You may use this matrix considering all rooms part of a wall, or you can use this matrix considering all rooms part of the path. You can, as Aeldan's generator does, not consider this matrix at all when calculating paths - essentially creating the paths and walls in a separate layer, then adding it to our master map matrix.
There are a few changes you need to make to the growing tree algorithm for it to generate higher quality passages than the maze-like corridors it otherwise creates. You would usually consider a path a square that only has one adjacent square that is a path. Here you'll want to give it a small possibility of creating a path where there are two adjacent squares, which may possibly create loops in your dungeon. This is fine.
Second, you want to give it a small chance of "looking ahead" and blocking off the path if you cannot go two steps in that direction. This means that when you are calculating how many adjacent squares you have (for path defining purposes, you want only one or, rarely, two) you will sometimes consider one move ahead as well: for each square you'll check north, south, west, and east, tallying up the number of "path" adjacent squares, but an empty north (or any other) may count as a path sometimes (say, 30%) if two squares north you have a path as well. Same applies to east, west, and south. This not only creates more space between your paths (leading to a less maze-y and a more organic dungeon layout) but also prevents dead-ends.
So now you've got it down. Great. You'll need to keep a matrix of all possible x and y squares along with their status: wall, path, or unexposed. You'll need to keep an array of exposed squares that you keep adding to, and removing from, as you iterate. And you'll need to verify - when you find a "path" square - whether your original matrix (the one containing the rooms) has that square as empty, and mark it as a path.
Next Article: Cleaning up dead-ends, generating doors.