вторник, 3 января 2012 г.

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

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

  • распознать игровое поле и его параметры;
  • перевести графическое представление поля в логическое (массив чисел);
  • найти последовательность оптимальных вариантов заливки;
  • автоматизировать процесс игры. Отобразить результат.
 По поводу последнего пункта: автоматизировать процесс, значит автоматически кликать на кнопки, отвечающие за заливку. Как правило, эти кнопки находятся за пределами игрового поля, но поскольку мы пишем универсальную программу, то кнопки также придётся находить автоматически. Немного подумав, я пришел к выводу, что лучше этого не делать, а просто вывести результат - последовательность заливаемых цветов. Может быть, с опытом, мне удастся решить эту проблему, но пока я не стал зацикливаться на этом. Пусть уж хоть как-нибудь работает, а улучшить всегда можно.
 Перейдём к разбору каждого из пунктов.

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

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

 Чтобы получить изображение всего экрана, нам на помощь придёт класс java.awt.Robot.
/*
 * Получение картинки размером [width x height] с экрана с позиции [x, y]
 * Если width или height равны -1, то возвращаем весь экран
 */
public BufferedImage getImage(int x, int y, int width, int height) {
    Rectangle area;
    if ((width == -1) || (height == -1)) {
        area = new Rectangle(Toolkit.getDefaultToolkit().getScreenSize());
    } else area = new Rectangle(x, y, width, height);
    return robot.createScreenCapture(area);
}
 Далее, нужно определить преобладающий цвет фона. Обычно это белый цвет, но ситуации бывают разные, поэтому не стоит пропускать этот шаг. Изобретать велосипед мне не хотелось, поэтому я воспользовался услугами великого Random'a - бросил MAX_COLOR_POINTS случайных точек и определил их цвета. Затем из полученного массива цветов выбрал наиболее преобладающий. В коде это выглядело так:
/**
 * Определить цвет фона.
 * @param numPoints сколько точек нужно для определения.
 * @return цвет фона
 */
private int getBgcolor(int numPoints) {
    // Получаем numPoints случайных точек
    Random rnd = new Random();
    int[] colors = new int[numPoints];
    for (int i = 0; i < numPoints; i++) {
        int x = rnd.nextInt(w);
        int y = rnd.nextInt(h);
        colors[i] = image.getRGB(x, y);
    }
    // Находим частоту вхождение каждого цвета
    int maxIndex = 0; // индекс максимального цвета в массиве
    int max = -1; // максимальное число вхождений
    for (int i = 0; i < numPoints; i++) {
        int num = 0;
        for (int j = 0; j < numPoints; j++) {
            if (i == j) continue;
            if (colors[i] == colors[j]) num++;
        }
        if (num > max) {
            maxIndex = i;
            max = num;
        }
    }
    return colors[maxIndex];
}
 Следующий шаг был для меня одним из сложных, нужно было распознать край игрового поля. Я пытался подойти к проблеме с разных сторон, но наиболее работоспособный вариант получился такой:
  • проходим по картинке по-вертикали и по-горизонтали с некоторым шагом;
  • подбираем размер ячейки (10~35);
  • проверяем параметры (координаты и размер ячейки) на соответствие левому верхнему углу поля.
  • проверка считается успешной, если по-вертикали, по-горизонтали и по-диагонали цвет пикселей, взятый с шагом размера ячейки, не является фоновым.
Критерий успешности проверки.
 Этот алгоритм работает, но только на тех играх, где цвет фона однороден. К тому же, иногда (хм, всегда) возникают проблемы с подбором размера ячейки. Для пользователя это не страшно - пару кликов для подбора размера ячейки решают эту проблему. Но оставлять без присмотра этот недочёт я не стал, поэтому позже я добавил еще пару проверок, и всё стало на свои места:
  • если цвет в предполагаемой точке (x, y) не совпадает с (x+size-1, y+size-1), значит размер подобран неверно;
  • проверка точки (x, y) должна быть успешной для x+1 и для y+1, и не успешной для x-1, y-1.


 Вот теперь есть вероятность того, что алгоритм распознает поле.

Вот код проверки:
/**
 * Проверить координаты на соответствие левому верхнему углу поля.
 * Меняя предположительный размер ячеек (от 10 до 35) проходим boardSize раз
 * и смотрим, чтоб все точки были отличны от фона.
 * @return размер ячейки, для которого выполнилось условие, 
 * или 0, если условие не выполнено
 */
