Procedural Level Generation for a 2D Platformer

Share on RedditTweet about this on TwitterShare on Google+Share on FacebookShare on LinkedIn

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 the post.

Here’s what it looks like.

10-game

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 post will focus the architecture (platforms, blocks, and ladders).

Step 1. Generating a level layout

Levels are composed by a random sets of discretly 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:

10-levelexample

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

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 naviguate trough all these rooms, to reach the last one. Given that the player movement is constrainted 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 directly the player to the level exit, without interruption.

10-layout2

At first, it may seem too straightfoward, but once the generation is complete, this path is “hidden” in the middle of the others platforms, and is not evident at all to the player. In fact, it is so camouflaged that I add to put sign posts indicating the direction to follow. The player often gets out the path, find alternatives 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, an 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 determines 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 heurisitics 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 block completely 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

As you can see, while the solution path is quite clear before this step, it is eventually neatly disguised.

Conclusion

This simple method produce a lot of variability, which is nice, yet the gameplay remains relatively consistent. After some runs, the player learn 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!

Share on RedditTweet about this on TwitterShare on Google+Share on FacebookShare on LinkedIn

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>