Arcade level generation on the example of an indie game

In this article I would like to talk about the level generation algorithm in the simplest runner game developed by me a few days ago. If you are interested in the theme of gamedev, as well as algorithms for randomly generating game levels, dungeons, traps or terrain, welcome to cat.

About the game

First, to make it clear what’s what, I’ll talk a little about the game itself. The game is a hardcore runner in which a small pixel man runs from left to right, and you need to have time to press one button (or tap on the screen, if this is a mobile version) so that this little man bounces or plans in the air and dodges numerous traps from spikes. The main mechanics of the game is to bounce in front of the trap in a timely manner and correctly calculate the planning time on the small handles (yes, according to the animation, the little man waves his hands, and the drop slows down due to this).

First generation version

The game was developed in the hackathon format , therefore, for the first version of the game, the simplest minimally working algorithm was created , which, as the player moved, created one of three types of spikes at a random distance from the previous one.

Types of spikes: The spikes


I called Shuriken were created at a random height between the floor and the ceiling. "Spikes on the floor" and "Spikes on the ceiling" corresponded to their name and were located on the floor and on the ceiling, so that the height, unlike the Shuriken, was stable.

For the first version, the generation turned out to be very good and interesting, but, unfortunately, there were two big minuses:

• Often traps were generated too high, because of this there were times when it was possible to run for a very long time without pressing anything.
• Periodically, combinations of spikes that were impossible to pass were created.

Based on the problems described above, I decided to create a good, well-developed generation algorithm that would not allow the creation of “impassable” places, would keep the player in constant tension and with all this would be heterogeneous and unique in each section of the level.

The final generation algorithm

Basic concepts

• Difficulty - a number from 0 to 100, at the beginning of the game it is 0, during the game it gradually increases at a speed of 1 unit. at 15 meters. When it reaches 100, it stops growing. Responsible for the "complexity" of the generated traps, no matter how trivial.
• Zone - a section of the level in which traps are generated according to a certain principle, depending on the type of zone.
• A trap is a single spike or group of spikes created simultaneously. There are several types of traps.
• 1 meter - the width / height of the man.

Zones

There are several types of zones, for simplicity I’ll give a piece of code:

enum Zones // зоны
{
	Random_spikes_on_floor, // случайные шипы только на полу
	Random_spikes_on_floor_and_solid_ceiling, // случайные шипы на полу и сплошные шипы на потолке
	Solid_spikes_on_floor, // сплошные шипы на полу	
	Shuriken_walls, // стены из сюрикенов (с дырками)
	Random // случайная генерация
}

At the beginning of the game, the zone is randomly selected from the 5 above types. The length of the zone is limited, when the player runs it completely, the next zone is selected in the same way as at the beginning of the game, randomly. When creating a new zone, a new random length is set (mainly from 40 to 100 meters). Also, when changing a zone, a small safety gap is created between the zones so that they do not "interfere" with each other.



Each type of zone has its own chance of appearing, for example, a new zone will turn out to be a zone with “walls of shurikens” with a probability of 30%.

The type of zone is responsible for what traps will be generated in this area. Therefore, each zone has its own characteristics and methods of overcoming obstacles, and, therefore, special rules for generation (so as not to create an impassable area).

As already mentioned above, the game has the Complexity parameter , which increases with time from 0 to 100, and this parameter directly affects the number or location of traps during generation in each zone. But let's move on from abstract things to concrete examples.

Zone with "random spikes on the floor"

In this zone, the algorithm is based on creating traps primarily from spikes on the floor in a more or less random sequence.

An example of generation at the minimum complexity (Difficulty = 0)


An example of generation at the maximum complexity (Difficulty = 100)


First, I will explain a little how generation works inside any zone. Upon entering the zone, one of the possible (randomly selected) traps is created, and depending on which trap was selected, a new delay is set (how many meters will a new trap be created in this zone). As soon as the player passes the delay , a new trap is created, again randomly selected. Naturally, for each type of trap in each zone there is a chance of occurrence.

The main principle in our zone: to create or not to create spikes on the floor (depending on the randomness). This zone is the simplest of all according to the algorithm and finding problem areas, because it consists mainly of spikes on the floor, which are always at the same height. Accordingly, we can determine how many spikes in a row you can put, and how many can not be done through routine testing.