private int testPoints(int x, int y, int boardSize) {
    boolean ok = false;
    int tempStep = 0;
    for (int step = 35; step >= 10; step --) {
        ok = true;
        for (int i = 0; i < boardSize; i++) {
            // Проверка на несовпадение по X
            if (image.getRGB(x+i*step, y) == bgColor) {
                ok = false;
                break;
            }
            // Проверка на несовпадение по Y
            if (image.getRGB(x, y+i*step) == bgColor) {
                ok = false;
                break;
            }
            // Проверка на несовпадение и по X, и по Y
            if (image.getRGB(x+i*step, y+i*step) == bgColor) {
                ok = false;
                break;
            }
        }
        // Цвет (0,0) и (step-1, step-1) относительно (x,y)
        // должен совпадать, ведь это одна и та же ячейка
        if (ok) {
            tempStep = step;
            if (image.getRGB(x, y) == image.getRGB(x+step, y+step))
                return step;
        }
    }
    return tempStep;
}
А вот код получения координат левой верхней клетки:
/**
 * Шаг второй.
 * Определить координаты левого верхнего прямоугольника игрового поля.
 * @param boardSize размерность поля (10x10, 14x14 и т.д.)
 * @return координата левого верхнего прямоугольника
 */
private Point getBoardXY(int boardSize) {
    for (int x = 5; x < w/2; x += 2) {
        for (int y = 5; y < h/2; y += 2) {
            int step = testPoints(x, y, boardSize);
            // Если условие для шага выполнено, то уточняем координаты
            if (step != 0) {
                // Слева и сверху не должно сходиться, а справа и снизу должно
                boolean left = testPoints(x-1, y, boardSize) != 0;
                boolean right = testPoints(x+1, y, boardSize) != 0;
                boolean up = testPoints(x, y-1, boardSize) != 0;
                boolean down = testPoints(x, y+1, boardSize) != 0;
                if (!left && !up && right && down) return specifyCoords(x, y, step);
            }
        }
    }
    // Определить не удалось
    return new Point(0, 0); 
}
Ну вот, с этим мы разобрались, переходим к следующему шагу.
Перевод графического представления игрового поля в логическое.
План действий таков:
  • вырезаем область игрового поля из изображения экрана;
  • считываем цвета клеток;
  • переводим цвета в индексы;
Имея на руках в памяти координаты левого верхнего угла, количество и ширину клеток, легко найти фактический размер игрового поля - нужно всего лишь умножить количество клеток (размерность игрового поля) на их ширину.
/**
 * Получить изображение игрового поля
 * @return картинка игрового поля
 */
public BufferedImage getBoardImage() {
    int size = cellSize * boardSize;
    try {
        return image.getSubimage(board.x, board.y, size, size);
    } catch (Exception e) {
        return image;
    }
}
Теперь нужно считать цвета клеток. Делается это всё также просто:
int[][] table = new int[boardSize][boardSize];
for (int i = 0; i < boardSize; i++) {
    for (int j = 0; j < boardSize; j++) {
        table[i][j] = detectImage.getRGB(j*cellSize, i*cellSize);
    }
}
 И, наконец, нужно перевести цвета в индексы. Практика показывает, что эти цвета существенно отличаются в различных версиях игры, например в одной есть оранжевый цвет, а в другой, вместо него используется сиреневый. Поэтому простой if (color == 0xED70A1) работать универсально не будет. В связи с этим, пришлось немного исхитрится и запоминать массив цветов для каждого индекса.
