Procedural Generation 1

Whenever I need a break from my regular programming and pixelling duties, I usually like to challenge myself with some sort of programming problem, and see if I can overcome it. I'm not educated in programming, and I don't yet thoroughly know any programming languages outside of GML (just odd tidbits of Java, Javascript, PHP, CSS, and Python). My new-years resolution for 2009 was to fluently learn at least one other programming language, and I plan to stick to that. This will probably be Flash ActionScript, and if that goes well, I'll delve into either some Java or C++.

So until then, I'll continue using Game Maker to prototype my little self-challenges.

My most recent endeavor of such was an A* Pathfinding method, which was a success...



Ever since I first stumbled upon Dwarf Fortress, I've been utterly obsessed with the idea of a procedurally generated world (by the way, a great wiki on Procedural Generation can be found here). I don't really think about the game that much, I just love discerning the steps as to how these sorts of things are created. I read up on Dwarf Fortress and, if I remember properly, I am pretty sure the programmer, Tarn Adams, wrote somewhere that he started by generating a height-map.

Now, I had no idea what this was, but I'd seen the Dwarf Fortress world maps...

(click it for full-image)


... and I had to get in on this secret. And so I did a whole bunch of research on height-maps (yes, this IS what losers like me do on their free time!). Basically, the height-map generating method I looked up had you place a whole bunch of coordinates evenly across the map. Those coordinates were all given height values within a certain range (or something like that). The, you had to basically create coordinates between all those coordinates, which would set their height by deriving a value that was a mean value of all the surrounding coordinates (with a slight bit of randomness). Basically, you keep on creating in-between nodes like this until the map is smooth enough and you have sort of a mountain-range thing going on.

Now that was probably the most hillbilly explanation of height-map generation ever, but I'm pretty sure I understood the basic concept. Unfortunately, I'm a fairly crappy coder, so for some reason I couldn't get the blaming thing to work. So then I went on this wild rampage where I studied all sorts of different PG algorithms and methods, and I finally found one that was easy, and gave very pleasing results.

Basically, it was a fractal method (which I'm pretty sure height-maps sorta are), but the way it was explained made things a lot simpler for me. Instead of using height values, I basically divided the grid into 2 different surface types: water and land.

So step 1 was to randomly splatter water and land on said grid. I liked this part, it was easy. I made it so you could choose % values, so you could have 50% of the map start land-covered, or 25% if you wanted more of an island-like world generated. Anyhow, here's what it would look like:



So basically that was a 128x128 grid, divided into 16x16 blocks. Next step was to break it into 8x8 blocks. After doing so, I would scan through each block, and have it choose to be either land or water. Basically, if it was mostly surrounded by land, it had a better chance of being a land block, otherwise it would have a better chance of being water. So after one loop, this is what happened:

-->

Hey, this was sorta working out! Notice how the second image looks sort of like the first, but with a little more detail? This is basically how this fractal method works. It creates more detail from less by breaking the grid down. I kept on breaking the grid down until it got to 1x1 blocks, so basically right down to the pixels...

--> -->

Now that's what I'm talking about! This is starting to look like a little map even. Just one more loop did the trick... but it was kinda hard to see, so I made another loop that darkened all the pixels that were next to water pixels, so it was easier to see the shape of the land...



And ladies and gentlemen, we have ourselves a pretty little grid-map. Sure, it's kinda bare now, but it'd take quite a bit more work to get mountains and stuff in there. Here's some bigger versions of some worlds I generated with this:




You might have noticed that I had the edges of the map "wrap around" to the other side, so the land actually connects. While this is physically impossible, because a square does not represent the shape of a spherical world spread onto a flat plane, it still can give the player the illusion that they're walking "around" the world. I basically accomplished this by, when the cells read the surface-types of adjacent cells, making the blocks on the edges of the map read the tiles on the complete opposite side of the map, causing them to match up just as if they were adjacent to each other.

This was a lovely success, to me, and I've been exploring more procedural generation ever since, in hopes of one day applying all I've learned to an awesome (multiplayer, maybe) computer game. But no no no, I'm not done yet. We now get to discuss my most-recent procedurally generated adventure!

Now, I figured since I had a procedurally generated map, it would only make sense for the other parts of the world to be procedurally generated as well. But I can't simply apply this same formula to every part of the world; think of a cave shaped like that, it wouldn't be convincing at all -- caves should be more claustrophobic, with narrow passages, occasional open caverns, and tunnels. It has to feel underground.

So next thing I hit up was making a cave generating algorithm. Firstly, I had tried several that I'd found randomly across the internet, converting them from other languages into GML... but I was never satisfied. Many of them took a long time to generate, and used really piece-meal approaches for achieving that rugged, yet enclosed cave-like look. So I figured it was time I tried to write my VERY OWN algorithm. I can apply things I already know, but I'm not usually not a very apt problem solver, I just hack'n'slash my way through code until things eventually work (only occasionally causing peoples computers to crash, instead of... well, always).

This is the premise of a lot of cave generators: start with a filled in room, and place a bunch of different rectangle empty-spots around the room. Then you use the algorithm to carve paths between these rooms and round the edges. This is a very nice tutorial, in which he places random empty "blocks" around the room, and then cycles through the cells, using the surrounding cells to determine whether that particular one becomes a floor or not. Afterwards, he scans through the level and seeks out any isolated areas (that are separated from the bulk of the level) and basically carves a tunnel connecting it to the cave's main body.

The result is something like this:


This looks very nice, but still wasn't what I wanted. To me, it looks too uniform. Every cave you generate is forced to fit inside this square, and everything is sort of in one big bulk of an area. I wanted caves that stretched on in different directions, and branched out into little passages. I wanted my caves to be caverns, to be tunnels, I wanted them to take you somewhere. So, after about 4 consecutive cups of coffee (see diagram for more info) at 4:00 AM, it hit me -- and here's what I did.

I do not create a bunch of empty blocks. The first thing it does is creates a start point. I usually put this in the center of a large grid (results are best when the size of the grid does not limit the cave's shape). A cell is carved out here, and that cell is added to a list. Then I create a loop. This loop starts with the first item on the list, and works with each cell in the list until it reaches the last one. With each cell, I have it check a random amount of adjacent cells and carve them out, then adding them to the list (thus extending the loop).

Here's the trick: there's a random chance that a cell will choose not to carve out any further. If this does happen, that path closes, and we move on to the next cell on the list. If that next cell reads that there are still other open paths, it will do the same as above. If it reads that it is the last open path left, it will NOT have a random chance of ending. Instead, it will have an increased chance of carving out adjacent cells.

What happens is you get multiple paths spanning out, changing direction randomly (lowering the chance of them changing their "carving direction" results in longer, narrower tunnels). These branches all eventually stop, but the last one left always keeps going. But eventually, the last path standing will come to a point where it circles around and has no adjacent cells to carve out anymore, meaning no more cells are added to the list, and the loop comes to and end.

This results in caves of many, many different sizes and shapes. Sometimes the randomness allows the "last path" to spread out quite far, and it will create more branch paths. But if you want to limit it, you can create a span-limit or a cell-limit, basically disallowing cells to carve further if they are either a certain distance from the beginning point, or if the maximum amount of "carves" has been reached.

Here's a few results using this system.



You'll notice little up and down ladders in there. Those are the exit and entrance ladders, which would essentially take you out, or deeper into the cave. They could be stairs or whatever. Their placement? Easy. One is placed at the starting cell of the algorithm, and the other is placed on the last cell handled by the algorithm. In those two cased, they were far apart, which works well, but in some cased the two ladders end up very near to each other. In most of these cases, the cave carved out a "roundabout", and came back to where it started.

This I actually would like to use as a gameplay element. In such situations, you could easily progress further, but the game would calculate the situation and count to the tiles created in the middle of the algorithm (each tile would have a number keeping track of where it was on the list). Usually in these situations, the middle tiles will be farthest away from where you start and finish, and you could hide special items in these places, so the more curious players could wander around more.

The treasure placement is quite bad in those shots, because I wrote it really quickly. But Lynx from the TIG Source forums had a great suggestion. He said that I could use A* Pathfinding to find the shortest path from the entrance to the exit, and number each tile according to their distance from this path. The tiles that were furthest away from the path (highest numbers) would be more likely to have treasure, because you would have to go further out of your way to get them.

Anyhow, that was today's little adventure with procedural generation. Keep in mind that I am still a beginner with this, and I may have made mistakes in my explanations at certain points. This is merely a learning experience that I find interesting and want to share with you all. If you have any corrections to make of things I've said here, then please post them here or email me and I'll address them in my next post, when hopefully I'll hit up another PG challenge.

Also, the .gmk source for the cave generation are available on request if you'd like to have a look at them. For the rest of you, here is an EXE that you can download if you want to see these generated in action!

DOWNLOAD CAVE-GEN

If you liked the article, please drop a comment and let me know. Thanks for dropping by!