Gamasutra: The Art & Business of Making Gamesspacer
How to Make Insane, Procedural Platformer Levels

Printer-Friendly VersionPrinter-Friendly Version
arrowPress Releases
April 19, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM TechWeb sites:


 
How to Make Insane, Procedural Platformer Levels

May 10, 2012 Article Start Page 1 of 3 Next
 

[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.

Design Requirement #1: It Must Be Feasible

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.


Short jump

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.


Long jump

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.

---

[1] 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.


Article Start Page 1 of 3 Next

Related Jobs

Activision Publishing
Activision Publishing — Vancouver, British Columbia, Canada
[04.19.14]

Principal Graphics Programmer
Insomniac Games
Insomniac Games — Burbank, California, United States
[04.18.14]

Associate Engine Programmer
Insomniac Games
Insomniac Games — Burbank, California, United States
[04.18.14]

iOS Programmer
Insomniac Games
Insomniac Games — Burbank , California, United States
[04.18.14]

Senior Engine Programmer






Comments


Rasmus Gunnarsson
profile image
You should check out the game TowerCimb http://www.davioware.com/index.php?page=2

I think it uses procedural levels very good for a platformer. Gives more life and excitement to the levels when you know they aren't that structured and doesn't hold your hand.

Jordan Fisher
profile image
TowerClimb looks great. I wish I could have convinced our team to go with super retro graphics. The atmosphere in TowerClimb is spot on!

I agree about procedural levels. There's something invigorating about playing a challenging, well crafted level that no one else has played before. Actually, the most interesting levels for me are when there is a bug in the level generation algorithm, and the computer fails to guarantee feasibility, but I still play the level hoping to prove it's possible anyway! Unfortunately now that the game is almost done those bugs don't happen anymore =/

Graham Luke
profile image
I liked your article very much.

I've been working a long time too on a game heavily dependent on procedural generation.

Tony Downey
profile image
This is fascinating stuff - far more robust than simply stitching together pre-built set pieces. And I love the concept of changing the physics late in development. Great article.

Mark Venturelli
profile image
This is amazing. If half of the things you promised are actually playable and effective, I need to see this ;)

Backing your Kickstarter! Good luck!

Jordan Fisher
profile image
Awesome, thanks Mark! I'm looking forward to getting you a copy of the game to show you it is indeed playable and effective =D

Eric Boosman
profile image
Interesting article, Jordan, thanks!

Vin St John
profile image
Great read, Jordan. Looking forward to playing Cloudberry Kingdom!

Rob Allegretti
profile image
Nice one. That is a cool system, and a great use of AI. I would be interested to see what the genetic algorithm came up with given enough iterations.

Jordan Fisher
profile image
It worked out surprisingly well. It honed in on interesting levels at the right difficulty, but it proved difficult to maintain genetic diversity, which in this case is just as important as satisfying the fitness function. Ultimately it was faster and more robust to just brute force the search.

Cartrell Hampton
profile image
He.

Very nice article.
____________________
- Ziro out.

Josh Bycer
profile image
Excellent article. And I was just thinking about how a procedural generated platformer could work the other day. Just thinking about it over the course of 3 days was a complicated matter. I can't imagine how much work and thought went into your idea. Congrats on the article and good luck with the kickstarter.


none
 
Comment: