Procedural level generation for puzzle games

If you have already tried to create your own puzzle game, you may already have realized that the implementation and coding of game rules are quite simple, but creating levels is a complicated and lengthy job. Or even worse - you spent a lot of time creating several levels trying to insert certain tasks into them, but when your friends tried to play them, they went through these levels in a completely different way or in such simple tricks that you did not even think about them.

It would be great to find a way to make the computer save you time and solve the problems that I mentioned above ... And this is where procedural generation comes to the rescue!

It must be said that for example there is only one way to sum vectors, and any programmer who needs it must follow the same rules; however, in the case of procedural generation, you are absolutely free. There are no right and wrong ways. The main thing is the result.

Fruit Dating - rules and features

Not so long ago, we released Fruit Dating for iOS devices (it is also available for Android and even for the unreleased (at the time of the release of the game) Tizen). This is a puzzle game with simple rules. Her goal is to connect pairs of fruits of the same color by swiping a finger across the screen. Moving your finger corresponds to the tilt of the playing field in the desired direction. When a player tries to complete his task, various obstacles such as stones, cars and other fruits stand in his way. All moving objects move in one direction. The pictures below show the first level, in which 3 moves are required to connect the fruits.





Over time, new features are added:

	One-way passages are placed at the tile boundary and limit the direction in which objects can be moved.
	Anteaters can look in different directions, but this direction is constant and does not change during the level. When the fruit is in the direction of the anteater’s gaze, it “shoots” with its tongue and draws the fruit to itself.
	Stones, cars and barrels can move through puddles, but not fruit. When a fruit falls into a puddle, it becomes dirty and the date is canceled for it!
	A sleeping hedgehog stands on a tile and wakes up when something hits him. If a barrel, stone or machine hits him, he falls asleep again because they are inedible. But when fruit hits it, the hedgehog eats it.

You probably already noticed that the level consists of tiles; this simplifies the work, because each level can be represented as a small grid. Its maximum size is 8x8 tiles, but there is always a fixed border, so the “useful” area is no more than 6x6 tiles. This may seem a little, but it is proved that for such a field you can create quite complex tasks.

Based on the basic rules (as additional features were added later), I began to create my own generator. At first, of course, I thought that someone in the world had already solved a similar problem, so I began to search the Internet for procedural generation of puzzle levels. It turned out that this issue was not considered very widely. I found only a few articles useful to me. They mainly focused on generating / solving levels for Sokoban. For example:

One and two .

It was also interesting that most of them were written by scientists (Sokoban professors :-)). From these articles I learned two principles: firstly, if you randomly generate something, it’s good to introduce a little symmetry so that people perceive the results more positively. Secondly, the choice of algorithm is up to you, but none of them are perfect.

Puzzle Tool

Obviously, each generated level must undergo testing (to understand whether it can be solved, and how difficult it is), so first I decided to create a tool for solving levels. Since at that time I took into account only the basic rules without additional features, I had the following ideas for the “solver”:

a) from the starting position, you can start moving in any direction (left, right, up, down);
b) from the next position you can continue in any direction again;
c) in any position, the fruit compounds are checked, matching fruits are removed from the field and paragraph b) continues until several fruits remain on the field.

As you can see, this is a simple brute force approach. So, the number of possible positions on the field was: 4, 4 * 4 = 4 ², 4 * 4 * 4 = 4 ³ , ... 4 ⁿ. On move 10, more than a million combinations of the field turned out, and on move 25 - 1125899906842624 combinations. Well, then we can limit the maximum number of moves, say to 10, and we will not be interested in more difficult levels, but here another danger lies. Some of the puzzles can be created or generated in such a way that a player who made some bad moves at the beginning cannot complete the level. Or in some levels a loop of states on the field may occur. If the algorithm branches in this direction too early, the level can be marked as unsolvable, even if there are shorter branches with a simpler solution. Also, if the algorithm finds a solution, there is no guarantee that it is the shortest - you need to complete all branches in order to find the shortest solution. Moreover, Such conditions often arise on the field that one move in a certain direction does not change anything. Look at the third picture in the section “Fruit Dating - rules and features” - nothing will change if we move to the left.

