Research Paper

Introduction

Spelunkey

If you've ever been big into role playing video games chances are that you've played a Rougelike game before. Popular titles that fall into this category include Spelunky, FTL: Faster Than Light, the Diablo series, the Pokemon Mystery Dungeon series and the Binding of Issac. What all of these games have in common and by definition makes them Rougelike games is procedural generation. In simpler terms this means that every time the game is played new maps are generated. This helps to solve one of the major problems of  designing a game; replay value. For the most part all of these games deliver that via creating a new and unique challenge for the player each time they play the game, so that the player has to constantly replay the game every time they fail until they master the core mechanics of the game. Therein lies the problem for many games of this genre though. By making the core mechanics of the game the major focus the random levels loose some of their novelty. Players can start to prepare for what the game throws at them because once they play it enough the game starts to look the same. All of these games, save for Spelunky are dungeon generator based. That means rooms and corridors are being generated each time the player loads up the game. Spelunky was different though. Not only was this game a platformer, but it took place in caves. I started my senior seminar with the goal to create something new and innovative in the game world, so I thought why not combine cave and dungeon generation? This would lead to whole new and exciting ways for people to experience the Rougelike genre and would add another layer to the level generation that players have come to love. This would ensure not only that maps would be wildly different from one play through to another but also potentially raise the replay value of the game.

Research

The first thing that I really needed to find was a decent cave generator. After looking around I found that the only doable way for me to do that was with cellular automata. Basically what it does is it sets a fill percentage for the area that its run in and then runs a really interesting smoothing algorithm, but more on that later. So now that I had my cave generating algorithm I needed some way of doing normal dungeon generation long with it. During my research I found that, much like anything in programming creating a dungeon generation algorithm can be done in several ways. Everything from procedurally constructing structures off of a central room like how a real underground dungeon would be built, to placing rooms around randomly and running a maze generator in the space left around the rooms. All of these could be useful for my project but due to the nature of it I had to look at all of these, keeping in mind that a cave generator would need to be run with them.

After looking at all of the generators that I found I determined that really only two would work in the ways that I needed them to. The first was the dungeon digging algorithm which could have the cave generation run beforehand on the entire map and then have the digging algorithm work as normal. The main problem with doing the generator this way would be that I would have to implement some kind of way for each block to know what section it is a part of. If I could do that then each block that makes up the corridors would know weather they are adjacent to a cave formation. If they were they could then delete themselves connecting the cave formations and the rooms. This method creates several problems though. The map wouldn't look very good and would be full of holes. Quite possibly all that would wind up differentiating the rooms from the caves is that a room would just be a cave formation with a giant chunk taken out of the center. It just wouldn't look right. On the other hand the corridors would be very cool having a passage with several branching paths coming off of it would lead to some interesting formations and maps. Ultimately though I decided that I couldn't go with this due to the lack of distinction between rooms and caves.

The second algorithm that I took a look at was BSP Tree, otherwise known as Binary Space Partitioning Tree. At first glance this had a vast number of advantages over the digging algorithm, first and foremost being that the rooms and corridors were placed at the very end of executing everything else. The whole time that this is running prior to placing the rooms it is dividing the main area into two smaller subsections. It then divides those subsections into smaller subsections branching out like a tree. Each of these subsections is called a leaf. Seeing how this worked made me very excited because I would be able to give each leaf a chance to instead of continuing to split into leafs it could do the cave generating algorithm in that larger leaf. The other leafs would then continue the algorithm until the leaves stopped splitting. The rooms and corridors would then be generated at this point and since the corridors are connected to the leaf and not the room generated inside connecting the caves to the rest of the map wouldn't be difficult at all. Even the addition of the cave generator doesn't change the way that BSP Tree works at all so integration should be fairly easy.

Cellular Automata

  

Simple Cellular Automata

