Мне, как и многим другим под новый год очень пришлась по душе Теплая, ламповая новогодняя игра, описанная здесь.
Но мне, как и многим другим, не удавалось достичь особых успехов в ней. Были жалобы на пропадающие призы (подтверждаю), проскальзывающее управление и просто лаги. Обычно я довольно равнодушен к таким вещам, но жесткий диссонанс между теплым и ламповым дизайном и кривой реализацией меня всерьез задел. К тому же, таблица рекордов там постоянно пополнялась, а мне не удавалось достичь и половины.
В итоге я решил измерить кривизну либо своих рук, либо самой игры.
К тому же я недавно заново открыл для себя Matlab. И если уж я в Matlab'e занимаюсь управлением шаговыми двигателями через LPT, то почему бы не попробовать в нем еще более дикую идею написания бота для игры.
В комментариях к игре были сообщения о багах и их исправлениях, поэтому я со спокойной душой уехал в отпуск, надеясь на лучшее. Но после праздников ничего визуально не изменилось и я начал писать.
Идея была следующая:
— берем скриншот
— парсим его с помощью Image Processing Toolbox на предмет самой змейки и призов
— в нужный момент нажимаем на кнопки
Цель — максимально возможное количество очков, в идеале как-то так 
Только максимальное количество очков было бы равно произведению длины поля (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). Вероятно, если я запущу свой скрипт на рабочем сервере, будет быстрее.
Отсылать результаты на сервер со своим именем я не стал по морально-этическим соображениям.
От неконструктивной — далек тем более, поскольку лично с ними не знаком и мне в общем все равно.
Основной зуд — от несоответствия шикарной задумки весьма посредственной технической реализации. Хотели как лучше…
Дизайнерам и креативщикам все равно респект.
Я постигаю дзен и получаю удовольствие в свое свободное от менеджерства время.
Уже вырисовываются новые задачки, за которые я возьмусь с получением этого опыта.
Всем спасибо, было хорошо. С удовольствием приму любые замечания и рекомендации по улучшению качества кода.
Автор: k2m30
