In this tutorial I'm going to introduce two terms I use to describe procedural generators: generative space, and possibility space. We're going to define these two terms and then look at some interactive examples to understand the difference between them. They're really useful terms to help describe a procedural generator, or think about the difference between two generators. Let's dive in!

Imagine an enormous book, in which is a screenshot of every single Minecraft world. Each one is labelled with the world's random seed, a unique number you can type into Minecraft to get it to generate that world. The first page shows the world from seed 0, the next shows the world from seed 1, and so on. Minecraft's world generator contains 2⁶⁴ random seeds in total, which is a huge, huge number: that's 18,446,744,073,709,551,616 worlds that it can generate. Every time you click "New World", you get one of those seeds served up to you. This number, 2⁶⁴, is the size of Minecraft's generative space - the set of all the things it can generate.

Now imagine a Minecraft world with nothing in it except flat grassland, forever, in all directions. No caves or rock underneath it, no trees, no hills, no animals. Just a single layer of grass tiles. Other than being pretty boring, this world isn't something you can generate in Minecraft (without modding it). We can imagine it, we can describe it, we can even open up Minecraft and create it ourselves by hand - but Minecraft can't generate it. How do we know this? There are lots of ways we could prove it, but an easy way is to think about Minecraft's biomes, regions like desert or jungle that are scattered around every world. Our flat grassland doesn't have these, and so we know it can't be generated by the standard world generator.

The flat grass world is in what we call the possibility space of Minecraft worlds - the set of all possible Minecraft worlds we can imagine, represent or describe. But the flat grass world isn't in Minecraft's generative space, because it can't be generated by the procedural generator we find in the game. We can imagine a Minecraft world with a perfect scale model of Persepolis in it, or one that has a lifelike stone sculpture of you sitting reading this article right now - these are all possible Minecraft worlds, but they aren't going to be generated by the game.

The diagram above gives us an idea of how this looks. Everything in Minecraft's generative space must also be in its possibility space, because if Minecraft can generate it it, it must be possible to make it in Minecraft! But not everything in its possibility space is in its generative space - like our flat grassland example. But the diagram above isn't to scale. In fact, Minecraft's possibility space is much, much bigger than its generative space.

To see how big, first let's calculate the size of a single Minecraft world. The volume of something is its width multiplied by its height multiplied by its depth. Minecraft worlds are 256 tiles high by default, and they begin to break down about 30,000,000 tiles away from the start in any direction, so that's an approximate volume of:

256 x 60,000,000 x 60,000,000 = 921,600,000,000,000,000 blocks

Each of these blocks can be different things: stone, grass, air, water. For our estimate we'll be generous and only use 'world blocks', which the Minecraft wiki says there are 64 types of in total. This means that every block in a Minecraft world has 64 possibilities it can be. The formula for calculating how many possible worlds there are is the number of tile possibilities for each block, raised to the power of the number of blocks:

64^{921,600,000,000,000,000} possible Minecraft worlds

This number is so big, I cannot find a calculator anywhere on the internet capable of calculating it. Update: Florian Völker got in touch to tell me that Wolfram Alpha can actually calculate it! It has over one quintillion digits, that means just writing the number down takes over one quintillion numbers. That's big.

To dive a bit deeper into generative and possibility spaces, we need an example we can wrap our heads around a bit better. So for the rest of this tutorial we'll be looking at 2D platformer levels, for games like Super Mario Bros. or Spelunky. We're going to look at a series of level generators for 2D platformers, all of which are interactive so you can generate your own levels. As we go through them we're going to ask some questions about their generative space. All of the examples are available in an open source Processing sketch on our GitHub.

As we go through, I'll sometimes ask questions in bold, like: what is the size of the possibility space for these platformer levels? Feel free to skip past them if you just want to read and play with the examples. I'll also sometimes add tips to help you answer the questions, like this:

Tip: the levels are 40 tiles wide and 10 tiles high, and each tile can be one of 3 things: empty, ground or powerup block.

