Writing a macro bot for the browser game

Introduction

Not so long ago, games appeared on Google+. After reading the topic about it , I decided to play something. The choice fell on the game Diamond Dash . After a while, the programmer in me started talking about the need to automate actions of the same type. And that's what came of it ...

* Note: it is difficult for even an experienced player to gain more than 400k with "hands"

Before, I had never encountered the tasks of working with a screen and a mouse. After a short googling, it was decided to use the macro language AutoIt to decide.
Under the cat you will find a brief description of the game, my way of recognizing the field, the algorithm for determining the point of depression, and a number of optimizations. As well as a link to the script github repository.
UPD Added video of the script.

Brief description of the game

The game is a simple click-to-area-more-three-square-one-color puzzle.

There is a field of 9 by 10, filled with squares of 5 colors. We have one minute to score the maximum points. When you click on an area of ​​3 or more monochrome cells, it disappears, what falls through it, and the missing drops from above. The number of points awarded depends on the size of the area: the larger it is, the more points.
In addition, if you make clicks quickly, and almost unmistakably, the field around lights up, and each deletion (in this case an explosion), captures the cells adjacent to the deleted area.

And finally, the last feature: at the top there is a scale with a diamond at the end, which is filled as the cells are destroyed (and decreases with erroneous clicks). When it is filled, a burning diamond appears in a random place on the field. When you click on it, time stops, and a fireball falls on top of the field, destroying all the cells in the row and column where the stone was located.

Determining window coordinates

This part was added at the very last turn, before that the coordinates of the angle were fixed in the code. Uses a function from the third-party ImageSearch library to search for a saved 10 by 10 pixel template. Apparently, the background varies slightly from game to game, because not every piece fit.
The forums everywhere do not recommend the use of ImageSearch due to the long working time. But since we need to determine the coordinates only once at the beginning of the game, there is no need to fear sagging in time.
')

Recognizing colors and saving screenshots

To determine the color of a pixel by its coordinates, AutoIt has a PixelGetColor function. But as practice has shown, the measurement of only 90 pixels takes a half second, which, of course, is not very good. But in fairness it must be said that a bot written using this function gained 400-600 thousand points, and this is more than a person can gain, even with great skill.
The forums found a method to save the current state of the monitor in Bitmap using WinAPI. By the way, this bitmap, if necessary (for example, for debug), can be saved into a file by the function _ScreenCapture. Next, we look at the colors of 90 pixels located along the lattice and build a table of color squares on them.

1. Func _GetField ( ByRef $ aiField ) ; getting an array of field colors
2. ; getting a bitmap of a screen using WinAPI
3. Local $ hWnd = WinGetHandle ( "Google+ Games - Google Chrome" )
4. Local $ Size = WinGetClientSize ( $ hWnd )
5. Local $ hDC = _WinAPI_GetDC ( $ hWnd )
6. Local $ hMemDC = _WinAPI_CreateCompatibleDC ( $ hDC )
7. Local $ hBitmap = _WinAPI_CreateCompatibleBitmap ( $ hDC , $ Size [ 0 ] , $ Size [ 1 ] )
8. Local $ hSv = _WinAPI_SelectObject ( $ hMemDC , $ hBitmap )
9. _WinAPI_BitBlt ( $ hMemDC , 0 , 0 , $ Size [ 0 ] , $ Size [ 1 ] , $ hDC , 0 , 0 , $ SRCCOPY )
10. _WinAPI_SelectObject ( $ hMemDC , $ hSv )
11. _WinAPI_DeleteDC ( $ hMemDC )
12. _WinAPI_ReleaseDC ( $ hWnd , $ hDC )
13. Local $ L = $ Size [ 0 ] * $ Size [ 1 ]
14. Local $ tBits = DllStructCreate ( 'dword [' & $ L & ']' )
15. _WinAPI_GetBitmapBits ( $ hBitmap , 4 * $ L , DllStructGetPtr ( $ tBits ) )
16. ; cell color detection
17. For $ iCol = 0 To $ iNumCols - 1
18. For $ iRow = $ iNumRows - 1 to 0 Step - 1
19. ; square color measurement
20. $ iX = $ iCornerX + ( $ iCol * 40 ) + $ iDeltaX
21. $ iY = $ iCornerY + ( $ iRow * 40 ) + $ iDeltaY
22. $ iPixelColor = Mod ( DllStructGetData ( $ tBits , 1 , $ iY * $ Size [ 0 ] + $ iX ) , 0x1000000 )
23. $ aiField [ $ iRow ] [ $ iCol ] = _GetCheckColor ( $ iPixelColor )
24. Next
25. Next
26. ; data deletion to avoid memory leaks
27. _WinAPI_DeleteObject ( $ hBitmap )
28. _WinAPI_DeleteObject ( $ hMemDC )
29. _WinAPI_DeleteObject ( $ tBits )
30. Endfunc

