Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
33Likes
Dislike

Procedural Level Generation for a 2D Platformer

By Fabien Benoit-Koch | Published Sep 01 2014 07:38 AM in Game Programming
Peer Reviewed by (Servant of the Lord, dejaime, Aardvajk)

procedural level generation 2d platformer

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 20×16 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:


Attached Image: 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:


Attached Image: 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.


Attached Image: 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.


Attached Image: 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.



About the Author(s)


After a decade in "corporate" software engineering, I decided to jump back to my first love, game development, hoping to
recreate the arcade feel of classics on modern platforms. With the help of my partner in crime, Marcin JP, we founded Arcade Pulp,
and we're currently busy with "Turbo Smash Blade", an old school brawler for mobiles phones.




Comments

Very simple and effective. Nice article!

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.

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.

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. :)

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!

Very nice article , thanks for sharing your experience with others

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

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


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS