Как программисты ищут отличия

в 17:58, , рубрики: just for fun, Алгоритмы, бессонная ночь, ненормальное программирование, обработка изображений, метки: ,

Как программисты ищут отличия

Часто за собой замечаю, что при виде какой-нибудь программы, игры или сайта у меня возникают странные мысли. И мысли эти меня пугают. А думаю я всякий раз о том, как эту программу/сайт/игру можно подхачить, взломать, обойти защиту, автоматизировать, расширить функциональность. Наверное, профессиональная деформация дает о себе знать. Или это подсознательное желание использовать накопленные знания, не находящие применения на работе. Как правило, эти желания остаются на уровне мыслей, но бывают исключения. Об одном таком случае я и расскажу вам сегодня…

Было это давно. Году, эдак, в 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 <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

Источник

Поделиться

* - обязательные к заполнению поля