/*
 * Преобразование массива с цветами в массив с идентификаторами
 */
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 с десятком различных цветов? Этот алгоритм сможет распознать и 10, и 20, и 220 различных цветов.
Думаю, самое время проверить работоспособность нашего алгоритма, и перевести изображение игрового поля в массив идентификаторов. Результат:
0  1  0  0  1  2  1  3  4  0  2  4  4  1  
4  1  2  4  3  3  2  1  0  1  1  1  4  0  
4  5  3  4  0  3  5  5  1  0  0  4  2  0  
0  1  5  3  4  4  1  5  1  0  3  0  4  4  
2  2  2  4  5  5  2  4  5  2  2  0  5  5  
5  4  4  5  3  1  3  5  0  1  3  3  2  5  
2  1  5  0  0  2  3  1  3  0  4  3  5  2  
0  1  4  3  2  0  3  3  2  3  3  4  2  2  
5  2  3  2  1  3  3  3  0  5  0  0  5  0  
4  5  3  5  1  5  2  2  2  3  1  4  4  0  
2  1  5  5  1  1  0  1  0  4  4  4  4  5  
5  4  1  5  1  2  2  2  1  4  5  2  5  2  
3  3  1  5  0  0  2  1  0  5  4  2  0  4  
3  0  1  4  1  0  5  4  4  5  0  2  5  1  
0 - фиолетовый, 1 - голубой, 2 - зелёный, 3 - желтый, 4 - красный, 5 - оранжевый.
Отлично, идём дальше.
Поиск последовательности оптимальных вариантов заливки.
 Вот, наконец, мы и подошли к самой важной части нашей программы. Нужно научить компьютер играть в Flood-It. Благо, это сделать легко. Нам потребуются такие функции:
  • заливка поля выбранным цветов;
  • подсчет клеток, залитых определённым цветом;
  • статус завершения игры (когда все клетки залиты);
 Две первые функции пахнут рекурсией, в прочем, я наверное не буду здесь объяснять что это такое и как с помощью неё заливать изображения, а сразу дам ссылку на хорошую статью, кто хочет - почитает.
 Имея эти три функции, можно приступать к обучению компьютера находить оптимальный вариант для заливки. Я опять не стал изобретать велосипед и решил модифицировать алгоритм, предложенный автором статьи на Хабре. Алгоритм заключался в переборе вариантов на 4 шага вперёд и последующим выбором наибольшего количества залитых клеток. Я решил не ограничиваться четырьмя шагами, и сделал произвольное количество глубины ходов. Но практика показала, что при четырёх шагах вперёд, алгоритм имеет хорошее соотношение время/оптимальность, а при шести просчетах мы выигрывали в оптимальности, но проигрывали во времени. Выше шести нет смысла ставить, так как лучшего результата вряд ли дождёмся. Так или иначе, константу FILL_STEPS по умолчанию я поставил в значение 4.
 Немного математики, и функция, определяющая, каким цветом заливать поле, была готова:
/*
 * Получить индекс следующего цвета для заливки
 */
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;
}
Надеюсь, объяснять подробнее этот кусок кода не надо.
Теперь, имея функцию определения цвета для заливки, можно написать функцию получения последовательности таких цветов:
/**
 * Получить последовательность заливки цветов
 * @return массив с цветами для заливки
 */
public int[] getFillSequence() {
    byte[][] copyTable = copyTable(table);
    ArrayList seq = new ArrayList();
    while(!gameCompleted(copyTable)) {
        seq.add(getNextFillColor(copyTable));
    }
    // Преобразовываем индексы в цвета
    int[] out = new int[seq.size()];
    for (int i = 0; i < out.length; i++) {
        out[i] = colors[seq.get(i)];            
    }
    return out;
}
Всё просто: вызываем функцию поиска цвета для заливки до тех пор, пока не зальётся всё поле. Затем преобразовываем индексы в реальные цвета из палитры. Осталось последнее...
Отображение результата.
Мы получили последовательность цветов, теперь нужно в понятном виде отобразить эти цвета пользователю. Для этого создадим изображение:
/**
 * Преобразовать массив цветов в графический вид
 * @param colors массив цветов
 * @return изображение последовательности цветов
 */
public BufferedImage sequenceToImage(int[] colors) {
    int size = 20; // размер каждого квадратика
    int width = colors.length * size;
    if (width == 0) width = size;
    BufferedImage out = new BufferedImage(width, size, BufferedImage.TYPE_INT_RGB);
    Graphics G = out.getGraphics();
    for (int i = 0; i < colors.length; i++) {
        G.setColor(new Color(colors[i]));
        G.fillRect(i * size, 0, size, size);
    }
    G.dispose();
    return out;
}
и отобразим его в модальном окне:
private void showImageWindow(String title, BufferedImage image) throws SecurityException, HeadlessException {
    ImageIcon icon = new ImageIcon(image);
    JLabel backlabel = new JLabel(icon);
    getLayeredPane().add(backlabel, new Integer(Integer.MIN_VALUE));
    backlabel.setBounds(0, 0, icon.getIconWidth(), icon.getIconHeight());
    JDialog dialog = new JDialog(this);
    dialog.setAlwaysOnTop(true);
    dialog.setLocationByPlatform(true);
    dialog.setTitle(title);
    dialog.setResizable(true);
    dialog.add(backlabel);
    dialog.pack();
    dialog.setVisible(true);
}
Создадим форму с кнопками и настройками и дадим на растерзание всё то же изображение игрового поля.
Скриншот работы программы.
При глубине просчетов на 5 ходов вперёд, результат был немного лучше:
Топ результатов.
Исходники можно взять здесь.
P.S. Конечно, то что получилось, bot'ом назвать сложно, но вот helper'ом вполне может называться ;)

Комментариев нет:

Отправить комментарий