When we started making Little Creeps – the 2D endless runner game on mobile – we were faced with the problem of creating an algorithm that is going to be the core of the game – creating unique path in realtime so we can play as long as we like without the feeling that we are running around in circle.

The approach to accomplish this is called procedural generation and basically means that you’re using a procedure (and some randomness) to generate part of the game in realtime. Thanks to that it will always gonna be different because it was just created. As you can imagine there is many way to do it depending what you want to accomplish.

One of our main goals while creating the algorithm was to make a game that in theory could be played forever. It means we didn’t want to create situation when the number of traps at the path would make it basically impossible to go further (not enough space to fit character between all of them).

Other goals include:

  • making the path as unique as possible, we didn’t want the player to see the same things in the same places.
  • freedom in creating obstacles in various shapes and sizes. We didn’t wanted to have the limit that obstacle must have size x and y.
  • despite randomness we wanted to be in control of how difficult the path is at a given moment.
  • random placement of object should make sense – for example there shouldn’t be a platform that is unreachable (too high to jump on it).

 

To meet those goals we developed an algorithm that was randomly spawning objects on the stage with two main restrictions:

Personal space

It is an invisible area attached to each object, adjusted in size so that the object could be displayed properly and – if needed – to give enough space for character to pass it.

For the algorithm, the role of the personal space is simple: when a new object is created, it checks to see if its personal space is overlapping another object’s space. If so, the new object is removed, otherwise the object stays.

Reaching space

Its main purpose is to create a route where every object was within range of an another. If an object would be too far away from others to make it reachable (see the picture no. 1 and 2) the algorithm would remove it. So to sum up, the reaching space is the opposite of the personal space – an object can not exist if its’ reaching space is not within the zone of an another object.

Picture 1. The first condition is met (platform does not overlap with any other) but the second condition is not fulfilled. The platform is too high to overlap the floor’s reaching space.

Picture 2. Thanks to the first platform, the new platform is available because of their overlapping reaching spaces. As we can see it makes sense, the player has the ability to jump on a upper platform from the previous one.

 

Before we go through the whole algorithm we still have a few things to point out:

Our stage is composed from three separated block. When the last one isn’t visible (this means the camera and the player moved to another segment) it is cleared from previously spawned object and then it is moved to the front. After that the generation procedure is triggered. Thanks to splitting the path to three fragments and reusing them, we avoid problems with memory – it would be bad idea to spawn to big fragments of the level at once or to keep them for too long.

Picture 3. red – level section, green – obstacles / platforms, blue – player, yellow – camera view

Another thing that helps us avoid performance issues is first spawning only objects indicators, personal and reaching spaces. Only when we are sure that the object can remain in this place we generate the rest of the components like graphics and physics bodies.

 

So as we cleared this out let trace the steps of the algorithm:

  1. First of all we start with generating the floor. This is a simple procedure. We randomly choose between the hole or the floor. Only the floor has a spawner that allows to spawn obstacles in point 3. Each of them have the personal space and the floor also have its reaching space that tell us how far from it the platform can be.
  2. Next thing is to spawn platforms. There is a spawner that randomly spawns them in the air. If their position is unacceptable, we have two options – retry spawning at different random place or go to another spawner. By controlling the number of trials we can control the density of their occurrence. Each platform have its personal space so it can’t be spawned in the floor or in another platform. Thanks to spawning them step by step, one platform at the time we can have platform placed higher and higher (new platform relay on the reaching space of previous one – see the picture no. 1 and 2).
  3. Once we have all the platforms placed, we begin putting obstacles. They are spawned by spawners placed on each floor and platform. Their position are coordinates of the spawner combined with some random offset, provided that they personal space does not overlap with area of some other object (except the area of floor/platform to which they spawner belongs).
  4. Last step is to spawn other thing like collectable items, they are placed by another kind of spawners, following to the rules similar to this from point no. 3.

Eventually this process is going to generate quite a random looking path. Of course there are even more things to discuss, such as how to create the most unique looking platform but this is outside for one article. Hopefully you find this interesting or useful.