Geekly Articles each Day
📜 ⬆️ ⬇️

Universal bot for the game Flood-It

image
Figure 1. The playing field.

Once, one little article caught my eye. Immediately after reading the title, dozens of ideas of this kind appeared in my head, including the very idea of ​​creating a universal bot for this game.

At that time I had no particular experience in the automation of games, but the desire was paramount. Therefore, taking out a notebook, I began to think about this process ...

')

Analysis



I started analyzing from the end, imagining that I already have a working program in my hands, pressing the right buttons in the right sequence. In order for her to do this, she needs to know the coordinates of these buttons, will she not poke at any place on the screen, in the hope that she will get there at least once? Next, you need to provide a sequence in which the bot will press the buttons, he will not poke any buttons, right? To provide the necessary sequence of clicks, you need to choose the most optimal algorithm for selecting colors for the fill, and how to do it without having data on the state of the field? That's right, no way! Therefore, you need to obtain data on the colors of the cells in the playing field. Fine, but the question is, where is the playing field itself? The answer "somewhere on the screen" is not accepted, so you will need to find it. Now everything seems to be, let's write down a plan for our further actions:


Recognition of the playing field and its parameters



The first thing was to somehow find out the position of the playing field on the screen. But first, it would not hurt to get a screenshot. For this, I needed a java.awt.Robot class, with its method: BufferedImage createScreenCapture (Rectangle screenRect).
And what next? And then there were many attempts to force the program to find the position of the playing field, tens of thousands of calls to the getRGB method of the BufferedImage class, attempts to find out the position of the playing field from a pattern, etc. All these results were unsuccessful. What worked for one game did not work for another. Then one day, such a plan flew into my head:


Having taken a screenshot, it would be nice to convert it to an ARGB array:
int[] pixels = new int[w * h]; image.getRGB(0, 0, w, h, pixels, 0, w);


It is difficult to work with a color image, so you need to binarize it, that is, make it monochrome, so that we have only black and white colors at our disposal. Everything is simple here: we take another color and look at its brightness, if it is lower than the threshold, then this color will be black, if higher, white. In the software implementation, it looks like this:
 int red = (color >> 16) & 0xff; int green = (color >> 8) & 0xff; int blue = color & 0xff; int mean = (qr + qg + qb) / 3; if (mean > thresholdValue) color = 0xFFFFFFFF; else color = 0xFF000000;

First you need to get the brightness of the current color, and it is taken either as the average amount of the RGB component, or by the formula: brightness = 0.3 * red + 0.59 * green + 0.11 * blue. The coefficients are taken for a reason, they mean the perception of a particular color component with the human eye.

Now you need to pick a threshold value (thresholdValue), 191 is quite suitable - on all sites with a game where there was a light background, binarization gave the following image:

Figure 2. Monochrome image.
And on sites with a dark background, the value 64 gave a similar picture, but inverse. By the way, I chose 191 for a reason, and according to law 255-64.

It is easy to see that in such an image the playing field is much easier to find than if we were looking for a color one. It remains only to find out whether our background is bright or dark in order to use the threshold 64 or (255-64) from these data and invert the image if necessary. In my code, it looks like this:
 private boolean[] threshold(int[] pixels, int value) { boolean inverse = isBackgroundLight(MAX_COLOR_POINTS); if (inverse) value = 255 - value; boolean[] bw = new boolean[pixels.length]; for (int i = 0; i < pixels.length; i++) { int brightness = getBrightness(pixels[i]); bw[i] = (brightNess >= value) ^ inverse; } return bw; }


isBackgroundLight takes the number of dots that are needed in order to understand that the background is bright or dark. We get MAX_COLOR_POINTS from a color image and find the average brightness. If it is more than 128, then the background is bright, if less - dark.

Further, in the resulting monochrome image, we need to calculate the number of white dots horizontally and vertically. This is done in two passes in the image. As a result, we get two arrays with the following values: 1440, 1440, 410, 23, 119, 838 ... Filter the values ​​below the average, and we get an array: 1, 1, 0, 0, 0, 1 ... And finally, we need to determine the longest sequence These are the ones who are not broken by zero. This is also a rather trivial task.

In the end, we get 4 values: the position of the playing field horizontally, vertically, the width and height of the playing field. Since it is square, the last two values ​​should be the same. To find out the size of each cell, you need to divide the size of the playing field by its dimension. The dimension is set by the user, because the field is not only 14x14, but also 10x10, 20x20, etc.

Retrieving cell color data



Now that we have determined the parameters of the playing field, we can read the colors of the cells:
 int[][] table = new int[boardSize][boardSize]; int offset = cellSize / 2; for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { table[i][j] = detectImage.getRGB(j*cellSize + offset, i*cellSize + offset); } }

In order to avoid mistakes, we will take colors strictly in the center of the cell.

Further, in order to make it easier to work with data, you need to translate these colors into identifiers: 0, 1, 2, 3 ... But you can’t do this if (color == 0xFF46B1E2), since the palette differs in different versions of games. For example, in one there is an orange color, and in the other, instead of it, lilac is used instead ... But do not worry, let's go round by - we will remember the colors for each index:
 private byte[][] colorsToIds(int[][] tableColor) { int size = tableColor.length; byte[][] out = new byte[size][size]; int colorsReaded = 1; //    for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { int color = tableColor[i][j]; for (byte k = 0; k < colorsReaded; k++) { //     if (colors[k] == -1) { colors[k] = color; colorsReaded++; if (colorsReaded > MAX_COLORS) colorsReaded = MAX_COLORS; } //     ,    ID if (color == colors[k]) { out[i][j] = k; break; } } } } return out; }


MAX_COLORS here is equal to 6, because in the games Flood-It there are just so many colors in the palette. But if suddenly someone wants to make a game with ten different colors in the palette, the program will be able to recognize them.

Now you can check the performance of this piece of code. After feeding the program the image of the playing field in Figure 1, the result did not take long to wait:

0 1 2 2 3 3 0 0 1 2 2 3 3 3
2 4 1 1 5 4 5 0 2 4 5 3 4 4
3 1 1 5 2 1 3 5 5 2 1 0 4 2
0 3 1 0 5 4 4 1 4 1 4 5 3 5
4 5 0 4 4 4 3 2 0 3 1 0 0 5
0 4 3 4 1 1 2 2 3 2 3 3 1 2
3 2 0 0 5 2 1 5 3 0 2 1 4 4
3 3 5 3 1 5 3 0 3 5 2 4 1 1
3 3 3 3 0 5 0 3 5 0 1 4 2 4
4 2 3 0 2 1 0 3 1 3 2 2 2 3
5 5 1 4 2 3 5 4 1 2 5 0 4 0
5 2 0 2 2 3 2 5 4 1 1 5 0 5
1 0 0 5 5 5 4 1 2 2 3 2 2 0
3 2 2 3 4 3 0 3 2 2 3 3 5 5

Search for the optimal sequence of fill options



No matter how I tried, I couldn’t work out an algorithm better than the author’s article . So I took his algorithm and rewrote it in a more universal way. I think he will not object.
 private byte getNextFillColor(byte[][] table) { //    int fillSize = (int) Math.pow(MAX_COLORS, FILL_STEPS); int[] fillRate = new int[fillSize]; //     int[] fillPow = new int[FILL_STEPS]; for (int i = 0; i < FILL_STEPS; i++) { fillPow[i] = (int) Math.pow(MAX_COLORS, i); } //  FILL_STEPS  MAX_COLORS  for (int i = 0; i < fillSize; i++) { byte[][] iteration = copyTable(table); for (int j = 0; j < FILL_STEPS; j++) { byte fillColor = (byte) (i / fillPow[j] % MAX_COLORS); fillTable(iteration, fillColor); } //     fillRate[i] = getFillCount(iteration); } //       FILL_STEPS   int maxArea = fillRate[0]; int maxColor = 0; for (int i = 1; i < fillSize; i++) { if (fillRate[i] > maxArea) { maxColor = i; maxArea = fillRate[i]; } } //        byte colorID = (byte) (maxColor % MAX_COLORS); fillTable(table, colorID); return colorID; }


Now we are not limited to four miscalculations forward and six colors in the palette, so you can change the values ​​at your discretion.
Based on this function, we compose a function for obtaining the complete winning sequence:
 ArrayList<Byte> seq = new ArrayList<Byte>(); while(!gameCompleted(copyTable)) { seq.add(getNextFillColor(copyTable)); }

gameCompleted checks whether all cells are filled with any one color, and if so, then the game is over.

Having launched the application, we will give it our picture 1 to be eaten, as a result of which we will get:
1 2 1 3 0 5 4 0 3 1 0 5 3 1 4 1 5 2 4 0 5
But this kind of result is not very convenient for us.

Search for the position of the fill buttons



So, at our disposal there is a sequence of identifiers for the fill, a palette with the colors of the cells, the coordinates of the field and its size. Buttons left. Looking at the playing fields you can see that the buttons are often to the left of the playing field, and at the same level with it. Of course, we will not limit ourselves to this. Suddenly somewhere there is a game with buttons on the top or on the right? Further, the colors of the buttons are close to the colors of the cells, but not always equal to them. This means that we will not be limited to a simple comparison of the points of the image with the palette. Well, let's collect everything in a heap and make up a button search algorithm:



Figure 3. The image is divided into parts.

All of the above in the code looks like this:
 public Point[] getButtons(int[] colors) { Point[] out = new Point[colors.length]; //      int size = boardSize * cellSize; //   ,      Rectangle[] partsOfImage = new Rectangle[] { new Rectangle(0, board.y, board.x, size), //    new Rectangle(0, 0, w, board.y), //    new Rectangle(board.x+size, board.y, w-board.x-size, size), //    new Rectangle(0, board.y+size, w, h-board.y-size) //    }; for (int i = 0; i < partsOfImage.length; i++) { Rectangle rect = partsOfImage[i]; BufferedImage part = image.getSubimage(rect.x, rect.y, rect.width, rect.height); //   ,     boolean found = true; for (int j = 0; j < colors.length; j++) { if (colors[i] == -1) continue; Point pt = findButton(part, colors[j]); if (pt != null) { //      pt.translate(rect.x, rect.y); out[j] = pt; } else { found = false; break; } } if (found) return out; } //      return null; }


findButton just goes through all the points of the image until it meets a color similar to the one given to it. To find such a color, you need to calculate the difference modulo each of its RGB components and compare it with a certain number - sensitivity:
 private boolean isEquals(int color1, int color2, int tolerance) { if (tolerance < 2) return color1 == color2; int r1 = (color1 >> 16) & 0xff; int g1 = (color1 >> 8) & 0xff; int b1 = color1 & 0xff; int r2 = (color2 >> 16) & 0xff; int g2 = (color2 >> 8) & 0xff; int b2 = color2 & 0xff; return (Math.abs(r1 - r2) <= tolerance) && (Math.abs(g1 - g2) <= tolerance) && (Math.abs(b1 - b2) <= tolerance); }


Automation of gameplay



So, when all the buttons are found and the desired sequence of their presses is given, you can proceed to the "auto-click". In order for the program itself to move the cursor to the right place and press the left mouse button, the same java.awt.Robot class serves. The function looks like this:
 public void clickPoint(Point click) { robot.mouseMove(click.x, click.y); robot.mousePress(InputEvent.BUTTON1_MASK); robot.delay(CLICK_DELAY); robot.mouseRelease(InputEvent.BUTTON1_MASK); }


Let me explain: first, move the cursor to the desired position of the screen, then press the left mouse button, wait a few fractions of a second so that the browser can manage to process the click, and then release the button. It's simple. And having a sequence of indexes for clicks and the coordinates of each button, you can write an automatic clicker:
 public void autoClick(Point[] buttons, byte[] result) { for (int i = 0; i < result.length; i++) { clickPoint(buttons[result[i]]); } }


All that remains now is to handle the situation when the buttons are not on the screen. In this case, simply create an image, draw on it all the colors (colors, not identifiers 0, 1, 2 ...) in order and display on the screen.
 public BufferedImage sequenceToImage(byte[] ids, int[] palette) { final int size = 20; //    //    10    final int CELLS_IN_ROW = 10; int width = CELLS_IN_ROW * size; if (width == 0) width = size; int rows = ids.length / CELLS_IN_ROW; BufferedImage out = new BufferedImage(width, (rows*size)+size, BufferedImage.TYPE_INT_RGB); Graphics G = out.getGraphics(); for (int i = 0; i < ids.length; i++) { G.setColor(new Color(palette[ids[i]])); G.fillRect(i % CELLS_IN_ROW * size, i / CELLS_IN_ROW * size, size, size); } G.dispose(); return out; }


Conclusion



That's what happened with the same picture 1:

Figure 4. Result.

Thank you for your attention, I will be glad to any advice and ideas on this topic.
Sources are available on github: Flood-It-Bot

Source: https://habr.com/ru/post/136380/

More articles:


All Articles