Matlab-bot, warm tube

Like many others for the new year, I really liked the warm, lamp New Year game described here .

But I, like many others, could not achieve much success in it. There were complaints about missing prizes (I confirm), slipping control and just lags. Usually I am rather indifferent to such things, but the hard dissonance between the warm and lamp design and the curve implementation seriously touched me. In addition, the table of records there is constantly replenished, but I could not reach half.

In the end, I decided to measure the curvature of either my hands or the game itself.
')
Besides, I recently rediscovered Matlab. And if I'm in Matlab'e do the management of stepper motors through LPT, then why not try in it an even wilder idea of ​​writing a bot for the game.


In the comments to the game there were reports of bugs and their corrections, so I went on vacation with a clear conscience, hoping for the best. But after the holidays, nothing visually changed and I started writing.

The idea was as follows:
- take a screenshot
- parse it using Image Processing Toolbox for the snake itself and prizes
- at the right time, click on the buttons



The goal - the maximum possible number of points, ideally somehow
Only the maximum number of points would be equal to the product of the field length (19) to its height (14) minus two initial squares. Those. 14 * 19 - 2 = 264.

The interaction of the matlab with the outside world is rather scanty and implemented via java.awt.Robot . It's simple: createScreenCapture for the actual screenshot, keyPress / keyRelease - simulate the keyboard. You can also move the mouse, but not necessarily. It seems impossible to find a specific window and work with it, so we will play like this.

I do not know how to write any algorithms for optimizing the path, and this goal is not worth it. So just going through the whole field. Bruteforce, in short.

With this, everything seems to be clear, but I have never worked with images, so I strained Habr. The benefit of the articles on the matlab is a bit, and already on the second page of the search I found this: Detection of roundness in the image using MATLAB

Everything seems clear and there is no reason not to try.

In order not to process the entire screen every time (1440 * 900 * 4) = 1.2 MB, I will search for the actual game field using software. Search for coordinates manually is somehow non-kosher.

So:

%% canvas detction robot = java.awt.Robot; %  scrSize = get(0,'ScreenSize'); %   pause (5); %,         I = getScreenCaptureImageData(scrSize); %  I = medfilt2(I, [5 5]); % ,      ,     I = edge(I,'canny', 0.15, 2); %  I = imfill(I, 'holes'); %  [B,L] = bwboundaries(I); stats = regionprops(L,'BoundingBox', 'Area'); %  ,     [n,m] = size (stats); for i=1:n %  ,  think vectorized     a(i) = stats (i).Area; end [n, m] = max (a); rect = stats(m).BoundingBox; %          I = imcrop(I, rect); %  

By the same method (with some differences) I find a red button inside the field and poke it with a mouse to begin with.

From this point on, the game itself begins after small brakes. In order not to blunt with them, I wait for the change of the picture, regularly comparing the difference of images.

Then I went to the forehead again.
Initially, I know the size of a snake, by calculating the area again I can calculate its coordinates and the direction of its movement (to the right). Since it is impossible to determine the "head" of a snake - it is all the same, I decided to scan the image for the appearance of a snake head in a new place.

Taking into account the brakes, for the first time the head is determined in positions from x, y from (8.5) to (11.5) and then I lead it. Upon reaching the border of the screen, I turn it in a new direction.

Let me remind you that the playing field has a size of 19 by 14 blocks.

About the brakes. I myself use mac air 2012 and FF18 as a browser. Approximately in 25-30% percent of cases when re-playing you have to start without a prize, you cannot continue. Snake movement visually goes at different speeds, even at the same level and can lag.
I had to download chrome. It seems to be better there: without prizes, the game starts in 5% of cases, the movement is smoother and there are no visible problems. CPU usage is significantly less. I learned that the program has sound.

