Automation of the game in Flood-it
Good afternoon.
After posting a question about whether it will be interesting to read about automation of the game process in Flood-it. Several positive reviews were received, in connection with which I am publishing this article.
Flood-it is a 14x14 playing field with multi-colored squares, the player’s task is to fill the field with one color for the least number of moves. Each move represents a choice of color from the palette, in total there are six colors in the palette. In total, 25 moves are given for the 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 implementations under a cat.
In the process of research, two algorithms were developed. The first algorithm was simpler and consisted of the following steps:
With this algorithm, 100 games were played, of which he won in 28. The maximum number of points scored was 640 (two consecutive wins).
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 much more can be painted over in two moves.
Figure 2: problem of the first algorithm.
In the figure you can see that if you first fill with green, then you can access the large pink area. If you paint it with purple, then you can get only the red area of two cells. Similarly, you can reason for other colors.
After testing the described algorithm, this problem was solved by analyzing several steps forward.
There are six colors in the game; you can paint one of five colors except for the current color of the first cell. Thus, for a simple search of 4 steps forward, you need to sort out 5 ^ 4 = 625 options. In fact, in the algorithm, 1296 (six in the fourth degree) combinations are sorted out. Each color combination is represented by one number, the order of filling is determined by the remainder of the division by six.
After filling with all four colors, the number of cells filled with the color of the first cell is counted. Among these numbers, the maximum is selected: The FloodLevel class is designed to simplify copying and shading and contains the following methods: The text of the methods can be viewed in the project source code, since the code is trivial and is a recursive image filling algorithm . Figure 3: Achieving the SuperPixie title. Testing the algorithm on 100 games showed such characteristics - 96 wins, a maximum of 19680 points. In the testing process, the title of SuperPixie was received. I stopped on this algorithm, since refactoring and optimization can be done indefinitely.
The level is a field consisting of multi-colored cells. Each cell is painted in a monotonous color, which makes it very easy to get the cell colors at the level: The pixel values are obtained from the screen using the Robot class, then each received pixel is checked for compliance with a certain 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 we are not playing the field.
To select a color, a simple algorithm is also used, which moves the mouse to the position corresponding to one of the colors and clicks on the color. After completing the action, you need to wait some time for the game to react and update the playing field. A slight delay is used for this.
Figure 4: 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 antipatterns, in particular Magic numbers. Also, the program does not find the level automatically; the offsets are relative to the screen angle (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:
After posting a question about whether it will be interesting to read about automation of the game process in Flood-it. Several positive reviews were received, in connection with which I am publishing this article.
Introduction
Flood-it is a 14x14 playing field with multi-colored squares, the player’s task is to fill the field with one color for the least number of moves. Each move represents a choice of color from the palette, in total there are six colors in the palette. In total, 25 moves are given for the 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 implementations under a cat.
Description of the first version of the algorithm
In the process of research, two algorithms were developed. The first algorithm was simpler and consisted of the following steps:
- obtaining the current state of the playing field;
- an attempt to fill each of the possible colors and count the number of cells poured;
- the color giving the largest fill area is selected for pouring
With this algorithm, 100 games were played, of which he won in 28. The maximum number of points scored was 640 (two consecutive wins).
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 much more can be painted over in two moves.
Figure 2: problem of the first algorithm.
In the figure you can see that if you first fill with green, then you can access the large pink area. If you paint it with purple, then you can get only the red area of two cells. Similarly, you can reason for other colors.
After testing the described algorithm, this problem was solved by analyzing several steps forward.
Description of the second version of the algorithm
There are six colors in the game; you can paint one of five colors except for the current color of the first cell. Thus, for a simple search of 4 steps forward, you need to sort out 5 ^ 4 = 625 options. In fact, in the algorithm, 1296 (six in the fourth degree) combinations are sorted out. Each color combination is represented by one number, the order of filling is determined by the remainder of the division by six.
- 1 - pink;
- 2 - purple;
- 3 - yellow;
- 4 - red;
- 5 - blue;
- 6 - green.
After filling with all four colors, the number of cells filled with the color of the first cell is counted. Among these numbers, the maximum is selected: The FloodLevel class is designed to simplify copying and shading and contains the following methods: The text of the methods can be viewed in the project source code, since the code is trivial and is a recursive image filling algorithm . Figure 3: Achieving the SuperPixie title. Testing the algorithm on 100 games showed such characteristics - 96 wins, a maximum of 19680 points. In the testing process, the title of SuperPixie was received. I stopped on this algorithm, since refactoring and optimization can be done indefinitely.
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
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(); // проверка завершена ли игра
}
Getting level image
The level is a field consisting of multi-colored cells. Each cell is painted in a monotonous color, which makes it very easy to get the cell colors at the level: The pixel values are obtained from the screen using the Robot class, then each received pixel is checked for compliance with a certain 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 we are not playing the field.
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;
}
}
Game management
To select a color, a simple algorithm is also used, which moves the mouse to the position corresponding to one of the colors and clicks on the color. After completing the action, you need to wait some time for the game to react and update the playing field. A slight delay is used for this.
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);
Conclusion
Figure 4: 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 antipatterns, in particular Magic numbers. Also, the program does not find the level automatically; the offsets are relative to the screen angle (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: