Knoxville, TN

Building a Procedurally Generated Platformer

May 9, 2016

ProceduralGeneratedPlatformerRecently, I’ve been playing around with a “procedurally generated endless runner” game concept in Unity. It’s really meant to be a set piece for Knox Game Design–a  multiplayer game that we can show off that’s both quick to play and has a lot of replay value. Here’s an explanation of how I accomplished that procedural generation.

First, it’s important to note that “procedural generation” is a general category of technique. There are many ways of doing (or, to put it another way: algorithms for) procedural generation–literally, it just means you’re using a procedure to generate some element of the game. It’s sort of like saying you’re using math to solve a problem (Algebra? Geometry? Calculus? Statistics?) or painting (Oil? Acrylic? Watercolor? What style?).

In my case, I’m building out a platformer. I don’t need a perfect algorithm that generates complex levels that calculates specific paths–just something that lets the player stretch their legs a bit, and gradually throw more traps at them, until survivability is basically impossible. It’s basically meta-level-design: designing the process for designing a level that gives the player a particular experience.

To do this, I start with the basic unit, which I call a chunk. In my game, a LevelChunk is 20 tiles wide by 50 tiles high. (That allows for some variability, but it’s also small enough to generate and instantiate quickly.) Each tile can be empty, a floor piece, a platform, or one of various types of traps. Chunks are created when a player enters the next-to-the-last chunk and destroyed once the player is well past them.

A chunk begins its life as a blank grid that knows the previous chunk’s floor height. (If it’s the first chunk, we randomly pick a floor height that’s not too close to the top of the grid.) In this example, we’ll use a 10×10 grid, with a starting floor height of 4:

ProceduralGeneratedPlatformerBlog0Our first task is to build the chunk’s floor.

To do that, we break up the floor into sections with random lengths. I limited floor sections to being 1-10 tiles wide (or 1-6 tiles wide if it’s a pit).

For each floor section, we generate a possible length (1-10). If it’s the first or last section in a chunk, it must be a floor section. Otherwise, there’s a 30% chance of it being a pit.

If it’s a floor section, we generate a floor height. We use the last floor’s height and add a random value from -3 (we don’t want the player to essentially fall out-of-frame) to +3 (we don’t want to create floor sections the player can’t jump on top of). (If this would go below 1, we set the height to 1 instead–we don’t want to inadvertently create a pit).

Once we have this information, we fill in the floor blocks in the grid. Let’s say that our first section generates a floor length of 3, with a height of +1. We’d fill in the first section like this:

ProceduralGeneratedPlatformerBlog1

If it’s a pit, we regenerate the length (1-6) and skip ahead that many tiles.

Let’s say our second section is a pit of length 2, followed by another section of length 4 and height -2:

ProceduralGeneratedPlatformerBlog2

We continue this process until we reach the end of the chunk:

ProceduralGeneratedPlatformerBlog3

This provides us with a pretty basic platformer level: it’s technically playable, but it’s not going to be interesting.

It’s definitely not going to be interesting for four players hopping around, because everyone’s going to be jumping and falling at roughly the same points. What we need to do is let players “pick a path,” so to speak. To avoid complication, we don’t necessarily want to create branching paths; we just want to let players change how they jump and dodge.

To do this, we make another pass through our grid. This time, we go column-by-column and create platforms. There’s a 20% chance that any given column will be the start of a platform.

Once we start a platform, we have to work out its height. To do this, we simply scan down the column until we find the first non-empty tile:

ProceduralGeneratedPlatformerBlog4

Then, we add a platform 2 or 3 tiles above that. (We don’t want platforms to be too close to the ground, but we also want them to be accessible.) Let’s say we created a platform on the 2nd column that is 3 tiles above the ground:

ProceduralGeneratedPlatformerBlog5

As with floor sections, we then generate a random length for the platform. This may not be the actual length–we’re going to apply some checks to ensure that platforms don’t intersect with other floors or platforms, and that there’s always at least one empty row between a platform and whatever’s below it.

Let’s say our first platform is 4 tiles in length:

ProceduralGeneratedPlatformerBlog6

And we can continue until we have a set of platforms:

ProceduralGeneratedPlatformerBlog7

That’s nice, but it could still be more interesting. Again, since we’re not trying to build complex paths, there’s a simple solution: just keep adding another layer of platforms.

Since our platform logic scans a column to find the highest non-empty tile, it will build platforms on top of platforms. So we could add another row:

ProceduralGeneratedPlatformerBlog8

With only 10 rows to work with, we’re hitting a practical limit, but we could continue this process multiple times to fill out a larger grid.

We’re still creating a very linear platforming stage, but the player has a choice of how they approach it. That’s going to be important when we add traps.

I’ll admit all of my traps are really just rip-offs of Super Mario Bros. Flame and cannon traps are from SMB3’s airships. Laser traps are from SMB’s castles. Spike traps are… well, not a direct rip-off, but a stationary object that will kill the player is literally the simplest trap you could add to a platforming game.

The reason we save traps for last is that we’re always going to place them in relation to an existing platform or floor tile. That way, the player is usually interacting with them in some way.

To do this, we’ll scan the entire grid row-by-row and column-by-column. (Note that traps are always a single tile, so we don’t have to consider areas like we did with floor and platform sections.) When we come to a floor or platform tile, we’ll generate a random number that tells us whether to place a trap, and if so, which trap.

I’m actually doing a little bit of extra logic when placing a trap, so these percentages are technically a bit skewed:

  • Flame and cannon traps have to be pointed at at least one empty tile.
  • Laser traps must have at least one empty tile on one side.
  • Spike traps actually get placed above the platform rather than replace it, but only if the tile above the platform is empty.

In short, there’s a lot of ways for a trap not to be placed.

Using these rules we might end up with the following trap placements:

ProceduralGeneratedPlatformerBlog9

And now we have the data that makes up our chunk. (Actually getting this to show up in Unity is a different matter that deserves its own blog post.)

Now, remember how I said we wanted to scale up the difficulty? The last step in the chunk generation process is to ratchet up the chances of each of the traps, and to increase the maximum drop distance when generating floor sections. This generates a bit of tension, as traps become more complicated and the player’s choice of platform starts to matter more and more. (I’ve found that, as I’ve configured the process right now, you’re lucky if you make it past 100 tiles.)

Eventually this will generate a trap that’s impossible to pass, which is actually fine–we want this to be a quick game, so that once a player’s eliminated, they don’t have to wait too long to get back into the action. In this case, our “good enough” algorithm might actually be more helpful in crafting the experience we want the player to have than a “perfect” algorithm that always generated a playable path.

×