Terraforming Earth is coming out tomorrow, so we thought we should share how we tackled the problem of generating infinite platform-puzzle levels. So this is it, the details behind Terraforming Earth's innovative level generator AI!
First, let's take a look at how most procedural platformers tackle level generation, a method that I call
Room-based level generation
Terraforming Earth is a roguelike puzzle platformer, a first of its kind. The closest thing I can compare it to is Spelunky. Spelunky, while not strictly a puzzle platformer, does create unique levels every time you play, using pre-defined room templates.
Many roguelikes do level generation using this technique, which we are going to call room-based level generation. The advantage of this approach is that the individual parts are separated, you only have to think about how you connect the rooms to their immediate neighbors, no need to mess with tricky dependencies further along the path to victory. You can play with an interactive version of Spelunky's level generator here, to get an idea of how it works in action: http://tinysubversions.com/spelunkyGen/
The main problem with this technique is that the amount of variation scales linearly with the number of room templates you make by hand. Once the player has exhausted the set of pre-defined rooms, the rooms start to look familiar and repetition rears its ugly head. The player is no longer forced to apply creative problem-solving to overcome unique situations. They can rely on experience and memorization to solve the room in the safest and most efficient way. Ultimately this results in the end of replayability.
Of course, this is fine for most roguelikes, since the game designer can introduce a ton of additional variations through different skills and weapon types. Room-based roguelikes are still a ton of fun.
Yet, I was wondering whether there's a different way. Since I was developing a platformer with some hard-core puzzling aspect, and since puzzles are notoriously one-trick ponies (meaning they are only fun once), I knew that I can't reuse puzzles constrained to pre-defined rooms.
Obstacle-based level generation
I realized that ultimately puzzles are not about what's inside the rooms, rather they're about getting from one room to the other. The obstacles between rooms, not the contents of the rooms, are what matter.
We'll call this approach obstacle-based level generation.
So but then how do you put together separate pre-defined obstacles in a way that is actually solvable?
We'll use an iterative approach, and start out with a room that's guaranteed to be solvable. We introduce new obstacles one at a time, making sure that the level stays solvable in each step.
I present to you a most excellent level.
The robots are guaranteed to be able to reach the purple exit marker. Not very interesting though, is it.
Time to introduce the first obstacle. First, the AI picks a random room to mangle. There's only one room now, so we pick it. Second, the AI picks a random object that it'll move in this iteration. Let's say it picks the exit portal. Third, it picks a random empty direction either horizontally or vertically. Let's say it moves the exit to the right. Fourth, it will pick a horizontal obstacle at random from a set of horizontal obstacles that the playing characters (the three robots) are able to overcome using their current skillset. Let's say a door that can be opened with a key.
So the AI spawns a new room to the right, moves the exit there, spawns a door in between the two rooms and spawns a key on the left side of the door. Now we have the most archetypical puzzle ever! 1) A physical barrier that denies access to the next room and 2) a solution that disables the barrier.
We can do the same loop one more time. Notice that the key is just another object that the generator AI can pick up, and move! The AI chooses a room at random, let's say the one with the key. It then picks a random direction, let's say to the left. Then it picks a random obstacle, that the heroes can overcome. Let's say a set of spikes that Curi can fly over. The AI creates the new room, moves the key there, and spawns the obstacle between the rooms.
Let's do it again, for the third time, just to drive the point home. This time the AI picks the robots themselves to move. It picks the down direction and an obstacle that involves a lawn-mower NPC the heroes can use to bounce their way up to what now became the second floor.
Note how the level stays solvable throughout this iterative process. The cool thing is that since the solutions to the puzzles are themselves objects that can be moved by the AI, this creates a lot of interdependence between the rooms. The key can be taken arbitrarily far away from its corresponding door. Even though you learn the pre-defined obstacles over time and realize that you need a certain object to pass the obstacle, you still have to figure out a way to acquire that object. The amount of variation scales exponentially with the number of pre-defined obstacles since the pre-defined pieces are now massively inter-dependent.
The results
Iterating this simple step many times results in huge, sprawling maps with lots of tricky situations and mind-boggling dependency graphs that's pretty fun to untangle. Watch how we (the creators of the game) struggle to solve this particular level to see the effectiveness of this approach.
Many puzzled faces right there :) I think the fact that the generator AI still challenges their creators every week, even after all this time is a nice demonstration of the replay value that obstacle-based level generation creates. We many games will adopt this approach in the future, we would love to see more games that keep putting us in new situations every time we play.
https://store.steampowered.com/app/1029220/Terraforming_Earth/