Досуг Общество Легенды и Мифы Живой мир Игры МАГАЗИН ДЛЯ ВСЕХ Полезное
2Пт
3Сб
5Пн
6Вт
7Ср
9Пт
10Сб
11Вс
12Пн
13Вт
14Ср
16Пт
17Сб
18Вс
19Пн
20Вт
21Ср
22Чт
23Пт
24Сб
25Вс
26Пн
27Вт
28Ср
29Чт
30Пт
31Сб
августа 2019
• Личный кабинет
Логин: (регистрация?) Пароль: (напомнить?)
• РЕГИСТРАЦИЯ
Свежие статьи Самые свежие статьи Вестника К

Полицейский из Подмосковья работал на ЦРУ, воевал в Донбассе и сел на 13 лет за госизмену. Мы с ним поговорили...

Мы выяснили у сопредседателя движения «Голос» Григория Мельконьянца, смогут ли теперь арестованные кандидаты продолжать борьбу за участие в осенних выборах.

Одна из самых запоминающихся участниц московского протеста — 17-летняя Ольга Мисик. Мы с ней поговорили...

Московские суды арестовали 29 июля не менее 40 человек, задержанных на акции протеста 27 июля, сообщает «ОВД-Инфо». Полный перечень решений можно посмотреть...

Зачем Россия отправляет в Венесуэлу военных советников и других специалистов...

• Реклама
О веселом Отдохни с Вестником

Собрали для вас примеры импортозамещения из России и дружественных республик. Глядя на них, хочется то ли плакать, то ли смеяться.

15 мая на аукционе Christieʼs в Нью-Йорке была продана скульптура «Кролик» американского художника Джеффа Кунса. Цена лота составила 91 075 000 долларов — это новый аукционный рекорд для работы ныне живущего художника.

Работа Клода Моне из серии «Стога сена» продана на аукционе Sothebyʼs в Нью-Йорке за 110,7 миллиона долларов. Это рекорд аукционной цены для картин этого художника.

Елена Фернандес из Сальвадора, Бразилия, открыла свой маленький тату-салон и тут же получила невероятную популярность среди местных жителей...

• Новости мира
В Ульяновске число отравившихся подсолнечным маслом увеличилось до 11
Пострадавшие от употребления подсолнечного масла кустарного производства продолжают поступать в медицинские учреждения Ульяновска. Так, по данным регионального министерства здравоохранения, 18 ...

Православные христиане отмечают Яблочный Спас
Православные христиане отмечают 19 августа праздник Преображения Господня, известный также как Яблочный Спас.

В ДНР опровергли сообщения об «участии» России в боях под Иловайском
Как указал Басурин, на вооружении армии Украины находились различные виды танковой техники, в том числе Т-72 и Т-80. Ранее The Guardian писала, что исследовательская группа Forensic Architecture ...


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

Информация к новости
  • Просмотров: 7917
  • Комментариев: 8
  • Автор: Xaoc
  • Дата: 21-11-2011, 10:36
  • В закладки:
  • 0
21-11-2011, 10:36


Не так давно на 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 Видео работы.

 

Источник





Вернуться   ==   Сообщить об ошибке? ==  Просмотров: 7917  ==  Комментариев: 8    Автор: Xaoc


Дорогие друзья! У нас появилась официальная группа вконтакте: http://vk.com/vestnik_k - теперь следить за нашими новостями еще удобнее!
поделиться с друзьями     
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь. Мы рекомендуем Вам зарегистрироваться, либо войти на сайт под своим именем, чтобы получить доступ ко всем ресурсам сайта.
<
  • Публикаций: 9
  • Комментов: 972
  • Skype:
  • Коммент №: 1
 

И что с этим делать?


  • Оценка:  0
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 771
  • Skype: Lamula_crng 
  • Коммент №: 2
 

кажеться я начинаю понимать как некоторые люди побеждают в турнире по камушкам  kz



  • Оценка:  14
  •    
  •    
<
  • Публикаций: 9
  • Комментов: 972
  • Skype:
  • Коммент №: 3
 

kz объясните как сделать скрипт!!!)

и скажите, как восстановить пароль к скайпу ((


  • Оценка:  0
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 113
  • Skype:
  • Коммент №: 4
 

Цитата: ЖиЗнЕрАд0сТнЫй МаКаК 
и скажите, как восстановить пароль к скайпу ((

Да-да, особенно, если не помнишь и пароля от мыла((  kz



  • Оценка:  0
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 152
  • Skype:
  • Коммент №: 5
 

Цитата: Ламула
кажеться я начинаю понимать как некоторые люди побеждают в турнире по камушкам

А я давно говорил, я предупреждал!! А меня админ нытиком назвал и форумку на трое суток впаял. ))))))))))))))))



  • Оценка:  0
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 162
  • Skype:
  • Коммент №: 6
 

не нашел алгоритм игры в камушки kz перебор не предлагать


  • Оценка:  0
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 49
  • Skype:
  • Коммент №: 7
 

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


  • Оценка:  2
  •    
  •    
<
  • Публикаций: 0
  • Комментов: 152
  • Skype:
  • Коммент №: 8
 

Face Out [9] (25-11-2011 08:53:43)
Забейте вы уже на этот турнир. Сказки про то что постоянные победители самые умные-разумные, а все остальные тупые нубы уже надоели. )) Есть проги помогающие выигрывать в камушки. То что их не могут отследить-либо лень, либо не хватает знаний. )) Пусть себе юзают их, побеждают. ) Зависть плохое чувство-потому проще забить и не замечать их.
# невидимка (25-11-2011 12:49:46)
А что тебе мешает прогу использовать? Бакланство? :)
# Face Out [9] (25-11-2011 12:56:40)
Это можно считать официальным разрешением? )
Как видите сам многонеуважаемый блюнев подтверждает, что такие проги
а) есть
б) используются
в) сам предлагает их использовать
Делаем выводы, господа. )))
Пы.Сы.Кстати.. Этим своим "бакланство, баклан" он мне каждый раз напоминает приподъездную наблатыканую шелупонь, дующую дешёвое пиво из пластиковых бутылок, громко матерящуюся и захаркивающюю все прилегающее пространство в подтверждение своей "крутизны". )) Ну, короче, риальный патсанчик. kz



  • Оценка:  2
  •    
  •    

Информация

Посетители, находящиеся в группе Гость, не могут оставлять комментарии к данной публикации.
  • На Главную
  • Реклама
    Новости мира
    В Ульяновске число отравившихся подсолнечным маслом увеличилось до 11
    Пострадавшие от употребления подсолнечного масла кустарного производства продолжают поступать в медицинские учреждения Ульяновска. Так, по данным регионального министерства здравоохранения, 18 ...

    Православные христиане отмечают Яблочный Спас
    Православные христиане отмечают 19 августа праздник Преображения Господня, известный также как Яблочный Спас.

    В ДНР опровергли сообщения об «участии» России в боях под Иловайском
    Как указал Басурин, на вооружении армии Украины находились различные виды танковой техники, в том числе Т-72 и Т-80. Ранее The Guardian писала, что исследовательская группа Forensic Architecture ...

    Вверх
    Вверх