Написание макроса-бота для браузерной игры

Не так давно на Google+ появились игры. Прочитав топик об этом, я решил во что нибудь поиграть. Игра Diamond Dash — еще один  пример популярной игры в Камушки. Через некоторое время игры программист побеждает геймера: однотипные действия нужно автоматизировать. И вот что из этого вышло…

*Примечание: «руками» даже опытному игроку сложно набрать больше 400к
После непродолжительного гугления было решено для решения использовать язык макросов AutoIt.
Под катом вы найдете краткое описание игры, один из способов распознавания поля, алгоритм определения точки нажатия, и некоторое количество оптимизаций. А так же ссылку на github-репозиторий скрипта.
UPD Добавлено видео работы скрипта.
Краткое описание игры

Игра представляет из себя простую «кликни-на-область-больше-трех-квадратиков-одного-цвета» головоломку.

Есть поле 9 на 10, заполненное квадратиками 5 цветов. У нас есть одна минута на то, чтобы набрать максимальное количество очков. При нажатии на область из 3 или более одноцветных клеток, она исчезает, то что над ней проваливается, а сверху падает недостающее. Количество начисленных очков зависит от размера области: чем она больше — тем больше очков.
Кроме того, если делать клики быстро, и почти безошибочно, поле вокруг загорается, а каждое удаление (в данном случае взрыв), захватывает соседние с удаляемой областью клетки.

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

Определение координат окна

Эта часть была добавлена в самую последнюю очередь, до этого координаты угла были жестко прописаны в коде. Используется функция из сторонней библиотеки ImageSearch для поиска сохраненного шаблона 10 на 10 пикселей. Судя по всему, фон слегка меняется от игры к игре, потому что не любой кусок подходил. 
На форумах повсеместно не рекомендуют использование ImageSearch из-за долгого времени работы. Но так как нам нужно определить координаты только один раз в начале игры, провисаний по времени можно не опасаться.
Распознавание цветов и сохранение скриншотов

Для определения цвета пикселя по его координатам в AutoIt есть функция PixelGetColor. Но как показала практика, измерение всего 90 пикселей занимает полторы секунды, что, конечно, не очень хорошо. Но справедливости ради надо сказать, что бот написанный с использованием этой функции набирал 400-600 тысяч очков, а это больше чем может набрать человек, даже при большой сноровке. 
На форумах был найден метод сохранения текущего состояния монитора в Bitmap, используя WinAPI. Кстати, этот битмап, при необходимости(например для дебага), можно сохранить в файл функцией _ScreenCapture. Далее смотрим цвета 90 пикселей, расположенных по решетке и по ним строим таблицу цветов квадратиков.

1. Func _GetField(ByRef $aiField) ; получение массива цветов поля
2. ; получение BitMap-снимка экрана с помощью WinAPI
3. Local $hWnd = WinGetHandle(«Игры Google+ — Google Chrome»)
4. Local $Size = WinGetClientSize($hWnd)
5. Local $hDC = _WinAPI_GetDC($hWnd)
6. Local $hMemDC = _WinAPI_CreateCompatibleDC($hDC)
7. Local $hBitmap = _WinAPI_CreateCompatibleBitmap($hDC, $Size[0], $Size[1])
8. Local $hSv = _WinAPI_SelectObject($hMemDC, $hBitmap)
9. _WinAPI_BitBlt($hMemDC, 0, 0, $Size[0], $Size[1], $hDC, 0, 0, $SRCCOPY)
10. _WinAPI_SelectObject($hMemDC, $hSv)
11. _WinAPI_DeleteDC($hMemDC)
12. _WinAPI_ReleaseDC($hWnd, $hDC)
13. Local $L = $Size[0] * $Size[1]
14. Local $tBits = DllStructCreate(‘dword[‘ & $L & ‘]’)
15. _WinAPI_GetBitmapBits($hBitmap, 4 * $L, DllStructGetPtr($tBits))
16. ; определение цветов клеток
17. For $iCol = 0 To $iNumCols — 1
18. For $iRow = $iNumRows — 1 to 0 Step —1
19. ; замер цвета квадратика
20. $iX = $iCornerX + ($iCol * 40) + $iDeltaX
21. $iY = $iCornerY + ($iRow * 40) + $iDeltaY
22. $iPixelColor = Mod(DllStructGetData($tBits, 1, $iY * $Size[0] + $iX), 0x1000000)
23. $aiField[$iRow][$iCol] = _GetCheckColor($iPixelColor)
24. Next
25. Next
26. ; удаление данных для избежаня утечки памяти
27. _WinAPI_DeleteObject($hBitmap)
28. _WinAPI_DeleteObject($hMemDC)
29. _WinAPI_DeleteObject($tBits)
30. EndFunc