In order to understand my algorithm, first there has to be an understanding of how the two algorithms that I based it off of work. The first algorithm is Cellular Automata. This is very different from just about every other dungeon generator, mostly in the sense that a dungeon isn't being generated at all, rather it's just a cave shape that gets created. In comparison to how the other generators work the first step here is fairly easy and all that it needs to do it is one extra piece of information beyond what normal generators need. All this algorithm needs passed into it at the beginning is the height and width similar to normal generators, but it also needs one other thing; a fill percentage. All that a fill percentage does is determine the likelihood of a given action taking place.

    

After Smoothing

After Connectivity

Describing how this algorithm works is also a touch easier than the other one. Thinking back to the room of tiles example, imagine that each tile in the room had a certain percentage chance to be filled. This is where the fill percentage variable comes in because this really gives the base for everything that is about to happen. Figure A gives an example of a generation run with somewhere around a 50% rate of filling any given block. This would be the starting point that a smoothing algorithm would run off of. What this would do is make each tile section more like it's neighbors. By this I mean the usage of the four or five rule. The four or five rule states that if the tile is in a state that at least four of its adjacent tiles are in then it stays that state, if not then it changes to the opposite state. Similarly if a tile is in a state and five of its adjacent tiles are in the opposite state then the tile changes to match. In this case this means changing from white to black or on to off. After this has happened four to six times or so this smoothing algorithm stops and the cave might look something like the second figure.

This kind of cave generation would be very problematic for a dungeon generator mainly because of the lack of connectivity between the sections. This can be solved by an algorithm that basically just connects the separated areas by digging tunnels between each of the sections. This step in the algorithm is fairly complicated. The simplest way to understand how this works is with lines being used to connect all regions.  Once that's done the program would dig tunnels connecting the regions over the lines. At the end of this the cave should look something like the third figure.

BSP Tree

Showing two separate "leafs"

Showing four "leafs"

    

Showing the fully connected map

Now that the other algorithm is out of the way you can see how it would fit into BSP Tree. BSP Tree works fairly simply and is easily understood with this simple analogy. Think of a room with floor tiles, now divide that room in half at a random point along the x or y axis. At this point the room should be two rectangles. Now divide each of those two halves in half the same way. The first division gives something that looks like the figure A dividing the room into two subsections A and B. The second division gives something that looks like the figure A divided into A1-B2. After doing this a couple more times this algorithm would give something similar to the figure B.

This is a dungeon generator so there would need to be some rooms. The algorithm does this by checking the size of each of the generated sub sections and generating a room inside with a smaller height and width than the section it is within, but what good are rooms if they aren't connected? So this algorithm goes and connects to the origin (center) of each of the generated rooms to each other with corridors. Why is this specific algorithm useful? Why not just place rooms randomly on the grid to begin with? Well, one of the reasons is that it ensures that there are no overlapping rooms, which is a major problem that most other methods of dungeon generation have to address within their algorithm. This one avoids that all together because it ensures that two rooms can never overlap. This also makes solving room connectivity, the other most common problem for level generators, fairly easy as well.

Room connectivity means simply that all the rooms are connected. This can be a problem for most generators because they have to go through the process of picking a random point on the wall, making a door there and either running a maze generating algorithm and trimming dead ends or placing straight corridors and connecting them at right angles. For this algorithm however it's pretty easy since the dungeon has already been subdivided. The algorithm can just place corridors using the width and heights of the generated rooms to decide where to place the corridors. The lengths of the corridors can be determined using the widths and heights of the generated rooms, so ensuring connectivity shouldn't be too hard.

Overall the advantages of this algorithm are ease of use and general neatness of the assembly. There are some negatives of using this method however, for example no more than one room can be placed within a "leaf" so this can lead to dungeons with larger gaps between rooms and a potentially blocky overall look to the dungeon.

The Algorithm Explained

Finished Base for Map

Now that you know how the two algorithms that are being combined you can understand the combined algorithm. Using BSP Tree to divide the map into subsections the cave generation algorithm could be run in 35% - 40% of the leafs. This would be done after only four or five branches so that the cave sections would be larger than the rooms. After the caves have been generated then the leafs that don't have anything in them would continue to be split into leafs for another two or three iterations. After this, rooms would be placed in the vacant leafs and they would be connected via corridors. The corridors would be connected to the origin of each leaf because that would ensure a connection to the rooms. The corridors would be connected in the reverse order of the leaves that were generated, so when a block was split in half and rooms put in each of those a corridor would be placed connecting those two rooms across the gap.

This Algorithm and Game Design

Brainstorming Methods

Concept Art

How does just this algorithm fit into the larger picture of a game? Well, for the most part this wouldn't have even started to be worked on until over a month into the design process, most times longer. This would come long after the game has been funded in some way. Most likely before the game is even funded there will be concept art, some kind of basic idea for the game itself. Once that is done then production would begin, this would consist of prototyping and brainstorming about how the game would work. This would be expanding upon the information and ideas within the initial concept. Along with that more concept art would be made by the creative department, and basic modeling would begin.

On the tech side the bare essentials would start to be made such as this algorithm. The bare essentials in this case are the things that the game can't be run without. The algorithm that generates the whole level the game is played on is kinda important, where as some specific enemy's AI isn't nearly as important. At around this point basic testing would start, soon followed by alpha and beta testing. Really once alpha and beta testing have begun most of the heavy coding has been done and there should only be minor changes made. But this small asset, this one algorithm is what a whole rouge like game is built on the back of.

Not just this part is important though, what would it be without the main character or the enemies? What would the game feel like without any sounds or art making the different enemies easily identifiable from one another different? It just wouldn't be the same. Moreover it would most likely be incredibly frustrating getting no feedback or information from the game, so really there isn't one most important part. All of the parts of the game are equally important because if it is missing just one key part the overall feel of the game is lost. That is quite possibly the most important part of any given game, the immersion. This all goes into the idea of creating a unique experience for the player every time they sit down to play a game. That game has to feel different from every other game, otherwise what was the point of making it?

Works Cited

Adam. (2013, November 2). The Cauldron – A random dungeon generator (Part 1) [Blog post]. Retrieved from The Ant Ranch website: http://theantranch.com/blog/the-cauldron-a-random-dungeon-generator/

Anderson, M. (n.d.). Dungeon-Building Algorithm. Retrieved October 13, 2015, from Rouge Basin website: http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm

Basic BSP Dungeon generation. (n.d.). Retrieved October 28, 2015, from Rouge Basin website: http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation

C, D. (2011, April 20). A Handful of Sweet Arse Dungeon Generators [Blog post]. Retrieved from The Dungeoneering Dad website: http://thedungeoneeringdad.blogspot.com/2011/04/handful-of-sweet-arse-dungeon.html

Chad. (2015, May 18). A RANDOM-DUNGEON GENERATOR FOR PHASER.JS [Blog post]. Retrieved from PERPLEXING TECHNOLOGY website: http://perplexingtech.weebly.com/game-dev-blog/a-random-dungeon-generator-for-phaserjs

Eskerda. (2013, December 22). Dungeon generation using BSP trees. Retrieved October 28, 2015, from Eskerda website: http://eskerda.com/bsp-dungeon-generation/

Hely, T. (2013, November 1). How to Use BSP Trees to Generate Game Maps. Retrieved October 28, 2015, from Tutsplus website: http://gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps--gamedev-12268

Lague, S. (2015, February 9). PROCEDURAL CAVE GENERATION TUTORIAL. Retrieved November 2, 2015, from Unity 3D website: http://unity3d.com/learn/tutorials/projects/procedural-cave-generation-tutorial

Nystrom, B. (2014, December 21). Rooms and Mazes: A Procedural Dungeon Generator. Retrieved October 13, 2015, from Journal with Stuff website: http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

Procedural Dungeon Generaton. (2011). Retrieved October 15, 2015, from Future Data Lab website: http://www.futuredatalab.com/proceduraldungeon/#algorithms

Random Dungeon Generator [Blog post]. (2015, September 2). Retrieved from Big Bad Waffle website: http://bigbadwofl.me/random-dungeon-generator/