Существует не слишком широко известная браузерная игра. Игровой процесс в ней очень простой и монотонный, что способствует появлению ботов. Для борьбы с ними в игру введена капча, время от времени вылезающая во время боя. На угадывание даётся 50 секунд, если угадать за 20, то дадут дополнительный бонус. Капч два вида: «Угадай пони» и «Пройди лабиринтик». С угадыванием пони проблем у меня обычно не возникало, а вот пройти лабиринт за 20 секунд — задача не всегда тривиальная. И я задумался, а нельзя ли написать Userscript, который бы самостоятельно проходил лабиринт и сообщал мне правильный ответ…
Первое, с чего следует начать — сбор информации. Вызываем появление лабиринта, лезем в исходный код, и смотрим, что там и как. Там мы находим вставленное изображение, и узнаём два момента: во-первых, изображение находится на том же домене, что и сама игрушка. Это упрощает работу с canvas. Во-вторых, оно находится в форме с id=«riddleform», в которой является первым изображением. В той же форме находится другое изображение.
Оговорка: в скрипте используется jQuery. Кидаться сапогами необязательно; я знаю, что подключать jQuery для того, чтобы вытащить одно изображение — не самое хорошее его применение. Дело в том, что этот скрипт планировался как часть другого, в котором jQuery уже использовалась.
Начинаем писать код
$('#riddleform img').load(function(){//пытаться что-то сделать до загрузки изображения нежелательно
if (this.src == "http://ehgt.org/v/battle/answer.png") return;//Здесь мы останавливаемся, если наткнулись не на то изображение
var rmimg = $('#riddleform img')[0];
var canvas = document.createElement("canvas");
canvas.width = rmimg.width;
canvas.height = rmimg.height;
var ctx = canvas.getContext("2d");
ctx.drawImage (rmimg, 0, 0);
var data = ctx.getImageData(0, 0, canvas.width, canvas.height);
});
В результате у нас получилась переменная data, в которую загружено изображение. Останавливаемся. Начинаем собирать изображения лабиринтов и сохранять их.
Все изображения имеют адрес вида «hentaiverse.org/riddlemaster.php?uid=[тут айдишник пользователя, одинаковый для всех изображений]&v=[тут, судя по всему, md5 хеш]». Например, «hentaiverse.org/riddlemaster.php?uid=123456&v=834a6b57de2d4e6d777478d7c2803d664293e7ec».
Собрав около десяти картинок, открываем их и начинаем их рассматривать.
(Изображения уменьшены)
Итак, изображение зашумлено, на нём могут проходить или не проходить светлый треугольник, который занимает левый нижний угол, и тёмный треугольник, который занимает левый верхний угол. Могут присутствовать оба. Может не быть ни одного. Вход и выходы всегда в одном и том же месте. Все изображения имеют одинаковый размер (615x615), и все они в формате jpg.
Куча больших изображений статью не украсит, поэтому я просто поставлю ссылки.
habrastorage.org/storage2/bfe/dcc/6a0/bfedcc6a0dc3b80e44d372a4b6660411.jpg
habrastorage.org/storage2/5c1/b6e/7c3/5c1b6e7c3fb4db6e547b95ecf0d5d81c.jpg
habrastorage.org/storage2/e85/6bc/c1e/e856bcc1ee6542acc66ab03601901eff.jpg
habrastorage.org/storage2/48d/535/62e/48d53562e8edb7d787419a726a5fea77.jpg
habrastorage.org/storage2/001/c2e/d34/001c2ed34a22d82fd467c3fcd36993e7.jpg
habrastorage.org/storage2/eca/80a/75a/eca80a75a60b41498f3d847afc207e71.jpg
Дальше — интереснее. Легко заметить, что шум на всех изображениях одинаковый. Далее, хотя цвета «стен» и отличаются от изображения к изображению, цвет «дорожек» всегда одинаковый. Если же приглядется внимательнее, то станет ясно, что большая часть клеток одинаковы на всех лабиринтах.
Чёрными квадратами обозначены клетки, которые всегда проходимы. Красной точкой обозначена центральная клетка. Клетки, находящиеся между чёрными точками по диагонали, всегда заняты. Они для нас неинтересны. Нам нужно выяснить, свободны или заняты клетки, находящиеся на тех же горизонталях и вертикалях, что и чёрные точки.
Первая мысль, которая приходит в голову — «Шум одинаковый, цвет клетки тоже. Мы можем просто взять любой пиксель в клетке и посмотреть на его цвет». Однако, это не работает. Более детальное изучение показывает, что шум не совсем одинаковый. Кроме того, для каждой клетки пришлось бы выбрать пиксель, выяснить, каких он может быть цветов, учесть треугольники; короче: возни много.
Всего в лабиринте клеток 37x37. Создадим массив, в который мы этот лабиринт загрузим.
var clear = [];
for (var tmp=0; tmp<38; ++tmp)
clear[tmp] = [];
for (var r=1; r<38;++r){
for (var t=1; t<38; ++t){
if ((r%2 == 1) && (t%2 == 1)){clear[r][t] = true;continue;}
if ((r%2 == 0) && (t%2 == 0)){clear[r][t] = false;continue;}
}
}
Осталось придумать, как отличить пустые клетки от занятых. Если мы не можем выбирать по одному пикселю, то выберем по всем: сложим и поделим. Размажем клетки, проще говоря. Снова приглядимся повнимательнее. Клетки имеют размер 15x15 пикселей.
var sum = [0,0,0]; var amount = 0;//сумма цветов и количество просмотренных пикселей
for (var j=t*15; j<t*15+15; ++j){
for (var k=r*15; k<r*15+15; ++k){
sum[0] += data.data[getrdata(j, k)];//getrdata передаёт номер элемента в массиве, в котором
sum[1] += data.data[getrdata(j, k)+1];//записан красный цвет ячейки с заданными координатами,
sum[2] += data.data[getrdata(j, k)+2];//а синий и зелёный получем, добавив 1 и 2.
++amount;
}
}
sum[0] = Math.round(sum[0]/amount);
sum[1] = Math.round(sum[1]/amount);
sum[2] = Math.round(sum[2]/amount);
Осталось выяснить, какие цвета соответствуют пустым клеткам. Их четыре вида: чистые, светлые, тёмные, и «светло-тёмные», в зависимости от того, появились ли треугольники, о которых я говорил в начале. К счастью, нет клеток, которые находилились бы на границе этих треугольников. Коротко: цвета были получены при помощи создания дива, в который скидывались все цвета клеток. Потом оттуда были выбраны необходимые. Какое-то время скрипт подгонялся, когда он натыкался на непроходимый лабиринт.
if ( (sum[0]>190)&&(sum[0]<202) && (sum[1]>170)&&(sum[1]<183) && (sum[2]>130)&&(sum[2]<145) ){//normal
clear[r][t] = true;
}else if ( (sum[0]>148)&&(sum[0]<160) && (sum[1]>135)&&(sum[1]<143) && (sum[2]>103)&&(sum[2]<114) ){//dark
clear[r][t] = true;
}else if ( (sum[0]>203)&&(sum[0]<213) && (sum[1]>190)&&(sum[1]<197) && (sum[2]>157)&&(sum[2]<169) ){//light
clear[r][t] = true;
}else if ( (sum[0]>171)&&(sum[0]<180) && (sum[1]>158)&&(sum[1]<167) && (sum[2]>133)&&(sum[2]<143) ){//grey
clear[r][t] = true;
}else{
clear[r][t] = false;
}
Осталась мелочь: пройти полученный лабиринт. Это сделает рекурсивный алгоритм.
function makeway(x,y,data){
if ((y == 11)&&(x == 37)) return 'A';//это клетка напротив выхода A
if ((y == 27)&&(x == 37)) return 'B';//и так далее
if ((y == 37)&&(x == 11)) return 'D';
if ((y == 37)&&(x == 27)) return 'C';
var t = '';
if (x<37 && data [x+1][y]) {data [x+1][y] = false; t = makeway (x+2, y, data);}//тыкаемся в одну сторону...
if (t != '') return t;
if (x>1 && data [x-1][y]) {data [x-1][y] = false; t = makeway (x-2, y, data);}//в другую...
if (t != '') return t;
if (y<37 && data [x][y+1]) {data [x][y+1] = false; t = makeway (x, y+2, data);}
if (t != '') return t;
if (y>1 && data [x][y-1]) {data [x][y-1] = false; t = makeway (x, y-2, data);}
if (t != '') return t;
return '';//дотыкались до тупика
}
После чего остаётся лишь создать в документе div и вызвать
answerdiv.innerHTML = makeway (1, 1, clear);Обратите внимание на то, что мы «прыгаем через клетку». Если свободна соседняя клетка, то мы прыгаем через неё, потому что точно знаем, что та клетка свободна: это одна из клеток с чёрными точками.
Всё это замечательно, но такой код не слишком удобно дебажить. Вот он сломался, не нашёл прохода, потому что не распознал клетку, как свободную. Вопрос: где же он сломался? Расширим скрипт. Добавим в аргументы функции makeway переменную ctx, а в начало…
ctx.fillStyle = "rgb(0,0,0)";
ctx.fillRect (y*15,x*15,15,15);
… И закрасим пройдённую клетку чёрным. В код скрипта добавим…
$('body')[0].appendChild(canvas);
… А в цикл, сразу после проверки на свободность клетки…
ctx.fillStyle = "rgb(" + sum[0] + ',' + sum[1] + ',' + sum[2] + ")";
ctx.fillRect (t*15,r*15,15,15);
Теперь в документе появится этот самый canvas, который может выглядеть, например, так:
Остаётся лишь открыть изображение в пейнте, ткнуть пипеткой в непроходимую клетку, и посмотреть её цвет.
И в заключение, оставляю ссылку на архив с несколькими изображениями и html-файл, в который можно вставить нужное изображение и посмотреть на результат, а также несколько рабочих файлов: dl.dropbox.com/u/42049925/rm.zip
Автор: Kelenius