Тут стоит оговориться, почему замер происходит всего по 1 точке. Этот метод был испробован мной в первую очередь, и остался в финальной версии. Между этими двумя моментами было испробовано довольно большое количество альтернативных способов, среди которых были: замер 64 точек на каждый квадратик(решетка 8 на 8) и различные усреднения полученных значений, случайный выбор координат для замера, хранение истории нескольких последних замеров для лучшей точности… Но все они оказались менее точными или удобными, чем самый первый способ. 
Возможно, что так как я весьма далек от темы распознавания изображений, я не знаю чего-то простого, способного помочь мне в этом вопросе. В таком случае буду рад любым предложениям. =)
Определение одноцветной области по таблице цветов

Ну, и, наконец, осталось найти подходящее место и кликнуть туда. Для этого обходим поле снизу вверх (потому что все падает вниз, а значит снизу менее пусто чем сверху), и проверяем одноцветные части. Я делал это с помощью алгоритма безрекурсивного поиска в глубину (DFS). Вкратце суть такова: кладем в стек стартовую клетку, а дальше, пока стек не пуст, достаем из него текущую клетку и обходим ее соседей, при совпадении цвета кладем в стек. Ну да что говорить, код понятней. =)

1. Func _DfsAreaSize(ByRef $aiField, $iStartX, $iStartY) ; нерекурсивный алгоритм поиска размера одноцветной области
2. ; методом поиска в глубину
3. Local $aiResult[$iNumCols * $iNumRows][2] ; список клеток входящих в область
4. Local $iResultSize = 0
5. Local $afMap[$iNumRows][$iNumCols] ; флаги пройденности
6. For $iRow = 0 to $iNumRows — 1
7. For $iCol = 0 to $iNumCols — 1
8. $afMap[$iRow][$iCol] = False
9. Next
10. Next
11. $afMap[$iStartX][$iStartY] = True
12. Local $aiStack[$iNumRows * $iNumCols][2] ; активный стек
13. Local $iStackSize = 1
14. $aiStack[0][0] = $iStartX
15. $aiStack[0][1] = $iStartY
16. While $iStackSize > 0
17. $iStackSize -= 1
18. $iX = $aiStack[$iStackSize][0]
19. $iY = $aiStack[$iStackSize][1]
20. $aiResult[$iResultSize][0] = $iX
21. $aiResult[$iResultSize][1] = $iY
22. $iResultSize += 1
23. For $iDirection = 0 to 3 ; перебор 4 рядомстоящих клеток
24. Local $iNewX = $iX
25. Local $iNewY = $iY
26. Switch $iDirection
27. Case 0
28. $iNewY += 1
29. Case 1
30. $iNewY -= 1
31. Case 2
32. $iNewX += 1
33. Case 3
34. $iNewX -= 1
35. EndSwitch
36. If ($iNewX >= 0 And $iNewX < $iNumRows And _
37. $iNewY >= 0 And $iNewY < $iNumCols And _
38. Not($afMap[$iNewX][$iNewY]) And $aiField[$iNewX][$iNewY] = $aiField[$iStartX][$iStartY]) Then
39. $afMap[$iNewX][$iNewY] = True
40. $aiStack[$iStackSize][0] = $iNewX
41. $aiStack[$iStackSize][1] = $iNewY
42. $iStackSize += 1
43. EndIf
44. Next
45. WEnd
46. Return $iResultSize
47. EndFunc

