man this movie was so good and so bad

So for my recent run-and-gun-slash-art-game-etc Flash game project, I needed a way to create a large area for the player to explore, but didn't really have the time or inclination to build a level editor or hardcode the level's design, and there were some thematic issues with having the massive underwater labyrinth being static anyways.  So I ported over a simple 2D level generation algorithm that I designed over the winter holidays for a C++ project and had some really pleasing results within a few hours!  I'm gonna break down the basic algorithm I used here with some nice big pictures so you don't even have to read about how to do it.  Hopefully this'll make up for the lack of bloggage earlier this week...

It's a very simple algorithm that has 3 major steps or phases.  I'll be focusing mainly on the first two, as the last is relatively simple and game-dependent.  Phase 1 is to place some items or powerups or items/places of interest in the space the level will eventually occupy.  Phase 2 involves digging large, coarse tunnels between these points of interest.  Phase 3 is filling your rough-cut tunnels back in a little to give the thing a more organic feel.

Step 1: Generate Targets

step 1

Here is a very simple way to generate some "targets", or areas of your level that are interesting for the player.  In my game, these were locations of fish that you collect.  However, these are placed very predictably, boring...ly even.  I did find it useful to loosely divide the targets into two columns though, as you'll see in a couple steps.

Step 2: Randomize Targets

step 2

So, scoot your targets around a bit!  You can see that they're sort of arranged in two columns still though.

Step 3: Place Items

step 3

Go ahead and place your items or powerups or keys or whatever they are in these locations, or at least save off these spots.  Because now we're gonna dig some tunnels to link them all together!

Step 4: The Alpha and Omega

step 4

I start Phase 2 or whatever of my algorithm by digging out the entrance and the exit first.  In Fathom these were extra wide areas that led off the screen.  I like to dig the entrance down to one "block" below the lowest of the two highest items, highlighted in cyan above.

Step 5: The First Two Tunnels

step 5

Then just dig a couple of simple, straight tunnels from the main shaft at the top there straight over to the two highest points.  Hooray!  You made a level!  It's kind of small and stupid though.  Let's make it bigger... (that's what she said??)

Step 6: Digging Down

step 6

So this is the first iteration of a relatively simple loop that will dig the remainder of the coarse tunnels.  I move one block back along the tunnel, and then one block away from the next node (e.g. I move up if the node is down).  Then I dig down to one block below the target node.  Like at the start of the tunnel, I move one block back up the shaft, and one block away from the node (e.g. left if the node is off to the right).  Then I dig straight to the node.

This might seem over-complicated; you could just dig tunnels straight between the different points.  But these little 1-block diagonal offsets at each joint help to break up the grid a little to be less pedestrian, and they're relatively easy to add to the simpler, "just connect the dots" approach, especially if it's in a loop like it should be!

Step 7: Switching Sides

step 7

To complicate things even more (in the name of better final results), I like to switch sides halfway through the tunnel-digging loop.  If you remember from the beginning, we divided all the targets up into two columns, even if we did randomize them a bit.  Then, we dug tunnels from the first node in each column to the second.  Now, we're going to switch it up, and dig a tunnel from the second node in one column to the third node in the other column.  This is again very easy to add to your loop, and makes the resulting level layout much less boring.

Step 8: Finishing The Coarse Tunneling

step 9

So we switch back, and dig from Column A Node 3 to Column B Node 4, and vice versa.  Then we dig from the last node in each column to the exit.  Voila!  A blocky, crappy looking level, but a level nonetheless!  This is more or less the end of "phase 2" as described at the get-go.  So now that we have our pickups or keys placed, and we can travel from the entrance to all those points, and on to the exit...where do we go from there?

Step 9: Messing Things Up

ta da

For each "block" that you carved out, you can add surface detail to each of the edges, and suddenly it is much harder to make out the cold, methodical computer mind behind the design!  Performing this process on a block-by-block basis helps simplify the problem, at least for me.  I think of it almost like a room-by-room dressup algorithm.

That's about all there is to it.  This is not by any means the only way to do this sort of thing, let alone the best way.  But it approximates my own mental level design process reasonably well, and allows me to break down a relatively intimidating problem (magically creating interesting levels) into a few smaller, easier to manage problems.