Here it is worth making a reservation, why the measurement occurs at only 1 point. This method was tried by me in the first place, and remained in the final version. Between these two moments a rather large number of alternative methods were tried, among which were: measuring 64 points on each square (grid 8 by 8) and various averaging of the obtained values, random selection of coordinates for measuring, storing the history of several recent measurements for better accuracy ... But they all turned out to be less accurate or convenient than the very first method.
It is possible that since I am very far from the topic of image recognition, I do not know anything simple that can help me in this matter. In this case, I will be glad to any suggestions. =)

Single-color area detection from the color table

Well, finally, it remains to find a suitable place and click there. To do this, we go around the field from the bottom up (because everything falls down, which means that the bottom is less empty than the top), and we check monochrome parts. I did this using a non-recursive depth-first search ( DFS ) algorithm. In short, the essence is this: we put the starting cell on the stack, and then, until the stack is empty, we pull the current cell out of it and go around its neighbors, if we match the color, we put it on the stack. Well, what to say, the code is clearer. =)

1. Func _DfsAreaSize ( ByRef $ aiField , $ iStartX , $ iStartY ) ; non-recursive one-color region size search algorithm
2. ; depth search method
3. Local $ aiResult [ $ iNumCols * $ iNumRows ] [ 2 ] ; cell list
4. Local $ iResultSize = 0
5. Local $ afMap [ $ iNumRows ] [ $ iNumCols ] ; flags of transcendence
6. For $ iRow = 0 to $ iNumRows - 1
7. For $ iCol = 0 to $ iNumCols - 1
8. $ afMap [ $ iRow ] [ $ iCol ] = False
9. Next
10. Next
11. $ afMap [ $ iStartX ] [ $ iStartY ] = True
12. Local $ aiStack [ $ iNumRows * $ iNumCols ] [ 2 ] ; active stack
13. Local $ iStackSize = 1
14. $ aiStack [ 0 ] [ 0 ] = $ iStartX
15. $ aiStack [ 0 ] [ 1 ] = $ iStartY
16. While $ iStackSize > 0
17. $ iStackSize - = 1
18. $ iX = $ aiStack [ $ iStackSize ] [ 0 ]
19. $ iY = $ aiStack [ $ iStackSize ] [ 1 ]
20. $ aiResult [ $ iResultSize ] [ 0 ] = $ iX
21. $ aiResult [ $ iResultSize ] [ 1 ] = $ iY
22. $ iResultSize + = 1
23. For $ iDirection = 0 to 3 ; search 4 adjacent cells
24. Local $ iNewX = $ iX
25. Local $ iNewY = $ iY
26. Switch $ iDirection
27. Case 0
28. $ iNewY + = 1
29. Case 1
30. $ iNewY - = 1
31. Case 2
32. $ iNewX + = 1
33. Case 3
34. $ iNewX - = 1
35. End switch
36. If ( $ iNewX > = 0 And $ iNewX < $ iNumRows And _
37. $ iNewY > = 0 And $ iNewY < $ iNumCols And _
38. Not ( $ afMap [ $ iNewX ] [ $ iNewY ] ) And $ aiField [ $ iNewX ] [ $ iNewY ] = $ aiField [ $ iStartX ] [ $ iStartY ] )
39. $ afMap [ $ iNewX ] [ $ iNewY ] = True
40. $ aiStack [ $ iStackSize ] [ 0 ] = $ iNewX
41. $ aiStack [ $ iStackSize ] [ 1 ] = $ iNewY
42. $ iStackSize + = 1
43. Endif
44. Next
45. Wend
46. Return $ iResultSize
47. Endfunc

