In the last news update I went into some detail about the creative process behind making a game, and came to the conclusion that I wanted to make an action rogue-like (ARPG) in the style of the classic Gauntlet. So, I have my design brief with a list of things that I want to achieve and at the top of the list is the procedural creation of dungeons for our player to explore...
Choices, Choices...
When it comes to generating procedural content, there are a few problems to overcome and some hard decisions to make, but the main one is how to produce the content! Since I'd never really done procedural generation of any type in my games, I obviously had to research the subject a bit, and my first port of call was downloading the Spelunky source. Spelunky is the great grand-daddy of procedural GM games, and one of the most well known aspects of it is the way it creates a random room for the player from some pretty simple rules... so I wanted to check it out and decide if this was something I could implement for myself.
After looking through the code and reading this fantastic article from Darius Kazemi, I realised that this "chunking" technique isn't really what I'm after and I had other ideas for my own game. So I continued my search and tested various other ideas, from cellula automata (nice, but too "cavey" for my needs - you can find a great example of how it works here) to drunken walks (too random, and created more "organic" feeling maps, like those in Nuclear Throne).
Binary Space Partitioning
After a fair bit of playing around with prototypes and another fair bit of Googling, I came upona system for making my game rooms called Binary Space Partitioning (Also called Binary Trees). This is used widely in computer graphics when rendering scenes and you may not immediately think of dungeon generation when you read up on it, but the concept behind binary trees struck me as an ideal way to split up a single area into dungeon rooms.
Stripping away all the technical stuff, binary space partitioning is simply a method of dividing an area into smaller and smaller pieces. You take a given area, generally called a "Leaf", and then split it - either vertically or horizontally - into two smaller Leafs, and then repeat the process on the smaller areas over and over again until each area is at least as small as a set maximum value. Below you can see a tree graphic of how this works:
Splitting Grids
So, BSP was the way to go and with that decided, I fired up GameMaker: Studio and started working on the code. The obvious choice for achieving my goals was a DS grid. I could have used a 2D array, but I find DS grids easier to use, and they have a fair bit of extra functionality built in which may be useful later on.
First thing I did was to create a room that was 400x400. I had no real idea quite what to expect, but since my game was to be low res with a base tile size of 8x8 , that room size will give me 50 tiles to a side which seemed a decent number to work with. I also created a Macro for the base tile size (called tile_size) and set it to 8. I could have just used "8" in my code - and it would have been quicker to write than tile_size! - but I've learned that "hard coding" important values throughout your game is a recipe for disaster, especially at those early stages. I could still change my mind about the visual aspect of the game, and changing "8" all though my code would be a chore, so at least this way I only need to change the macro to a new value and the rest of the code should just "work".
Next thing to do was decide how to go about splitting the grid and storing the created areas for later. I figured that the best thing to do would be to simply store the number that corresponds to each split (leaf) in the grid itself, clearing the area to that value. So, split one would create areas 0 and 1, then split 2 would create areas 0, 1, 2, and 3, etc...
It was a simple task to set a number of iterations at the start and have the script store the last highest grid value (starting at 0), then loop through each of the areas and split them in turn along either the horizontal or vertical axis to create more areas, incrementing the grid value as we go. At first I made the position of the split as a random value based on the width/height of the axis along which the split had to occur, but I quickly found that this gave areas which were way too long or too narrow to be practical and so eventually went for creating the splits in an area that was half the length/width.
I also had to add in some extra code to check a split's length and width, since I didn't want any areas to be narrower or wider than 5 grid squares. If a split was detected as being too small, then the code just skipped that one and kept on with the next. This meant that even if I specified a large number of iterations, I would always be guaranteed areas of the minimum correct size without having to worry about errors or illegal areas. You can see how the code worked out in this GIF:
Note that the gif was made thanks to a debug script that I made for the game. I find visual feedback really important when coding things, and try to make any debug output I have as clear as possible and as visual as possible. In this case, I draw a a grid of 8x8 pixel tiles, then parse the DS grid to get the value. Each possible value has a colour assigned to it on startup, and this colour is then used to draw it in the debug script, along with the value itself.
Turning Areas Into Rooms
As you can see from the GIF above, this splitting of the DS grid into areas works well, but over a number of iterations the splits create areas more or less similar. The system was still too "generic" and I wanted to have the rooms be positioned less obviously... Really what I wanted was something that would end up looking similar to this (image from donjon.bin.sh):
What to do next then? Well, my original plan was simply going to be to add walls around the edges of the splits and then open "doors" in the edges to create the room system, but that was going to make the rooms feel like a house rather than a dungeon! And with the rather uninspiring layout that the BSP was giving me I had to do something to make it more interesting. And that something was to further split the areas!
Think about this... an area that is 10 by 7 grid squares in size. There is no reason really why that area can't have a "room" within it that is 5 by 3, is there? Basically, every area created can have a space designated as the "room" which is where I will spawn the walls. The next gif illustrates this too:
These "room" areas, I flagged with the value -4 in the DS grid to signify an "empty" grid position, which meant that adding walls to these areas to close them in was simply a case of parsing the grid and if the value was greater than -4, create a wall instance. Hooray! I was creating instances already, so things were going well.
Joining The Dots
However it wasn't to be that easy. Once I had a few hundred walls and some empty room areas created, how the heck was I supposed to join them up? I tried several things at this point - like taking random points along the edge of each room and projecting a line outwards and if there was another empty space along the line, destroying all the walls between - but nothing really worked for me, until I hit on the idea to use the path finding functions!
For my idea to work though, I had to rethink the method for creating the room walls, and decided on creating a 2D room array that would hold the x, y, width and height of each room area that is created. This was then used to flag the DS grid positions around the room as being "walls" (I created another Macro value for "bsp_wall" to make parsing the grid easier later), but note I'm not actually creating anything now, only marking the grid with set values. I then opened "doors" in these walls by setting the DS grid for the square to a different value - again, easy to parse later - which was simple enough to do now that I have the position and size of each room. I made sure that each "door" was a random distance from each corner and I also limited the length of an edge required to support a door, so some walls wouldn't get any.
That image shows the debug output for the BSP generator, and for me it was like looking at the Mona Lisa! I could finally see this whole thing coming together and an actual dungeon with personality was starting to emerge. All I had to do now was join up the rooms through the doors using my path finding idea.
If you look at the above image you'll see that there are white squares in each of the room areas. Those are simply pathfinding markers that I added into the script that creates the rooms (just random point within the room area). My idea was to use an MP Grid to pathfind from one room to the next, and that way ensure that all rooms are accessible, since if the pathfinding function fails, it returns an empty path. I can now check for this, and restart the room if it happens!
Okay, so I now had a pretty good method to check for "valid" rooms, but that still didn't solve my corridor problem! Or did it? When you create a path using mp_grids the path has a point defined for every grid square it goes through... which means that I could now get the x/y position of each point of the path from room to room and flag it with a special value for corridors. In fact I could also check either side of the path and see if the grid value was anything other than -4 and flag it as a wall, making those linking corridors that I was after.
The Finished Map
After a good few days of work, and quite a bit of trial and error, I finally have something that is more than workable for my game. I have a DS grid which contains all the base data for the whole room - walls, doors and empty areas - and I can be sure that all the important areas of the grid are accessible. I also have an array of values which I can use to get the position and size of any areas within the room, meaning that I can rapidly look up a single room and do something with it if I want - like spawn enemies, chests, shrines, etc...
The whole process of creating this engine was starting to really excite me now, especially after I started playing with some of the basic input parameters like minimum area and the number of binary splits to iterate through and discovered how wildly different the results could tun out (you can play around yourself with a version as there is a live version at the end of this post, and if you want to get a copy, you can find it also on the Marketplace). However, as much fun as it was tinkering with the engine, it was time to move out of the conceptual space and get into the "physical" space and actually start spawning instances and thinking a bit more about how to turn this cool little generator into the full game I had in my head... so, more in the next news update, but until then, you can play with the dungeon generator scripts from this interactive demo I made.
