The history of the game Triplex, or how many squares do you need to break your head
To master the basics of Web programming, I decided to write an HTML5 puzzle game called Triplex ( www.quadpuzzle.ru ). Writing a game for yourself and for friends is half the battle. I wanted to bring the project to mind, making a game a product for a wide range of users. How it happened - to judge you.The rules of the game are simple. On the playing field laid out the figures of the squares. The goal of the game is to lay all the shapes in the specified rectangle. You can rotate only one shape, marked with a circle, if it is. The solution in each problem exists and only.
')
Works in new versions of the following browsers: Opera, Opera-mobile, Safari (Windows, iPad2), Android (HTC Desire, Samsung Galaxy Tab 10.1), Chrome, FireFox and IE9.
Implemented the following ideas:
- The game consists of a single html file. It can be downloaded to your local disk and play without the Internet. IE9 does not support this mode.
- If there is a network connection, then you can mark your passing levels on the server and see the results of all the noted players.
- The table of records for each level stores the name of the player who decided this level first. Also stored statistics on the passage of levels by other players.
- Each next level is encoded by the decision of the previous one. So just take and go through the last level will not work, despite the fact that all levels are stored in a single html file.
- The game is translated into 5 languages: Russian, English, French, German and Chinese.
Similar games
It would be dishonest to say that I did not invent the game. The prototype of Triplex was a very similar game BlockPuzzle 500 ( www.mtoy.biz ), in which I had the opportunity to play on my first Android phone.
In essence Triplex differs from it in the following:
- size of figures:
BlockPuzzle uses figures from 2, 3, 4 and 5 squares, in Triplex there are figures from only 2 and 3; - Triplex can have several identical figures on the same level, and BlockPuzzle is all different;
- there are no rotating figures in BlockPuzzle, in some Triplex there is one rotating figure on some levels;
- BlockPuzzle is only for Android, and Triplex can be played on any device, if it has a browser with HTML5 support.
Honestly, on Android it is more pleasant to play BlockPuzzle - the interface is more responsive. I would be glad if someone wants to port Triplex on Android or another platform. All you need is in triplex.html.
Where the tasks come from
The level generator for this game was developed first. At first, just for the sake of curiosity. I wanted to understand the nature and properties of such tasks. How many of them all, how difficult it is to find such tasks, how difficult it is to solve them ... There was written a program in the Java language that can generate levels. I wanted to play, touch and solve with these levels. Apparently, in childhood I did not play enough with cubes, so now I wanted to play with the squares. The idea arose not only to make a level visualization program with user interface elements, but also to make a game out of it.
The generator looked for levels as follows:
- went through all the combinations in the fields 3x2, 3x3, 4x3, ... with 3 or more figures from 2 and 3 squares;
- eliminated all similar (up to turns and reflections);
- chose those in which there is only one solution;
- chose one rotated shape, if it did not add other solutions.
Computational complexity of the algorithm
Initially, the program was conceived for the selection of tasks with an arbitrary number and size of shapes of arbitrary sizes. The algorithm works by the branch and bound method .
Let the decision figure be a rectangular figure of size WxH consisting of other figures (figures from the problem condition). Consider all pairs of contiguous squares (squares with a common face) that make up the solution. All such faces (2 * W * H - W - H).
Each face can be in one of two states:
0. closed - adjacent squares may belong to different figures;
1. open - two adjacent squares belong to the same figure.
Let's call N-ku from (2 * W * H - W - H) binary values ​​a set of states of all faces. Obviously, an arbitrary set of states uniquely corresponds to a partition of a rectangle into shapes (see the description of the partition coloring algorithm). Obviously, for any partition there is at least one set of states.
The set of various sets of states contains 2 (2 * W * H - W - H) elements. That is, to iterate over all possible partitions, it is enough to start the cycle from 0 to 2 (2 * W * H - W - H) -1, and consider every i-th bit of the binary representation of the index variable state of the i-th face. If the complexity of the cycle body is limited to a constant, then the total complexity of enumeration of all combinations will be exponential of the solution area. Let's estimate how many iterations will work out.
| dimension | quantity iterations |
|---|---|
| 1x1 | 2 (2 * 1 * 1 - 1 - 1) = 2 0 = 1 |
| 2x1 | 2 (2 * 2 * 1 - 2 - 1) = 2 1 = 2 |
| 2x2 | 2 (2 * 2 * 2 - 2 - 2) = 2 4 = 16 |
| 2x3 | 2 (2 * 2 * 3 - 2 - 3) = 2 7 = 128 |
| 2x4 | 2 (2 * 2 * 4 - 2 - 4) = 2 10 = 1024 |
| 3x3 | 2 (2 * 3 * 3 - 3 - 3) = 2 12 = 4096 |
| ... | ... |
| 6x6 | 2 (2 * 6 * 6 - 6 - 6) = 2 60 |
That is, the loop index for the 6x6 task is still placed in a 64-bit integer type. If you start such a cycle with an empty body at a speed of 1 processor clock per iteration on a processor with a frequency of 3GHz, then the program will run for 12 years = 2 60 / (3 * 10 9 * 3600 * 24 * 365).
Reduce brute force filtering
In order to significantly reduce the brute force, you need to try to throw away entire groups of such partitions that are obviously not suitable. For this, the following filtering mechanism was invented. Sort all the squares in descending order from left to right and from top to bottom: the upper left is the oldest, the lower right is the youngest. Each square uniquely corresponds to its pair of faces: right and bottom. So, the order on the squares, in a natural way, induces order on the adjoining faces: let it be the lower - the oldest, the right - the younger. Each split passes from one filter to the next through a filter function that either skips the split further or not. If the split passes all the filters, then it falls into our game. If the partition does not satisfy the condition of any filter, then the filter may indicate the least significant square, due to which the condition is not fulfilled. Then the search for partitions continues not from the lowest face, but from the lowest face of the specified square.
In the general case, for an arbitrary filter it is difficult to estimate how much one can thus reduce the number of partitions. However, a very simple example shows that sometimes significantly. So, thanks to the filter that drops partitions with isolated squares (squares that are an independent figure from one square), the number of partitions at the first step is reduced by 25%: the highest square must have at least one common face with one of two neighbors. That is, instead of 12 years, we have enough 9. If the 4 corner squares are not neighbors, the filter of the “isolated squares” reduces the search by 25% for each of them, and this is (1 - (3/4) 4 ) = 68 % Similar considerations for the remaining squares add up to a reduction in the search of the order O (2 W * H ).
To generate Triplex levels, the following filters were used in the following order:
1. 2x2Duplicates
- filter discarding partitions in which there are four small squares (2x2) belonging to one shape, but at least one of the four common faces is not common.
2. 1x1Cell
- filter of isolated squares, described above.
3. StraightCut
- filter discarding partitions with straight horizontal or vertical cuts. Such a cut divides the split into two parts, rearranging which, we get the second solution. This rule is not executed only when both parts of the split consist of the same sets. In this case, the second solution does not work, but for our game the partition is not of interest, because each part of the partition is an independent task of a smaller dimension.
4. Shapes3
- filter discarding tasks with the number of figures less than 3. It is not at all interesting to solve puzzles from two figures.
5. Shape23
- filter discarding partitions in which there are figures of 4 or more squares. This filter is specific to Triplex.
6. RotatedAndReflected
- a filter that rejects the same partitions - such partitions, which are obtained from each other by turning 90, 180 or 270 degrees and / or mirror reflection. Each partition is thus assigned 8 identical partitions. Since we have introduced a linear order on the set of partitions, then from each eight, we can choose the minimum partition. If the filtered partition is not minimal, then we discard it. This means that we have already considered the partition from this eight.
7. Solver
- filter discarding partitions for which there is more than one solution. This filter is probably the most interesting, but I don’t want to describe the algorithm of its work, in order not to make the task easier for programmers who want to write their own solver to get through the game. I would like to say, however, that Solver selects solutions by the branch and bound method. The number of leaves on the 'branches' (the number of combinations) is calculated by the formula
C! / (C 1 ! C 2 ! ... C m !),
where C is the number of figures in the partition, m is the number of different figures in the partition (the number of groups of identical figures), C i is the number of identical figures in each of the groups. For example, if all the figures are the same, then the combination is only one: m = 1 and C = C 1 . The first level (3 different figures, until we pay attention to the rotating figure) gives 3! / (1! 1! 1!) = 6 combinations. The tenth level (6 figures in four groups) gives 6! / (2! 2! 1! 1!) = 180 combinations. The hundredth level (9 figures, in five groups) gives 9! / (3! 3! 1! 1! 1!) = 10080 combinations. The sixth level gives about 10 11 combinations. Despite the fact that there are many combinations, Solver solves all the tasks of Triplex in 1-2 seconds. This suggests that finding tasks is much more difficult than solving them. For example, when searching for 6x6 tasks, Solver solved 5887655 tasks, choosing only 46 of them.
For Triplex, with figures of two and three squares, the described filter set is far from optimal. But the program was designed to generate more complex tasks, and Triplex is just a special case, for which there is a completely different, simpler algorithm, which I will discuss next.
It is worth noting that the order of the filters greatly affects the performance of the program. At the top of the list, you need to put filters that have the least algorithmic complexity, and those that reject the maximum number of bad partitions in large groups. For example, Solver, if you put it first, most likely, it will throw away the greatest number of splits. However, it will work unacceptably long, evaluating the splits one by one.
Generator report
Consider the task generation report for 6x6 dimensions. The following table shows how many breaks were processed and by what filters.
| checked | accepted | thrown away | discarded% | discarded% from the general numbers | filter |
|---|---|---|---|---|---|
| 596745944245 | 295317406559 | 301428537686 | 50.51 | 50.51 | 2x2Duplicates |
| 295317406559 | 110686580321 | 184630826238 | 62.52 | 30.94 | 1x1Cell |
| 110686580321 | 79876633976 | 30809946345 | 27.84 | 5.16 | Straightcut |
| 79876633976 | 79875530828 | 1103148 | 0.00 | 0.00 | Shapes3 |
| 79875530828 | 47094698 | 79828436130 | 99.94 | 13.38 | Shape23 |
| 47094698 | 5887701 | 41206997 | 87.50 | 0.01 | RotatedAndReflected |
| 5887701 | 46 | 5887655 | 100.00 | 0.00 | Solver |
| 596745944245 | 46 | 596745944199 | 100.00 | 100.00 | Total |
The first thing you want to pay attention to is the total number of checked partitions - 596745944245 <2 40 . That is, thanks to the mechanism of 'boundaries', it was possible to reduce the check from 2 60 to 2 40 . If we consider that this task was spinning for 12 days, then without the mechanism of 'boundaries' it would work for 12 * 2 20 ~ 12 * 10 6 days or it would be necessary to use a million processor cores instead of one. This table lacks one very interesting column that would show how each filter reduced brute force to understand what the divider 2 20 consists of.
As one would expect, RotatedAndReflected threw 7/8 = 87.5% of all partitions given to it, choosing only one of each eight identical tasks. It is interesting to note that among the considered partitions, more than a million different variants were found, rejected by the Shapes3 filter, which are split variants from two figures. It is even hard to imagine that from the quintillon (2 60 ~ 10 18 ) 6x6 partitions for Triplex, only 46 were chosen. As the saying goes, “all the best”.
Timeline
This is how for the 6x6 task the graphs of the number of found levels (LEVELS FOUND) versus time and% of considered partitions (WORK DONE) versus time (in days) look like.
I would like to note two points:
- First, WORK DONE starts at 25% due to the filter of the isolated small squares applied to the upper left square, as explained above.
- Secondly, despite the fact that the program worked 12
days, all levels were found in the first 4 days at WORK DONE values ​​from 25% to 40%. With other dimensions the same thing - most of the found levels were found at the beginning of the search. This is due to the RotatedAndReflected filter, in which the minimum of the eight similar tasks is selected.
Task Dimension Table
This table provides data for all tasks that hit the game.
| Square solutions | Dimension | amount levels | Time | General quantity levels | General time |
|---|---|---|---|---|---|
| eight | 4x2 | 2 | 0s | 2 | 0s |
| 9 | 3x3 | one | 0s | 3 | 0s |
| ten | 5x2 | one | 0s | four | 0s |
| 12 | 4x3 | four | 0s | eight | 0s |
| 15 | 5x3 | 6 | 0s | 14 | 0s |
| sixteen | 4x4 | five | 0s | nineteen | 0s |
| 18 | 6x3 | eight | 0s | 27 | 0s |
| 20 | 5x4 | 48 | 0s | 75 | 0s |
| 21 | 7x3 | sixteen | 0s | 91 | 0s |
| 24 | 6x4 | 27 | 2 minutes | 118 | 2 minutes |
| 8x3 | sixteen | 1 minute | 134 | 3 min | |
| 25 | 5x5 | 22 | 3 min | 156 | 6min |
| 27 | 9x3 | nineteen | 12min | 175 | 17min |
| 28 | 7x4 | 45 | 41min | 220 | 59min |
| thirty | 6x5 | 55 | 3h | 275 | 4h |
| 10x3 | nineteen | 2h | 294 | 6h | |
| 32 | 8x4 | 112 | 17h | 406 | 23h |
| 33 | 11x3 | 22 | 20h | 428 | 2 days |
| 35 | 7x5 | 158 | 7d | 586 | 9d |
| 36 | 6x6 | 46 | 12d | 632 | 21d |
| 9x4 | 69 | 16d | 701 | 37d | |
| 12x3 | 20+ | 8 days + | 720+ | 45 days + |
It is worth noting that:
- The generator worked more than 45 days.
- Tasks up to square 32 were generated on the first day.
- The search for tasks with an area of ​​36 took 36 days.
- An unexpectedly large number of tasks were found for 8x4 and 7x5 dimensions: 112 and 158, respectively. This is significantly more than for other dimensions.
Coloring coloring
The first three filters operate only on face states as a set of bits. The following filters operate in terms of shapes. To translate a set of binary states into a set of figures, use a single-pass algorithm for coloring partitions into separate figures:
int color = 1; for(int i = 0; i < H; ++i) { for(int j = 0; j < W; ++j) { if (painted[i][j] == 0) { flood(i, j, color++); } } } Here, the flood function fills the shape, starting at the cell (i, j), using a queue of adjacent cells belonging to the same shape. The total complexity of this coloring algorithm is linear in the number of squares - O (W * H).
Rotation figures
Rotated figures are searched in selected brute force splits. For each figure, a set of all possible turns and reflections — transformations — is considered: 4 turns and a reflection — a total of eight options. For Triplex, the maximum is 4: at the rods 2 each, at the corners 4. If in the initial set of figures, one is replaced with any transformation of it, and a solution cannot be made from the new set, then this
the shape can be allowed to rotate - the solution will remain the same. Further, from the set of rotated figures, one is chosen for the game, which most complicates the task of finding a Solver solution. The selected shape is rotated randomly.
Intuitively, it seems that tasks with turning figures are easier to solve - we collect all the figures, leaving free space.
for turning, and then more likely that the figure will fit into the left place. However, when you consider that by making a figure
when turning, we do not add new solutions, the number of combinations that Solver has to check,
increases by as many times as many different transformations of a rotated figure (2 or 4 for Triplex).
One could choose several rotated figures, for example, one of the most complicating decision subsets of figures. Perhaps in future versions this will be done.
How tasks are ordered
Solver solves problems in a natural way, sequentially going through possible combinations. Solving the problem, Solver assigns it a difficulty level - the number of iteration cycles performed, which is limited from above by the number of possible combinations, calculated using the formula C! / (C 1 ! C 2 ! ... C m !). Triplex tasks are ordered by increasing the level of complexity described. Such an assessment of complexity does not coincide with the complexity experienced by a person. In order to estimate the complexity of each task from the player’s point of view, anonymous statistics of the solution time of each task are kept on the server. In the future, I hope, such statistics will help streamline tasks better.
Other variants of the generation algorithm
The search for all possible partitions is not the only possible way to search for all tasks that satisfy the condition of the game. You can search for tasks by going through all sorts of sets of figures, which by the total area coincide with the area of ​​the solution. In Triplex, for example, there are a total of 8 different figures: two double sticks, two triple sticks and four triple corners.
For the 6x6 = 36 task, the maximum number of figures is 18, the minimum is 12. Thus, the number of sets can be estimated from above with the value of 8 18 / (2! 6 3! 3!) = 2 48/9 <2 45 (each of the 18 figures can be one of 8 possible, and divided by the minimum number of permutations) and below 8 12 / (8! 4!)> 2 16 (each of the 12 figures can be one of 8, and divided by the maximum number of permutations). For ordered sets, the formulas are the same, but without divisors. On the one hand, there will be more ordered options, but, most likely, it will be possible to come up with a more optimal border traversal.
It is possible to sort through all possible eights of numbers (a 1 , a 2 , ... a 8 ), where a i is the number of i-th figures in the solution. For such eights, there is a linear restriction on the total area of ​​the figures:
2 * a 1 + 2 * a 2 + 3 * a 3 + 3 * a 4 + ... + 3 * a 8 = 36
The program, which worked according to this algorithm, found all levels of Triplex in 2 hours. This is 500 times faster than it took to iterate over partitions. The truth is worth noting that the complexity increases exponentially. Over the next two weeks, this method found only 1300 levels.
Client part of the game
An important part of the game is a program that provides the player with the opportunity to solve the generated tasks. The game is written in HTML, CSS and JavaScript (total 2100 lines). All logic, all resources and even all 700+ levels fit in one html file. Therefore, once you download the game, you can go through to the very end without a network connection.
Graphic design
The graphics in the game is very simple, without pictures, not counting the background. The squares are made in the form of multicolored <div> s with a gradient fill. The circle inside the rotated square is also a square, only with maximally rounded borders and a reverse gradient fill. It turned out that IE9 does not provide such a trick and the gradient fill of the circle is still square.
The background in the game I wanted to make alive. On it should have been put to sleep slowly gray circles from divines. Apparently inspired design HTC Sense. However, I came across two obstacles.
First of all: forcing them to fly very smoothly did not work: the movement for one pixel per second for some reason looked abrupt, jerked. I tried to shift more often in increments of less than 1.0, but they still shifted discretely.
Secondly: in some browsers for Android, even several large circles loaded the system very heavily. So I just made a static image from the background and 'stitched' it inside the html file with this CSS spell: background-image: url (data: image / png; base64, / 9j / 4AAQSkZ ... =);
To adjust the size of the squares to the size and resolution of the screen, I did not use sprites, because when scaling they become fuzzy.
Maybe someone will ask why I did not use HTML5 Canvas for 2D graphics? I agree that for such simple graphics, the Canvas functionality would fit very well. But it so happened that when I wrote the prototype, I knew one unpleasant feature of the Canvas grid: the integer coordinates indicate the intervals between pixels. Also, the performance of the Canvas on my new tablet was not encouraging. Therefore, the first prototype used HTML DOM and squares from DIV elements that survived to the final version.
Saving Levels Passed
The perception of HTML games for most people whom I showed Triplex, made them worry about saving the results of the passage. Usually they asked somewhere at the 15-30 level: “And if the network turns off or the computer hangs, will you have to go through everything again?”
Probably it is important to note that the game is automatically saved every 10 seconds in your browser profile on your hard drive. Therefore, do not be afraid to turn off the computer or refresh the page. The save mechanism uses HTML5 localStorage . This, as well as the fact that all levels are stored in the game itself, allows you to play without a network connection.
However, localStorage has a reverse side of the coin, which I discovered during beta testing, deciding to register a new domain name and move the game to a new address. The fact is that localStorage is tied to the domain name of the site. It turns out that if a player downloads a game from another site, then he will have to start all over again. To systematically approach the issue, let's clarify what localStorage is still attached to. To a local disk, which means that you will not play on another device (either at work, or at home, or on the phone). There is also a binding to the browser, we do not know where and in what format localStorage is stored. Here my hands reached out to the good old checked cookies, logins, passwords and server support with clever scripts. And while laziness resisted, it was decided to resort to an even more ancient method of those times, when our great-grandfathers were still pulling the ears off the black-and-white TV and the Dandy console. Yes, you guessed it, I'm talking about writing the level number and its code in pencil on a piece of paper. The code can be found in the game options.
Internationalization and localization
I promised my aunt that I would finish the game and she could play. Therefore, I decided to realize the opportunity to translate the game into Russian or another language. This possibility is called internationalization, and in the circle of developers i18n is designated, because in the English word internacionalization there are 18 characters between the first i and the last n.
I got such a simple idea of ​​implementing i18n that I didn’t even have to look for ready-made solutions. For each HTML element that contains language text, the class 'i18n' was specified. For example: <span class = 'i18n'> simple graphics </ span>. In the game code, I18N structure is entered, which contains translations of all phrases:
// var I18N = { "OK": { ru: "OK", fr: "bon", de: "OK", zh: "??" }, "simple graphics": { ru: " ", fr: "graphiques simple", de: "einfache Graphik", zh: "????" }, ... } When the language is first changed, for all elements of the i18n class, their original content is stored in the origHTML field and replaced with the translation specified in the I18N structure.
The phrase 'N seconds / minutes / hours / days ago' required a context-sensitive translation. For this we had to complicate the logic a bit. In the I18N structure, instead of translation, you can specify a function that translates depending on the context:
"seconds ago": { en: i18nSecondsAgoEn, ru: <b>i18nSecondsAgoRu</b>, fr: " il ya quelques seconds", de: i18nSecondsAgoDe, zh: " ???" }, ... function <b>i18nSecondsAgoRu</b>(context) { return i18nNumberRu(context, '', '', ''); } ... function i18nNumberRu(context, num0, num1, num2) { var num = +context; var result; if (num >= 20) { num = num % 10; } if (num == 1) { result = num1; } else if (2 <= num && num <= 4) { result = num2; } else { result = num0; } return context + ' ' + result + ' '; } Russian localization (l10n = localization) was done by myself, French, German, and Chinese; I made friends: Julia, Masha, Sergei, and Alexey .
Table of achievements
For players who are interested in competitive spirit, the game is complemented by server support for the achievement table, which is available from the main page of the game. The achievement table for each level stores the name of the player who decided this level first.
Playing online:
- all players see who and how long ago was the first to decide the current level;
- after passing each level, the time of passing the level is sent to the server, and if no one has passed this level yet, then you can also enter your name in the table.
How to hack the game
I am sure that there will be craftsmen who will try to enroll in the table of records, not solving the problem of the game. I want to say that in the forehead this will not work. To mark on the server your passing level, you must provide a checksum of the solution. This checksum is also needed in order to proceed to the next level. That is, each level in the game is encoded by the decision of the previous one.
I also tried to protect the server side from hacking:
- there are checks for all input parameters;
- escaping special characters in SQL queries;
- escaping special HTML characters in the high score table.
It is easy to spoil the statistics on the passage time, but it does not affect the game in any way, and is made only for an approximate assessment of the difficulty levels.
Questions of preparing the site and placing the game on the Internet
To share the game not only with friends, but also with a large Internet audience, I had to immerse myself in the study of a large number of related technologies: hosting, domain name registration, forums, social networks, web services, openID, ... All these terms are well-known among most users. but even in order to simply decide whether or not this or that technology is suitable for solving specific problems, it is necessary to study it more deeply.
Money issue
It turned out that not everything in this world can be done for free. While the cost of the game is quite modest: 150 rubles / year for a domain name, 300 rubles / year for a simple hosting, not burdened by advertising. Recently, I transferred the game to a free hosting service provided by friends ( AlexeiZavjalov , vitroot ) and installed the phpBB3 forum engine on it. I do not plan to transfer Triplex to commercial rails, and I will try to keep the game free and free from advertising. In the future, perhaps, I will lay out the source code of the level generator. Although, I think, it will not be difficult for any programmer to write it himself by reading this article.
Conclusion
Well, that seems to be all that while there was time to tell. I hope you enjoy the game as much as I was interested in creating it.
Source: https://habr.com/ru/post/141085/
All Articles