The Cauldron – A random dungeon generator (Part 1)
There are these points in one’s development lifetime where one must try to make certain things… just to see if one can do it. The Fantasy Role Playing Game, The Networked Game, The Randomly Generated Dungeon…
Yes, I’m fussing with making a procedural dungeon…
Is this like chicken pox? Something that passes after a while and if you don’t scratch too much it won’t scar that bad?
Now, just to be clear: This is a hobby project, so expect it to develop very slowly…
Where to begin?
I am fascinated by procedural content. Not just Minecraft, which intrigues me less for it’s voxel blockiness than it’s very firm and comfortable landscape and gameplay, but any game where procedural content comes into play. At a session of the London Unity Users Group, Tom Betts, aka Nullpointer, gave a great talk on procedural generation in Unity that’s well worth watching. Procedural content creation and character AI seem to me like both might and magic rolled into one.
I’ve been reading up on procedural generation algorithms and AI recently, and this has encouraged this dormant bug. So, giving into the urge, I began to read up on and mull over the different ways people have made random dungeon generators.
There are a few good sites to visit: PCG on WikiDot (The Procedural Content Generation Wiki) – specifically the Dungeon Generation Section which has a number of articles and a good set of external links, RogueBasin (The Roguelike information source) which covers procedural generation in the context of making Roguelike games. I also used both Google and the Google Custom Search Engine targeting Unity related subjects to search for phrases like “Procedural Dungeon Generation C#” for additional sources. To be honest, most of these end up referring back to the same base articles.
There are a number of different approaches for these algorithms.
Some of these make rooms first, shuffle them around and try to connect them with corridors. The linked description has links to the base concepts used, like Park-Miller Normal Distribution and Delaunay Triangulation. The page also includes a link to an interesting visual example of how the algorithm works.
Other make mazes and then fill in the blank space. Some make natural or organic system, like caves, using Cellular Automata, as described here on PCG wiki.
Still more make rooms and if they overlap: “Who Cares?” – the algorithm just makes them into a bigger more irregular room, and adds walls last.
Some of the algorithms check to make sure all rooms are reachable using pathfinding and adds additional corridors and doors if they aren’t. Others simply delete unconnected rooms. Many do some combination of both.
I was attracted to this algorithm on RogueBasin where you make a room, find a space for a door, add a corridor, add more rooms, and so on – as if you were building the dungeon yourself with your horde of construction minions.
I discovered this project that uses many of these methods all in one system.
To get started, I needed assets, so I grabbed BitGem’s Dungeon Builder Starter Set from the Unity Asset Store. The Dungeon Builder Starter Set has floor tiles, wall sections and a some good props. The set even has a nice pit to fall into and few treasure chests to scatter around. If I really want to keep with the look and feel of these great hand painted assets as this project continues, BitGem also had a few animated characters that would match the environment. The only downside I found with these assets is that they are perfectly tuned for these cute animated characters, so the geometry is about half scale when compared to the usual humanoid capsule of (1, 2, 1). To use these on a human scale in Unity, the assets need to be imported at a scale factor of 2.
To make my dungeon, I want to move beyond the grid so often used in creating procedural dungeons with this algorithm. I want to break free from both the square box containing the level and the plane upon which it rests.
So I decided to base this experiment on one square meter floor tiles. I would use the floor tiles to make the rooms and corridors in the Unity scene volume, and then generate the walls, doors, props and perhaps a roof afterwards.
I felt that this approach would be more controllable and more versatile than, say, having a set of room prefabs that I would instantiate, position and connect with random corridors.
Thinking ahead, I am assuming that I’ll have a greater ability to vary the floor tiles or wall pieces used to build the rooms based on the code I write over using pre-built room prefabs. I could even pre-define room types or styles. Each room type or style could have specific individual characteristics or build recipes, but the ingredients would all be these very basic and reusable elements. I would also hope that this will help me break out of the flat matrix so many procedural dungeons have, and start using the full volume of 3D space available in the Unity scene. This would allow me to include stairs, pits, tunnels, vaulting ceilings… maybe even balconies, catwalks, mezzanines… and definitely rooms above and below each other – anything to break up that feeling of being stuck in a flat 2D space. The perfect solution would allow me to mix prefabs with completely generated rooms in the final build; even perhaps mixing prefabs and basic elements in the same room.
At this point, I’m not worried about the type of game – first, third, isometric. I’m only interested in how to effectively build the dungeon itself, while hiding or minimizing that feeling of random generation. I want these locations to feel new with each build, but not feel simply generic.
Duck’s Scriptable Wizard
For Unite 13 training day, a prototype wizard was created by one of the field engineers working for Unity Technologies, Duck. Duck created a solution for quick prototyping where you can lay down floor tiles and then with a simple ScriptableWizard, build the walls around the defined floor space < code/script link coming when it gets posted! >. Duck works with Unity as a teacher and field engineer, and created the material for the Training Day seminar and is currently working on the sample assets that will be distributed by Unity Technologies.
I started by getting a handle on Duck’s ScriptableWizard. By laying out tiles by hand, generating walls and deconstructing the script, I understood the concept and the implementation Duck had used, and I understood how t0 use this concept in another context.
The simple version is fairly straightforward. The tiles all have a component that simply flags the tile as floor tile. The scriptable wizard knows that anything flagged as a floor tile wants to participate in wall generation. When the ScriptableWizard executes, it finds all of the floor tiles in the scene and iterates through all the active tiles with their “Build Walls” flag turned on. The wizard then checks for space on all four sides of each tile. If there is nothing next to the floor tile, the wizard builds (instantiates) a wall in that empty space and rotates it to face in towards the tile.
The advanced script has solutions to certain issues, like inner and outer corners, joins and other features that are absent in the simple version.
My first evening, albeit short, was spent simply trying different variations on the theme and adapting the script to work the BitGems geometry. Most of my early attempts were a disaster. Eventually I bent the simple script to my will.
Random Rooms – 1st attempt
My second night was breaking ground on my own code for a simple level generator.
I began with simply creating rooms of a random size where each side could be 1-6 tiles in length, and then laying the tiles down as the floor. For this I took a hint from my inventory manager code. With Inventory Manager I built the inventory bag windows from an inventory length and a bag width. By using length/width and length%width, I could quickly and easily lay out the columns and rows in an inventory bag. Using this method, I was able to quickly make single random rooms.
Building the tiles directly into the scene volume was my first step in building the level in the scene volume itself.
With this in mind, I built a class to attach to the floor tile, that, expanding on what Duck had done, not only flagging this tile as a floor tile and available for wall building, but giving the tile a place to hold all the information needed from that tile to build the entire dungeon. This included whether this tile was “an edge”, which would need a wall, and if so, which edge it was – as I felt it was best to calculate that up-front, even if we were building it later.
The random room generator algorithm was very simple, and worked well for creating a single room.
A few nights later, I spent a couple of hours fussing with how to find a door point from that first room and then building additional rooms off of the one single door. If this worked, I was hoping to expand on this later.
Using the class attached to the tiles, this was relatively straight forward:
I build a random room from based on my Level Generator’s “minRoomSize” and “maxRoomSize” variables. Then I look at all the tiles that were created and test the area on all 4 sides to see if that space was occupied. This was essentially the meat of Duck’s “simple” script. When instantiated, each tile has an “isEdge” variable flagged as false. If there is no tile in any of the four directions from the tile we are testing, then “isEdge” is set to true. I then take all of my edge pieces and find the ones with only one edge that is unoccupied – as I didn’t want to get any corner tiles which would have two – and put them in a list. I randomly select one from the list and build a door next to it in the single obvious empty space.
Finding the start point for the next room is easy. I have the originally selected tile and the new door tile position, so with those coordinates, the next tile in the direction of selected tile and new door tile is the start point for the new room. I can simply send that to my room generator, and generate the next room.
Here is where I’ve failed to think things through. As my rooms now build, they build in only one direction… making columns from left to right along the x, advancing by rows along the z… positively. So, when a random room is started to the negative of my original room, it simply builds over it.
Not very clever.
What I need to do is build the room, then position it, rather than position the start point and then build the room.
So – I wrapped up this session, knowing I would start over.
The Cauldron – A random dungeon generator (Part 2)
Continued in The Cauldron – A random dungeon generator (Part 2).
Stefa168about 8 years ago Reply
Hi Adam, I liked your algorithm ofr Dungeon generation and actually I'm working on something similar. I know that this blog post is from 2013, but I wanted to ask you if you could send me the project, so I can see more in depth how you made the whole thing. I don't want to copy or anything like that, it's just that I need some inspiration to start programming everything. Thank you!
Adamabout 8 years ago Reply
Well, the project isn't really fit for distribution. I still have embedded assets and other rubbish that I can't really distribute. The point to the post is to give an idea of the logic behind the system, so anyone could recreate it with their own code. Give it a try and I can help you over the rough patches.