Optimization

Optimization 1. Almaziki

Written above was enough to get a million. But I wanted more. The biggest drawback of the above algorithm was, perhaps, the inability to determine diamonds. Therefore, at the end of the minute, the field looked like this:

Meanwhile, diamonds are a very useful thing, because while the fireball falls, the timer stops and the squares fall. So the gaps are filled, and there will be fewer errors.
To determine diamonds, to begin with, we had to play with the coordinates of the measurements, so that the colored cells were determined correctly, and the diamonds did not fall under any of their colors. After that, we create an array of $ aiDiams of size 3 (we will check only the bottom 3 lines, because all diamonds will fall there sooner or later) * width (in our case - 10). At each measurement, we look through the bottom 3 lines, and if the cell is defined, then reset the corresponding place in $ aiDiams, otherwise we increment it. Thus, for cells with diamonds, the values ​​will be high. With the accumulation of a certain threshold, we click.

1. For $ iRow = $ iNumRows - 1 to $ iNumRows - 3 Step - 1
2. For $ iCol = 0 to $ iNumCols - 1
3. If $ aiField [ $ iRow ] [ $ iCol ] <> 0 Then
4. $ aiDiams [ $ iRow ] [ $ iCol ] = 0
5. Else
6. $ aiDiams [ $ iRow ] [ $ iCol ] + = 1
7. If $ aiDiams [ $ iRow ] [ $ iCol ] > 15 Then
8. MouseClick ( "Left" , $ iCornerX + 30 + ( $ iCol * 40 ) , $ iCornerY + 10 + ( $ iRow * 40 ) , 1 , $ iMouseSpeed )
9. $ aiDiams [ $ iRow ] [ $ iCol ] = 0
10. Sleep ( 500 )
11. Return 0
12. Endif
13. Endif
14. Next
15. Next

Optimization 2. Over Explosion

Here it is necessary to explain why it is very important to reduce the number of errors, and why there is a 1/10 second delay in my script between adjacent screenshots. The fact is that when the field lights up and the cells start to explode, the number of points increases many times. But if you make too many mistakes, the field stops lighting up. Therefore, the minimization of errors is no less important part than the optimization of recognition time (and taking into account the time margin, the only important one).
Despite a 1/10 second delay between adjacent screenshots, some cells still do not have time to fall, and are not determined in their places. To reduce their number, an explosion test was introduced. When the explosion in the box appears a halo of almost pure white color (#fffefc to be exact), and it is easy to determine. All cells above the explosion, without further ado, can be stamped as indefinite.

Optimization 3. Last Clicked Area

Protection against a repeated error, in the effectiveness of which I am not sure. The fact is that in the game itself, if an error occurs, the cell becomes gray, and the gray color is determined by the algorithm as undefined (the tautology turned out =)). But this check can’t be made worse, so let it live.
The bottom line is that with each click we save the area we click on, and with the next click we don’t touch it.

Total

After all of the above, my record has become something like this:

I really wanted 2 million, but 4 days of attempts, a couple of thousand lines of experimental code (with self-logging and saving screenshots), careful smoking of logs and checking with screenshots did not give any results. = (
Link to github repository: github.com/EvilTosha/DiamondDash

Instead of postscript. A couple of words about AutoIt

I was very surprised that this language is almost not covered in Habré. Actually, the desire to correct this injustice and prompted to write this topic.
The language at the same time knows quite a lot, and has an amazing ease of learning. A couple of hours after I learned about its existence, I already had all the knowledge necessary to write this macro.
With AutoIt, you can automate almost any routine action: saving a screenshot, installing the program (if you need to install on many computers), multiple login somewhere ... You can compile into an exe-file, connect DLLs.
But something I, as an evangelist, spoke. =)

UPD Video work.


Thank you for your attention, I will be glad to any comments.