Универсальный бот для игры Flood-It

Рисунок 1. Игровое поле.

Однажды, попалась мне на глаза одна статейка. Сразу же после прочтения заголовка, в голове появились десятки идей подобного рода, среди которых была та самая — идея создания универсального бота для этой игры.

На тот момент особого опыта в автоматизации игр я не имел, но желание было превыше всего. Поэтому, достав тетрадь, я начал обдумывать сей процесс…

Анализ

Анализировать я начал с конца, представив, что у меня на руках уже есть работающая программа, нажимающая нужные кнопки в нужной последовательности. Чтобы она умела это делать, ей нужно знать координаты этих кнопок, не будет же она тыкать в любое место на экране, в надежде на то, что хоть раз попадёт? Далее, нужно предоставить последовательность, по которой бот будет нажимать кнопки, не будет же он тыкать любые кнопки, верно? Чтобы предоставить необходимую последовательность нажатий, нужно выбрать наиболее оптимальный алгоритм выбора цветов для заливки, а как это сделать не имея данных о состоянии поля? Правильно, никак! Поэтому нужно получить данные о цветах ячеек в игровом поле. Отлично, но возникает вопрос, а где же само игровое поле? Ответ «где-то на экране» не принимается, поэтому нужно будет найти и его. Вот теперь вроде всё, распишем план наших дальнейших действий:

• распознать игровое поле и его параметры;
• получить данные о цветах ячеек в игре;
• найти оптимальную последовательность вариантов заливки;
• отыскать положение кнопок заливки по каждому цвету;
• автоматизировать процесс игры.

Распознавание игрового поля и его параметров

Первым делом нужно было как-то узнать положение игрового поля на экране. Но сначала не помешало бы получить снимок экрана. Для этого мне понадобился класс java.awt.Robot, с его методом: BufferedImage createScreenCapture(Rectangle screenRect).
А что же дальше? А дальше было множество попыток заставить программу находить положение игрового поля, десятки тысяч обращений к методу getRGB класса BufferedImage, попытки узнать позицию игрового поля по шаблону и т.д. Все эти результаты были безуспешны. То что работало для одной игры, не работало для другой. И вот однажды, в голову ко мне влетел такой вот план:

• бинаризировать изображение;
• при необходимости инвертировать его, чтобы значимые точки были белыми, а фон чёрным;
• подсчитать количество вхождений белых точек по горизонтали и по вертикали;
• отсеять ненужные вхождения;
• найти самую длинную последовательность ненулевых значений. Позиция, с которой начинается эта длинная последовательность будет точкой начала игрового поля, а длина этой последовательности — размером в пикселях.

Получив снимок экрана, неплохо было бы перевести его в ARGB-массив:

int[] pixels = new int[w * h];
image.getRGB(0, 0, w, h, pixels, 0, w);

Работать с цветным изображением сложно, поэтому нужно бинаризировать его, то есть сделать монохромным, чтобы в нашем распоряжении были лишь черный и белый цвета. Здесь всё просто: берём очередной цвет и смотрим на его яркость, если она ниже пороговой, значит этот цвет будет чёрным, если выше — белым. В программной реализации это выглядит так:

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;

Сначала нужно получить яркость текущего цвета, а она берётся либо как среднее сумм RGB компонент, либо по формуле: brightness = 0.3 * red + 0.59 * green + 0.11 * blue. Коэффициенты взяты не просто так, они означают восприятие человеческим глазом той или иной компоненты цвета.

Теперь нужно подобрать пороговое значение (thresholdValue), 191 вполне подошло — на всех сайтах с игрой, где был светлый фон, бинаризация выдавала такое изображение:

Рисунок 2. Монохромное изображение.
А на сайтах с тёмным фоном, значение 64 давало подобную картинку, но инверсную. К слову, 191 я выбрал не просто так, а по закону 255-64.

Легко заметить, что на таком изображении игровое поле найти гораздо проще, чем если бы мы искали на цветном. Остаётся только узнать, светлый или тёмный у нас фон, чтобы по этим данным применить порог 64 или (255-64) и инвертировать изображение при надобности. В коде у меня это выглядит так:

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 принимает число точек, которые необходимы для того, чтобы понять, что фон светлый или тёмный. Получаем MAX_COLOR_POINTS из цветного изображения и находим среднюю яркость. Если она больше 128, значит фон светлый, если меньше — тёмный.

Далее, в полученном монохромном изображении, нам нужно подсчитать количество белых точек по горизонтали и по вертикали. Делается это двумя проходами по изображению. В итоге получаем два массива со значениями вида: 1440, 1440, 410, 23, 119, 838… Отфильтруем значения меньше среднего, и получаем массив: 1, 1, 0, 0, 0, 1… И наконец, нужно определить самую длинную последовательность вот таких единичек, которые не разорваны нулём. Это тоже довольно тривиальная задача.

В конце концов мы получаем 4 значения: положение игрового поля по горизонтали, по вертикали, ширину и высоту игрового поля. Так как оно квадратное, то два последних значения должны совпадать. Чтобы узнать размер каждой ячейки, нужно поделить размер игрового поля на его размерность. Размерность задаётся пользователем, ведь поле бывает не только 14x14, а и 10x10, 20x20 и т.д.

