MiniDungeon – A Free Random Dungeon Jump Start for Unity

The other day I was discussing with a friend about automatic dungeon creation in Unity3D and I recommend him an excelent and also a free and easy Unity project I had found some time ago. The project is called "MiniDungeon – A Free Random Dungeon Jump Start for Unity" and it used to be hosted here http://www.stevegargolinski.com/minidungeon-a-free-random-dungeon-jump-start-for-unity/
For my and his suprise, the website was (actually is) down but I told him to not to worry because I have the source home at home.
As I think this code is great, I decided to re post the original blog spot (I have it in my pocket ;) and to upload the original source code to my public bitbucket.

First of all, you can download the minidungeon source code here https://bitbucket.org/hzaldivar/minidungeon.git

Here you have the original blog post written by Steve Gargolinski (@sgargolinski):

Over my holiday break I spent some time messing around with Unity on a basic random dungeon generator with lightweight RPG elements, and I’ve decided to post a version up here as a jump start in case anyone is interested in working on something similar. Hopefully this will help someone out.

I’ll start this post with a web player version and then the full Unity project download, and then go into a bit more detail below. I also want to throw out the caveat up front that this code is not polished and hasn’t been iterated on much or tested extensively.

With that out of the way, click the image below to check out MiniDungeon in the web player. There is a ‘walkthrough’ below.
The Basics / “Walkthrough
MiniDungeon starts off at a main menu, but the only real current option is to play the game. Clicking on Play takes you to the Home Base, which is what I envision as the hub in between adventures – a place to upgrade weapons/armor, train skills, shop for healing potions, maybe get some info from townsfolk, etc.
I also envisioned the Home Base as a quest hub, where you choose which adventure you want to go on and the future dungeon/storyline is configured to make this happen. So you might choose “Go Rescue the Princess” or “Go Slay the Dragon”, and the dungeon generator/storyline will be customized appropriately. In this demo, all you can do from here is click “Go on an Adventure”.

At this point you are launched into a randomly generated dungeon. There are some instructions on hotkeys in the upper-left, and then some info on your character in the upper-right. This randomly generated dungeon floor includes stairs up (green) and stairs down (red). If you move around (with WASD) to the stairs down, you can press spacebar to go to the next level. Note that the dungeon floor counter in the upper left will increment. As you go down each level, there’s a random placeholder story segment to advance the future story.

If you want to see a larger view of the dungeon, hit ‘Z’ to zoom out and then back in. You can also hit ‘Tab’ to skip ahead to the next dungeon level. Zooming out and then repeatedly hitting ‘Tab’ will show you the range of dungeon floors that can be generated.

Every once in a while you will hit a random battle vs a giant toad. Press ‘X’ to defeat him, you’ll notice that sometimes you’ll lose HP from this battle. If you run low on HP you can hit ‘I’ to open up your inventory and use a Healing Potion. Defeating a bunch of toads will level you up and increase your max HP/MP.

That’s about it – nothing staggering, but probably a pretty good jump start if you’re interested in making a random dungeon game. The only real complicated aspect of this project is the random dungeon generation, so I’ll go into a bit more detail on that.

Random Dungeon Generation
The random dungeon generation algorithm included (in the DungeonGenerator class) is something that I worked out off the top of my head. I did some quick research and couldn’t find an algorithm to do what I was looking for, but it’s possible I just didn’t look in the right place. My goal was something similar to the iPhone game Deep Deep Dungeon (link here), and I’m definitely happy with the results. The algorithm is definitely not optimal or optimized, but it works well enough and should get you started.

We start off with sixteen dungeon building blocks. Here’s a page from my notebook that shows what we’re working with along with my naming convention.

The prefabs that represent these can be found in Prefabs/Dungeon Building Blocks. These are what we’re going to piece together in order to create our dungeon.

