Предыстория
Всем доброго времени суток. По профессии я web-программист. Честно говоря, web-программирование для меня скорее хобби, которое приносит мне доход. Другим моим хобби являются городские экстремальные игры Encounter.
Если вкратце, то суть в том, что необходимо зайти на сайт игры, получить задание, в котором зашифровано место в городе, приехать на это место и решить загадку оставленную там авторами игры. После решения необходимо ввести ответ на сайте и получить следующее задание. Я как играю в игры, так и организовываю их.
Однажды, блуждая по Интернету, я наткнулся на флеш-игру «Водопровод».
Немного поиграв в неё, я решил сделать эту игру заданием на одной из предстоящих игр.
Суть идеи
Не буду рассказывать здесь о тонкостях работы движка Encounter, ибо это, как говорится, совсем другая история. Скажу только, что провести игру можно, не обладая знаниями в области программирования. Но при умении программировать на JavaScript можно реализовать самые необычные задумки.
Изначально перед игроками была пустая сетка:
По мере нахождения кодов (они были прописаны маркером на локации) и их вводе на сайте, сетка заполнялась сегментами труб:
Чтобы перейти на следующий уровень необходимо было открыть как можно больше сегментов, собрать из них водопровод и ввести в движок последовательность букв, расположенных во всех сегментах от начало до конца водопровода.
Код для перехода на следующий уровень: AKEZFDMIMQOYGBRZOGJTCSJAUODVYW.
Изначально всё казалось довольно таки простым в плане реализации. Проблемы начались, когда я случайно нашел ещё одно решение:
Код для перехода на следующий уровень: AKEZTASWYENBPKRRJAUODVYW.
Получается, сколько всего решений неизвестно, но надо найти их все и «сообщить» игровому движку все коды, чтобы при вводе любого из них, он перевел игроков на следующий уровень.
Выход из ситуации
В качестве инструментов сгодились PHP и MySQL. В базе MySQL хранится информация о каждом сегменте сетки, а скрипт на PHP проходит по всем возможным путям следования «воды» по трубе.
База данных
В таблице базы данных информация о сегментах хранится в следующем виде:
- y — номер строки
- x — номер столбца
- type — форма сегмента. Если значение поля 1, то сегмент представляет из себя «колено», если 0, то — «прямую».
- lit — буква в сегменте. Это поле было добавлено в самом конце, чтобы не составлять коды перехода на следующий уровень вручную, а доверить это скрипту.
Алгоритм
Для поиска всех возможных решений была написана рекурсивная функция tube.
<? function tube($x1, $y1, $x2, $y2, $str) { ... } tube(1, 0 , 1, 1, '|0-1|'); ?>
- $x1 и $y1 — координаты предыдущего сегмента
- $x2 и $y2 — координаты нового сегмента
- $str — строка, состоящая из координат всех сегментов водопровода, разделенных символом "|"
При первом вызове функции в нее передаются координаты «крана», координаты верхней левой клетки и строка, в которой изначально только координаты «крана» — ‘|0-1|’.
Функция должна выполнять следующие задачи:
- Проверять, не присутствует ли новый сегмент в водопроводе уже
if (strpos($str, '|'.$y2.'-'.$x2.'|')) return; else $str=$str.$y2.'-'.$x2.'|'; - Проверять, не уперся ли трубопровод в границу сетки
if ($x2==10 || $x2==0 || $y2==0) return; if ($y2==9 && $x2<9) $err = return; - Проверять, не дошел ли водопровод до искомой клетки (в нашем случае координаты этой сетки 9-9) и, если решение найдено, выводить его
if ($y2==9 && $x2==9) $str.'<br>'; - Если водопровод не уперся в границу сетки и решение не найдено, функция должна определить какие сегменты могут быть следующими в водопроводе и вызывать саму себя для каждого из «возможных» сегментов.
На это пункте остановимся подробнее. Прежде всего необходимо узнать, какой тип у нового сегмента («колено» или «прямая»). Для этого обратимся к нашей базе данных:
$result=$dbh->query('SELECT type FROM tube WHERE (x='.$x2.') AND (y='.$y2.')'); $row = $result->fetch(PDO::FETCH_ASSOC);Если тип нового сегмента «колено», то в зависимости от того, откуда «пришел» водопровод, возможны следующие варианты развития событий:
- Вода пришла сверху или снизу, уйти может только влево или вправо.
- Вода пришла слева или справа, уйти может только вверх или вниз.
В коде это выглядит следующим образом:
if ($row['type']==1) { if ($y1!=$y2) { tube($x2, $y2, $x2-1, $y2, $str); tube($x2, $y2, $x2+1, $y2, $str); } if ($x1!=$x2) { tube($x2, $y2, $x2, $y2-1, $str); tube($x2, $y2, $x2, $y2+1, $str); } }Если тип нового сегмента не «колено» (то есть «прямая»), то опять же в зависимости от того, откуда «пришел» водопровод, возможны следующие варианты развития событий:
- Вода пришла сверху, уйти может только вниз.
- Вода пришла снизу, уйти может только вверх.
- Вода пришла слева, уйти может только вправо.
- Вода пришла справа, уйти может только влево.
Код:
else { if ($y1<$y2) tube($x2, $y2, $x2, $y2+1, $str); if ($y1>$y2) tube($x2, $y2, $x2, $y2-1, $str); if ($x1<$x2) tube($x2, $y2, $x2+1, $y2, $str); if ($x1>$x2) tube($x2, $y2, $x2-1, $y2, $str); }
Вот и всё. Осталось только дополнить функцию кодом, который при нахождении решения задачи будет составлять буквенный код для перехода на следующий уровень:
if ($y2==9 && $x2==9) { $mass = explode('|', $str); $answer = ''; for ($i=0; $i<count($mass)-1; $i++) { if ($mass[$i]!='' && $mass[$i]!='0-1' && $mass[$i]!='9-9') { $koor = explode('-', $mass[$i]); $result=$dbh->query('SELECT lit FROM tube WHERE (y='.$koor[0].') AND (x='.$koor[1].')'); $row = $result->fetch(PDO::FETCH_ASSOC); $answer=$answer.$row['lit']; } } echo $str.'<br>'.$answer.'<br>'; return; } И всё вместе:
function tube($x1, $y1, $x2, $y2, $str) { if (strpos($str, '|'.$y2.'-'.$x2.'|')) return; else $str=$str.$y2.'-'.$x2.'|'; if ($x2==10 || $x2==0 || $y2==0) return; if ($y2==9 && $x2<9) $err = return; if ($y2==9 && $x2==9) { $mass = explode('|', $str); $answer = ''; for ($i=0; $i<count($mass)-1; $i++) { if ($mass[$i]!='' && $mass[$i]!='0-1' && $mass[$i]!='9-9') { $koor = explode('-', $mass[$i]); $result=$dbh->query('SELECT lit FROM tube WHERE (y='.$koor[0].') AND (x='.$koor[1].')'); $row = $result->fetch(PDO::FETCH_ASSOC); $answer=$answer.$row['lit']; } } echo $str.'<br>'.$answer.'<br>'; return; } $result=$dbh->query('SELECT type FROM tube WHERE (x='.$x2.') AND (y='.$y2.')'); $row = $result->fetch(PDO::FETCH_ASSOC); if ($row['type']==1) { if ($y1!=$y2) { tube($x2, $y2, $x2-1, $y2, $str); tube($x2, $y2, $x2+1, $y2, $str); } if ($x1!=$x2) { tube($x2, $y2, $x2, $y2-1, $str); tube($x2, $y2, $x2, $y2+1, $str); } } else { if ($y1<$y2) tube($x2, $y2, $x2, $y2+1, $str); if ($y1>$y2) tube($x2, $y2, $x2, $y2-1, $str); if ($x1<$x2) tube($x2, $y2, $x2+1, $y2, $str); if ($x1>$x2) tube($x2, $y2, $x2-1, $y2, $str); } } tube(1, 0 , 1, 1, '|0-1|'); Результат работы скрипта (первые 5 из 39 решений задачи):
|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-2|5-1|6-1|7-1|7-2|7-3|8-3|8-4|8-5|8-6|7-6|6-6|6-7|5-7|5-6|4-6|4-7|4-8|5-8|5-9|6-9|7-9|7-8|8-8|8-9|9-9| AKEZFDMIMHYENQOUWIXBZIUAJSCZOGJTQYLVYW |0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-2|5-1|6-1|7-1|7-2|7-3|8-3|8-4|8-5|8-6|7-6|6-6|6-7|7-7|7-8|8-8|8-9|9-9| AKEZFDMIMHYENQOUWIXBZIUAJSDVYW |0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|2-6|2-7|1-7|1-8|1-9|2-9|3-9|3-8|3-7|4-7|5-7|5-6|6-6|6-7|7-7|7-8|8-8|8-9|9-9| AKEZFDMIMHYENBPKSRONHIGULAHGCZJSDVYW |0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|2-6|2-7|3-7|3-8|3-9|4-9|5-9|5-8|4-8|4-7|4-6|5-6|5-7|6-7|6-6|7-6|8-6|8-7|7-7|7-8|8-8|8-9|9-9| AKEZFDMIMHYENBPKSRONHALPQTJGOZCSJAUODVYW |0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|4-6|4-7|4-8|5-8|5-7|6-7|6-6|7-6|8-6|8-7|7-7|7-8|8-8|8-9|9-9| AKEZFDMIMHYENBPKSROGJTCSJAUODVYW Всем спасибо за внимание.
ссылка на оригинал статьи http://habrahabr.ru/post/158059/
Добавить комментарий