Geekly Articles each Day
📜 ⬆️ ⬇️

Level generation in the arcade on the example of indie game



In this article I would like to tell you about the level generation algorithm in the simplest game of the “runner” genre, which I developed a few days ago. If you are interested in the topic of game development, as well as algorithms for random generation of game levels, dungeons, traps or landscape, welcome to the cat.

About the game


To begin with, to make it clear what's what, I’ll tell you 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 man jumped or planned in the air and dodged numerous spikes from traps. The main mechanic of the game consists in timely jumping up to the trap and correctly calculating the planning time on small handles (yes, in the animation, the little man waves his arms, and the fall slows down due to this).

First generation version


The game was developed in the hackathon format, so 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 thorns:


The spikes, which I called the "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, in contrast to 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:

Based on the problems outlined 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 non-uniform and unique at each level segment.

Final generation algorithm


Basic concepts


Zones

There are several types of zones, for simplicity, I will 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 selected randomly from the 5 types above. The length of the zone is limited when the player completely runs through it, the next zone is selected as well as at the beginning of the game, randomly. When creating a new zone, a new random length is set (mostly, from 40 to 100 meters). Also, when changing zones, a small safety net is created between zones, so that they do not “interfere” with each other.



Each type of zone has its own chance of appearance, for example, a new zone will be a zone with “walls of shuriken” with a probability of 30%.

The type of zone is responsible for which traps will be generated at this site. Therefore, each zone has its own peculiarities and ways to overcome obstacles, and, consequently, special rules for generation (so as not to create an impassable section).

As mentioned above, the game has a parameter Difficulty , 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 from abstract things to concrete examples.

Zone with "random spikes on the floor"

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

An example of generation with minimal complexity (complexity = 0)


Generation example with maximum complexity (Complexity = 100)


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

The basic principle in our area: create or not create spikes on the floor (depending on the randomness). This zone of all is the simplest in terms of 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 can be set, and how many can not be by means of routine testing.



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

In this zone, each next trap (or absence of a trap) is generated with a delay equal to the trap width. Thus, if the traps are created continuously, then there will be no free space between them until they are 5 in a row (our condition “no longer than 5 spikes in a row” will work).

But we must not forget about the role of randomization in the generation. Each new trap can either be created or not created. Here, finally, complexity will play its role. The higher the complexity , 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. It is necessary to add rare spikes on the ceiling to add variety, but it is impossible to break the basic logic of overcoming traps. For example, if you make spikes on the ceiling just above 5 spikes somewhere between them, then the player simply cannot jump as high as he needs to overcome 5 spikes in a row. Therefore, the spikes on the ceiling should be located somewhere along the edges of such large groups of "floor" traps.

Add to the algorithm the creation of "spikes on the ceiling" with a probability of from 70% to 100% (depending on complexity), provided that:
 if ((Last_traps[1] == Traps.None) || (Last_traps[2] == Traps.None) || (Last_traps[3] == Traps.None)) { // ...      ... } else { // ...  ... }

That is, if the penultimate, or the pre-penultimate, or the pre-penultimate trap is missing (there are no thorns on the ground), then you can create thorns on the ceiling, otherwise you cannot.

Great, one algorithm is ready. It remains to disassemble the remaining 4!

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

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

Differences:

Difficulty = 0 (minimal)


Difficulty = 50 (medium)


Difficulty = 100 (maximum)


There are no strong differences in the algorithm from the previous zone, except that not spikes on the ceiling are randomly generated, but “shurikens”, and at various difficulties there is a different chance of the appearance of a “shuriken”. A “shuriken” can appear with a probability from 30% to 60% (linearly dependent on complexity) over a place without spikes on the floor (because if you create them over spikes, there is a very high probability that an impassable place will occur).

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

Difficulty [0-50) - Create a shuriken high.
Difficulty [50-80) - 50% Build high; 50% Build at medium height
Difficulty [80-100] - Create at medium height.

Spiked Area on the Floor

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

Difficulty = 0 (minimal)


Difficulty = 50 (medium)


Difficulty = 100 (maximum)


The main focus in this zone was that the player should always jump to his maximum, that is, through 5 spikes. But, since the game has a changing complexity , 3 variations of the zone were introduced (see screenshots above):

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

This zone is probably the easiest, 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 a complexity of 75, problems begin, because if at least a little wrong time is calculated and you jump earlier, you will fall on the spikes.

The spikes on the ceiling here are generated on the same principle as in the first zone, but unlike the first zone, there is no benefit from them except fear and diversity, since it is impossible to run into them because of too small islands without spikes. .

Area with “walls of shuriken”

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

Difficulty = 0 (minimal)


Difficulty = 50 (medium)


Difficulty = 100 (maximum)


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

Difficulty [0-40) - Light zone, holes of width mostly 2 shurikens each.
Difficulty [40-90) - The middle zone is much more complicated than the “Light” one, since basically there are holes with a width of 1 “shuriken”, there are different ways to overcome it.
Difficulty [90-100] - Difficult area, the holes are always 1 “shuriken” wide, a bit more difficult than the “Medium”, since the passage is always the same.

The main principle of generation of such walls: between each wall is always a constant distance (independent of the 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 complexity , the smaller the distance), and when moving from one subtype of the zone to another (for example, from the Light Zone to the Middle Zone) the distance between the walls will again decrease from 8.5 m to 7.5 m. Thus, with a difficulty of 39.99, there will be “light walls” in the zone, but the distance between them is 7.5 meters, and with a difficulty of 40 - “medium walls”, but a distance of 8.5 meters.

The 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 to allow at least some complication within the subtype of the zone.

Now 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:



Zone with "random generation"

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



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

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

Conclusion


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

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 .

Source: https://habr.com/ru/post/230943/

More articles:


All Articles