Получение данных о цветах ячеек

Теперь, когда мы определили параметры игрового поля, можно считывать цвета ячеек:

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);
    }
}

Во избежание ошибок, цвета будем брать строго по центру ячейки.

Далее, чтобы проще было работать с данными, нужно перевести эти цвета в идентификаторы: 0, 1, 2, 3… Но простым if (color == 0xFF46B1E2) это не сделать, так как палитра различается в разных версиях игр. Например в одной есть оранжевый цвет, а в другой, вместо него используется сиреневый… Но ничего страшного, пойдём обходным путём — будем запоминать цвета для каждого индекса:

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 здесь равен 6, так как в играх Flood-It именно столько цветов в палитре. Но если вдруг кому-то вздумается сделать игру с десятью различными цветами в палитре, программа сможет распознать и их.

Теперь можно проверить работоспособность этого куска кода. Скормив программе изображение игрового поля на рисунке 1, результат не заставил себя долго ждать:

0 1 2 2 3 3 0 0 1 4 2 3 5 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 4 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 5 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 4 3 5 5

Поиск оптимальной последовательности вариантов заливки

Как я ни пытался, но придумать алгоритм лучше чем у автора статьи у меня не получилось. Поэтому я взял его алгоритм и переписал на более универсальный лад. Думаю он возражать не будет.

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;
}

Теперь мы не ограничены четырьмя просчетами вперёд и шестью цветами в палитре, поэтому можно менять значения по своему усмотрению.
Составим на основе этой функции, функцию получения полной выигрышной последовательности:

ArrayList<Byte> seq = new ArrayList<Byte>();
while(!gameCompleted(copyTable)) {
    seq.add(getNextFillColor(copyTable));
}

gameCompleted проверяет, залиты ли все ячейки каким-нибудь одним цветом, и если да, значит игра завершена.

Запустив приложение, дадим ему на съедение наш рисунок 1, в результате чего получим:
1 2 1 3 0 5 4 0 3 1 0 5 3 1 4 1 5 2 4 0 5
Но такой вид результата не слишком удобен для нас.

Поиск положения кнопок заливки

Итак, в нашем распоряжении есть последовательность идентификаторов для заливки, палитра с цветами ячеек, координаты поля и его размер. Остались кнопки. Взглянув на игровые поля можно заметить, что кнопки зачастую находятся левее от игрового поля, причём на одном уровне с ним. Этим мы ограничиваться, конечно же не будем. Вдруг где-то есть игра с кнопками сверху или справа? Далее, цвета кнопок близки к цветам ячеек, но не всегда равны им. Это значит, что простым сравнением точек изображения с палитрой мы ограничиваться не будем. Что ж, соберём всё в кучу и составим алгоритм поиска кнопок:

• выделяем одну из четырёх частей изображения окна: слева от игрового поля, сверху, справа и, наконец, снизу;
• для каждого цвета из палитры ищем близкий к ней цвет на изображении. По нахождению, запоминаем позицию этой точки;
• если точки найдены для всех цветов из палитры, то всё отлично, с заданием справились. Иначе, переходим к первому шагу и выбираем следующую часть изображения;
• если были просмотрены все части изображения, но кнопки так и не нашли, значит их просто нет! В этом случае просто выдадим результат в более человеческом виде.

Рисунок 3. Разбивка изображения на части.

Всё вышеописанное в коде выглядит так:

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 просто перебирает все точки изображения, пока не встретит похожий на заданный ему цвет. Чтобы найти такой цвет, нужно посчитать разность по модулю каждой его RGB компоненты и сравнить с некоторым числом — чувствительностью:

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);
 }

Автоматизация игрового процесса

Итак, когда все кнопки будут найдены и будет дана нужная последовательность их нажатий, можно приступать к «автокликанью». Для того, чтобы программа сама переводила курсор в нужное место и нажимала левую кнопку мыши, служит всё тот же класс java.awt.Robot. Функция выглядит так:

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);
}

Поясню: сначала переводим курсор в нужную позицию экрана, затем нажимаем левую кнопку мыши, ждём несколько долей секунд, чтобы браузер смог успеть обработать нажатие, и затем отпускаем кнопку. Всё просто. А имея последовательность индексов для нажатий и координаты каждой кнопки, можно написать автоматический кликер:

public void autoClick(Point[] buttons, byte[] result) {
    for (int i = 0; i < result.length; i++) {
        clickPoint(buttons[result[i]]);
    }
}

Всё, осталось теперь обработать ситуацию, когда кнопок нет на экране. В этом случае просто создадим изображение, нарисуем на нём все цвета (именно цвета, а не идентицикаторы 0, 1, 2...) по порядку и выведем на экран.

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;
}

Заключение

Вот что получилось всё с тем же рисунком 1:

Рисунок 4. Результат.

Спасибо за внимание, буду рад любым советам и идеям по этой тематике.
Исходники доступны на github: Flood-It-Bot