Jump to content
  • Advertisement
  • 09/01/14 01:38 PM
    Sign in to follow this  

    Procedural Level Generation for a 2D Platformer

    General and Gameplay Programming

    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:
    The first step is to create this random path of rooms. The goal is to get a data structure describing something like this:
    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.
    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.
    As you can see, while the solution path is quite clear before this step, it is eventually neatly disguised.


    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.

      Report Article
    Sign in to follow this  

    User Feedback



    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.

    Share this comment

    Link to comment
    Share on other sites

    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.

    Share this comment

    Link to comment
    Share on other sites

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

    Share this comment

    Link to comment
    Share on other sites

    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!

    Share this comment

    Link to comment
    Share on other sites

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

    Share this comment

    Link to comment
    Share on other sites

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!