Как программисты ищут отличия
Часто за собой замечаю, что при виде какой-нибудь программы, игры или сайта у меня возникают странные мысли. И мысли эти меня пугают. А думаю я всякий раз о том, как эту программу/сайт/игру можно подхачить, взломать, обойти защиту, автоматизировать, расширить функциональность. Наверное, профессиональная деформация дает о себе знать. Или это подсознательное желание использовать накопленные знания, не находящие применения на работе. Как правило, эти желания остаются на уровне мыслей, но бывают исключения. Об одном таком случае я и расскажу вам сегодня…
Было это давно. Году, эдак, в 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 картинки и «ксорим» их одна на другую:
XOR двух половинок #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
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
// 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 ()). Результат подсветки: 
От полностью программной игры пришлось отказаться — ПП и так слишком облегчала игру, если бы она еще и за тебя играла, то было бы вообще неинтересно. Но докрутить ПП до бота проще простого — зная координаты областей-отличий можно прокликать их мышкой, дождаться следующего уровня, распознать отличия и так далее…
Это все возможно, но, судя по всему, тогда меня хватило только на одну бессонную ночь.
