[In this article, Cloudberry Kingdom developer Jordan Fisher explains precisely how he created the algorithmic level design system for the procedurally generated platformer -- and how you can design your own AI. You can back Cloudberry Kingdom on Kickstarter right now.]
So you want to make a procedural platformer. You want it to spit out levels on demand, and you want the levels to be awesome, challenging, and fun. You want the algorithm to be flexible, so that you can design a new obstacle or change the game physics and instantly have new levels created with your new content. You want it to spit out easy levels for new players, hard levels for core players, and brain melting insanity for leet StarCraft gods with APMs over 9000.
Oh, and all this insanity had better be possible to actually beat, or the players will organize a coup and destroy your reputation via Reddit, 4chan, and probably their personal blogs that they started just to pummel you.
Basically, you want a silicon imprint of Miyamoto and team that you can capture in a box of software to distribute to the masses.
That, or a well-trained level design AI. As lead programmer at Pwnee Studios, my job has been developing such an AI for our first platformer title.
Procedural content has done wonders in genres other than platformers. The expansive plains and dungeons in Diablo, the beautiful landscapes in Minecraft, the creature animations in Spore. Dungeon crawlers and sandboxes in particular have a long history of awesome procedural generation. There are side-scrollers with random levels too, such as the amazing Spelunky and Terraria.
In this piece, I talk more specifically about random levels for a faster paced style platformer (Mario, Sonic, Super Meat Boy). This is a relatively unexplored area for procedural algorithms, and is in many ways much more challenging. We want pixel-perfect jumps, death-defying brushes with lasers, and tunable difficulty for any skill level, all while guaranteeing the levels generated have solutions.
There are three things a good procedural algorithm needs to nail:
1. Feasibility. Can you beat it?
2. Interesting Design. Do you want to beat it?
3. Appropriate Skill Level. Is it a good challenge?
Satisfying any one of these is actually pretty easy. Satisfying them all simultaneously forms a very tight constraint problem. Feasibility, in particular, is a constraint that has greatly hampered efforts to make good procedural platformers; however, the other two requirements are just as difficult to perfect.
The first constraint, feasibility, is the most brittle requirement, so we will start there.
There are simple techniques to guarantee a dungeon in Diablo has a path through it, analogous to how one assures that a generated maze has a solution. In a maze, the player has absolute control over their position, not considering the constraints imposed by walls. In a platformer, a player has a much looser control of her position and must factor in the game’s physics: momentum, gravity, friction, and so on. This greatly exacerbates the difficulty of the problem.
If you generate a maze with no solution, then you can knock down a few walls until a solution appears. If you generate a platformer level with no solution, it's not at all clear how to fix things.
We need to make sure our levels are possible to beat. To satisfy this need for provable feasibility we rely on a very good computer player that we can hand off levels to. The player AI directly proves the levels are possible by beating them. This is easier to say than implement, but luckily good platformer player AI is a well-researched topic, with some notable implementations, such as this one. Implementing a good AI is non-trivial, but fairly straightforward.
Now that we have our awesome ninja AI, we can test our levels before throwing them at our players. Even better, if a player gets stuck on a level, we can let them watch the AI. The player can learn and improve, or at least suspend their incredulity.
We still have a problem, though. How do we actually make a feasible level in the first place? Like NP-complete problems, it seems like it's easy to verify a solution, but very hard to find the solution to begin with.1 What we need is for the AI designing the levels to itself have some notion of what is and isn't possible.
The simplest way to do this is to give the AI knowledge about the player physics. Starting with a player standing on a block, we can pre-compute all possible destinations a player may arrive at by jumping in different directions.
Enumerating possible destinations.
The AI then takes this information and uses it as a constraint. Each block it places must be within a certain range of some other block, dependent on the relative heights of the blocks. For simple player physics this is a good model, but if the physics also has momentum, friction, and variable jumping heights, then the pre-computation suddenly becomes a lot bigger. We need to know where the player can end up depending on every start configuration: running at half speed, running at full speed, doing a full jump, a half jump, etc.
Imagine a simple situation where a player is about to run and jump from one block to another. In the first case, a passing fireball forces the player to stop before proceeding to jump. The player now jumps, starting from a standstill, with no initial momentum, retarding the full extent of the jump. The player could first backtrack to get a running start, but perhaps there is an advancing wall of doom impinging on the player.
Now imagine a second, simpler case without the fireball. The player can run at full speed and can clear a longer jump. Good for the player, bad for the AI designer. Now it's not enough for the AI to know the relative positions between pairs of blocks, the AI must also know what the player context of each block is. The AI needs to know what state and situation a player will be in when the player is on Block A, so that it can calculate how far away it can place Block B.
Unfortunately, things are even more complicated than this. It turns out it's not enough to know just the player's state and how far the player can jump in different states. Imagine another simple situation, where a player is jumping from a lower block to a higher block. In the first case, the blocks are stationary, and the player can successfully clear the jump. In the second case, the blocks are moving in such a way that even though the final position of the block when the player intends to land is within jumping range, the block itself intersects the player's path earlier on in the jumping arc.
Left: valid path. Right: invalid path.
Suddenly we need to keep track of the player context, the range of possible jumps, as well as how all possible player trajectories interact with every block we place and even intend to place. It may turn out that an obstacle we place at the end of a level affects the player's path at the beginning of the level. This is known as a dense problem. Dense in the sense that where we should place each object in our universe is intimately dependent on the location of every other object, forming a dense tangle of messy dependencies.
 We could just randomly sample levels until we find one that works, but presumably the space of provable levels is much smaller than the space of all levels, which would make this method impossible in practice. I wonder what a truly random sample from the space of provable levels looks like, though.