You can always pause at a tip before scrolling further down if you don't want the answer revealed. Alright! Let's look at our first generator.

Algorithm 1: Randomness

Our first level generator is very simple – it’s totally random. Every map has a start tile on the left-hand side, and an exit tile on the right-hand side. Every other tile in the map has a 33% chance to be empty, a 33% chance to be solid, and a 33% chance to be a powerup block. Click on the example below to regenerate a level, and see what kind of results you get.

You’ve probably noticed that this isn’t a very good level generator. In fact, most of these levels aren’t even playable, let alone being fun or interesting. Generate a few more levels and then think about this question: how big is this generator’s generative space, compared to its possibility space?

Tip: Can you think of a level which is in the possibility space, but not in the generative space? Is there a level you can imagine that this generator can't make?

The answer is that the generative space of this generator is the same as the possibility space. Any tile in the map can take on any value, and so every possible level we can imagine is in the generative space. The most fun, most interesting levels are in this generative space, even a map which spells out SUPER MARIO IS AWESOME in powerup blocks. Unfortunately, the generative space is so large, that finding a cool level like that is very, very unlikely. As you can see by clicking on the generator, most of the levels are just junk.

Algorithm 2: Random Shape Drawing

Our next algorithm is a bit more involved, and makes levels that look a bit more like they belong in a game. Starting with an empty level, it picks a random point somewhere, and then draws a line or a square of either powerup or solid blocks. It does this 20 times in total, resulting in a bunch of shapes being drawn randomly across the level. As before, you can click on the example below to rerun the algorithm and generate another level.

This is beginning to look a bit more like a platformer level, isn’t it? As you generate levels, try to imagine playing them in your head (be as generous as you need to - imagine having a double-jump if you need it, or being able to jump out of the ceiling of the map). How many levels do you need to generate before you find one you can complete? Don't worry about being too precise with your mental playthroughs - just judge it as roughly as you need to.

When I do this exercise with an audience, the average is usually around 10 tries to find a level. How many did it take you? Keep that in mind, and now look at this variant of the same generator, below. This generator is the same as the one you just saw, except that it draws 10 shapes on the level instead of 20. Now calculate it again: how many levels do you need to generate before you find one you can complete?

You probably found it took you less time to find a level that was playable. Let’s pause here for a second and think about the differences between these two generators, which are almost identical apart from one small tweak. Which generator has the bigger generative space, the 20 Shape generator or the 10 Shape generator?

Tip: Think about a level from the 10 Shape generator – could the 20 Shape generator create it? Now think of an example the other way around.

The answer is that the 20 Shapes generator has a bigger generative space, in fact it contains the entire generative space of the 10 Shapes generator within it. To show this, imagine any level from the 10 Shape generator. Our 20 Shape generator could produce this by randomly drawing the same ten shapes, and then randomly drawing them a second time on top of each other. However, any level with twenty distinct shapes in could never be drawn by the 10 Shape generator.

This means our 20 Shapes generator has more levels, which means it has more interesting levels, too. But remember, it was a lot easier to find a level that was playable with the 10 Shapes generator. If you had to choose a generator to put in your videogame, which one would you choose? There's no right answer here, really, but this is a very important decision we often have to make with procedural generators. One generator can generate a bigger variety of things and has more surprises, but the other one is more reliable and less frustrating for the player.

Algorithm 3: Level Chunks

This algorithm is based on the level generator used in the Spelunky, which you can read more about here. The level generator randomly picks a level chunk designed by a human (me) and pastes it into the level. Then it picks another level chunk at random and pastes it next to it, and so on until the level is complete. Here’s the generator, with the background shaded so you can see the chunk boundaries easily:

