Pull to refresh

Matlab-бот, тёплый ламповый

Reading time 8 min
Views 6.3K
Мне, как и многим другим под новый год очень пришлась по душе Теплая, ламповая новогодняя игра, описанная здесь.

Но мне, как и многим другим, не удавалось достичь особых успехов в ней. Были жалобы на пропадающие призы (подтверждаю), проскальзывающее управление и просто лаги. Обычно я довольно равнодушен к таким вещам, но жесткий диссонанс между теплым и ламповым дизайном и кривой реализацией меня всерьез задел. К тому же, таблица рекордов там постоянно пополнялась, а мне не удавалось достичь и половины.

В итоге я решил измерить кривизну либо своих рук, либо самой игры.

К тому же я недавно заново открыл для себя Matlab. И если уж я в Matlab'e занимаюсь управлением шаговыми двигателями через LPT, то почему бы не попробовать в нем еще более дикую идею написания бота для игры.


В комментариях к игре были сообщения о багах и их исправлениях, поэтому я со спокойной душой уехал в отпуск, надеясь на лучшее. Но после праздников ничего визуально не изменилось и я начал писать.

Идея была следующая:
— берем скриншот
— парсим его с помощью Image Processing Toolbox на предмет самой змейки и призов
— в нужный момент нажимаем на кнопки

image

Цель — максимально возможное количество очков, в идеале как-то так image
Только максимальное количество очков было бы равно произведению длины поля (19) на его высоту (14) минус два начальных квадратика. Т.е. 14*19 — 2 = 264.

Взаимодействие матлаба с окружающим миром довольно скудное и реализовано через java.awt.Robot. Все просто: createScreenCapture для собственно скриншота, keyPress/keyRelease — имитируем клавиатуру. Можно еще и подвигать мышкой, но необязательно. Найти конкретное окно и работать с ним вроде как нельзя, поэтому будем играться так.

Никаких алгоритмов по оптимизации пути я писать не умею, и цель такая не стоит. Поэтому просто прохожу все поле целиком. Брутфорс, короче.

С этим вроде все понятно, но я изображениями я никогда не работал, поэтому напряг Хабр. Благо статей по матлабу немного, и уже на второй странице поиска нашел вот это: Детектирование округлостей на изображении средствами MATLAB

Все вроде понятно и нет причин не попробовать.

Чтобы не обрабатывать весь экран каждый раз (1440*900*4) = 1,2 МБ, буду искать собственно поле игры программными средствами. Искать координаты вручную как-то некошерно.

Итак:
%% 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); %обрезаем лишнее


Тем же методом (с небольшими отличиями) я нахожу красную кнопочку внутри поля и тыкаю в нее мышкой для начала.
Ищем красную кнопку
%% button detection and press
I = I (:, :, 1); %работаю только с красным каналом
...
se = strel('disk',10); 
I = imopen(I,se); %морфологическое открытие для удаления лишнего. так и не понял сути этого процесса с умным названием, но результат мне подходит
...
[B,L] = bwboundaries(I);
stats = regionprops(L,'Centroid', 'Area'); % в этот раз ищу центр наибольшего прямоугольника (красной кнопки)
...
coo = stats(m).Centroid;
robot.mouseMove(coo(1),coo(2)); %прицеливаюсь
robot.mousePress  (java.awt.event.InputEvent.BUTTON1_MASK); %нажимаю кнопку
robot.mouseRelease(java.awt.event.InputEvent.BUTTON1_MASK);


С этого момента начинается собственно игра после небольших тормозов. Чтобы не тупить вместе с ними, жду изменения картинки, регулярно сравнивая разницу изображений.
Тупим
%% waiting for begin
difference = 0;
while difference < 2000
    K = I;
    I = getScreenCaptureImageData(rect); 
    Diff = imabsdiff(I, K);
    difference = sum (Diff(:))/1000
    pause (.2);
end


Дальше я опять пошел в лоб.
Изначально я знаю размер змейки, методом подсчета площадей опять могу вычислить ее координаты и направление ее движения (вправо). Поскольку определить «голову» змеи нельзя — она вся одинаковая, то я решил сканировать изображение на предмет появления головы змеи в новом месте.

С учетом тормозов, в первый раз голова определяется в положениях от x,y от (8,5) до (11,5) и дальше я ее веду. По достижении границы экрана я ее поворачиваю в новом направлении.

Напомню, игровое поле имеет размер 19 на 14 блоков.

Про тормоза. Сам я пользую mac air 2012 и FF18 в качестве браузера. Примерно в 25-30% процентах случаев при повторной игре приходится начинать без призов, продолжать нельзя. Движение змейки визуально идет с разной скоростью даже на одном уровне и может лагать.
Пришлось качать хром. Там вроде получше: без призов игра начинается в 5% случаев, движение более плавное и на глаз проблем не видно. Загрузка процессора значительно меньше. Узнал, что в программе есть звук.

Вот мой основной цикл:
%Запускаем таймер
t = timer('StartDelay', 0.1, 'Period', X, 'TasksToExecute', k,'ExecutionMode', 'fixedRate');
t.TimerFcn = { @timer_callback};
start(t);
...

%обработчик я делаю nested функцией, чтобы не тратить время на создание новых переменных каждый раз и не передавать это все в параметрах
function timer_callback (obj, event)
    
%сканируем экран и вычисляем матрицу Р 19х14, состоящую из 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

Применив способ распознавания изображений, который отлично работает в статике, я не получил работающего скрипта — весь цикл на моем компьютере занимал примерно 0,8с (800 мс), в то время, как даже на начальном уровне змейка перемещается примерно каждые 0,2с (200 мс). Змейка регулярно встречалась со стенами.

