Mon, Feb 02, 2015

Level Generation for Platform Games

For my new game 1-bit Ninja Remix Rush I wanted to create a twist on the endless runner genre. A game that would be score/distance focused, use procedural generation to create different challenges each play-through yet keep the tight level design that people enjoyed in the original 1-bit Ninja. An endless platformer if you will.

1-bit Ninja Remix Rush screenshot

In this article I'll explain the implementation I ended up with for 1-bit Ninja Remix Rush's level generation. It is by no means the most sophisticated approach one could take but I think it is surprisingly effective and for all the information out there on procedural content generation, techniques specific to side scrolling platform games seem to be in the minority. I hope you enjoy!

Maintaining a Hand Designed Feel

Creating procedurally generated levels that feel hand designed is almost certainly a priority for any 2D platform game. Procedural content generation is by it's very nature random and so the best results will always require human input in some form. For 1-bit Ninja Remix Rush I decided to start with a basic template system that would allow me to design small sections of level layout that could then be stitched together by the generator.

1-bit Ninja Remix Rush is built on the same custom game engine as the original 1-bit Ninja. A level is loaded as chunks, small subsections of a level 8 tiles wide by 16 tiles high. Luckily this was an ideal starting point for the template system. I tried several different dimensions for each template but eventually settled on 3 chunks per template, bringing the total dimensions to 24 tiles wide by 16 tiles high.

Level template editing in Tiled editor

Levels in both 1-bit Ninja and Remix Rush are designed in the open source map editor Tiled, exported as XML and then converted to a custom binary format using my own conversion tool. To keep things simple, the templates in 1-bit Ninja Remix Rush are contained one after the other in a single level file. With over 150 unique templates in the game, having them laid in a single file made creation of new templates and editing of existing ones easy and helped in the later stages of the generation process.

Laying Out a Level

Using the collection of level templates as a starting point it is then the responsibility of the level generator to stitch them together to create a coherent never ending level for the player to enjoy. I toyed with several different approaches ranging in complexity but in the end it was the simplest technique that won out.

Since the player will always enter a new template from the left and exit from the right and we know the maximum height the player can jump (3 tiles), all the generator has to do is pick a random template who's left-most platform is reachable from the previous template's right-most platform. Keeping with the simple approach, I made it a prerequisite that all templates must start and end with a solid platform. Starting or ending a template with a lip, that is a platform above a platform, could potentially result in unreachable or player-trapping areas however with 24 tiles per template width this was a minor trade-off.

Level template stitching diagram

Sorting the templates for stitching is a two part process. First, every template's tile map is scanned for the left-most solid platform and right-most solid platform, this information is stored with the template. Second, 16 arrays are created, 1 for each possible tile Y position and the index of each template reachable from that Y position is added to the appropriate array. When the screen scrolls to a point where a new template must be stitched the generator uses the right-most platform's Y position in the last template to pick the appropriate array and then simply pulls a random index from it thus choosing a random, yet guaranteed reachable new template. While this initial sorting phase could be conducted in a preprocessing step it is so light that it's actually run every time at the start of the game with no perceivable delay.

Adding Variance

The level template system was working great however I wanted to add an extra level of variance to the output of the level generator. I'd read an article on Spelunky's level generation and it's use of probability tiles to create randomized rooms that still maintained a predefined structure and figured this would be ideal. Since Tiled allows multiple layers in a tile map and my custom level format already had a few remaining unused bit flags per tile it was easy to implement several ranges of probability for both tiles and sprites. Using this approach, minor details all the way to entire sections of a template can be made to only appear with certain probability when instantiated. In 1-bit Ninja Remix Rush this is used to not only vary the overall layout of the level and enemies but also the appearance of the time-extending big bits and invincibility giving potion.

Want to check out the end result? 1-bit Ninja Remix Rush is now available on the App Store. If you haven't played the original 1-bit Ninja, you can now purchase it along with Remix Rush for a discount in the 1-bit Ninja Bundle.