Написание бота для Diamond Dash

от
Java   бот

Не так давно, просматривая ленту на Хабре, наткнулся на такую вот статью. Бегло просмотрев её, я решил сделать подобное на своём родном языке Java. Сейчас постараюсь в точности описать ход своих мыслей и идей. Приступим.
Первым делом нужно было узнать, умеет ли Java работать с мышкой? Интуиция выдала стопроцентный положительный результат, затем, через десять секунд был введён запрос в Google и получено подтверждение - в таких делах наш помощник это класс java.awt.Robot. Он умеет получать изображение с экрана, эмулировать нажатия клавиш и управлять мышью. То что нужно. Для начала решил освоить этот класс, для этого написал метод, который "набирал" переданный ему текст. Исходный код этого метода выглядит так:
  1. /**
  2.  * Автоматическое написание сообщения
  3.  * @param text "печатаемый текст"
  4.  */
  5. public void writeMessage(String text) {
  6.     for (char symbol : text.toCharArray()) {
  7.         boolean needShiftPress = Character.isUpperCase(symbol) && Character.isLetter(symbol);
  8.         if (needShiftPress) {
  9.             robot.keyPress(KeyEvent.VK_SHIFT);
  10.         }
  11.         int event = KeyEvent.getExtendedKeyCodeForChar(symbol);
  12.         try {
  13.             robot.keyPress(event);
  14.         } catch (Exception e) {}
  15.         if (needShiftPress) {
  16.             robot.keyRelease(KeyEvent.VK_SHIFT);
  17.         }
  18.     }
  19. }
Здесь всё просто: проходим по тексту символ за символом и проверяем, строчная или прописная буква перед нами. В зависимости от этого "нажимаем" SHIFT, а потом "отпускаем".
  1. int event = KeyEvent.getExtendedKeyCodeForChar(symbol);
кодирует символ в его код, для передачи непосредственно в метод нажатия клавиши в классе Robot.
Вот так инициализируется наш робот в конструкторе:
  1. robot = new Robot();
  2. // секунда на то, чтоб свернуть приложение
  3. robot.delay(1000);

Вдоволь наигравшись, я решил всё-таки перейти к делу. Нашел на facebook'е игру Diamond Dash, которая и послужила учителем моего бота. Первым делом я произвёл замеры области игры на экране. Узнал смещение, откуда начинают рисоваться блоки. Узнал размер одного блока - 40 пикселей. Размер поля - 10 на 9 блоков.
  bricks.png

Недолго думая, была выведена формула, по которой можно было бы обращаться к любому блоку:
  1. xClick = startx + xClick * BRICK_SIZE + BRICK_SIZE/2;
  2. yClick = starty + yClick * BRICK_SIZE + BRICK_SIZE/2;
Где startx / starty - смещение игрового поля от левого верхнего угла экрана, xClick / yClick - индекс нажимаемого блока, BRICK_SIZE/2 позволяет нам кликать мышкой ровно по центру блока.
В итоге был написан метод, кликающий по выбранному блоку:
  1. /**
  2.  * Кликнуть по нужному блоку
  3.  * @param xClick
  4.  * @param yClick
  5.  */
  6. private void clickBlock(int xClick, int yClick) {
  7.     xClick = startx + xClick * BRICK_SIZE + BRICK_SIZE/2;
  8.     yClick = starty + yClick * BRICK_SIZE + BRICK_SIZE/2;
  9.     robot.mouseMove(xClick, yClick);
  10.     robot.mousePress(InputEvent.BUTTON1_MASK);
  11.     robot.delay(150);
  12.     robot.mouseRelease(InputEvent.BUTTON1_MASK);
  13. }
Сначала мы высчитываем позицию, куда нужно переместить курсор, затем перемещаем его в это место. Далее нажимаем левую кнопку мыши, держим её 150 мс. и потом отпускаем. Вроде всё просто и прозрачно.

Вскоре, после написания еще одного метода, программа уже была работоспособна и пригодна для первого теста. Я не стал заморачиваться и сделал случайный выбор нажимаемого блока.
  1. /**
  2.  * Автоклик
  3.  * @param numOfClicks количество кликов
  4.  */
  5. public void click(int numOfClicks) {
  6.     for (int i = 0; i < numOfClicks; i++) {
  7.         clickBlock(random.nextInt(10), random.nextInt(9));
  8.     }
  9. }

