Friday, October 24, 2014

Procedural Generation of Puzzle Game Levels

 This article was originally published at The discussion there, below article, brings some improvements to solver part of generator.

1. Introduction

 If you ever wanted to create a puzzle game you probably found that implementation and coding of game rules is relatively easy, while creating the levels is a hard and long-lasting job. Even worse, maybe you spent a lot of time on creating some levels, with intent to incorporate specific challenges into it, but when you asked your friend to try it, she solved it in a totally different way or with shortcuts you never imagined before.

How great would it be if you found a way to employ your computer, saved lot of time and solved issues similar to the above mentioned... Here is where the procedural generation comes to the rescue!

It is necessary to say that while there is only one correct way how, for example, to sum vectors and every programmer wanting to do it has to follow the same rules, when it comes to procedural generation you are absolutely free. No way is right or bad. The result is what counts.

2. Fruit Dating – its rules and features

In past days we released our Fruit Dating game for iOS devices (it is also available for Android and even for unreleased Tizen). The game is a puzzle game with simple rules. Your target is to match pairs of fruit of the same color simply by swiping with your finger. The finger motion matches the tilting of the board in any given direction. So, while trying to fulfill your goal, various obstacles like stones, cars or other fruit, get in the way. Simply, all movable objects move in the same direction at once. To illustrate, in the pictures below you can see first level that needs 3 moves to match a pair.

Over time new features are introduced:

One-ways are placed on the border of the tile and limits directions in which you can move.
Anteaters can look in any direction, but its direction is fixed and unchanging during the level. When fruit is in the direction of the anteater and no obstacles are in the way, the anteater will shoot its tongue and drag the fruit to it.
Mud can be passed through with stones, cars or barrels but not by fruit. When the fruit falls into mud it gets dirty and there is no date!
Sleeping hedgehog is sitting on a tile and wakes up when hit by something. If hit by a barrel, stone or car he falls asleep again as these items are not edible. But when he is hit by fruit he eats it.

You probably noticed that the game is tile-based which simplifies things as each level can be represented with a small grid. Maximum size is 8x8 tiles but as there is always solid board, the “usable” area is 6x6 tiles. It may seem to be too small but it proved that some very complex puzzles can be generated for it.

With the basic rules (as the additional features were added later) I started to build my generator. My first thought was that someone in the world surely already solved a similar problem, so I started to search the internet for procedural generation of levels for puzzle game. It showed that this topic is not widely covered. I found only a few articles useful for me. Most of them were about generating / solving Sokoban levels - for example:
It was also interesting, that most of them were written by academic people (professors of Sokoban! :-)) From the papers I learned two things: first, when generating something randomly it is good if it has some symmetry in it as people will perceive it more positively. Second, the algorithm is up to you, but none is ideal.

3. Solver

As it was obvious that every generated level will have to be tested (whether it is possible to solve it and how easy or hard it is) I first wanted to code a solver. As at that time I was only considering basic rules and not features added later I came up with these ideas for the solver:
  1. from initial position you can start in any direction (up, left, right, down),
  2. from next position you can continue in any direction again,
  3. in any position check for fruit match, remove matched fruits from board and continue with b) until some fruits remain on board.
As you can see, it is a simple brute force approach. So, the number of possible board situations was: 4, 4*4 = 4^2, 4*4*4 = 4^3, … 4^n. In the 10th move it was more than a million board situations and in the 25th move it was 1125899906842624 board situations. Okay, you could limit maximum moves to some number, let's say 10 and not be interested in more difficult levels, but there is hidden another danger. Some of the puzzles can be designed or generated in such a way that if a player does some bad moves in the beginning, she cannot finish the level. Or, in some levels you can get into a loop of board situations. If the algorithm branched early into such a way the level would be marked as not solvable, even if there were other branches with a simpler solution. Also if this algorithm found a solution there would not be any guarantee that it is the shortest solution – you would have to finish all branches to find the shortest solution. Beside this there are very often board situations in which one move in particular direction does not change anything. See third picture in “Fruit Dating – its rules and features” - there is no change if moved left.

So, the rules changed:
  1. from current position try to move in any direction,
  2. if there is a change in the board situation, check if the situation is new or you already were in such a situation,
  3. if a new situation, store it along with solution depth (number of moves to get into this situation)
  4. if previously was in this situation and solution depth was equal or lower, terminate this branch. Else, remove old situation (as you just got into it with less moves) and continue.
There are also other rules, like checking matches and thus terminating the whole process when a solution is found and later new rules when features were added, but this is the core of the solver. It quickly cuts whole branches without a solution. Beside solution depth, it also references to parent situations stored in each board situation, so it is easy to print the final solution in the end. Let's show it on the first level of the game:

From the initial position a move into all four directions is possible. These are labeled 1-1, 1-2, 1-3, 1-4. The algorithm always tries to move right, up, left, down in this order. As it employs a stack to store situations to examine further, the first situation to continue is the last one pushed onto the stack (1-4 in this case). Again, first is a move to the right (2-1) and as this is a new situation it is put onto the stack. Next is a move up which results in situation 2-2. We already were in this situation and it was in the first round. So, we apply rule d) and terminate this branch – nothing is put onto the stack. Next, a move to left is tried. It results in a new situation (2-3) and this is put onto the stack. Last move is down, but there is no change between 1-4 and 2-4 so we put nothing onto the stack (rule b) … no new situation = do nothing). Now, the stack top situation is 2-3. From it we move right and get into situation 3-1, which is equal to situation 2-1. But in 2-1 we were in the second round so we terminate this branch. Next we move up and fruits are on adjacent tiles, matched and as it was the only pair the game ends.

The algorithm works, however it may not find the shortest way. It is simply the first solution found. To overcome this I first start with limiting the maximum moves to 30. If a solution is not found I say that the level has no solution. If a solution is found in, let's say, 15 moves I run the solver again with maximum moves depth 14 (15 – 1). If no solution is found then 15 was the shortest way. If solution is found in, let's say, 13 moves I run the solver again with 12 (13 – 1) maximum allowed depth. I repeat while some solution is still returned. The last returned solution is the shortest solution.

 See discussion on below article. As Makers_F pointed the correct way would be to use Uniform Cost search. The algorithm described is fortunately only one step from it. When exploring new board situations, prefer those with lowest cost, where cost is number of moves to get into the situation. In other words, described algorithm in point c. is storing it into LIFO stack. Replace it with priority queue. The rule d. then changes from "if previously was in this situation and solution depth was equal or lower, terminate this branch." to "if previously was in this situation, terminate this branch.". After these changes the algorithm will find the shortest solution in first iteration.

4. Generator

Now that the solver works, we can move to the generator and validate every generated puzzle with it.

The generation phase can be split into two parts:
  • generating walls
  • generating on-board objects
The wall generation always start with drawing a solid board border:

Some random parameters are generated that say whether wall will be paint by one tile a time or two tiles a time. If two tiles a time then random symmetry is generated. It says where the second tile will be placed – if it will be flipped horizontally, vertically or rotated by 90 degrees or combination of these. First grid in the picture below is when one tile a time is painted. The rest are for two tiles a time with different random symmetries:

The number of walls is random as well as their length and direction. Each wall starts from a random point on the border. Every wall is drawn in one or more iterations. After the first iteration, a random number between 0 and wall length – 1 is chosen. If equal to zero, the iteration loop is terminated. If greater than zero, then this number becomes the length of the next part of this wall. A random point on the current wall part is chosen, direction is set randomly to be orthogonal to the current wall part and the next part of the wall is drawn. The result may look like this (the numbers label the iterations):

From picture it can be seen that every next part of the wall is shorter, so you can be sure it will be terminated at some point.