Therefore, the rules have changed:

a) from the current situation, try to move in any direction;
b) if the state on the field has changed, check whether such a state is new, or if it already was;
c) if the state is new, save it together with the depth of the solution (the number of moves needed to get into such a state);
d) if previously there was such a state, and the depth of the solution was equal to or less than the current, delete the current branch. Otherwise, replace the old state (because we got into it through fewer moves) and continue.

There are also other rules, for example, checking the coincidence of fruits and terminating the whole process when finding a solution; in addition, later other rules related to additional features arose, but I described the basic solution tool. He quickly cuts off entire branches without a solution. In addition to the depth of the solution, it also checks the parental positions stored for each state on the field, so that at the end you can easily print the solution. Let's look at an example of the first level of the game:


From the starting position, the moves branch into four possible directions. We mark them as 1-1, 1-2, 1-3, 1-4. The algorithm always seeks to move in the following order: right, up, left, down. Since it is necessary to use the stack to further study the stored states, the first continuing state is transferred to the stack last (in our case, 1-4). Again, the first move is a shift to the right (2-1) and since this is a new state, it is written onto the stack. The next is a shift up, which leads to a state of 2-2. We were already in this state in the first iteration. Therefore, we apply rule d) and terminate this branch - nothing is written to the stack. Next is an attempt to move to the left. It leads to a new state (2-3) and it is pushed onto the stack. The last move is a downward shift, but there is no difference between 1-4 and 2-4, therefore, we do not push anything on the stack (rule b) ... there is no new state = we are not doing anything). Now the top state of the stack is 2-3. From it, we move to the right and fall into state 3-1, which is equal to state 2-1. But at 2-1 we were in the second iteration, so we cut off this branch. Then we move up, the fruits are on neighboring tiles, and since it was the only pair, the game ends.

The algorithm works, although it may not find the shortest path. He simply takes the first solution found. To fix this, I first limited the maximum number of moves to 30. If no solution is found, I consider the level impassable. If the solution is, let's say, on move 15, I again start the “solver” with a maximum solution depth of 14 (15 - 1). If no solution is found, then 15 is the shortest path. If a solution is found, for example, on move 13, I run the tool with a maximum depth of 12 (13 - 1). I continue the process until some solution comes back. The last returned solution is the shortest solution.

Generator

We created a “solver”, now you can go to the generator and check with it every generated puzzle.

The generation phase consists of two parts:

• wall generation
• generating objects on the field

Wall generation always starts by drawing a fixed field border:


Random parameters are generated that tell whether the wall will be painted one tile at a time, or two tiles each. In the case of two tiles, random symmetry is generated. It tells where the second tile should be located - whether it will be reflected vertically, horizontally, rotated 90 degrees or will there be a combination of transformations. In the first grid in the figure below, only one tile is painted at a time. In all other grids, various examples of random symmetry of two tiles are presented:


The number of walls, their length and direction are random. Each wall begins with a random point on the border. Each wall is drawn in one or more iterations. After the first iteration, a number is randomly selected between 0 and (wall length) - 1. If it is zero, the iteration cycle stops. If it is greater than zero, then this number becomes the length of the next part of the wall. A random point of the current part of the wall is selected, the direction is chosen randomly, orthogonal to the current part of the wall, then the next part of the wall is drawn. The result may look like this (iteration is indicated by numbers):


The picture shows that each next part of the wall is shorter, so you can be sure that at some point the wall will end.