Количество кликов фиксировано, иначе мы не смогли бы пошевелить нормально мышкой, так как программа перехватывала бы все наши действия.
Честно говоря, я ожидал худшего результата, но после запуска, мой рандомный бот набрал около 200000 очков, что уже превышает игру "ручками". Довольно-таки неплохо, но на этом глупо было останавливаться. Я решил продолжить, и сделать распознавание необходимых блоков. Алгоритм прост:
1. Получаем скриншот экрана с помощью Robot.
2. Сканируем изображение и идентифицируем цвет каждого блока.
3. Сопоставляем каждому цвету свой целочисленный индекс.
4. Ищем, какие блоки удовлетворяют нашему условию.
5. Кликаем по блоку.

Скриншот необходимой области экрана получать очень просто - задаем размеры и готово:
  1. /*
  2.  * Получение картинки размером [width x height] с экрана с позиции [x, y]
  3.  */
  4. public BufferedImage getImage(int x, int y, int width, int height) {
  5.     return robot.createScreenCapture(new Rectangle(x, y, width, height));
  6. }

С идентификацией немного сложнее, особенно тем, кто мало знаком со структурой изображений. Нужно получить цвет пикселя, и сравнить его с одним из пяти представленных в игре цветов. Здесь помог опыт реализации чувствительности для заливки. Весь код распознавания изображения и перевода его в числовые данные представлен здесь:
  1. /*
  2.  * Преобразование картинки в массив со значениями цветов.
  3.  * ID цвета будем брать на основе преимущества цветовой компоненты в пикселе.
  4.  */
  5. public int[][] getBricksID(BufferedImage image) {
  6.     int[] brickColors = new int[] {
  7.         0xFF0000, // RED
  8.         0x00FF00, // GREEN
  9.         0x0000FF, // BLUE
  10.         0xFFFF00, // YELLOW
  11.         0xFF00FF, // MAGENTA
  12.     };
  13.     for(int y = 0; y < brickId.length; y++) {
  14.         for (int x = 0; x < brickId[0].length; x++) {
  15.             // Сначала берём цвета пикселей
  16.             int color = image.getRGB(x * BRICK_SIZE + BRICK_SIZE/2+BRICK_SIZE/4,
  17.                                      y * BRICK_SIZE + BRICK_SIZE/4);
  18.             // Проходим по всем цветам блоков и выбираем наиболее подходящий цвет
  19.             brickId[y][x] = 0;
  20.             for (int id = 0; id < brickColors.length; id++) {
  21.                 if (isEquals(color, brickColors[id], COLOR_TOLERANCE)) {
  22.                     brickId[y][x] = id + 1;
  23.                 }
  24.             }
  25.  
  26.         }
  27.     }
  28.     return brickId;
  29. }
  1. /**
  2.  * Проверка, соответствуют ли цвета друг другу
  3.  * @param color1 первый цвет
  4.  * @param color2 второй цвет
  5.  * @param tolerance чувствительность
  6.  * @return true - соответствуют, false - нет
  7.  */
  8. private boolean isEquals(int color1, int color2, int tolerance) {
  9.     if (tolerance < 2) {
  10.         return color1 == color2;
  11.     }
  12.     int r1 = (color1 >> 16) & 0xff;
  13.     int g1 = (color1 >> 8) & 0xff;
  14.     int b1 = color1 & 0xff;
  15.     int r2 = (color2 >> 16) & 0xff;
  16.     int g2 = (color2 >> 8) & 0xff;
  17.     int b2 = color2 & 0xff;
  18.     return (Math.abs(r1 - r2) <= tolerance) &&
  19.            (Math.abs(g1 - g2) <= tolerance) &&
  20.            (Math.abs(b1 - b2) <= tolerance);
  21. }

В массиве brickColors записаны цвета блоков в формате RGB. Далее проходим по центру всех блоков и получаем их цвета. Затем этот полученный цвет сравниваем с шаблоном (массив brickColors) на предмет соответствия с погрешностью в COLOR_TOLERANCE значений цвета. Если цвет блока близок к цвету одного из шаблонов, то этому блоку присваивается соответствующий номер.
В итоге для той картинки, которая представлена выше, функция предоставит следующий массив:
2334232212
5224155525
1141331153
5323525524
1453254424
4325433433
2431224521
4331445413
5343152525