How long does it take to generate a playable level now? You should find that nearly every single level is playable. We know exactly what is in each chunk, which means we can make sure there's interesting things to jump on or challenges to avoid. At the same time, it's more dynamic than a static level - we don't know which chunks will appear, or in which order. Spelunky's algorithm is even richer than this, with vertical movement, and little random variance in each chunk. Darius Kazemi made an amazing interactive Spelunky level generator which you can find here.

Generators like this are a good tradeoff of surprise or control. When a generator picks from a catalogue of things and puts them together (sometimes using special rules, like Spelunky) we call it a grammar-based generator. Grammars let us decide what building blocks a procedural generator has to use, but relaxes the rules on how they get put together. This control and safety comes at a price, though. Take a look at the generator again, and think back to earlier examples. How often would this level generator surprise you?

Initially the generator is very surprising, as you encounter each chunk for the first time. But as you play more, you'll quickly begin to spot where one chunk ends and another begins. Even though there are hundreds of combinations of chunks in this generator, after just a few levels you'll begin to feel like you've seen them all. The simplicity and easy-to-understand nature of a chunk grammar is great for developers, but it can also be a drawback in terms of player enjoyment.

Algorithm 4: Human Design

For this last example, we're not technically looking at an algorithm, but a very different kind of creative process: paying humans to design levels. Click the generator below and you'll get served up one of the first two levels from Super Mario Bros. (or at least, the first bit of each one).

After beginning in total randomness, we've ended up here, with one of the most famous examples of 2D platformer level design in history. This isn't a generator, of course, but in a sense these levels can be thought of generators that produce just one, very high-quality level. The ultimate tradeoff of control versus quality. Looking at this level, think back over the generators we've looked over today, and think about this question: which of these generators contain these famous levels in their generative space?.

• Random Generation
• 20 Shape Generation
• 10 Shape Generation
• Level Chunks

Only our first generator, Random Generation, is capable of producing these levels. Our shape generators might if we increased the number of shapes they could draw, but that would also greatly increase the number of bad or weird levels it creates too. Our level chunk generator might be capable if we gave it a different set of chunks, but would all the other combinations of those chunks be playable?

This shows you how tricky it is to build a procedural generator. We want to think about our generators like normal game content, to imagine a player playing a specific level and enjoying it. But as generative designers we have to think about the whole generative space, not just a single example from it. How big is the space? How rich with surprises is it? How often does it produce something boring, or something bad? Can we detect it and filter it, or do we need to find a way around it? These are just some of the things we have to bear in mind when building something generative.

Summing Up

Today we learned about the following ideas:

Generative Space

The generative space of a procedural content generator (like Minecraft's world generator) is the set of all the things it can generate. If we change the algorithm or tweak a variable, the generative space changes.

Possibility Space

The possibility space of a particular type of content (like a Minecraft world) is the set of all examples of that content we can imagine or describe. It's usually, but not always, much bigger than a procedural generator's generative space.

Bigger Isn't Always Better

A generator with a big generative space usually has more good content, more surprising content and more varied content in it. But it also usually has more junk content, more boring content, and more unusable content.

A generator with a smaller generative space is easier to control, easier to test, and easier to understand. But this can make it more predictable and less surprising.

Finding ways to balance the strengths and weaknesses of these two extremes is the art of generative software design!

Read More & Thanks

That concludes this tutorial! Thank you so much for reading all the way through. If you want to ask me a question, make a suggestion or submit a correction, you can find ways to contact me here.

For some fun related reading on things we discussed today, I recommend:

• Spelunky, by Derek Yu - a great breakdown of how Spelunky was designed, including reflections on its procedural generator.
• Tracery Tutorials, by Kate Compton - learn how to write replacement grammars with text, a great way to practice thinking about generative space!
• Dr. Gillian Smith's excellent book chapter on expressive range (which we'll cover in a later tutorial).
• Dr. Smith has lots of free resources as well, like her excellent GDC talk on tradeoffs in procedural generation.
• Finally, don't forget you can find all of these generators in an open-source Processing sketch here.

Posted January 31st, 2019

Back to the blog index