Flood-it game automation

Good day.



After posting the question of whether it will be interesting to read about automating the process of the game in Flood-it. There were several positive reviews, in connection with which I publish this article.

Introduction

')

Flood-it is a 14x14 playing field with multi-colored cells, the player’s task is to fill the field with one color in the least number of moves. Each turn represents a choice of colors from a palette, there are six colors in the palette. There are 25 moves per game.





Figure 1: The playing field.



It is necessary to implement an algorithm to select the optimal color for the fill. Details can be read implementation under a cat.

Description of the first version of the algorithm

During the study, two algorithms were worked out. The first algorithm was simpler and consisted of the following steps:

• obtaining the current state of the playing field;
• attempt to fill each of the possible colors and count the number of filled cells;
• for the fill color is selected giving the largest fill area

With this algorithm, 100 games were played, of which he won at 28. The maximum number of points scored was 640 (two wins in a row).



The problem with this algorithm was that it did not track the situation when one cell closes several adjacent cells of a different color, and in two moves you can paint a lot more.





Figure 2: the problem of the first algorithm.



In the figure you can see that if you first fill in with green, then you can access a large pink area. If you paint in purple, then you can only get a red area of ​​two cells. Similarly, you can reason for other colors.



After testing the described algorithm, this problem was solved by analyzing a few steps ahead.

Description of the second version of the algorithm

A total of six colors in the game, you can paint over one of the five colors except the current color of the first cell. Thus, for a simple search 4 steps ahead, you need to go through 5 ^ 4 = 625 options. In fact, the algorithm gets 1296 (six to the fourth degree) combinations. Each combination of colors is represented by one number, the order of filling is determined by the remainder of division by six.

• 1 is pink;
• 2 - purple;
• 3 - yellow;
• 4 - red;
• 5 - blue;
• 6 - green.

After completing the fill with all four colors, the number of cells filled with the color of the first cell is counted. Among these numbers the maximum is chosen:



int[] fill_rate = new int[1296]; //

int max_color;

int max_count;



for (int i = 0; i < 1296; i++) {

FloodLevel t = new FloodLevel(colors);



t.fill(i / 1 % 6 + 1); // 1-

t.fill(i / 6 % 6 + 1); //

t.fill(i / 36 % 6 + 1); // ..

t.fill(i / 216 % 6 + 1);

fill_rate[i] = t.count(); //

}



max_color = 0;

max_count = 0;



for (int i = 0; i < 1296; i++)

if (fill_rate[i] > max_count) {

max_color = i;

max_count = fill_rate[i];

}



// - max_color % 6 + 1





The FloodLevel class is designed to simplify copying and filling and contains the following methods:



public final class FloodLevel {

public FloodLevel();

public FloodLevel(FloodLevel prototype); //



public void setColors(int[] new_colors);

public void setColor(int i, int j, int color);

public int getColor(int i, int j);



public void fill(int color); //

public int count(); //

public boolean gameCompleted(); //

}





The text of the methods can be viewed in the source code of the project, since the code is trivial and is a recursive algorithm for filling images.





Figure 3: Achievement of the title SuperPixie.



Testing the algorithm on 100 games showed such characteristics - 96 wins, the most scored 19680 points. In the process of testing, the title SuperPixie was obtained. I have stopped on this algorithm, since refactoring and optimization can be done indefinitely.

Obtaining level image

The level is a field consisting of multi-colored cells. Each cell is shaded in monotonous color, which makes it very easy to get cell colors at the level of:



FloodLevel colors = new FloodLevel();



for (int move = 0; move < 25; move++) {

for (int j = 0; j < 14; j++)

for (int i = 0; i < 14; i++) {

int color = robot.getPixelColor(FIELD_X_OFFSET + 24 * i, FIELD_Y_OFFSET + 24 * j).getRGB() & 0x00ffffff;



switch (color) {

case 0x00ed70a1: //

colors.setColor(i, j, 1);

break;



case 0x00605ca8: //

colors.setColor(i, j, 2);

break;



case 0x00f3f61d: //

colors.setColor(i, j, 3);

break;



case 0x00dc4a20: //

colors.setColor(i, j, 4);

break;



case 0x0046b1e2: //

colors.setColor(i, j, 5);

break;



case 0x007e9d1e: //

colors.setColor(i, j, 6);

break;



default: //

return;

}

}





Obtaining pixel values ​​from the screen is performed using the class Robot, then each received pixel is checked for compliance with a particular color in the game. Since the cells of the playing field are monotonous, it can be argued that any color that does not belong to the listed colors means that there is no playing field in front of us.

Game control

A simple algorithm is also used to select a color, which moves the mouse to the position corresponding to one of the colors and clicks on the color.



switch (max_color % 6 + 1) {

case 1:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 0, BUTTON_Y_OFFSET + 45 * 0);

break;



case 2:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 1, BUTTON_Y_OFFSET + 45 * 0);

break;



case 3:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 2, BUTTON_Y_OFFSET + 45 * 0);

break;



case 4:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 0, BUTTON_Y_OFFSET + 45 * 1);

break;



case 5:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 1, BUTTON_Y_OFFSET + 45 * 1);

break;



case 6:

robot.mouseMove(BUTTON_X_OFFSET + 45 * 2, BUTTON_Y_OFFSET + 45 * 1);

break;

}



robot.mousePress(InputEvent.BUTTON1_MASK);

robot.mouseRelease(InputEvent.BUTTON1_MASK);





After completing the action, you must wait for some time so that the game has time to react and update the playing field. For this, a small delay is used.

Conclusion

Figure 4: The maximum points earned by the program.



The program was written in one day - from Saturday evening to Sunday morning. In this connection, I apologize for the anti-patterns, in particular Magic numbers. Also, the program does not find the level automatically, offsets relative to the screen angle are hard-coded in the code (I use the Seamonkey browser under Gnome). If the topic is interesting, I can finish the automatic search for the playing field.



Source code can be downloaded:

• from this link from the people;
• follow this link from github.