Немного пошаманив с коэффициентами фильтров и входных параметров, я добился результата в 350мс.
Оставил только один канал для фильтров, 190 мс, пошло. Максимальный результат — 11 очков. «Ускоряется, змея..» — подумал, я и продолжил.

Переписал, убрал все циклы. Потом я убрал фильтры вообще, разбил получаемое изображение на 19х14 блоков (42х42 пикселя) и стал вычислять сумму пикселей каждого блока — 100мс, максимальный результат 35 очков.

Наверное дело в операционной системе, не realtime все-таки. Хотя замеры реального времени выполнения (команды tic и toc, а также profiler) не сильно отличаются от расчетных. Идем дальше.

Зачем считать сумму всех 42х42 пикселей в каждом блоке? Достаточно взять 20х20, отличить черное от белого и не спутать с призом. 70 мс, 52 очка.

Теперь сам скриншот был максимальным куском, поэтому я переписал его так, чтобы работать только с одним каналом (Red), сократив объем обрабатываемой информации в четыре раза.
Функция скриншота до и после
%before
function imgData = getScreenCaptureImageData(positionRect)
    if isempty(positionRect) | all(positionRect==0) | positionRect(3)<=0 | positionRect(4)<=0  %#ok ML6
        imgData = [];
    else
        rect = java.awt.Rectangle(positionRect(1), positionRect(2), positionRect(3), positionRect(4));
        robot = java.awt.Robot;
        jImage = robot.createScreenCapture(rect);

        h = jImage.getHeight;
        w = jImage.getWidth;
        pixelsData = reshape(typecast(jImage.getData.getDataStorage, 'uint8'), 4, w, h);
        imgData = cat(3, ...
              transpose(reshape(pixelsData(3, :, :), w, h)), ...
              transpose(reshape(pixelsData(2, :, :), w, h)), ...
              transpose(reshape(pixelsData(1, :, :), w, h)));
    end

%-----------------------------------
%after
function imgData = getScreenCaptureImageData(positionRect)
    if isempty(positionRect) | all(positionRect==0) | positionRect(3)<=0 | positionRect(4)<=0  %#ok ML6
        imgData = [];
    else
        rect = java.awt.Rectangle(positionRect(1), positionRect(2), positionRect(3), positionRect(4));
        robot = java.awt.Robot;
        jImage = robot.createScreenCapture(rect);
        h = jImage.getHeight;
        w = jImage.getWidth;
        imgData = typecast(jImage.getData.getDataStorage, 'uint8');
        imgData = reshape (imgData(3:4:4*w*h), w, h)';
    end 


30мс гарантировано (на пиках), в среднем 25мс и 75 очков максимум. Вообще говоря, это была моя цель на момент начала работ, но к этому времени особо упорные (теперь я подозреваю, что это тоже боты) подняли планку до 116 очков. Так что идем дальше.

В принципе, стало уже понятно, что дело не в кривизне моих рук, поскольку гарантировано 33 раза в секунду алгоритм смотрел в экран и вовремя нажимал на кнопки. Но управление продолжало «проскальзывать», а уменьшение периода работы положительно сказывалось на результатах.

Дошло дело до грязных приемов. Выбрасываю суммирование вообще и смотрю только каждый 42-й пиксель по вертикали и горизонтали. Если больше определенного порога, то считаю, что змея здесь. Подбираю такое значение порога, чтобы не путать змею с призами. 25мс гарантировано и 87 очков. Только-только попадаю в тридцатку.

Опять скриншот — самый большой кусок времени. Ускорить его у меня уже не получается, но ведь можно скриншотить меньшую область! Бью поле пополам (с небольшим перекрытием) и смотрю только в ту половину, где находится голова. 22мс и 101 очко.

Где два, там и четыре. Беру четыре квадранта A, B, C, D. 17 мс гарантировано и 11 в среднем.
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 - порог срабатывания

Бинго! 131 очко.


Уже была мысль сканировать только края экрана и определять появление там змейки, чтобы выиграть еще милисекунду-другую, но все, пока хватит.
Во-первых, я уже первый.
Во-вторых, понятно, что максимума в 262 очка добиться невозможно из-за особенностей реализации программы.
В-третьих, задержки от операционной системы уже сравнимы с временем работы алгоритма (11мс в среднем, на пиках 17). Т.е. ОС дает погрешность в 6мс.
В-четвертых, моей основной цели — научиться работать с изображениями я тоже не достиг(ну).
В-пятых, временной результат очень аппаратно-зависим, и на моем домашнем компьютере с плюс-минус тем же железом работает в среднем в два раза медленнее (Win7x64). Вероятно, если я запущу свой скрипт на рабочем сервере, будет быстрее.

Отсылать результаты на сервер со своим именем я не стал по морально-этическим соображениям.
Дисклеймер
Я далек от конструктивной критики разработчиков программы, поскольку никогда не работал с HTML5 и вообще с веб-приложениями.
От неконструктивной — далек тем более, поскольку лично с ними не знаком и мне в общем все равно.
Основной зуд — от несоответствия шикарной задумки весьма посредственной технической реализации. Хотели как лучше…
Дизайнерам и креативщикам все равно респект.

Зачем?
Примерно затем же, зачем люди пишут иероглифы на асфальте водой, которые испаряются через минуту.
image

Я постигаю дзен и получаю удовольствие в свое свободное от менеджерства время.
Уже вырисовываются новые задачки, за которые я возьмусь с получением этого опыта.

Всем спасибо, было хорошо. С удовольствием приму любые замечания и рекомендации по улучшению качества кода.
Tags:
Hubs:
+27
Comments 11
Comments Comments 11

Articles