My Obsession With ProcGen

ByWheffle

The Beginning

One of my favorite games on the NES as a kid was Solar Jetman, a game about flying around weird planets in a small pod exploring and finding crap to bring back to your mothership while trying not to die to the oddly hostile natives. The game had a real odd alien feel to it that enhanced the sense of discovery I felt.

Nowadays with games having been released with procedural levels like Spelunky, I thought, you know what would be dope? Solar Jetman with procedural levels. A couple years ago I went ahead and took a shot at doing just that during a 48-hour Ludum Dare game jam, and it came out in the form of Sanguinite (you can try that version for free in your browser over at itch.io).

As it turns out, a full version or “spiritual successor” to that game jam entry is the project that we are currently working on, going by the same name. The procedural generation code that started as some scratch code, went through a game jam, went through more prototyping and finally through more refinement has been on quite a journey. I have become quite engrossed in what proc gen has to offer, and all the ways to use it. Some kind of simplex noise seems to make it into every single project I start nowadays.

Baking Procedural Levels

I’m going to dive fairly deeply into how Sanguinite generates levels in its current form, because honestly I think it’s hella cool. If you aren’t into algorithms and stuff, this section might not interest you that much.

There are plenty of well-known methods out there for generating nice looking 2D terrain maps, like 2D simplex noise. However, I needed something that specifically created cave-like structures, and if you simply google “procedural generation cave” it’ll come up with a billion tutorials for doing so using cellular automata and marching squares. Most of them are specifically for Unity, but the concepts are absolutely universal. So this is what I went with.

The cellular automata method is a lot like John Conway’s Game of Life. All you have to do is vomit some 1-bit random noise onto a 2D grid so that each cell is either “on” or “off”, you set up some “smoothing rules”, and then you execute a number of smoothing passes. On every pass, you go through each cell one by one and change it to be “on” or “off” based on some simple rules:

  1. Check all eight neighboring cells and count how many are “on” (positions off the edge of the grid count as “on”)
  2. If the number of neighboring “on” cell is over a certain threshold, flip this cell to “on”
  3. Otherwise, flip this cell to “off”

In Sanguinite right now the neighbor threshold is hard-coded at 4, which seems to produce nicely rounded diphthongs cave walls. The number of smoothing passes is also somewhat arbitrarily hard-coded to 8, that seems to get the job done without extending generation times too much. You can definitely fiddle with these numbers to get different looking caves, although if your neighbor threshold drops lower than 3 then you have to account for the fact that the outer walls of the grid won’t always be solid (since a cell on the edge of the grid will always have at least 3 out-of-bounds neighbors that count as “on” in this algorithm).

The smoothing passes will chip away at straggler cells and rough edges while filling in small holes and connecting close branches, miraculously forming a sweet looking cave system.

These are minimaps of a level in the current build of Sanguinite at different smoothing stages.

So the map looks pretty good after a few smoothing passes, but it’s still underbaked. There are some issues. The first is a simple one: in Sanguinite, each level is supposed to start on the surface of a planet where the shuttle lands, so the top part of the map needs to be open to simulate an open surface. We could just chop off the top at some depth, but that would make everything square and therefore look dumb. So here I turned to 1D Perlin Noise to generate a nice 1D height map and use that to chop the top off.

The inner-workings of the Perlin noise algorithm are a little out of scope here (this post is already a novel), but for anyone familiar with signal theory (who honestly probably already know how perlin/simplex noise works), suffice to say it’s the simple addition of several randomly-generated signals, some at high amplitude and low frequency and others progressively at lower amplitudes and higher frequencies, which results in an organic-looking signal that looks like the cross-section of some terrain. The common 2D version is a popular method for generating terrain heightmaps in games like Minecraft (or they probably use simplex noise instead, I don’t know, basically the same thing).

Perlin noise TL:DR: Big wavy line combined with small squiggly line makes nice looking line.

The nice surface line doesn’t show up that well for this particular level, but it’s there.

