Algorithms of intellectual autogeneration of levels in iOS game

I love to look at the starry sky and think about distant worlds, but the fact of the infinity of the universe hardly fits in my head. According to the big bang theory, our universe is continuously expanding and cooling from a singular state, but let's assume that our infinite universe is constantly generated according to certain rules, and the number of these rules is limited. It can be assumed that our universe has already been generated, that is, for each point of the infinite universe, generation was generated according to a finite number of rules (generation was performed an infinite number of times), as a result we have an infinite generated universe.

Let's return to our task, we need to intelligently generate maps for the IPhone / iPad games of the “Mario” type, for a start we will look at the generation of a map within a field of 128x128 cubes.

Why even generate a map for the game if you can draw it in the map editor? Developing the iOS game “tanchiki”, I made a level editor with the ability to save a level on my server, I expected that the players themselves would draw maps and send them to me. But the reality turned out to be more severe, the players piled me with thousands of cards, which, to put it mildly, were unfinished, unfinished and simply ugly. Developing a new game, I firmly decided that the level should be generated automatically and look as far as possible, comparable to the levels from the editor.
')
What we have:
- The map consists of 128x128 blocks, each block has a size of 32x32 pixels;
- The map is stored in the form of an array of 128x128, where:

• 0 - empty block;
• 1 - the ground, the character can mix up on this block and can blow it up;
• 2 - stone - a block that can not be blown up;
• 3 - a box with jewels;
• 4 - thorns, on falling on which the player dies;

Level generation by simple method or random method

To begin with, I decided to implement the function of generating a map with a simple formula that includes the randomization function. By changing the values ​​of the variables in the formula, I hoped to calibrate the map to an acceptable state.



strong> The formula generated the following elements of the game map:

1. Floors: the whole map was divided into conditional floors, the distance between the floors was determined by the "Rand" function.
2. Gaps: between floors a random number of passes of random width was generated.
3. Noise: random blocks formed on the floors.
4. Rooms: a random number of rectangular rooms with one, two exits or no exits was formed on each floor.
5. Treadmills: in order for the player to accelerate while running, a random number of straight running tracks were generated on each floor, a “ceiling” of random height was randomly drawn over some of them.

Cons level generation method "random"

• The level passed too quickly, as often the openings between the floors were one above the other.
• The levels looked too monotonous.
• Maps visually looked too unpresentable.

Improving the complexity of the formula for generating a map could have achieved a better result, but I decided to move along a different path.

Requirements the algorithm must meet

• For this game, the main character must get from point A to point B.
• While advancing in level, a player should not be stuck or stumble on a dead end.
• You must have space to fly a jetpack.

Level generation using path

How to generate maps? By patterns! And the templates themselves will contain smaller templates (subpatterns).

To begin, let's divide our playing field into 64 squares, 8x8, for each of these squares we will load the values ​​from the template in the future, let's call this square “room”. So, now our map consists of 8x8 = 64 rooms.

The essence of the game is to get from point A (entry point) to point B (exit point) while moving from one room to another. In this case, the entry point is in the upper row of rooms, and the exit point is at the bottom of the map.

So, first we need to create a route (path) along which the player should move. To do this, we divide our rooms into types:

• 0: A room that is not in the path of the main route.
• 1: The room from which there is guaranteed to have an exit on the left and on the right.
• 2: The room from which there is guaranteed to have an exit on the left, on the right and below.
• 3: The room from which there is guaranteed to have an exit on the left, right and above.

This algorithm for generating a path resembles the device of a Turing machine; we have a control device (write-read head) that moves through the matrix of rooms. The number of possible states of the control device is of course and precisely specified, the states correspond to the types of rooms.