Here is my main loop:

 %  t = timer('StartDelay', 0.1, 'Period', X, 'TasksToExecute', k,'ExecutionMode', 'fixedRate'); t.TimerFcn = { @timer_callback}; start(t); ... %   nested ,                  function timer_callback (obj, event) %      1914,   0  1.   -  . head (x,y) -   ... %% head detection, P is already detected switch direction case right if P ( head (1,2), head (1,1)+1) head (1,1) = head (1,1) + 1; end case left if P (head (1,2), head (1,1)-1) head (1,1) = head (1,1) - 1; end case up if P (head (1,2)-1, head (1,1)) head (1,2) = head (1,2) - 1; end case down if P (head (1,2)+1, head (1,1)) head (1,2) = head (1,2) + 1; end end %% new direction switch direction case right if head (1,1) == 19; direction = down; robot.keyPress (direction); robot.keyRelease (direction); end case left if (head (1,1) == 1) && (head (1,2)==14) direction = up; robot.keyPress (direction); robot.keyRelease (direction); elseif (head (1,1) == 2) && (head (1,2) < 14) direction = down; robot.keyPress (direction); robot.keyRelease (direction); end case up if (head (1,1) == 1) && (head(1,2) == 1) direction = right; robot.keyPress (direction); robot.keyRelease (direction); end case down if (rem(head (1,2), 2) == 0) && (head (1,1) == 19) direction = left; robot.keyPress (direction); robot.keyRelease (direction); end if (rem(head (1,2), 2) == 1) && (head (1,1) == 2) direction = right; robot.keyPress (direction); robot.keyRelease (direction); end end end 

Using the image recognition method, which works perfectly in statics, I did not get a working script - the whole cycle on my computer took about 0.8 s (800 ms), while even at the initial level the snake moves about every 0.2 s (200 ms) Snake met regularly with walls.

A little shuffling with the coefficients of filters and input parameters, I achieved a result of 350ms.
Left only one channel for filters, 190 ms, went. The maximum result is 11 points. "Accelerated, the snake .." - I thought, I continued.

Rewrote, removed all cycles. Then I removed the filters altogether, broke the resulting image into 19x14 blocks (42x42 pixels) and began to calculate the sum of the pixels of each block - 100ms, the maximum result of 35 points.

Probably it's in the operating system, not realtime after all. Although measurements of real-time execution (commands tic and toc, as well as profiler) are not very different from the calculated ones. Go ahead.

Why count the sum of all 42x42 pixels in each block? It is enough to take 20x20, to distinguish black from white and not to be confused with the prize. 70 ms, 52 points.

Now the screenshot itself was the maximum piece, so I rewrote it to work with only one channel (Red), reducing the amount of information processed four times.

30ms guaranteed (on peaks), an average of 25ms and a maximum of 75 points. Generally speaking, it was my goal at the time of the start of work, but by this time especially persistent (now I suspect that these are also bots) raised the bar to 116 points. So go ahead.

In principle, it has already become clear that the matter is not in the curvature of my hands, since the algorithm was guaranteed to look at the screen 33 times a second and hit the buttons in time. But management continued to “slip”, and a decrease in the period of work had a positive effect on the results.

It came to dirty tricks. I throw away summation in general and look only every 42nd pixel vertically and horizontally. If more than a certain threshold, then I believe that the snake is here. I select the threshold so as not to confuse the snake with the prizes. 25ms guaranteed and 87 points. Only just get into the thirty.

Again the screenshot is the biggest piece of time. I can no longer speed it up, but you can take a screenshot of a smaller area! I beat the field in half (with a small overlap) and look only at the half where the head is. 22ms and 101 points.

Where there are two, there are four. I take four quadrants A, B, C, D. 17 ms guaranteed and 11 on average.

 if (head (1,1) <=10) && (head(1,2) <=7) I (1:9*42, 1:11*42) = getScreenCaptureImageData(rectgA); elseif (head (1,1) >= 11) && (head(1,2) <=7) I (1:9*42, 8*42+1:end) = getScreenCaptureImageData(rectgB); elseif (head (1,1) <= 10) && (head(1,2) >=8) I (5*42+1:end, 1:11*42) = getScreenCaptureImageData(rectgC); elseif (head (1,1) >= 11) && (head(1,2) >=8) I (5*42+1:end, 8*42+1:end) = getScreenCaptureImageData(rectgD); end P = I (i,j) > 150; %i = 3:42:42*14; j = 1:42:42*19; 150 -   

Bingo! 131 points.


There was already a thought to scan only the edges of the screen and determine the appearance of a snake there in order to win another millisecond or two, but that's enough for now.
First, I am already the first.
Secondly, it is clear that a maximum of 262 points cannot be achieved due to the nature of the program implementation.
Thirdly, the delays from the operating system are already comparable with the running time of the algorithm (11ms on average, at peaks 17). Those. OS gives an error of 6ms.
Fourth, my main goal - to learn how to work with images, I also did not achieve (well).
Fifth, the time result is very hardware-dependent, and on my home computer with plus or minus the same hardware works on average two times slower (Win7x64). Probably, if I run my script on the production server, it will be faster.

I did not send the results to the server with my own name for moral and ethical reasons.


Thank you all, it was good. I am pleased to accept any comments and recommendations for improving the quality of the code.