In the DungeonGenerator object, you are able to specify the size of the dungeon – NumBuildingBlocksAcross and NumBuildingBlocksDown. The default values create an 8×8 dungeon, but it should work for most size specifications. I just tested a 1×8 dungeon floor (not very interesting), and a 100×100 dungeon floor (took a while to generate) – which both work.

Here is the basic algorithm that we use to generate a dungeon floor:
  • We start off by creating a grid of empty building blocks. The grid matches the size specified (discussed above), and the cells are defined in the (x, z) plane. (0,0) is in the bottom-left, (max, 0) in the bottom-right, and (max, max) in the top-right. 
  • At this point we iterate through the entire grid, bottom-left to top-right, and choose a ‘valid’ building block for each cell position. What’s a ‘valid’ building block? I’m glad you asked! 
    • If the surrounding cells are all empty, then we choose a building block type randomly. We leave out the ‘capper’ building blocks from this choice, which are the four blocks used to cap off dead ends (Nx, Sx, Wx, and Ex). 
    • If some of the surrounding cells are not empty, then we choose a building block that matches the existing paths. 
      • Let’s say we have a cell to our west that’s a passage from west to east. We’ll make sure that the block we choose has an exit to the west to match the existing path. 
      • Let’s say we have a cell to our east that’s a passage from north to south. We’ll make sure to NOT choose a block that goes west, since it would create a disconnect with the existing path. 
      • So basically we narrow down the possibilities based on surrounding cells, and then choose randomly from the valid building blocks. 
  • After filling out the grid in this way, there’s the potential that the algorithm has generated ‘islands’. Sections of the maze that are separated from each other with no connecting paths. There might be a way to update the ‘filling out’ section of the algorithm to eliminate these islands, but right now I deal with it through some post processing. 
    • I do a little bit of low-class pathfinding in the CellConnectedToCell() function to identify these islands and turn them into empty cells. There might be a better way to recover and connect the islands instead of deleting them, solid exercise for the reader. 
    • Right now I consider an Island to be any section of the maze that has no way to connect to the center of the grid. 
  • The final step in the pathway generation is to cap off dead ends. As mentioned above, there are four ‘capper’ dungeon building blocks that are dead ends. We go through the grid and identify any hanging passages that don’t connect to anywhere and cap them off with dead ends. 
  • After completing the maze, we choose a random location on the path for the stairs up (start position) and stairs down (exit position). 
And that’s it, we’re done! As mentioned above, there are some shortcomings and lots of potential optimization and improvements – but it works well enough.

Future Work
It’s not hard to come up with a list of future work for this project, since the possibilities are endless. Here are some ideas off the top of my head that should result in a pretty solid dungeon crawler: 
  • Add in some real graphics, animation, sound, models, etc. 
  • Create a real combat system, maybe stat-based and simulated or some sort of combat mini-games? Special abilities, magic spells, bonusus? 
  • Add an inventory and loot system. 
  • Add a shop/economy. 
  • Extend the random dungeon algorithm to be more interesting. The one included works well, but is bare bones. Some potential extensions/improvements are discussed above, and there are plenty more… 
  • Right now the dungeon building blocks are just basic passages, but there’s no reason they can’t be much more interesting. 
  • Create different dungeon floor exit conditions. Maybe some levels need to be completed by defeating a specific monster instead of finding stairs down. 
  • Make some real quests, and parameterize the dungeon to be different based on the type of quest you’re doing. Add some real storyline segments (talking heads, text, lots of possibilities here) that advance the story. Maybe add a branching quest structure? 
  • Develop a hero. 
  • Try using this approach for a different game genre. You could try making a FPS with random maps, for example. 
  • Add support for additional building block ’tilesets’. 
  • … and many, many more. 
What Can I Use This For?
Feel free to use this project for whatever you want, I only ask that you take the time to drop me a message and let me know what you’re using it for.

Good luck!

Oh yeah, one last thing – here’s a link to a thread on the Unity3D forums for MiniDungeon: http://forum.unity3d.com/threads/minidungeon-a-free-randomly-generated-dungeon-jump-start.72525/