Geekly Articles each Day
📜 ⬆️ ⬇️

How programmers look for differences



I often notice for myself that when I see a program, game or website, I have strange thoughts. And these thoughts scare me. And I think every time about how this program / website / game can podachachit, hack, circumvent protection, automate, expand functionality. Probably, professional deformation makes itself felt. Or is it a subconscious desire to use the accumulated knowledge that is not used at work. As a rule, these desires remain at the level of thoughts, but there are exceptions. I will tell you about one such case today ...

It was a long time ago. Year, commercials, in 2008. It was a normal winter day. Nothing foreshadowed a sleepless night. But then I noticed how the future wife played on the computer in one game ...


It was a “Find 5 Differences” game (originally “5 Spots”). When I saw the user interface of the game, I immediately had the above desire - “Can I write a program that would look for differences and tell the player where to press it with a mouse, or even move it itself and sting it?”. As it turned out, everything is possible.
')
The game itself is quite old and primitive. As can be seen from the screenshot, it shows 2 pictures with differences and waits while the user clicks on them with the mouse. It's simple. I chose this approach in my decision:
1. the user runs the program prompter (PP)
2. launches target game
3. presses a magic key combination
4. in the right places of the picture PP highlights the differences

I like it when programs talk to me: they write logs, report on their actions, report errors. Then it seems that the program is not a soulless, dry algorithm that just does its job, but a living organism. He can be silent, occasionally displaying messages, or talkative, actively figa in the console ...


In general, I chose the console application as the basis for the PP. I registered a keyboard shortcut Ctrl + F1 (like, “help”), hung up a handler. But how to find the differences in 2 pictures from the game? For a start, the pictures needed to be “seen” programmatically. Here, too, everything is simple - we “photograph” the window in focus into memory by pressing the hot keys:

Screen photography
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);



The positions of the pictures with differences in the game are constant, the size of the game window too - so the hardcode of offsets and sizes decide here (after all, our software works only with this game). In memory, we take 2 pictures and “xorim” them one on another:
XOR two halves
  #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 );



The following picture is displayed:


And then begins the search for differences.

Now, when I write this article, I remember that I had some kind of lab or course project at the university on this topic. On the subject of processing similar images. And there I wrote this algorithm. I understand perfectly well that I have not invented anything new - most likely, this algorithm even has some special name. And he is not attached to the images at all. In general, who knows what it is, tell me.

So, we have a black image with non-black pixels in places where there were differences. Moreover, these pixels are not located close to each other, but, in general, with some intervals. But, as can be seen from the screenshot, the areas of difference are quite localized. The algorithm for finding these areas is as follows:
1. we pass on the picture
2. find non-black pixel
3. we look into its neighborhood and look for its non-black neighbors — we place all this in the area found (if the pixels in question have not been processed before)

The “size” of the pixel neighborhood serves as a tunable parameter — how far away you can look from it. This allows you to search for more “blurred” areas of difference. It is clear that all this is imperfect and, in the general case, the areas found will be greater than the differences in the pictures - after all, in the pictures-tasks themselves there can be noise from compression, a mouse cursor or something else that looks like a difference at the program level, but imperceptible from the point of view of the player. Therefore, the differences found need to be sorted by area — the more non-black pixels the region contains, the greater the likelihood that this is not noise, but the difference.

Later, I found out and tried OpenCV (perhaps, there will be an article about it). I think that there are faster and more optimized algorithms. But then it was enough for me on this option.


Source search for differences (code is old, publish unchanged):
Finding differences
 #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; }



It is even easier to highlight the areas found on the screen. Since the program of the game does not use any DirectX'ov (as far as I can tell), then simple graphics output on the game window helped. In general, if there was DirectX, then it would not have been possible to simply “take a picture” of the screen, let alone highlight the differences over the game. But here WinAPI taxis (function :: Rectangle ()). Backlight result:



It was necessary to abandon the completely software game - the PP made the game too easy to play, and if it also played for you, it would not be interesting at all. But screwing up the PP to the bot is easy - knowing the coordinates of the areas of difference, you can click them with the mouse, wait for the next level, recognize the differences, and so on ...

This is all possible, but, apparently, then I only had enough for one sleepless night.

Source: https://habr.com/ru/post/224727/

More articles:


All Articles