Source: Nolithius.com » roguelike
Although I have worked on two (albeit short-lived) roguelikes prior to Dance of Death, this is the first to feature a dungeon generation algorithm. While it relies greatly on brute force searches, especially for connectivity, I am quite happy with it, and it definitely gets the job done!
From a bird’s eye view, it is a pretty straightforward carving algorithm with the following steps:
- Make every tile for the area a wall.
- Generate random rooms and place them randomly.
- Connect the rooms with halls until the whole dungeon is connected.
- Add doors.
- Add stairs.
- Generate and add items.
- Generate and add monsters.
- Position player.
Steps #2 and #3 are the tougher parts of the whole process, so they warrant a bit of fleshing out:
The first thing I do is decide how many rooms to place (between a constant min and max). Then, generate that number of rectangles, with a width and height between a preset min and max, and throw them into an array. These rectangles are sorted by area, larger to smaller, to aid placement. Placing larger rooms first results in less failures in the next step: finding a space for the rooms.
The findSpace() function takes a rectangle (room), generates a random coordinate for the top-left of that room, and tests to see if the room fits. This is so if it is within the dungeon bounds (guaranteed if your random boundaries are carefully calculated), and if it does not overlap an already existing room. If after a set number of retries no space is found, then give up and use the last coordinate generated (resulting in a room overlap). I initially had 20 iterations, but after optimizing the system by adding the larger-room-placed-first approach, 5 iterations work just as well, especially since overlapping rooms add a bit of variation to the dungeon.
After space for a room is found, it is carved (all of the tiles in the rectangle are set to a floor), and the process is repeated until all the rooms are placed. At this point, the dungeon consists only of disconnected rooms.
Connecting the rooms is actually the most expensive part of the process. There are cheaper approaches, but they resulted in more sparse, loosely connected dungeons, with little or no loops. The checkConnected() function iterates through the map every time it is called and does the following for every tile: check if the tile has been checked this iteration, if so, skip; else, mark as checked, and set an incremental cluster value to this cell. Each time a cell is found that gets a new cluster, recursively floodfill from that cell to each cell in its neighborhood and mark those cells as checked and with the same cluster number. Also, add the tile to a two-dimensional array that is a collection of tiles bucketed under their cluster number.
After all the tiles have been checked and the clusters have been assigned, we have a list of clusters. If the cluster list length is larger than 1, it means that the dungeon is not fully connected. If so, connect 2 random clusters by carving a hall between a random tile in each of the two clusters. After a hall is drawn, repeat the checkConnected() until it yields a cluster list length of 1, which means that only one floodfill was necessary to traverse every floor tile in the dungeon, or, in other words, the dungeon is fully connected!
The rest of the steps are pretty straightforward as far as placement— generating interesting items and monsters is an entirely different topic!
I am really happy with the results of this dungeon generator. I have some ideas to create variations on the algorithm, which will result in different dungeons (although this will do the trick for now):
- Define sets of constants that will result in different configurations, such as a few very large rooms, or many very small rooms.
- Skip room if no space can be found for it, guaranteeing no overlaps.
- Treat rooms as graph nodes, and connect them blindly without checking for connectivity at every step.
- Generate circular rooms.
- Generate rooms with corner pillars or pillars along the walls.
- Generate rooms and halls with spaced-out niches.
- Generate variations on the halls, such as wider halls, or 3-tile-wide halls lined with alternating center columns.
These items are, of course, fairly low in the priority list, but warrant noting down for a few months down the line when I am able to get to them!
French