Saturday, January 1, 2011

Cave/Dungeon Generator Breakdown

I've been requested to write an exposition on my level generator-- So here I go!

First off, you can download the functions used to generate my levels HERE
If you don't have Game Maker, just open the file in any text editor you'd like. #define denotes a new function.

The breakdown:
To function, my level generator is based on a grid of true/false booleans. True means the space is filled in.

The very first thing my generator does, is go in and fill every space of the grid with TRUE. And here, we run into the first variables my generator works with: Width and Height.

WIDTH - Defines the width of the grid
HEIGHT - Defines the height of the grid


Next, my generator selects two random points on the grid as START and END points. If they are too close or too far apart, the generator will select another set of points, ad nauseum until it selects two points it's satisfied with. Two variables are used for this:

MINDIST - The minimum distance between start and end
MAXDIST - The maximum distance between start and end

Now, the basics are pretty much covered. That's all the setup it takes to begin generating.

The next thing it does is enter a while loop, denotated by a variable called 'keep', a boolean variable so that we can abort the generation at any time.

My generator works on a random 'path carving' system. It's direction is randomized, with a chance for it to change every loop. Although the direction is randomized, it is tailored to have more probability to go towards the END point, which is the ultimate goal of the generator.

DIRCHANGE - This is a probability(out of a hundred) that the generator will change direction.

The path carving goes in a single unit of it's direction every loop cycle. As this is going, if the path gets close enough to the END point the direction will stop being random, and the path will be carved straight to the end.

KILLDIST - The distance from the END point at which the path will stop moving randomly, and move straight towards the END.

Quick stop: There are only two conditions where the generation will stop:
1) The carving point hits the END point.(desired)
2) The loop iterates over 1000 times. I created this as an initial failsafe, however, and it might not be necessary for you. Might cause trouble with larger map generation where the iteration really do go over 1000.

So, while the generator is going along it's merry way, it has a chance to create a tributary. Although this is a term for a river branch, I could not think of anything better at the moment. It's the same idea as a river, though. Tributaries use two variables:

TRIBUTARYCHANCE - A probability that the generator will make a tributary
TRIBUTARYKILL - A probability that the tributary will stop in it's tracks

My tributary carving is done from creating another loop within the original while loop, almost identical to the original loop for initial path carving. Tributaries act on the same DIRCHANGE variable to change direction, but are not tailored to go towards the end point.
With the TRIBUTARYKILL variable above, the tributary can also stop at any moment.
If the tributary makes a turn and hits a block that has already been carved out, it will also stop.
As a twist, if a tributary hits the END point, it will NOT stop.

Those are the basics of the cave generation.

Smoothing is operated by a simple algorithm that iterates through the grid and does neighbor-checks on the grid to see if the grid point should be solid or free. They're very easy to understand. I wrote four different variations, all of which give very different and interesting results.

Refinement is a process which doubles the size of the grid(stretches it), and then performs smoothing on the doubled grid.
Very useful for creating different variations of caves.

What if you want a large, open cavern, but it seems like my grid is restricted to more path-like generation? Assume your game operates in a 64x64 map.
For example, you can create a 16x16 grid and generate. It will be fairly small, and lots of the grid will be open, much like an open cavern. Through doing the refinement process twice, your grid will now be 64x64, and you will have achieved a large, open cavern, rather than a small tunnel-based map.

That's all for me,
I'm still discovering the very potential of my generator, myself. But it seems there's quite a bit I can do with it.

Until next time~!