Часто за собой замечаю, что при виде какой-нибудь программы, игры или сайта у меня возникают странные мысли. И мысли эти меня пугают. А думаю я всякий раз о том, как эту программу/сайт/игру можно подхачить, взломать, обойти защиту, автоматизировать, расширить функциональность. Наверное, профессиональная деформация дает о себе знать. Или это подсознательное желание использовать накопленные знания, не находящие применения на работе. Как правило, эти желания остаются на уровне мыслей, но бывают исключения. Об одном таком случае я и расскажу вам сегодня…
Было это давно. Году эдак в 2008. Был обычный зимний день. Ничего не предвещало бессонной ночи. Но тут я заметил, как будущая жена играет на компе в одну игру…
То была игра «Найди 5 отличий» (в оригинале «5 Spots»). При виде пользовательского интерфейса игры у меня сразу возникло вышеуказанное желание — «А можно ли написать программу, которая бы искала отличия и подсказывала игроку куда жать мышкой, а то и сама бы двигала ей и жала сама?». Как оказалось, возможно все.
Сама игра довольно старая и примитивная. Как видно из скриншота, она показывает 2 картинки с отличиями и ждет пока юзер прокликает их мышкой. Все просто. Такой подход избрал и я в своем решении:
1. юзер запускает программу-подсказчика (ПП)
2. запускает целевую игру
3. жмет волшебную комбинацию клавиш
4. в нужным местах картинки ПП подсвечивает различия
Мне нравится, когда программы разговаривают со мной: пишут логи, отчитываются о своих действиях, сообщают об ошибках. Тогда создается впечатление, что программа не бездушный сухой алгоритм, просто делающий свою работу, а живой организм. Он может быть молчаливым, изредка выводящим сообщения, либо разговорчивым, активно фигача в консоль…
В общем, я выбрал консольное приложение как основу для ПП. Зарегистрировал комбинацию горячих клавиш Ctrl + F1 (типа, «помощь»), повесил обработчик. Но как найти отличия в 2х картинках из игры? Для начала, картинки нужно было «увидеть» программно. Тут тоже все просто — «фотографируем» окно в фокусе в память по нажатию на горячие клавиши:
HWND targetWindow = ::GetForegroundWindow(); HDC targetWindowDC = ::GetWindowDC(targetWindow); if (targetWindowDC != NULL) { HDC memoryDC = ::CreateCompatibleDC(targetWindowDC); if (memoryDC != NULL) { CRect targetWindowRectangle; ::GetWindowRect(targetWindow, &targetWindowRectangle); HBITMAP memoryBitmap = ::CreateCompatibleBitmap(targetWindowDC, targetWindowRectangle.Width(), targetWindowRectangle.Height()); if (memoryBitmap != NULL) { ::SelectObject(memoryDC, memoryBitmap); ::BitBlt(memoryDC, 0, 0, targetWindowRectangle.Width(), targetWindowRectangle.Height(), targetWindowDC, 0, 0, SRCCOPY);
Позиции картинок с отличиями в игре постоянные, размеры окна игры тоже — поэтому тут решает хардкод смещений и размеров (ведь наша ПП работает только с этой игрой). В памяти берем 2 картинки и «ксорим» их одна на другую:
#define BITMAP_WIDTH 375 #define BITMAP_HEIGHT 292 #define COORD_X_LEFT_IMAGE_UPPER_LEFT 19 #define COORD_Y_LEFT_IMAGE_UPPER_LEFT 152 #define COORD_X_RIGHT_IMAGE_UPPER_LEFT 405 #define COORD_Y_RIGHT_IMAGE_UPPER_LEFT COORD_Y_LEFT_IMAGE_UPPER_LEFT ::BitBlt( memoryDC, COORD_X_LEFT_IMAGE_UPPER_LEFT, COORD_Y_LEFT_IMAGE_UPPER_LEFT, BITMAP_WIDTH, BITMAP_HEIGHT, memoryDC, COORD_X_RIGHT_IMAGE_UPPER_LEFT, COORD_Y_RIGHT_IMAGE_UPPER_LEFT, SRCINVERT );
ВыXORивается следующая картина:
А дальше начинается поиск отличий.
Сейчас, когда пишу эту статью, вспоминаю, что была у меня какая-то либо лаба, либо курсовой проект в универе на эту тему. На тему обработки похожих изображений. И там я написал этот алгоритм. Я прекрасно понимаю, что ничего нового не изобрел — скорее всего, у этого алгоритма даже есть какое-то специальное название. Да и не привязан он к изображениям вовсе. В общем, кто знает, что это, подскажите.
Итак, мы имеет черную картинку с нечерными пикселями в местах, где были отличия. Причем пиксели эти расположены не вплотную друг к другу, а, в общем случае, с какими-то промежутками. Но, как видно из скриншота, области отличий достаточно локализованы. Алгоритм поиска этих областей состоит в следующем:
1. проходим по картинке
2. находим нечерный пиксель
3. смотрим в его окрестность и ищем его нечерных соседей — все это помещаем в найденную область (если рассматриваемые пиксели не были обработаны ранее)
Настраиваемым параметром тут служит «размер» окрестности пикселя — на сколько далеко можно от него заглядывать. Это позволяет искать более «размазанные» области отличий. Понятное дело, что все это неидеально и, в общем случае, найденных областей будет больше, чем отличий в картинках — ведь в самих картинках-заданиях возможен шум от сжатия, затесавшийся курсор мыши или что-то еще, выглядещее как различие на программном уровне, но незаметное с точки зрения игрока. Поэтому найденные различия нужно отсортировать по площади — чем больше нечерных пикселей вмещает область, тем больше вероятность того, что это не шум, а именно различие.
Уже потом я узнал и попробовал OpenCV (возможно, и о ней будет статья). Думаю, что есть более быстрые и оптимизированные алгоритмы. Но тогда меня хватило именно на такой вариант.
Исходник поиска различий (код старый, публикую без изменений):
#include "StdAfx.h" #include ".\bitmapinfo.h" #include <stack> const CPixel CBitmapInfo::m_defaultPixel; CBitmapInfo::CBitmapInfo(void) { m_uWidth = 0; m_uHeight = 0; } CBitmapInfo::~CBitmapInfo(void) { Clear(); } HRESULT CBitmapInfo::Clear() { m_uWidth = 0; m_uHeight = 0; // Pixel clearing for (CPixelAreaIterator pixelAreaIterator = m_arPixels.begin(); pixelAreaIterator != m_arPixels.end(); ++pixelAreaIterator) { delete (*pixelAreaIterator); } m_arPixels.clear(); return S_OK; } HRESULT CBitmapInfo::LoadBitmap(HDC hDC, const CRect &bitmapRect) { Clear(); m_uWidth = bitmapRect.Width(); m_uHeight = bitmapRect.Height(); m_arPixels.assign(m_uHeight * m_uWidth, NULL); for (INT nPixelY = 0; nPixelY < m_uHeight; ++nPixelY) { for (INT nPixelX = 0; nPixelX < m_uWidth; ++nPixelX) { CPixel *pPixel = new CPixel(nPixelX, nPixelY, ::GetPixel(hDC, nPixelX + bitmapRect.left, nPixelY + bitmapRect.top)); SetPixel(nPixelX, nPixelY, pPixel); } } return S_OK; } HRESULT CBitmapInfo::GetPixelAreas(INT nPixelVicinityWidth, CPixelAreaList &arPixelAreaList) { arPixelAreaList.clear(); if (m_uHeight > 0) { // Reinitialize all pixel reserved values (if needed) const CPixel *pFirstPixel = GetPixel(0, 0); if (pFirstPixel->IsValid() != FALSE && pFirstPixel->GetReserved() != CBitmapInfo::m_defaultPixel.GetReserved()) { for (INT nPixelY = 0; nPixelY < m_uHeight; ++nPixelY) { for (INT nPixelX = 0; nPixelX < m_uWidth; ++nPixelX) { CPixel *pPixel = GetPixel(nPixelX, nPixelY); pPixel->SetReserved(-1); } } } // Process pixels typedef stack<CPixel*> CPixelStack; // Look through all bitmap pixels const UINT uPixelCount = m_uWidth * m_uHeight; UINT uPixelAreaIndex = 0; for (INT nPixelY = 0; nPixelY < (INT)m_uHeight; ++nPixelY) { for (INT nPixelX = 0; nPixelX < (INT)m_uWidth; ++nPixelX) { CPixel *pPixel = GetPixel(nPixelX, nPixelY); // If this pixel is valid (belongs to bitmap) if (pPixel->IsValid() != FALSE) { // If this current pixel is not already processed if (pPixel->GetReserved() == CBitmapInfo::m_defaultPixel.GetReserved()) { // Set this pixel as processed pPixel->SetReserved(uPixelAreaIndex); // If this pixel matches localization criteria if (pPixel->GetColor() != COLOR_BITMAP_BACKGROUND) { // Add pixel to its area CPixelArea *pPixelArea = new CPixelArea(); pPixelArea->push_back(pPixel); // Push pixel to its stack CPixelStack pixelStack; pixelStack.push(pPixel); do { CPixel *pVicinityPixel = pixelStack.top(); pixelStack.pop(); INT nStartingX = pVicinityPixel->GetX(); INT nStartingY = pVicinityPixel->GetY(); for (INT nVicinityY = nStartingY - nPixelVicinityWidth; nVicinityY <= nStartingY + nPixelVicinityWidth; ++nVicinityY) { for (INT nVicinityX = nStartingX - nPixelVicinityWidth; nVicinityX <= nStartingX + nPixelVicinityWidth; ++nVicinityX) { pVicinityPixel = GetPixel(nVicinityX, nVicinityY); // If this pixel is valid (belongs to bitmap) if (pVicinityPixel->IsValid() != FALSE) { // If this current pixel is not already processed if (pVicinityPixel->GetReserved() == CBitmapInfo::m_defaultPixel.GetReserved()) { // Set this pixel as processed pVicinityPixel->SetReserved(uPixelAreaIndex); // If this pixel matches localization criteria if (pVicinityPixel->GetColor() != COLOR_BITMAP_BACKGROUND) { pPixelArea->push_back(pVicinityPixel); pixelStack.push(pVicinityPixel); } } } } } } while (pixelStack.size() > 0); arPixelAreaList.push_back(pPixelArea); ++uPixelAreaIndex; } } } } } } return S_OK; }
Дальше еще проще — подсветить найденные области на экране. Так как программа игры не использует никаких DirectX’ов (на сколько я могу судить), то тут помог простой вывод графики на окно игры. В общем-то, если бы был DirectX, то так просто «сфоткать» экран не получилось бы, не говоря уже о подсветке различий поверх игры. Но тут WinAPI рулит (функция ::Rectangle()). Результат подсветки:
От полностью программной игры пришлось отказаться — ПП и так слишком облегчала игру, если бы она еще и за тебя играла, то было бы вообще неинтересно. Но докрутить ПП до бота проще простого — зная координаты областей-отличий можно прокликать их мышкой, дождаться следующего уровня, распознать отличия и так далее…
Это все возможно, но, судя по всему, тогда меня хватило только на одну бессонную ночь.
ссылка на оригинал статьи http://habrahabr.ru/post/224727/
Добавить комментарий