In this post it will be a question of my participation in the tender Ludum Dare 34 which was about three weeks ago.
As a result the puzzle under the name Growing Sakura which gameplay it is possible to see on a gif image turned out (be not frightened, it weighs only 300 KB):
Briefly about rules of the game: initially we have a hexagonal field and several root buds (or one, as on a gif image above). From it it is possible to start up 3 branches (by two methods — clicking left or the right mouse button). On a branch the left click of a mouse can be made of each bud a Y-branching, and right — it is simple to continue a branch further (I-branching). If the branch cannot grow in any direction (the corresponding cage is occupied or in the necessary direction there is no cage) — that the branch does not grow. According to the last condition it is necessary to select correctly poryadkok "deployment" of branches. As a result the tree (or several trees) it that between two adjacent branches there are no acute angles will turn out. The game purpose — to cover all cages of a game field.
Without looking under kat try to think seconds 10 and to estimate how difficult can be this game.
What for Ludum Dare?
This competition is held time in 4 months and this time it was already the 34th action. A tender essence (in the nomination Compo): it is required to create in 48 hours a computer game on the set subject. The subject becomes known the first minutes of competition. Game has to be it is created solo and from scratch (all from scratch: the code, graphics, sounds and td), is however allowed to use third-party programs and practices of a code, but it is necessary to declare them in advance (we will tell, to write in the blozhik on the website Ludum Dare "I will use Paint, Unity, C ++ and Delphi, here according to the link a template of the starting project"). There is still a simplified weakening nomination Jam where it is possible to make game command even 72 hours, to use old practices and even (about horror!) it is not required to publish together with game source codes at the end. However, personally the nomination Jam is not interesting to me, I sometimes pass into it only if at 48 o'clock I do not manage to keep within.
The subject of tender is defined by vote and this time the greatest poll was gathered at once by two subjects: "Growing" and "Two Button Controls". It was possible to use or one of these subjects, or both at once. Interpretation of a subject remains at the discretion of the participant: so, the first subjects could be interpreted as "Growth", "Cultivation" or "Growing", and the second — "Control of two buttons" or "The power of two buttons". As it is possible to see higher from the description of game, I somewhat connected both subjects together.
Day the first
When I woke up, tender already went a couple of hours. The subject did not propose obvious solutions. Having slowly breakfast and being filled in with coffee, I considered that - to adjust it interesting to this subject. Of course, there was a wish to connect both subjects together. Several concepts emerged:
- Puzzle which emulates the window manager: on the screen a heap of windows (with two buttons everyone!), them it is necessary to close everything, but everything is complicated by the fact that both available buttons sometimes make very cunning actions (we will tell, to close a window more to the right of given). As a joke there was an idea to make the windows with the heading "Agreement" filled with the text like "Bla-bla-bla-bla" with two buttons "Agree" and "Disagree" which just close this window.
- Strategy croissant: development of underground base. The base consists of square tayl, with each of which it is possible to make one or the other actions, thus expanding (growing!) base.
- Some strange mechanism consisting of a lot of units on each unit is two buttons "Vklyukl" and "Vyklyukl".
- Again strategy, this time minimalist clone of Settlers II. Tayla gaksagonalny, with them besides it is possible to make one or the other actions (more roads or to construct a lodge). The idea was that for construction of more abrupt buildings it was necessary to bring several roads to a tayl. But experiments on a piece of paper showed that roads somehow quickly came to an end that stopped growth of the settlement.
All these concepts were boring, too difficult in implementation (and I before this tender had a month of works involving all hands on work and study therefore to strain oh as there was no wish). Still there was an idea to make Super Hexagon clone (there control of two buttons!), but I chucked in this idea because there was no "Growing". To the middle of day there was the following concept which turned out by simplification of idea about settlers:
- There is a hexagonal field, in some cages — stones, in some — beans. And we from beans have to grow up roots of some plants. Roots are grown up by rules which were described at the very beginning of this post. For each bean it is known how many cages the root system that the bean tree grew big and healthy has to cover. Well and the player's task — to grow up backs so that all beans grew.
Rules of the game arose from the following mathematical problem:
So, I just assumed that conforming to such rules it is possible to make some rather difficult puzzle.
quickly outlined a prototype of game mechanics:
Also saw that it is good!
At the end of the first day the idea of cultivation of roots was transformed to idea of cultivation of branches of an Oriental cherry (but in a game code all objects still are called according to roots!). For game simplification all numbers were thrown out and the purpose was reduced to the elementary according to the formulation: it is simple to cover all game field. The prototype of game grew to the following:
There was an idea to make so that branching lines became thicker according to distance to the most distant leaf (and it is visible on a gif image). However for long branches stretching became so big that their appearance spoiled. I spent a lot of time for that everything turned out beautifully. As a result hammered — a lot more things should be made. From now on all branches remained identical thickness.
On it I decided to finish the first day and left to sleep.
Day of the second
As usual, after the first day I decided not to save on a dream, and instead not to sleep the second night. Since morning sat thought out levels. Even outlined a hexagonal grid in the Word and printed, being active further a pencil and an eraser. It became clear that without automatic solver will be farther with some difficulty.
No sooner said than done. Outlined an unpretentious solver of a puzzle on C ++. It recursively touches all possible actions of the player and looks the puzzle is solved or not. On each iteration of search the current status of game remains in std:: set. If there is the same status of game later — that search is rolled away. Thus, the solver does not consider the same options of succession of events on hundred times.
It turned out that the puzzle mentioned above on two gif images (we will call its puzzle A) has even 47 different solutions. On complete search 93 seconds were required, at the same time 10810046 statuses of game were considered. This solver very strongly helped further.
Example of work of a solver already for other level:
This level was solved in 7 seconds, in std:: set was saved 711211 statuses and exactly one solution was found. A strange line at the very bottom — the description of level which is inserted already into game.
A bit later the solver was optimized heuristics of "a lonely cage". Namely: if on any step one of free cages was surrounded with busy cages ("walls" or cages in which already sprouted Oriental cherry branches), and it is impossible to start up a branch in this cage from next — that became clear that there are no solutions here and search was rolled away. After adding of this heuristics the puzzle of A began to be processed in 5 seconds at quantity of the considered statuses only 723225.
Until the end of the second day I hands drew interesting game grids and solved them my applet. Meanwhile, I added to game of the menu (and what else to do when the solver touches solutions?), redrew icons. Game began to look as follows:
As it is possible to see from a gif image, I set to myself quite ambitious task: to develop the whole 40 puzzles. By the time of creation of a gif image only 17 levels from 40 were ready. Until the end of tender there was a night more, namely about 10 hours.
Part of levels were generated as follows: some symmetric figure was drawn, the root bud was stuck into its accidental cage. After that the solver was started. If the received solutions turned out too much or in general any — level was a little modified (we change a form a little or we replace a root sprout somewhere to other place) and the solver, and so was again started until suitable level was not constructed.
For other levels the figure was intentionally asymmetrical, usually there several branches of an Oriental cherry met in general "lump" then it was necessary to weave accurately them with each other. These levels were created by means of a solver too.
Further I began to add levels which had several root buds. Game became at once much more various! An example of level with several buds:
Yes, sometimes for passing of level it is not possible to cover only one bud …
At night I added to game the screen with rules of the game, created several sounds by means of a remarkable applet of Bosca Ceoil well and at last finished all 40 levels (forty, Karl!), as well as it was planned. The last levels are so difficult that they do not give in completely to my solver: he finds several solutions before him as memory comes to an end, and it crumbles. Therefore I do not know precisely how many exactly there solutions though with confidence it is possible to tell — all puzzles in game have a solution.
Game was finished in the last hour and already weakening hands is recovered on the tender website.
After completion of tender organizers select 3 weeks for vote. Participants of Ludum Dare download games of other participants and evaluate them. I was engaged in it about a week too, and in parallel all thought as far as the game Growing Sakura can be difficult. As a result, everything poured out in the following:
Growing Sakura NP is difficult
Here I will try to state the proof (I hope in it did not bungle anywhere!).
It is possible to find the proof that the problem of check of existence of a Hamilton cycle in the planar cubic 3-connected graph NP is complete in this article (let's call for brevity it a problem of X). At once I will decrypt all unclear words:
The graph is several points (they are called tops), some couples of which are connected by lines (they are called edges). The graph is called planar if him it is possible to locate on the plane so that edges were not crossed. The graph is called cubic if exactly 3 edges proceed from each its top. The graph is called 3-coherent if to destroy him at least on 2 parts, it is necessary to delete not less than 3 edges. The Hamilton cycle in the graph is a sequence of in pairs different tops of v1, v2,…, vn such that vi and vi+1 are connected by an edge for any <=i
This article is a translation of the original post at habrahabr.ru/post/273349/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: firstname.lastname@example.org.
We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.