Как видно, алгоритм довольно точно преобразовывает графическую информацию в логическую.

  Следующим немаловажным шагом было написание алгоритма поиска необходимых блоков, по которым нужно кликать. Здесь я решил не делать лишних телодвижений, а просто рассчитать всевозможные комбинации, которые приводили бы к успеху. То есть имеем текущий блок с координатой [x,y], для которого нужно решить, находится ли он в блоке из более трёх таких же квадратиков. Значит нужно просмотреть все блоки вокруг и определить, какие из них такого же цвета. Я решил воспользоваться для этого двумерным массивом boolean, размером 3x3. Алгоритм заполнения этого массива такой:
  1. Получаем индекс блока [x, y].
  2. Если индекс нулевой, значит что-то в этом блоке не так: либо там серые квадратики, которые не нажимаются, либо там еще пусто. Поэтому блоки с нулевым индексом кликать не будем.
  3. Сравниваем индексы блоков, стоящих вокруг блока [x, y]. Те блоки, индексы которых совпадают, будут в массиве выглядеть как true, все остальные - false. Это поможет нам в дальнейшем, чтобы узнать комбинации необходимых блоков.

После этого создаём шаблон с размещением правильных блоков. Так как вариантов может быть несколько, то воспользуемся трёхмерным массивом.
  combinations.png

Правильные комбинации будут выглядеть так:
  1. private static final int[][][] good = {
  2.     { {0, 1}, {2, 1} },
  3.     { {1, 0}, {1, 2} },
  4.  
  5.     { {0, 0}, {0, 1} },
  6.     { {1, 0}, {2, 0} },
  7.     { {2, 1}, {2, 2} },
  8.     { {1, 2}, {0, 2} },
  9.  
  10.     { {0, 1}, {0, 2} },
  11.     { {1, 2}, {2, 2} },
  12.     { {2, 0}, {2, 1} },
  13.     { {0, 0}, {1, 0} }
  14. };
Сначала идёт значение y, а потом x. Так как [1,1] у нас всегда true, то проверять его не стоит.
Теперь можно написать функцию, которая подсказывает нам, стоит ли кликать по блоку [x, y] или нет.
  1. /**
  2.  * Поиск смежных одноцветных блоков
  3.  * @param x координата блока по-горизонтали
  4.  * @param y координата блока по-вертикали
  5.  * @return стоит ли кликать по текущему блоку?
  6.  */
  7. private boolean searchArea(int x, int y) {
  8.     int curID = getId(x, y);
  9.     if (curID == 0) return false;
  10.     // Совпадают ли вокруг блока (x, y) индексы.
  11.     boolean[][] indexEquals = {
  12.         { getId(x-1, y-1) == curID, getId(x, y-1) == curID, getId(x+1, y-1) == curID },
  13.         { getId(x-1, y) == curID, true, getId(x+1, y) == curID },
  14.         { getId(x-1, y+1) == curID, getId(x, y+1) == curID, getId(x+1, y+1) == curID }
  15.     };
  16.  
  17.     // Проверка соответствия нашей комбинации искомой
  18.     for (int i = 0; i < good.length; i++) {
  19.         if ( (indexEquals[ good[i][0][0] ][ good[i][0][1] ]) &&
  20.              (indexEquals[ good[i][1][0] ][ good[i][1][1] ])) {
  21.             return true;
  22.         }
  23.     }
  24.  
  25.     return false;
  26. }

Ну что ж, теперь самое время связать наши "кирпичики":
  1. /**
  2.  * "Умный" клик
  3.  */
  4. public void click() {
  5.     // Проходим снизу вверх, так как внизу блоки всегда есть
  6.     // Причем крайние блоки не трогаем
  7.     for(int y = brickId.length - 1; y > 0; y--) {
  8.         BufferedImage screen = getImage(startx, starty, 10 * BRICK_SIZE, 9 * BRICK_SIZE);
  9.         brickId = getBricksID(screen);
  10.         for (int x = 0; x < brickId[0].length; x++) {
  11.             if ( ((getId(x, y) != 0) && searchArea(x, y))) {
  12.                 clickBlock(x, y);
  13.             }
  14.         }
  15.     }
  16. }

Демонстрация работы программы:

Исходный код можно скачать здесь.
+5   5   0
1490