Garland generation algorithm for the New Year puzzle

In order to occupy himself somehow on sleepless nights, he again sat down to write toys for Android. So as soon as the new year, I decided that the toy should be New Year's. For me, the garland is an integral part of the new year and the New Year tree, so the solution came to the idea itself - I will do a puzzle - collect a garland. In the development process, for me there were two interesting points:

1. Generation of a garland.
2. Work with payments on Google Play.

That's what I'll tell you more below ...

So, the idea of ​​the game is shown in the screenshot:
')


More precisely, this is a screenshot of what happened, but in fact, this is exactly what was originally intended.
The main task was to come up with a garland generation algorithm, so that each time it was new, and it was interesting to play.

Having read a little about various algorithms for generating various graphic structures, I came to the conclusion that the algorithm for generating labyrinths is closest to my task.

Since the new year is getting closer and closer, I took, in my opinion, the simplest and far from the most optimal maze generation algorithm found on Habré .

But it had to be supplemented a bit - it was necessary to add information about the connection with adjacent cells to each cell, or if the cell is dead-end, then it is necessary to know which side came to this cell.

Thus, the value of 1,2,4 or 8 is assigned to each side of the cage. Well, or so that it is more understandable 0001, 0010, 0100, 1000.



Now the algorithm will look like this:

1. We set the initial cell and indicate which side came to the given cell (for example, came from below);
2. We make the initial cell current and assign the cell the value of the side adjacent to the cell from where it came to the current cell (for example, if it came from the lower cell, then the initial value of the current cell will be 4);
3. We are looking for free neighbors in the current cell;
4. If there are free neighbors, then:
5. If there are no free neighbors, then:
6. Repeat steps from the 2nd while there are cells in the stack.

With this implementation of the algorithm, there will be very few dead ends, that is, 2-3 lamps will appear on our garland on the strength of 2-3 lamps, which is not at all interesting, so add the length of the path.

And now I will show how I implemented it (I did it in a hurry without optimizations, so many places were made completely crooked):

public void init() { clearGarland(); //     FIFOStack.clear(); //  ,  FIFO  Cell currentCell = new Cell(garlandWidth-1,garlandHeight-1,1); //      ,       boolean generationtree = true; int garlandLength = 0; //     int maxGarlandLength = 5; //      do { switch(currentCell.Position) { //      case 1: //     garland[currentCell.X][currentCell.Y][0] = 4; break; case 2: //     garland[currentCell.X][currentCell.Y][0] = 8; break; case 4: //     garland[currentCell.X][currentCell.Y][0] = 1; break; case 8: //     garland[currentCell.X][currentCell.Y][0] = 2; break; case 0: //     break; } Cell[] neighbCells = searchNeighbours(currentCell); //   ,      ; int neighbCount = 0; //    //     -    X       0,       1 for(int z=0;z<4;z++) { if (neighbCells[z].X >= 0) { neighbCount++; } } //         ,     if ((neighbCount>0)&&(garlandLength < maxGarlandLength)) { // ,                FIFOStack.push(currentCell); //      int randomCell = randomizer.nextInt(neighbCount); //     garland[currentCell.X][currentCell.Y][0] = garland[currentCell.X][currentCell.Y][0]+neighbCells[randomCell].Position; //       ,     currentCell = neighbCells[randomCell]; //      garlandLength++; //      } else { //      ,       garlandLength = 0; //   currentCell = FIFOStack.get(); //          (    - FIFO) currentCell.Position = 0; if (currentCell.X == -1) generationtree = false; //   ,       false } } while (generationtree); //   //   ,    1,2,4,8    ,      (3,5,6,7,9,10,11,12,13,14,15)    ( )        . randomizeTree(); //    ,          . } 

As it turned out, generating a garland is very simple.

Now a little about the game itself.

The rules are very simple:

1. Rotating the elements of the garland it is necessary to light all the lamps, after which the star on the Christmas tree will light up;
2. ALL elements of the garland should be involved;
3. The power supply is in the lower right corner. When connected to a power source, the wires brighten, and if the current reaches the lamp through the wires, it lights up;
4. In the garland there can be no loops, that is, the path to the lamp is always unequivocal;
5. The light bulb should fit the wire on one side only.

And now the link to the toy on Google Play

Happy New Year! and let it be more interesting than the previous ones!

PS In the second part of the article about this toy, I will tell you how I worked with payments on Google Play.