So far all walls started from the border, so every single tile was always connected to the border. It looked boring so I added another step where inner walls are generated. Inner walls are not connected to any existing tile. It starts by selecting a random tile and checking if it is free as well as its 3x3 tiles surrounding. If yes a wall WILL be placed into the grid and the next tile is chosen based on random direction (this direction is randomly chosen before first tile was tested). Loop terminates when condition for 3x3 free surrounding is not true. Notice the stress on word “will” above. If you placed the wall into the grid immediately and proceeded to next tile, the 3x3 surrounding would never be free as you just placed a wall there. So I store all wall tiles into some temporary array and place them into the grid at once when the loop is terminated.

During wall generation some of the walls may overlap others and it is very probable that some small spaces will be created or even that the initial area will be divided into several disconnected areas. This is something we do not want. And this is why in the next step I check which continuous area is largest and fill all others with walls.

In this check I iterate through the whole board grid and if the tile is free I recursively fill whole continuous area with area ID (free tiles are tiles without wall and with no area ID yet). After that I iterate through the whole board again and count tiles for each area ID. Finally I iterate the board one last time filling all tiles with area ID with walls except for the area ID with the highest count.

The whole process of generating walls can be seen in this animation. There is wall generation, inner wall generation and in the last frame a hole in lower right corner is filled during area consolidation:

When walls are generated we can generate objects. We need at least one pair of fruit and zero or more obstacles (represented by stones, cars, barrels in the game).

It would be nice if fruit was placed most of the times into corners, in the end of corridors or so. Placing it in the middle of an open area can be also interesting sometimes but the first is more preferable. To achieve this we will add weights to every free tile from the point of its attractiveness for placing fruit there.

For the end of corridors, surrounded with tiles from 3 sides I selected weight 6 + Random(3). For tiles in horizontal or vertical corridors I selected weight 2. For corners I selected 3 + Random(3) and for free areas 1.

From weights it is obvious that the most preferable placement is in the end of a corridor, followed with placement in corners, corridors and free areas. The random numbers in weights can also influence this and change weights between corridor ends and corners. The weights are generated only once for each generated level.

Obstacles (stones, cars, barrels) are placed in a similar way, only the difference is these weights are separate from weights for fruits and also some random obstacles density, which says how many obstacles will be in level, is chosen.

By the way, with the weights you can do other tricks. Features added later were sleeping hedgehog or anteater (see features description in the beginning). Placing them into the middle of a corridor made no sense so they have a weight for corridors = 0.

In animation bellow you can see populating level with fruits and obstacles:

The final generated level is in the static picture below. It takes 6 moves to solve it (right, up, left, down, right, up). Great, after 1-2 minutes of clicking on the Generate button we have a level that looks interesting, and the solution is possible in 6 steps (no one will play levels with solution in 30 steps!), while it is also not a breeze to find it. But … it still could be little bit better. It is this point where our manual entries took place to make the levels nicer.


5. Editor

The generation ended in the previous part. Our editor supports drag and drop, so it is easy to rearrange the objects to achieve a higher level of symmetry like this:

It is important to re-test the level with the solver after adjustments. Sometimes a small change may lead to an unsolvable level. In this case the adjustments increased the number of solution steps from six to seven.

With this manual step the approach to procedurally generated levels forks. If you need or want manual adjustment then procedural generation only works for you as a really big time saver. If this step is not necessary or you think that generated levels are OK then the generator can be part of the final game and players have the possibility to generate future levels by themselves.

6. Final result

Generating levels procedurally saved us enormous amounts of time. Although the generator also generates rubbish – levels too easy to complete or levels too hard to complete, levels full of obstacles or ugly looking levels - it still saved us an enormous amount of time. It also allowed us to make selections and throw a lot of levels away. If we made it by hand it would take months. This is how levels generated in this article look like in the final game:

Fruit Dating at iTunes
Fruit Dating at Google Play
Fruit Dating at Amazon

Thursday, October 9, 2014

