Over the last several months I have been researching and experimenting with different types of procedurally generated maps. I was working on a top down, zelda-like game that used procedural generation to create the dungeons throughout which the player would explore, encountering monsters and hidden treasures. Development never got to far on this game, but it was a great learning experience and I got my maps to a state I was really happy with.
Over the last week, I’ve been doing more procedural generation for a game that my brother, Liam, and I are creating. It’s going to be a rather simplistic and casual game when done, but one of the most exciting things about it is that every level is completely generated from scratch, creating rich, varying, environments every time you play. You can check out what’s been done so far (as of this post) here.
Since posting that, I asked if people were interested in me writing up the process that my generation takes to create the maps seen in the demo above. I got enough interest that this definitely seemed worth while, so here it is!
PART ONE: THE BASICS
Before I explain anything, make sure you’ve actually seen how the generation looks in-game. If you missed the link above, see it here.
The idea for this game was to create a vast cave with interesting tunnels, pockets, and enclosures. I started off with a number of different methods that ended in very interesting shapes but nothing quite like how I wanted. I searched around a bit for different methods and ran into Chevy Ray’s example that he posted here (edit: dead link). I never actually took a look at the code for this (not sure if it’s available or not?) but I liked the basic approach he was taking, along with his results. My end method is relatively similar to what he was doing, with some variations.
CREATE THE MAP
The first thing that my generation code does is create a 2D vector (array), containing ID’s (integers) of the different types of cells. To start, I create a 400×300 size grid, all with the value “1″. In my case, ID=1 stood for walls, and ID=0 stood for empty space (titled floors, even though they’re not, really). Later on I add Water, which is ID=3, but that’s not important right now.
THE MINER
Once the map is created, I then create a “miner”. In my case this is actually just called a “Cell”, but it makes more sense if you consider it to be a miner. The miner is created in the center of the map (200×150) and is labeled as “active”. When generating the map, I create a loop that goes through every active miner, and runs their “dig” function. When the miner “digs”, it picks a random cell around it, that is not yet an empty space (ID=0) and digs it out, moving itself in that direction.
For example, if the miner was at 5×4, and decided to move UP, it would dig out the cell 5×3, and move itself there.
Whenever a miner digs, it also has a small chance of spawning a new miner in a random direction. In my generation code, the chance is about 8% that a new miner is added.
If a miner has no walls surrounding it (ID=1) then it unactivates itself, and stops digging. If this miner happens to be the last miner alive, then it just moves around until it finds a new wall to start digging.
CALL OFF THE DIG
Depending on how you want your maps to look, there are a number of different ways and times you can stop the miners from digging. You can stop the digging when there is only 1 active miner left, which is what I was originally doing. The problem with this though, is sometimes you’ll have gigantic maps, and sometimes your maps will be 4 cells big. It’s too random for me.
Instead, what I decided to do was say that once 400 miners had been added, STOP digging. 400 is just a random number I chose, after experimenting with higher and lower values, and this size seemed to represent a good amount of miners for the size of level I wanted.
WHAT WE’VE GOT
At this point, my levels were generally looking like this:
The general shape is awesome (in my opinion) but it’s cluttered with horrible little bits of dirt everywhere! Which is why we needed ….
PART TWO: CLEAN UP!
So, as you can see from the image above, the map definitely needs some cleaning up. If we were to stick a player and run around in that it would feel horribly awkward and cluttered. This had me stumped for a little bit, because I was trying to think of ways to alter the original generation to remove these oddities. In the end though, I decided it would be much easier to simply run through my map one more time, and remove anything I found unfitting. So, I ran through every cell in the map, checking the following with each cell:
LONELY WALLS
These cells were walls sitting all by themselves with no one around. If I found any walls that had no adjacent walls (up/down/left/right) I would remove them.
STRANDS
These cells only had 2 adjacent walls, in most cases creating long strands of walls. These looked really awkward and just took up space, so I removed all of these as well. This also gave the map edges a more rounded look.
TINY ISLANDS
These cells were a group of 4 cells. I removed these as well.
This might sound like I over do it, but ultimately the end results are a lot cleaner:
PART THREE: WATER(FALLS)
This is by far the easiest part of the entire thing. I had a few people think that the water actually may be part of the generation, but, it definitely isn’t. Water is added in at the very end, after we have the result above.
THE POOLS
The pools at the bottom of the map are really simple. No, they aren’t generated by waterfalls, and no, there isn’t some magic algorithm that makes them. All I do is grab the lowest empty cell (ID = 0) in the map, and fill every cell 20 cells high from that point up, with water. That’s it.
THE WATERFALLS
The waterfalls are also really simple. I grab 4 random points that are adjacent to a wall (above it) and create that point as the start of the waterfall. Then, the water just automatically keeps moving down until it finds a wall below it, at which point it moves left/right until it either can’t anymore, or it can move down again. Once the water can no longer move down, it stops, renders out the waterfall (to a tilemap) and removes itself (well, the thing that generates the water fall does – obviously the graphics for the water doesn’t).
PART FOUR: TILE PLACEMENT
CONCLUSION
That’s it! Hopefully it was an interesting read and helped you make your own maps. If you somehow missed the live example of this in action, you can find it here. Feel free to post any questions or comments, I appreciate them! 
Simple but very effective! Thanks for sharing.
Hi Noel, congrats about the post, it’s a good way to start. Thanks.
But I have a question, what do you mean with ‘cells’? It’s like a array of image without range? Sorry for this question, may be I am a little noobie for understanding this part at all.
Thanks again.
Glad you found it useful! By “Cell”, I mean an individual item in the 2D array (in my case Vector, since I’m using AS3). For example, map[50][32], or map[x][y]. I’m not sure what else to call it
Thanks for your attention. Now I understand really what you said.
Do you has some links what you recommends to read about procedural generation? And about Fractal, do you know something about it? (I am developing a game where I want to use fractal to create clouds.)
Thanks again.
Hmm. I’m not aware of too many links, but some good ones are Adam Saltsman’s post on procedural generation, and this tigsource topic.
I’m afraid I haven’t used or heard of Fractal.
Thanks for the links. I will see them as soon as possible.
About Fractal, may be this helps: http://en.wikipedia.org/wiki/Fractal
It’s a useful stuff, I guess.
Cheers
Thanks alot for sharing!
Even though I am very new to programming, I was able to reproduce your method without problems using Java/OpenGL.
http://img508.imageshack.us/img508/5298/cavegenerator.jpg
Generates in 10ms!
The only thing that I haven’t figured out yet is the 2×2 detection of cells in the “air”.. I can only imagine a way with many, many IF()s. Any tips?
Thanks again for this great post.
Whoa, very cool! Glad you got that working so well
For removing some large blocks of cells, I did have to loop through everything once doing some general checks with if statements. For the most part I was able to keep that fairly to a minimum though.
But yeah, I’m not sure of any good ways to do this without a few if statements. I would go along and check if a cell was dirt. If it was, it would check cells above it and below it, and depending on what it found, it would remove itself (and potentially the cells around it as well)
I just want to say that this is very awesome, and I hope to be able to try my hand at implementing something like this in the future.
Hi! I have a question. When the miner chooses a tile around it. Does it choose only from the n,s,e,w tiles or all tiles including the diagonal ones? What about when a new miner is created? What is its current position and should it be near the miner which created it? Thanks!
It only chooses tiles in 4 directions. You could potentially do 8 directions, but I simply kept it NSEW as then there wouldn’t be breaks in tunnels or walls. When a Miner creates a new miner, it also sets it directly one tile from itself (again, only in 4 directions). Once it places a miner, it makes sure not to move right where it just put it.
with your random generated level, how will you know where to place your player?
It really depends what you want to do, and what kind of game it is. For the platformer game that I used this method for (and the reason I developed this method in the first place) I generally placed a pre-created room on the edge of the map, and attached it to the nearest open space.
Actually, you can see the room in all of the screenshots of the post. There’s a little rectangular room at the top-most part of every map. I decided, in my case, I wanted the room to always be at the highest place possible (while still having enough space to actually place the start-point)
You could probably use a simple algorithm to choose a random place that is reasonably open and already existing as well (ex. search all floors looking for an open rectangle)
Hey Noel, nice method you’ve got here. I’ve been trying to replicate your results and have had some success. My dwarves are digging out some random looking caves, but I’m not getting anywhere near the same kind of tunnely, snakey paths that your pictures show. I’ve tried the 8%, 400 miner, 400×400 map, like you have written here, as well as some other parameters, but I just keep ending up with one big room that has a few short tunnels coming out of the sides. Kind of reminds me of a bacteria with little celias. Do you have any suggestions for what I could possibly be doing wrong, or are there any steps that might have been left out concerning the algorithm that might impact this behaviour? My company is developing an RPG for the android, and I am trying to add a dungeon crawl mode in addition to the story mode, so this algorithm really peaked my interest. Cellular automata is good, but I really like the shape of the caves shown in this post. Any help is appreciated!
Rono
Valorware
Thanks bro, awesome tutorial
https://www.facebook.com/photo.php?fbid=484528224892539&set=a.452720514739977.111563.100000060975334&type=3&theater
This is great! A strange method, but very simple. I played the game for at least a half hour
I think this’ll help make the caves in my game nice and unique!
Could I have some source. I am having some issues with the miners. Are the miners stored in the same array as the world?
Hi,
That is a really intereasting approach. My current algo is very simple, it moves through the tilespace and on a random event (around 5%) it removes a dome shaped space, flat floor (random sized) this sounds odd but each Y element of the triangle also has a random element added or removed to it. The end result is a pretty nice cavern. I’m going to try your miner approach as I prefer the look of your caves to mine they look better. Thanks for sharing