So, the last real problem we still have is that, if you hadn’t noticed, there are two “rooms” in the cave system that are disconnected from the main cave. This is quite common at this stage. It might be fine for games where every cell is destructible, but that is not the case in Sanguinite. The next phase involves figuring out a way to detect rooms and deal with them.

Up to this point we’ve used well-known algorithms and methods and taken a well-trodden path. However, I wasn’t able to discover any simple and universal method for connecting an arbitrary number of isolated rooms in a way that looks organic (feel free to contact me if you know of one so that I can feel sad about opportunity loss).

So this was a bit brute-force for me here.

  1. First, we identify all the rooms using a flood fill algorithm. Any rooms touching the top of the screen are good to go.
  2. Next, we simply fill in any rooms that are too small. We use another arbitrary cell count cut-off for this.
  3. Now we do some analysis on each room and find all of the edge tiles, along with the room’s geometric center. We now have a list of rooms with some information on each, including the “big one” that touches the surface.
  4. We go through the list of rooms to find out which two are the closest based on their geometric centers.
  5. We go through both of those room’s edge tiles until we find the two edge tiles, one from each room, that are the closest to each other.
  6. Finally, we stamp out a tunnel step-by-step from one edge tile to the other. Be sure to use a “brush” larger than one cell in this step to get a decently wide tunnel.
  7. Now merge those two rooms. Add that merged room back into your list of rooms and delete the original two.
  8. Go back to step 4 until our list of rooms has a single room in it.
Here in our example level, the room circled in red has been filled in and the tunnel circled in green has been dug out.

Now, finally, we have a nice grid map to build a level on. Sprinkle some enemies in there and shake a bit of loot into the caverns and you’ve got yourself an epic mission.

There are some other small corner issues to deal with in Sanguinite, like finding a spot for the shuttle to land (and carving one out if there isn’t one), but the bulk of the work is done. You can also do some cool stuff with the room analytics we gleaned from the process earlier, like plug up tunnels with destructible blocks and hide bosses and loot in the hidden rooms.

The final minimap in-game looks a bit different due to the placement of some alien structures after terrain generation.

What Else Can Procedural Generation Do?

To be honest, I’m not sure I can think of many other uses for the cellular automata method besides creating blotches or cave structures. Maybe more creative people out there have found many other uses. Marching squares is apparently used a lot in graphics, but I don’t know much about that. However, once I discovered Perlin noise, and then progressed on to knowing about simplex noise which my current favorite game engine has a built-in easy-to-use class for, I have become obsessed.

The more I use it, the more things I think of to use it in. Another recent Ludum Dare jam entry I did involved an endless tunnel that you fell down into. The tunnel’s path? Simplex noise. Adding roughness to the edges of the tunnel: two more instances of simplex noise. Jittery movement patterns for fish in the tunnel? Simplex noise. The pattern of a light flickering due to damage or low energy!? SIM. PLEX. NOISE-UH.

Conclusion

The level generator is one of the most complex systems in Sanguinite, and one of the most fun to build for me. Given the chance, I will blab anyone’s ear off about procedural generation.

You do have to be careful though, and not just from a technical standpoint. It’s really easy to overuse procedural generation and make your game bland. I recently watched a GDC talk by Kate Compton about using proc gen, and she calls it the “10,000 bowls of oatmeal” problem; each bowl is mathematically unique and “new” but there is nothing interesting about them.

I’ve implemented a few systems in Sanguinite to try to tackle this issue, such as varying the types and amounts of enemies, changing the graphical tileset, involving “anomalies” in some missions that mix up the rules (like changing gravity or spawning an acid lake), and including some pre-defined structures that offer objectives and small puzzle elements that procedural generation just isn’t cut out to do on its own. One easy thing you can do is to simply tweak the parameters on the generator, like the neighboring cells rule and the number of smoothing passes. Tweaking these can result in distinct looking “types” of cave systems. I’ve done this with prototypes in the past and plan on implementing parameter variation in Sanguinite eventually.

I sure had fun ranting about this, and hopefully it will have been entertaining to some poor soul that stumbles upon this one day. Until next time, happy simplex-noising!