Mobile Income Report #4 - September 2014 (monthly income report from Android, iOS, Tizen, bada, ... games)

previous parts
  Mobile Income Report #3 - August 2014
  Mobile Income Report #2 - July 2014
  Mobile Income Report #1 - June 2014
  Apps page - Portfolio (what are my assets?)

 If you do not want to miss any of my Income Reports you can follow me on Twitter. Just click the button above.

 Under Apps page you can see my portfolio. It is list of the games that are then reported in Income Reports. The portfolio is regularly updated with new information (releases for new platforms, new updates, ...)

What I did in September

  • on 3rd September Shards was featured in "Free App of the Day" (FAD) event at Amazon. What does it mean? You have to agree to give your paid app for free for one day. For 24 hours your app is then placed on the welcome page of Amazon appstore. As you can imagine it is really big promotion. In one day the game was downloaded by more than 125000 people! The average rating was 3,8 stars which is more or less similar to average rating of free version with ads at Google Play. In comments we also got some useful feedback from users. Being promoted in this way had also positive effect on paid downloads in next days - unfortunately not in thousands nor hundreds, but in ones and few days after event in tens of downloads (see Reports section of this post). What was really good, was fact, that the interest raised not only at Amazon, but also at Google Play and even at Apple's iTunes. On the other side, we did not see any changes in Samsungapps downloads.

  • On 27th September we finally released our Fruit Dating game on iOS. Game has one universal binary for iPhone / iPad and it is available here at iTunes. Unfortunately, there was bug in iOS8 version (related to screen orientation) so we had to update it immediately. The update is just in approval process. The game is puzzle game with nice graphics by Tomáš Kopecký and music by Matúš Široký
 For generating puzzles I coded special procedural generator which helped us very much - really big time savings. Generated puzzles were then manually adjusted to look more attractive. Below is one screenshot from editor and final game. As the procedural generation of puzzles is very interesting topic I will publish article on it in next days.

  • believe it or not, beside FAD for Shards we were featured in one more FAD event in the same month! Our earlier game Deadly Abyss 2 was promoted on 30th September at Amazon. The game got average rating 2,7 stars with more than 60000 downloads. The rating is not good. Lot of user were complaining about controls. But, unfortunately, most of them obviously did not see the tutorial. For me it means: in any other game where tutorial is necessary I must force the player to go through it. Other part of users did not like gameplay and lack of information on upgrades. These are right - the gameplay is very unbalanced. Even if you play for first time you can survive for long time. Also the explanation on upgrades in ... none. You can guess from icons, but for the next time we must add clear description.


 And now to figures. September was highly affected by "Free App of the Day" event in the beginning. Stats for paid apps are these:

 You can see jump in Shards downloads for Android and iOS. Compared to August earning ($39,7) there is increase to $375. It is great, but from detailed day-by-day data it is clear that October will be poor again. To make reports clear I shifted downloads during FAD events (125000 for Shards and 64000 for Deadly Abyss 2) into table with free downloads.

 The most profitable game was Shards again raising its share from 86% in August to 93%. No wonder - thanks to FAD. Fruit Dating is still very low. Let's see whether it will change in October with iOS version released.

 For the ads supported versions the September was better than August. The earnings raised from $121,7 to $168,7 (by 38,6%)

 In absolute figures Chartboost is still most profitable, but it is loosing its relative position (from 57% to 45%). It is given by increase in earnings from Amazon ads (from $17,7 to $38,0). My Chartboost eCPM is around $2,5. If Amazon keeps its eCPM higher I may consider to redirect some traffic there.

 So, total income for SBC team in September = $375,0 + $168,7 = $543,7 (+ 336,9% compared to August report).


 While Shards performed well in September I am still below my mid term target ($750). So, current portfolio will not probably pay my bills. It is time to move further. The Unity game I am working on is big project, it will not be finished soon, so I have to start some smaller projects beside to keep my indie life.