Blog 732: More Fun With Level Generation

This might be the sixth time I’ve reworked my level generator. It’s incredibly complex and every time I think I’ve got it right… Well, after each rework, everything goes smoothly until I start to layer on another system — then suddenly the architecture can’t hold anymore and it’s causing more pain than gain.

Other times, yes, I’ve just been too clever for my own good and tripped over my own shoelaces. Is this one of those times? Erm, possibly…

More Fun With Level Generation

Usually my “reworks” have focused only on what comes after the fundamental layout has been established, but this time I’ve kind of gone all the way.

I was using a binary-space-partition (BSP) algorithm to carve up the level area into rooms, which could then be populated. As I was working with the systems that connect those rooms together and make them into shiny playable spaces, I started to realise that this approach was more pain than it’s worth.

BSP works by taking the main area and sub-dividing it into two, then sub-dividing each part into two, and so on until the rooms are as small as they can go. It produces quite interesting results from a bird’s-eye view — layouts are rectangular enough that they look artificial, but as the partition borders shift around you still get quite unpredictable layouts.

These have some problems, though. If you put a tiny type of room inside a larger partition, you end up with huge expanses of corridor that you can’t do very much with and are boring to traverse. Plus, the unpredictable overlaps between partitions makes joining them very awkward.

Exhibit 1: the noodly lengths of a BSP-generated level, interesting and varied from above but mostly boring empty corridors from within.

So I’ve gone back to using the growing tree maze generator. I’ve previously been quite dismissive of mazes, as their output is generally too regular and constrained. While that’s certainly true when you apply a maze to a 1-1 grid, it can be offset when you use the maze as a way to structure a larger area. As a drop-in replacement for the original BSP system, I draw a small maze and make each open tile a square partition and the rest of the system proceeds as if nothing has changed.

This means partitions become regular sizes, but I can offset this by occasionally joining a couple of adjacent partitions together — though to be honest, some of the rooms under the old system were too long and stringy and made the game feel janky. (Though now the rooms are closer together, the bot call-for-help range is leading to slightly larger pile-ups than originally intended. Erk.)

Exhibit 2: maze-based level, less interesting from above but more compellingly varied from within.

Alas, the original reason for this rework project wasn’t even that part of the system; it’s actually just collateral damage. I was initially having trouble with turning the partitions into challenge chambers and drawing walls and placing traps and decorations.

The last time I worked on this area, I was a little bit overzealous with Unity’s ScriptableObject framework. This is a system whereby you can create pieces of code that behave like static assets — as if they were textures or 3D models. The only state they have is the properties you specify in the asset, which is quite handy for certain things.

So I hit upon the strategy of using ScriptableObjects to represent room types. Thus when generating a room, the system would pick a random room type from my list of layouts, feed in the current grid state, and the room type would apply all the gubbins to create a fully-formed chamber. The ScriptableObject-type behaviour meant that I could easily have multiple room types generated by the same piece of code, differentiated only by the properties configured on the room type asset.

Exhibit 3: Static assets are great for plugging together, but are absolutely awful for this kind of system.

The problem with this approach is that room generation seems to need to be a multi-stage process. As I added decorations and traps to my previous systems, I kept adding them to the single pass that a stateless room type could make — because the traps and decorations need to know about the way a room is constructed, in a way that a stateless asset can’t hold, I had to do everything in one place.

This clashed with the need to ensure adjacent rooms don’t touch each other; when you have decorations and traps that can change the shape of the world, but only fit in specific places… Ideally, you draw the world down, set up all the rooms, then you can place decorations and traps knowing that they won’t be interrupted by another room drawing over the top of them.

Exhibit 4: an area outlines its bounds when selected, so I can actually tell what tiles are part of which zone and why.

So I’ve reworked the system to convert partitions into areas before anything happens. Now while a partition is just a rectangular block of space known only to the algorithm, an area is placed into the game world.

That means that it can hold onto state, and therefore be triggered to build itself in steps: do a first pass to set the world geometry down, then another pass to put down decorations, then another pass to put down enemies. With each pass, the previous pass is already guaranteed to be complete for all rooms so there won’t be any more annoying overlap, but each area master object remembers what it did before and therefore where it can place decorations and units in subsequent steps.

The other advantage is that since areas now exist in the game, I can turn them on and off depending on the player’s current location. That means I can stop brutalising the processor by running the bots in rooms that are irrelevant to your interests.

Exhibit 5: the advantages of pre-configured ScriptableObject assets can be retained by having template objects that are cloned out into the real world during generation.

So, yes, another break from adding new features to patch up old ones. When I say “rebuild the level generator” I am, however, being a little bit melodramatic. Each iteration of the system has focused on different parts of it, so while I will be cutting out some poor choices there are as many bits and pieces that will continue to contribute to our happy future. Hey, turns out that procedural level generation is quite a complex endeavour — who knew?

… what do you mean, this is keeping me from implementing my final festive feature, the Towers of Hanoi puzzle? You’ll have to be patient, its time is almost upon us.


And you tell me...

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s