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