Оптимизации

Оптимизация 1. Алмазики

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

А между тем, алмазы — очень полезная вещь, потому что пока падает огненный шар, таймер останавливается, а квадратики падают. А значит пробелы заполняются, и ошибок будет меньше. 
Для определения алмазов для начала пришлось поиграть с координатами замеров, чтобы цветные клетки определялись корректно, а алмазы — не попадали ни под один из их цветов. После этого создаем массив $aiDiams размером 3 (будем проверять только нижние 3 строки, потому что все алмазы рано или поздно туда упадут) * ширину (в нашем случае — 10). При каждом замере просматриваем нижние 3 строки, и если ячейка определилась, то обнуляем соответствующее место в $aiDiams, иначе инкрементируем его. Таким образом для клеток с алмазиками значения будут велики. При накоплении некоего порога, кликаем.

1. For $iRow = $iNumRows — 1 to $iNumRows — 3 Step —1
2. For $iCol = 0 to $iNumCols — 1
3. If $aiField[$iRow][$iCol] <> 0 Then
4. $aiDiams[$iRow][$iCol] = 0
5. Else
6. $aiDiams[$iRow][$iCol] += 1
7. If $aiDiams[$iRow][$iCol] > 15 Then
8. MouseClick(«Left», $iCornerX + 30 + ($iCol * 40), $iCornerY + 10 + ($iRow * 40), 1, $iMouseSpeed)
9. $aiDiams[$iRow][$iCol] = 0
10. Sleep(500)
11. Return 0
12. EndIf
13. EndIf
14. Next
15. Next

Оптимизация 2. Over Explosion

Тут надо объяснить, почему очень важно уменьшить количество ошибок, и почему в моем скрипте между соседними снимками экрана стоит задержка в 1/10 секунды. Дело в том, что когда поле загорается и ячейки начинают взрываться, количество очков многократно возрастает. Но если слишком много ошибаться, поле перестает загораться. Поэтому минимизация ошибок не менее важная часть, чем оптимизация времени распознавания (а учитывая запас времени, вообще единственно важная).
Несмотря на задержку в 1/10 секунды между соседними снимками экрана, некоторые ячейки все равно не успевают упасть, и определяются не на своих местах. Чтобы уменьшить их количество, была введена проверка на взрыв. При взрыве в квадратике появляется ореол почти чисто-белого цвета (#fffefc если быть точным), а это легко определить. Все клетки над взрывом, не мудрствуя лукаво, можно проставить как неопределенные.
Оптимизация 3. Область последнего клика

Защита от повторной ошибки, в эффективности которой я не уверен. Дело в том, что в самой игре при ошибке клетка становится серого цвета, а серый цвет алгоритмом определяется как неопределенный (тавтология получилась =) ). Но хуже эта проверка точно сделать не может, поэтому пусть живет. 
Суть в том, что при каждом клике сохраняем область, по которой кликаем, и при следующем клике не трогаем ее.
Итог

После всего вышеописанного, мой рекорд стал примерно таким:

Очень хотелось 2 миллиона, но 4 дня попыток, пара тысяч строк экспериментального кода (с самописным логгированием и сохранением скринов), тщательное курение логов и сверки со скриншотами, результатов не дало. =(
Ссылка на репозиторий github: github.com/EvilTosha/DiamondDash

Вместо постскриптума. Пара слов об AutoIt

Меня очень удивило, что этот язык почти не освещен на хабре. Собственно, желание исправить эту несправедливость и побудило написать этот топик.
Язык при этом умеет довольно много, и обладает поражающей простотой изучения. Через пару часов после того, как я узнал о его существовании, я уже обладал всеми знаниями нужными для написания данного макроса.
С помощью AutoIt можно автоматизировать почти любое рутинное действие: сохранение скриншота, установка программы(если надо поставить на много компов), многократный логин куда-либо… Можно скомпилировать в exe-шник, подключать DLL-ки.
Но что-то я как евангелист заговорил. =)

UPD Видео работы.

 

Источник