I recently did something called a Lightning Talk to my work colleagues about the ultimate basics of procedural level generation. I’m scared of, and terrible at, doing presentations, so I volunteered because I need to learn to face my fears. (Be bold, etc.)

A Lightning Talk is when three or four people do very short, five-minute presentations about Something Cool — so I figured that, since I kind of care about this stuff, at least my enthusiasm would shine through if my tongue refused to cooperate (it did).

This was written as an introduction for absolute beginners, because nobody at work gives two figs about game technology (except me), so it should be interesting enough for mildly technical people with a passing interest in the area.

Dungeon Delving: A Short Introduction to Procedural Level Generation

Disclaimer: when I say “random”, I mean “sufficiently unpredictable as makes no difference”.

Yes, I am quite aware it’s six minutes long. One day, I swear, I’ll pick a lightning topic that I can actually condense into five minutes…

Links

• Download: ProceduralLightningTalk.pptx from Dropbox

These are the original resources I started from. They give a decent enough grounding but none are particularly comprehensive, so you probably want to augment these with the source code for my implementations below.tw

• Growing Tree:http://pcg.wikidot.com/pcg-algorithm:maze
• Cellular Automata:http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
• Binary Space Partition:http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation

In Depth

Fun With Growing Trees

The growing tree algorithm isn’t quite as simple as I say either. If you follow the rule I stated, counting only the four cardinal compass points as neighbours, you’ll end up with mazes that look a bit rubbish — they’ll have diagonal connections.

The subtlety that eluded me for so long when I just blindly implemented the algorithm as per the example on the link above, is that it’s not strictly one space you need to check for. You are allowed to have two, or even three spaces, as long as they are down only one side.

For example, T-junctions and L-junctions are totally okay. In my implementation, the three tiles down the side of a T-junction actually only count as one space, because they’re connected by the central tile to the tile we’re examining. By being careful about this, we get the classic hedge-maze look we really want.

Binary Space What Now?

Yes, I mention naively connecting trees but don’t offer a solution. (Come on, it was supposed to be condensed into five minutes, I couldn’t go crazy.)

In my implementation, it’s simple enough — connect the two rooms whose centres are closest together. By the nature of the algorithm, those two rooms will naturally have no rooms in between them. That means that, between any given subtrees, you pair up every combination of rooms in that subtree and sort them by distance; with the bottom pair of rooms that’s easy enough, but further up you’ll have a big set of four, eight, sixteen and so on to choose from.

Tthat’s when my first draft turned to mush — if you always connect the leftmost or the rightmost rooms, things get messy as you’ve no guarantee the left room of one tree will actually be adjacent to the left room of its sibling. Of course things get even worse when you factor unpredictable horizontal and vertical splitting, and the random position of the split.

Déjà Vu

Some of you may remember that, yes, I have already briefly covered the Growing Tree maze generator and Cellular Automata cave generator on this blog — because my first introduction to these algorithms came while working on Project Y4. Unfortunately the Asteroid Wars bonus scenario never panned out, so only the Growing Tree system ever got used. I did end up using it twice to make up for that, though!

So a  month or two ago I decided that I wanted to revisit all this procedural generation lark, in a real programming language rather than Warcraft 3‘s gimped built-in scripting system (I had to write 1D-array implementations of 2D arrays and lists, it was endless fun). Since, well, now Unity is on the scene and also just so happens to be quite comfortable with C#…

The Source of All Code

I started completely from the ground up, rebuilding the algorithms in the new world in as modular and extensible a way as I could. Let’s face it, nobody’s going to get far with vanilla implementations of these things — I wanted a framework that could combine these algorithms with designed tweaks and rules, so that I can get something a bit more interesting than Just Another Maze Game.

So here ya go…

• Download: Proceduralis.7z from Dropbox

Have fun!