Since all walls start from the border of the field, each individual tile was connected to the border. It looked boring to me, so I added another step where internal walls are generated. The interior walls are not connected to any existing tiles. The stage begins by choosing a random tile and checking if it is free and tiles within 3x3 of it. If so, then the wall WILLplaced in the grid, and the next tile is selected according to a random direction (this direction is randomly selected before testing the first tile). The cycle is interrupted when the condition for 3x3 tiles is not satisfied. Pay attention to the word "will" highlighted above. If you put the wall in the grid right away and proceed with processing the next tile, the area within 3x3 will never be free, because you just placed the wall there. Therefore, I save all the wall tiles in a temporary array and at the same time put them in the grid after the loop terminates.

When generating walls, some of them can overlap, and it is very likely that small spaces will be created, or even the original area will be divided into several unconnected areas. Of course, we do not want this. Therefore, in the next step, I check which continuous area is the largest and fill the rest with walls.

During this check, I go through the entire grid of the field and if the tile is free, I recursively fill its entire continuous area with the identifier of this area (free tiles are tiles without a wall and so far not marked with the identifier of the area). After that, I go through the entire field again and count the tiles with each area identifier. And finally, I go through the whole field again and fill all the tiles with the area identifier with walls, except for the area with the largest number of tiles.

The entire process of generating walls can be seen in this animation. This shows the generation of walls and the generation of internal walls, and in the last frame, the void in the lower right corner is filled in at the stage of merging areas:


After completing the generation of walls, you can start generating objects. We need at least one pair of fruits and zero or more obstacles (represented by stones, cars and barrels in the game).

It will be good if the fruits are located in most cases in corners, at the ends of corridors and other similar places. It may sometimes be interesting to place them in the middle of an open area, but the former is more preferable. To achieve this, we add weight to each free tile in terms of the attractiveness of the location of the fruit on it.

For the corridor ends surrounded by tiles on three sides, I chose the weight 6 + Random (3). For tiles in horizontal or vertical corridors, I chose weight 2. For corners, I chose weight 3 + Random (3), and for free areas - 1.

Based on the weights, it is obvious that the most likely location of the fruit is at the ends of the corridors, followed by the location in the corners, corridors and free areas. For each generated level, weights are generated only once.

Obstacles (stones, cars, barrels) are created in a similar way, but the difference is that their weights are separated from the weights of fruits; there is also a certain random density of obstacles, which indicates the number of obstacles in the level, if selected.

By the way, with the help of scales, you can do other tricks. Later I added a sleeping hedgehog and anteater (their descriptions are given at the beginning of the article). It does not make sense to place them in the middle of the corridor, so for corridors their weight = 0.

This animation shows the location at the level of fruits and obstacles:


The final generated level is shown in the static image below. The solution requires 6 moves (right, up, left, down, right, up). Well, in 1-2 minutes after clicking on the Generate button, we have an interesting looking level, the passage of which is possible after 6 moves (no one will play levels that require 30 moves to pass!); moreover, for his search we did not have to suffer a bit. But ... you can always do a little better. And from this point in our article we will try to make the levels more beautiful.

Editor

Level generation completed in the previous part. Our editor supports drag & drop, so you can easily drag and drop objects to get a higher level of symmetry. For example, like this:


After making the changes, it is important to re-test the level using the solver. Sometimes small changes can lead to unsolvability of the level. In our example, the changes increased the number of moves to the solution from six to seven.

At this stage of manual editing, the approach to the procedural generation of levels branches out. If you need or want to apply the changes manually, the level generator will serve you simply for a huge saving of time. If this step is not required and you think that the generated levels are good enough, then the generator can become part of your final game. Players will be able to generate new levels on their own.

Final result

Procedural level generation has saved us a tremendous amount of time. Despite the fact that the generator can create garbage - levels that are too easy or too difficult to pass, levels full of obstacles or ugly levels - it still saved us a lot of time. He also allowed us to select and drop some of the non-liked levels. If we did them manually, it would take months of work. Here's how the levels generated in this article look in the final game:


About the Author: Tomas Rychnovsky is an indie developer of small mobile games for Android, iOS, and Tizen.