The image above shows that at the maximum jump height and hover time, the player can overcome no more than 5 spikes going close to each other. Accordingly, a condition is necessary in the algorithm: if there are already at least 5 traps in front of the generated trap, be sure to leave an empty space (do not generate a trap). To do this, it is necessary to remember what traps were in front of the current one (I used the usual array of enums of size 10 for this, because I do not need to remember more than 10).

In this zone, every next trap (or lack traps) generated with a delayequal to the width of the trap. Thus, if traps are created continuously, then there will be no free space between them until there are 5 in a row (then our condition “no more than 5 spikes in a row” will work).

But we must not forget about the role of randomness in generation. Each new trap can either be created or not created. Here, finally, complexity will play its role . The higher the difficulty , the higher the chance of a spike on the floor.

random = UnityEngine.Random.Range(0f, 100f); // случайное число от 0 до 100
if (random < 40f + (Difficulty.Difficulty_of_game() * 0.4f))  //  Difficulty.Difficulty_of_game()  возвращает сложность игры
{
	// ...создать ловушку...
}
else
{
	// ...не создавать...
}

Great, it turned out a good algorithm for generating spikes on the floor, but something is missing. You need to add rare spikes on the ceiling to add variety, but you can't break the basic logic of overcoming traps. For example, if you make spikes on the ceiling directly above 5 spikes somewhere in between, then the player simply will not be able to jump as high as he needs to overcome 5 spikes in a row. Therefore, the spikes on the ceiling should be somewhere along the edges of such large groups of "floor" traps.

We add to the algorithm the creation of "spikes on the ceiling" with a probability of 70% to 100% (depending on complexity), provided:

if ((Last_traps[1] == Traps.None) || (Last_traps[2] == Traps.None) || (Last_traps[3] == Traps.None))
{
	// ...в этом месте шипы сверху создавать нельзя...
}
else
{
	// ...создаём шипы сверху...
}

That is, if the penultimate, or pre-penultimate, or pre-pre-penultimate trap is absent (there are no spikes on the ground), then you can create spikes on the ceiling, otherwise you can’t.

Ok, one algorithm is ready. It remains to make out the remaining 4!

Zone with "random spikes on the floor and solid spikes on the ceiling"

This zone is essentially a sophisticated version of the "zone with random spikes on the floor."

Differences:

• Throughout the zone there are spikes on the ceiling.
• For a change, “shurikens” have been added in some places.
• The maximum number of spikes on the floor in a row is not 5, but 4 (due to the spikes on the ceiling, the maximum jump height decreases).

Difficulty = 0 (minimum)


Difficulty = 50 (average)


Difficulty = 100 (maximum)


In the algorithm there are no strong differences from the previous zone, except that random spikes are generated on the ceiling, but “shurikens”, and there’s a different chance for different difficulties the appearance of "shuriken." “Shuriken” can appear with a probability of 30% to 60% (linearly depending on complexity) above a place without spikes on the floor (because if you create them above the spikes, it is very likely that an impassable place will arise).

In addition, “shurikens” can appear at different heights depending on complexity. If you look closely at the screenshots, it becomes clear that the lower the “shuriken”, the more difficult it is not to hurt him when jumping. Based on this, I created a dependence of height on complexity:

Difficulty [0-50) - Create a “shuriken” high.
Difficulty [50-80) - 50% Create high; 50% Create at Medium Altitude
Difficulty [80-100] - Create at Medium Altitude.

Zone with "solid spikes on the floor"

This zone strongly resembles the first zone “with random spikes on the floor”, but has two differences:

• Spikes are always in a row in groups of 3 to 5 spikes (it depends only on complexity , randomness does not matter).
• Between groups of spikes there is always a gap in width comparable to the width of the spikes (2.25 meters).

Difficulty = 0 (minimum)


Difficulty = 50 (medium)


Difficulty = 100 (maximum)


The main emphasis in this zone was that the player would always have to jump to his maximum, that is, after 5 spikes. But, since the game has varying complexity , 3 zone variations were introduced (screenshots see above):