• To begin with, we place the first room in the top row, the type of room can be 1 or 2, but for a start we set type 1.
• Then we have to decide in which direction we should move, for this we take at random a number from 1 to 5, if this number is 1 or 2 - then we move our way to the left, if 2 or 3 - then to the right, if this number is 5 - then we move down, while changing the type of the very first room from 1 to 2 (now the starting room has an exit below).
• If, while moving, our path “rests” against the screen boundaries on the left or on the right, then we change the direction to the opposite. It is worth noting that each time we move down, we must overwrite the type of the current room from 1 to 2 (as this room has an exit from below).
• After moving to the next room, we check from which room we have just moved. If from a room with type 2 - then now our room can have again type 2 (with the next exit down) or type 3 (exit from the top, left and right). Since the rooms of type 2 and 3 have exits to the left and to the right, we can repeat our algorithm again and again.
• If we are already in the bottom row, and the algorithm suggests that we move even lower, then we simply place the exit from the room and complete the algorithm.

At this stage, we have formed a movement path for the character, now we just fill all the rooms unaffected by the algorithm with zeros (0 is a room that may not have exits at all).

Algorithm parameters

How can you influence the algorithm so that it generates paths with different characteristics, for example, less tortuous or, conversely, more entangled?

If you choose a random number from 1 to 7 on the first paragraph of the algorithm, move the number from 1 to 3 and move to the left, with the number from 4 to 6 to the right, and if the number 7 goes down, then during the generation there will be more rooms on each floor such as “1”, this will make the path more confusing. A random number from 1 to 3, by analogy will make the path less tortuous.

Displays the path on the map

On these screenshots, I tiled all-purpose rooms like “0” to better display the path.

Templates

Each room is a 16x16 square, we have 4 types of rooms, for each type of room the templates will be in a separate .plist file:

room0.plist
room1.plist
room2.plist
room3.plist

To begin with, we will define restrictions for our types of rooms, rooms of type 1 do not have exits at the bottom and at the top, which means that regardless of the pattern, exits at the top and bottom for rooms of type 1 can be immediately “closed”. For rooms of type 2, we “close” the exit from below, and for a room of type 3 - exit from the top.



Each time for each room of type 1, the program selects any template from the file room1.plist,
and for this template in 50% of cases makes a mirror image from left to right.

Consider an example of patterns for rooms of type 1:



When drawing up a map from a template, we use the following rules:

• 0 - empty block;
• 1 - the ground, the character can mix up on this block and can blow it up;
• 2 - stone - a block that can not be blown up;
• 3 - a box with jewels;
• 4 - thorns, on falling on which the player dies;
• 7 - “sub-pattern” - a block with a height of 3 and a width of 5.
• 8 - 75% chance that there will be land. 25% - the probability of emptiness.
• 9 - 50% chance that there will be land.

Masking pattern

If you assemble a card from templates, then on large maps there will be repeated sections with blocks, our task is to make the cards within the same template differ from each other.
To do this, in addition to mirroring the templates horizontally, we enter the numbers 8 and 9 in the templates, which, with a probability of 75% and 50%, respectively, are replaced by one (earth block). If our GZCH (write-read head) stumbles upon the number 7 - then this section of the template is replaced with a “sub-pattern”, which is read according to the rules similar to the template.

Sub-patterns

Subpatterns are also introduced to make two identical patterns different from each other. There are 7 numbers in the templates - if the algorithm stumbles on the number 7, then it fills the template with any “sub-template” from the boxTemplate.plist file

Examples of sub patterns:

00100
01110
00100

11111
01110
00100

00100
11111
00100

For subpatterns, in 50% of cases we make a mirror image from left to right.

I tried to avoid creating a graphical map editor, but for drawing templates I still had to implement it. The more templates and sub patterns you add to the game, the more diverse your cards will look.

Result of using “sub-template”

In these four screenshots, you see the same template , which, thanks to the numbers 7,8,9, looks different every time.


In the video you can see how the generation of levels looks like in practice:

Perspectives

• The number of templates directly affects the quality of the level, so adding new templates will greatly improve the gameplay.
• For more diverse cards, you can make “sub-templates” in “sub-templates”.
• By changing the scale of the world and the points of entry and exit - you can generate an infinite map, dynamically forming blocks in the way of the character and caching the traversed sections.

If you are interested in this topic, let me know, I will cover the topic in more detail.

To compile this article, I partially used Spelunky game level generation algorithms, but there may be games with more advanced level generation that I don’t know about.

Write in the comments what other games with good level generation you know.

All errors on this article, please send in private messages.