Procedural Level Generation for a 2D Platformer

Published September 01, 2014 by Fabien Benoit-Koch, posted by fabienbk
Do you see issues with this article? Let us know.
Advertisement
Jack Benoit is my latest mobile game, a not-so-original 2D platformer for Android. My goal was to make a fast, responsive game for mobiles, with the best possible controls, and to have complete procedural generation for the levels. By complete, I mean not based on manually crafted level pieces, assembled randomly, but truly randomized to the tile granularity, something that is often advised against. But hey, it was fun to try and the results are not that bad. I'll describe the whole process in this article.

Description of the game

You control a character able to jump and climb ladders, and your goal is to simply reach the exit of a level, which are made of various sets of platforms, ladders, and hazard zones (spikes). Jack Benoit uses 4 layered tile maps:
  • The parrallax background,
  • The platforms,
  • The ladders,
  • The sprites (collectable items, decorations, etc).
All of the layers are constructed procedurally. The background is simply made out of Perlin noise, filtered and smoothed using transition tiles, I won't talk about it, the subject has been covered to death by better authors than me. This article will focus the architecture (platforms, blocks, and ladders).

Step 1. Generating a level layout

Levels are composed by a random set of discretely connected "rooms" (rectangles of 20x16 tiles). Each room can have up to 3 "walls", at its own edges. Two rooms are connected if their shared edge doesn't contain a wall. The structure becomes quite clear when you see a whole level. This one is made of 15 rooms: 10-levelexample.png The first step is to create this random path of rooms. The goal is to get a data structure describing something like this: 10-layout.png We simply represent this using a 2D array of Room objects. The algorithm is a simple recursive graph exploration, with backtracking. function findPath(x, y, minDistance): if (x,y is goal and minDistance == 0) return true if (x,y not open) return false mark x,y as part of layout path switch(random number 1 out of 4): case 1: if (findPath(North of x,y, minDistance - 1) == true) return true case 2: if (findPath(East of x,y, minDistance - 1) == true) return true case 3: if (findPath(South of x,y, minDistance - 1) == true) return true case 4: if (findPath(West of x,y, minDistance - 1) == true) return true unmark x,y as part of solution path return false Once this is done, we make sure the structure is easily iterable, and each Room knows about the location of next and the previous ones.

Step 2. Generating a solution path

The second step is the most critical to ensure the correctness. It's very easy, if you're not careful, to produce impossible levels! In our example, the player must always be able to navigate through all these rooms, to reach the last one. Given that the player movement is constrained by physics (he can jump 4-5 tiles high), we had to make sure that the vertical parts (two or more rooms vertically connected) were always in reach. That part proved to be tricky. I finally chose to create a solution path, i.e. a set of platforms and ladders that leads the player directly to the level exit, without interruption. 10-layout2.png At first, it may seem too straightfoward, but once the generation is complete, this path is "hidden" in the middle of the other platforms, and is not evident at all to the player. In fact, it is so camouflaged that I had to put sign posts indicating the direction to follow. The player often gets off the path, finding alternative ones, but at least a solution is guaranteed to exist (no impossible levels). The process is quite simple. Generate a random position in each room, then connect all of them using one ladder, and one platform. for each room in the layout: select a random point P1(X1,Y1) in the room select a random point P2(X2,Y2) in the next room of the layout set cursor C(Xc, Yc) to P1 while P2 is not reached by cursor: if (selectionFunction): create a platform between (Xc, Yc) and (X2, Yc) move cursor to (X2, Yc) else: create a ladder between (Xc, Yc) and (Xc, Y2) move cursor to (Xc, Y2) The selectionFunction is used to determine if we start by a ladder or a platform. It's randomized, however in order to generate well-designed levels, it will also take some heuristics into account, like the minimum length of a ladder or a platform.

Step 3. Fill the rooms with platforms

Now that the path is secured, we must actually fill the rooms. I tried some top-down approaches (generating perlin noise to spread platforms homogenously) but the simplest ones (pure randomness guided with some ad-hoc heuristics) often produced the best results. I simply iterate on each empty tile of the room, starting in the top-left corner, and for each empty tile (in the platforms layer), there is a chance to generate a platform of some random length. We also make sure that this platform, if generated, does not completely block the level (horizontally or vertically).

Step 4. Generate ladders

On each the generated platforms, we place a ladder top at a random X position on the platform. We then "grow" them (like a plant, which is fortunate, because some of the ladders are actually plants) downward until it reaches a platform below, or the ground. 10-ladders.png As you can see, while the solution path is quite clear before this step, it is eventually neatly disguised.

Conclusion

This simple method produces a lot of variability, which is nice, yet the gameplay remains relatively consistent. After some runs, the player learns to "guess" what the solution path is. It has some drawbacks though: some (rare) platforms remain sometimes unreachable, because putting a ladder on 100% of all the platform produces too many of them. A more complex graph exploration, based on the physical characteristics of the player would be necessary to detect and correct these cases, but it is costly, and felt unecessary given the frequency and the gravity of the problem. Thanks a lot for reading this. If you have any questions, feel free to ask! Note: This post was originally published on Fabien's blog and is republished here with kind permission.
Cancel Save
0 Likes 9 Comments

Comments

lask1

Very simple and effective. Nice article!

August 28, 2014 05:48 AM
Sporniket

Interesting.

I guess that when you generate the solution path, you could randomly break the sub-path between two steps of the solution to add between 0-2 sub-steps. That way the path between each steps would be less straigth-forward.

August 28, 2014 10:37 AM
KnolanCross

Great read, but could you please specify how you find the paths to the points?

It seems to me that you align the path to one axis then use a straight line in the next, but I could not understand how you define which axis you align first.

August 28, 2014 05:20 PM
Madolite

I'd like my upcoming game to have some combination of a procedurally generated macro world with randomized and hand-made chunks and micro chunks. So I'll definitely look deeper into this stuff as a starting point for that. :)

August 28, 2014 06:55 PM
Mak
Mak

Very nice Fabien! An elegant overview... you've made me want to dig an old platformer project back out into the harsh light of day... the time consuming aspect of designing challenging levels is what put it at the back of the shelf!

August 28, 2014 08:22 PM
TheItalianJob71

Very nice article , thanks for sharing your experience with others

August 29, 2014 08:31 PM
GrimmBro

Always interesting to read up on Procedural Level Generation. A nice addition would be to let the path intersect itself.

September 03, 2014 07:15 AM
Paragon123

Very nice article... very enlightening, and it even managed to be an enjoyable read.

September 06, 2014 03:51 AM
Dmitry Demenkov

Wow. I heard about platform roguelikes before. This is very useful for future projects.

February 14, 2015 11:04 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!

Procedurally generating every element of a level for a 2d platformer is rarely discussed -- Fabien details his entire approach.

Advertisement

Other Tutorials by fabienbk

fabienbk has not posted any other tutorials. Encourage them to write more!
Advertisement