Автоматизация игры во Flood-it

Добрый день.

После размещения вопроса о том интересно ли будет почитать об автоматизации процесса игры во Flood-it. Было получено несколько положительных отзывов, в связи с чем публикую данную статью.

Введение

Flood-it представляет собой игровое поле размером 14x14 с разноцветными клетками, задача игрока заполнить поле одним цветом за наименьшее количество ходов. Каждый ход представляет собой выбор цвета из палитры, всего в палитре шесть цветов. Всего на игру дается 25 ходов.


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

Необходимо реализовать алгоритм, для выбора оптимального цвета для заливки. Подробности можно прочитать реализации под катом.

Описание первой версии алгоритма

В процессе исследования было проработано два алгоритма. Первый алгоритм был более простым и состоял из следующих шагов:

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

С данным алгоритмом было сыграно 100 игр, из которых он выиграл в 28. Максимальное количество набранных очков составило 640 (две победы подряд).

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


Рисунок 2: проблема первого алгоритма.

На рисунке можно увидеть, что если сначала выполнить закраску зеленым, тогда можно получить доступ к большой розовой области. Если закрасить фиолетовым, тогда можно получить только красную область из двух клеток. Аналогично можно рассуждать для других цветов.

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

Описание второй версии алгоритма

Всего в игре шесть цветов, закрасить можно одним из пяти цветов исключая текущий цвет первой клетки. Таким образом для простого перебора на 4 шага вперед нужно перебрать 5^4 = 625 вариантов. Фактически же а алгоритме перебирается 1296 (шесть в четвертой степени) комбинаций. Каждая комбинация цветов представляется одним числом, порядок заливки определяется остатками от деления на шесть.

• 1 — розовый;
• 2 — фиолетовый;
• 3 — желтый;
• 4 — красный;
• 5 — синий;
• 6 — зеленый.

После выполнения закраски всеми четырьмя цветами подсчитывается количество клеток закрашенных цветом первой клетки. Среди этих чисел выбирается максимальное:

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


Класс FloodLevel предназначен для упрощения копирования и закраски и содержит следующие методы:

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(); // проверка завершена ли игра
}


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


Рисунок 3: достижение звания SuperPixie.

Тестирование алгоритма на 100 играх показало такие характеристики — 96 побед, максимально набрано 19680 очков. В процессе тестирование было получено звание SuperPixie. На данном алгоритме я остановился, так как заниматься рефакторингом и оптимизацией можно бесконечно долго.

Получение изображения уровня

Уровень представляет собой поле состоящее из разноцветных клеток. Каждая клетка закрашена монотонным цветом, что позволяет очень просто получить цвета клеток на уровне:

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


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

Управление игрой

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

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


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

Заключение

Рисунок 4: максимальное количество очков заработанное программой.

Программа писалась за один день — с вечера субботы по утро воскресенья. В связи с чем прошу прощения за антипаттерны, в частности Magic numbers. Также программа не находит уровень автоматически, в коде жестко прописаны смещения относительно угла экрана (я пользуюсь браузером Seamonkey под Gnome). Если тема будет интересна, могу допилить автоматический поиск игрового поля.

Исходный код можно скачать:

• по этой ссылке с народа;
• по этой ссылке с github.