Difficulty [0-25) - Easy zone, 3 spikes in a row.
Difficulty [25-75) - Middle zone, 4 spikes in a row.
Difficulty [75-100] - Difficult zone, 5 spikes in a row.

This zone is probably the simplest, because there are no unexpected and very difficult places, the same situation repeats throughout the zone (N spikes in a row, space, N spikes in a row, space, etc.). Although, with difficulty 75, problems begin, because if you calculate the time even a little incorrectly and jump earlier, you will get to the spikes.

Spikes on the ceiling here are generated according to the same principle as in the first zone, but unlike the first zone, they are of no use here except frightening and variety, since it is impossible to run into them because of islands that are too small without spikes .

Shuriken Wall Area

Here we come to probably the most difficult zone to pass. Its main principle is similar to a trick with a “ring of fire” in a circus: you need to fly between the spikes without hitting them. Let's look at the screenshots for different difficulties:

Difficulty = 0 (minimum)


Difficulty = 50 (medium)


Difficulty = 100 (maximum)


As in the previous zone, we have 3 variations in complexity:

Difficulty [0-40) - Easy zone , holes with a width of mainly 2 "shurikens."
Difficulty [40-90) - The middle zone is much more complicated than the “Easy” one, since basically there are holes with a width of 1 “shuriken”, there are different options for overcoming it.
Difficulty [90-100]- A difficult zone, holes are always 1 "shuriken" wide, a little more complicated than the "Medium" one, since the passage option is always the same.

The basic principle of the generation of such walls, always a constant distance between each wall (not depends on randomness), which varies depending on the current complexity . The distance between the walls is always from 8.5 m to 7.5 m (the higher the difficulty , the smaller the distance), and when moving from one subtype of the zone to another (for example, from the Easy Zone to the Middle Zone), the distance between the walls will again decrease from 8.5 m to 7.5 m. Thus, with a complexity of 39.99 in the zone there will be “light walls”, but the distance between them is 7.5 meters, and with a complexity of 40 - “medium walls”, but the distance is 8.5 meters.

Distances were tested on different combinations of walls, and it was found that 7.5 meters is the minimum distance at which you can comfortably manage to land and jump again without hitting the spikes. A gradual decrease from 8.5 meters was made so that there was at least some complication within the subtype of the zone.

Now about how it is determined which wall will be next in the zone. Everything is very simple, for each complexity there is a certain set of walls from “shurikens”, and each time a random wall is selected from this set:

Random Generation Zone

When I created the 4 previous zones, everything was fine, but something was missing. Although my first version of generation (full random) was flawed, it still had its own charm. Therefore, I decided to create another zone, which would be essentially a copy of my first version of the generation, but without its previous drawbacks (impassable and boring places):



To create an improved version of the old generation, I created a zone from existing traps and set certain rules and odds:

• 35% "Shuriken" at a random height - the distance to the next trap is from 7 to 4 meters (depending on complexity).
• 30% Weak wall of “shurikens” - created 4 meters further from the previous trap, the distance to the next trap from Random (9.5, 11.5) to Random (7.5, 8.5) meters (depending on complexity), provided that Random ( N, M) is a random number from N to M.
• 20% Spikes on the ground and ceiling - the distance to the next trap is from 6 to 3.75 meters (depending on complexity).
• 10% Spikes on the ground - the distance to the next trap is from 6 to 3.75 meters (depending on complexity).
• 5% Spikes on the ceiling - the distance to the next trap 6 to 3.75 meters (depending on the complexity).

The distances between the traps were obtained by numerous tests (including the most critical cases), although after the release one jamb was found in the creation of the “shuriken” wall, because of which it was very rarely an impassable or very difficult place, but I quickly corrected this jamb .

Conclusion

As a result, I obtained a fairly complete and non-trivial algorithm for generating traps in the game, which:

• Dynamically generates difficult to complete levels, which creates a kind of challenge .
• Does not create dead ends or near dead ends.
• Each time creates a unique level, not similar to the previous one.
• Depends on gradually increasing complexity.

Thank you for reading! If you have questions or find any errors, be sure to write about it in the comments. You can play the game for free here - niceplay-games.com/games/hardmode-on.html .