Procedural content generation is a great way to generate interesting worlds, and dungeon generation is often the first step in level creations. A variety of algorithms have been researched and developed to produce interesting random levels that make games, especially roguelike games, unique and fun.
This was originally the level generation part of the Lighters project. As the project grew and more (than necessary) dungeon generation algorithms were added, the code was split off as a separate app. The original concept had been toyed with in Procedural Cave, but this app is a complete dungeon generator that will produce nice dungeons using a variety of algorithms.
The dungeon generation code is organized such that it should be very easy to add new dungeon generation algorithms in the future. The code creates a grid in the form of a 2D array grid, and passes the array to the dungeon generation algorithm. Too add a new algorithm, just pass the grid array to a new file containing the algorithm.
Several algorithms are implemented; some are very simple while others contain complex data structures and pathfinding algorithms. Read on for an explanation of each algorithm, or go to the end to look at the results, as well as downloads and the source code.
Random Room Placement
One of the most simple and probably the most used dungeon algorithm. This algorithm places rooms randomly on the grid, then loops over each room and attempts to connect each room. If given the chance, random tunnels can also be dug out to give the dungeon a more natural feel. The basic idea of the algorithm is as follows:
- Determine the number of rooms to be created based on the room layout selected, and updates various user-configured variables in updateParam()
- Calls initRooms() to create a room of random width and height at a random location on the grid. A random number of openings (doors) are placed in the room walls.
- Check if the room is outside of the grid or blocked by another room or corridor through blockRoom(). If blocked, deleted the room and repeat step 2.
- After all rooms are initialized, call initCorridors() connect the openings of each room. In basicAStar(), A* pathfinding algorithm is used to look for the optimal path from one door to another. Weights are used so that the corridors are more likely to be straight and join each other.
- If there are any openings left unconnected, randomly tunnel corridors out from the opening by calling tunnelRandom(), if the corridor reaches a room wall, add a door there.
Different types of dungeons can be generated based on the min/max room size and the room numbers. The A* algorithm uses the Manhattan method to calculate the heuristics, and a Binary Heap is used to store the nodes.
Based on the cellular automata method by Jim Babcock, this algorithm uses cellular automaton to create natural-looking caves. Usually cellular automation uses the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its nine neighbors were walls, or if it was not a wall and 5 or more neighbors were. This algorithm is a slightly modified version of that:
Tile T will be filled if either
- T is already filled *and* at least 4 of its neighbors are filled
- T is not yet filled *and* at least 5 of its neighbors are filled
This is the same thing as sayin
Tile T will be filled if the number of tiles within one step of T, including T itself, is at least 5.
But this is not the function which my sample program uses. The function I use is
Tile T will be filled if the number of tiles within one step of T, including T itself, is at least R1Cutoff OR the number of tiles within TWO steps of T, including T itself, is at MOST R2Cutoff.
So, if R1Cutoff=4 and R2Cutoff=5, that will happen almost all of the time.
Anyways, the function I eventually chose as the 'best' answer was
Repeat 4 times:
R1 cutoff: 5
R2 cutoff: 2
Repeat 3 times:
R1 cutoff: 5
R2 cutoff: -1
So the parameters would be
xsize ysize 40 5 2 4 5 -1 3
So, it first fills the grid randomly with walls and empty cells, then goes over each grid cell and applies the follow rules to the cell:
- A tile T becomes a wall if 5 or more of the tiles within one step of T are walls.
- A tile T becomes a wall if 2 or less of the tiles within two step of T are walls.
Repeat three times, and the user gets a somewhat natural-looking cave. To clean up the cave further and reduce the number of disconnected caves, the loop is run four more iterations, except this time a tile T becomes a wall if 5 or more of the tiles within one step of T are walls, and becomes a wall if none of the tiles within two step of T are walls.
Do note that although the second iteration lowers the possibility of disjointed caves, it may still happen.
This is an algorithm that takes advantage of a tree data structure called BSP tree to make sure there are no overlapping rooms during dungeon generation. The algorithm itself it fairly straightforward, as outlined below (check here for a more visual explanation):
- Start with a rectangular dungeon.
- Choose a random direction (horizontal or vertical) and location (x for vertical or y for horizontal).
- Split the dungeon into two sub-dungeons using the parameters obtained in step 2.
- Pick a random sub-rectangle and repeat step 2 for n iterations.
- After n iterations, place random sized rooms in each of the rectangles.
- Connect each room by looping through all the split rectangles and connect each split sub-regions.
Based on the method described by Mike Anderson, this is another fairly simple algorithm, and one that most resemble how an actual dungeon is built. The algorithm first generates a room in the center of the grid, then connects more rooms and corridors to the room and newly placed elements. In effect, the dungeon "grows" outward from the center room:
- Fill the whole map with solid earth
- Dig out a single room in the centre of the map
- Pick a wall of any room
- Decide upon a new feature to build
- See if there is room to add the new feature through the chosen wall
- If yes, continue. If no, go back to step 3
- Add the feature through the chosen wall
- Go back to step 3, until the dungeon is complete
The original code tended to create rooms connected to rooms with dead end corridors sticking out, this version is modified to reduce the number of dead ends and increase the likelihood of a room being generated at the end of a corridor.
This algorithm is implemented to test the extensibility of the dungeon generator, efforts were made to retain as much of the original code as possible.
The app is meant to be fairly straight forward to use. Press 'space' to generate new dungeon, play around with the parameters and see how they affect the dungeon. Click 'Save' to save the current dungeon to a file.
Download the generator for your system of choice:
Or play around with an online version: