Классическая задача при игре в лабиринте состоит в поиске прохода через него от входа до выхода. Путь-решение рисуется на карте лабиринта. В большинстве случаев лабиринты генерятся компьютерами, которые пользуются алгоритмами вроде поиска в глубину. Интересно, что решать лабиринт можно при помощи того же самого алгоритма.
Читаем лабиринт
Лабиринт можно представлять в разных форматах. Мы будем использовать SVG, поскольку в этом случае легко будет нарисовать решение поверх него.
Пример лабиринта в SVG:
<?xml version="1.0" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <svg width="112" height="96" version="1.1" xmlns="http://www.w3.org/2000/svg"> <rect width="112" height="96" fill="white" stroke="none" /> <title>5 by 4 orthogonal maze</title> <g fill="none" stroke="#000000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round"> <line x1="16" y1="16" x2="32" y2="16" /> <line x1="48" y1="16" x2="80" y2="16" /> <line x1="16" y1="80" x2="96" y2="80" /> <line x1="16" y1="16" x2="16" y2="80" /> <line x1="96" y1="16" x2="96" y2="80" /> <line x1="64" y1="16" x2="64" y2="32" /> <line x1="32" y1="32" x2="32" y2="48" /> <line x1="32" y1="32" x2="48" y2="32" /> <line x1="64" y1="32" x2="64" y2="48" /> <line x1="64" y1="32" x2="80" y2="32" /> <line x1="32" y1="48" x2="48" y2="48" /> <line x1="48" y1="48" x2="48" y2="64" /> <line x1="48" y1="48" x2="64" y2="48" /> <line x1="80" y1="48" x2="80" y2="64" /> <line x1="16" y1="64" x2="32" y2="64" /> <line x1="48" y1="64" x2="64" y2="64" /> <line x1="80" y1="64" x2="80" y2="80" /> </g> <g fill="black" stroke="none" stroke-width="1"> <text x="24" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">1</text> <text x="40" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">2</text> <text x="56" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">3</text> <text x="72" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">4</text> <text x="88" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">5</text> <text x="24" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">6</text> <text x="40" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">7</text> <text x="56" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">8</text> <text x="72" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">9</text> <text x="88" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">10</text> <text x="24" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">11</text> <text x="40" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">12</text> <text x="56" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">13</text> <text x="72" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">14</text> <text x="88" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">15</text> <text x="24" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">16</text> <text x="40" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">17</text> <text x="56" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">18</text> <text x="72" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">19</text> <text x="88" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">20</text> </g> </svg>
Файл мы будем обрабатывать двумя регулярками – одна для размера, а вторая – для поиска линий.
Размер:
m/<title>([0-9]*)\sby\s([0-9]*).*/g Линии:
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g Передадим данные в структуру, хранящую линии, которая будет выглядеть так:
{ "x1" => 0, "y1" => 0, "x2" => 0, "y2" => 0 } В svg-файле все данные основаны на множителях 16. Поэтому мы поделим x и y на 16, и получим увеличивающуюся последовательность.
Последнее, что мы сделаем с файлом – сохраним количество строк и столбцов. Это будет первая группа, полученная из регулярки.
Составляем список соседей
Последнее, что надо сделать перед запуском – составить список соседей. Это список всех элементов, соседних с нужным.
Вывод списка для указанного выше лабиринта:
1: 2 6 2: 0 3 1 3: 8 2 4: 5 5: 0 10 4 6: 1 11 7: 8 8: 3 7 9: 10 14 10: 5 15 9 11: 6 12 12: 17 11 13: 14 14: 9 19 13 15: 10 20 16: 17 17: 12 18 16 18: 19 17 19: 14 18 20: 15 Это не такая простая задача – нужно учесть линии «стен», которые отсекают от нас некоторых соседей. Для этого сначала найдём всех соседей. Те, до которых мы не можем добраться, пометим как -1. Другие будут обозначены положительными числами.
Затем мы переберём все линии и исключим тех соседей, с которыми у нас нет связи. И в конце мы вынесем список всех соседей в массив и выведем, как указано выше.
Получив списки соседей, мы начнём работать с алгоритмом.
Поиск в глубину
При наличии графа мы можем перебирать узлы, проходя через каждый узел. Разделим их на три категории:
— чёрные – найденные узлы
— серые – найденные, но не обработанные
— белые – не найденные
Затем, начав со случайного узла, обойдём всех его соседей. Каждого соседа отметим, как найденного, и повторим указанные шаги – пока не переберём все узлы.
В псевдокоде это выглядит так:
// найденные узлы discovered = array(); // инициализация белых узлов for (i = 0; i < discovered.size(); i++) discovered[i] = false; // старт endIdx = someEndIndex; start_node_idx = someStartNodeIndex; DFS(start_node_idx); // алгоритм void DFS(nodeIdx) { if (nodeIdx == endIdx) { // конец – отметить найденным и вернуть true discovered[nodeIdx] = true; return true; } else if (discovered[nodeIdx]) { // если уже найденный, вернуть false return false; } else { // иначе отметить найденным и обработать соседей discovered[nodeIdx] = true; foreach (neighbour i of nodeIdx) { result = DFS(i); if (result) { return true; // решение найдено, возвращаемся } } return false; // ничего не нашли, отбой } } Вывод решения
Это самый простой шаг. Находим центр каждой клетки (lefttop+rightbot2) и рисуем линию.
Код для всего вышеописанного
@ARGV = ("/PATH/05.svg"); undef $/; $input=(<>); $idx = 1; my $rows; my $cols; # ==================== # Считываем строчки # ==================== while ($input =~ m/<title>([0-9]*)\sby\s([0-9]*).*/g) { ($colCount, $rowCount) = ($1, $2); $rows = $rowCount; $cols = $colCount; print "Rows: $rows Cols: $cols\n"; } my @lines; while ($input =~ m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g) { ($x1,$y1,$x2,$y2) = ($1 / 16,$2 / 16,$3 / 16,$4 / 16); my %H = ( "x1" => $x1, "x2" => $x2, "y1" => $y1, "y2" => $y2 ); #print "#$idx: X1 : ".$H{"x1"}." X2: $x2 Y1: $y1 Y2: $y2\n"; $idx++; # Установим счётчики строк и столбцов #if ($y2 > $rows + 1) { $rows = $y2 - 1; } #if ($x2 > $cols + 1) { $cols = $x2 - 1; } # Добавляем к строкам push @lines, \%H; } # ================================================ # Поиск соседей # HASH[EL + 1][top|right|bot|left] = value; # ================================================ $elCount = $rows * $cols; # Получаем границы каждого элемента my @elements = (); my @corners = (); for (my $i = 0; $i < $elCount; $i++) { my %H = ( "top" => ($i + 1) - $cols, "right" => ($i + 1) + 1, "bot" => ($i + 1) + $cols, "left" => ($i + 1) - 1, "left_top_x" => 0, "left_top_y" => 0, "right_top_x" => 0, "right_top_y" => 0 ); # Строки и столбцы $row = int($i / $cols) + 1; $col = int($i % $cols) + 1; # Границы if ($H{"top"} > $elCount || $H{"top"} < 1) { $H{"top"} = 0; } if ($H{"right"} > ($row * $cols) || $H{"right"} < 1) { $H{"right"} = 0; } if ($H{"bot"} > $elCount || $H{"bot"} < 1) { $H{"bot"} = 0; } if ($H{"left"} < ((($row - 1)* $cols) + 1) || $H{"left"} < 1) { $H{"left"} = 0; } #print "Row: $row Col: $col\n"; $mult = 1; #print "El: #".($i + 1)." \n"; @corners[$i] = { "left_top_x" => (($col + 0) * $mult), # Левый верхний угол "left_top_y" => (($row + 0) * $mult), "right_top_x" => (($col + 1) * $mult), # Правый верхний угол "right_top_y" => (($row + 0) * $mult) }; #print "Top: (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 0) * $mult).")\n"; #print "Bot: (".(($col + 0) * $mult).",".(($row + 1) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n"; #print "Right: (".(($col + 1) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n"; #print "Left: (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 0) * $mult).",".(($row + 1) * $mult).")\n"; foreach (@lines) { #print "(".$_->{"x1"}.",".$_->{"y1"}.") -> (".$_->{"x2"}.",".$_->{"y2"}.")\n"; # сосед сверху if ($_->{"y1"} == (($row + 0) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) { # print "No Top Neighbour: ".($i + 1)."\n"; undef $H{"top"}; } # сосед снизу if ($_->{"y1"} == (($row + 1) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) { # print "No Bot Neighbour: ".($i + 1)."\n"; undef $H{"bot"}; } # сосед справа if ($_->{"x1"} == (($col + 1) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) { # print "No Right Neighbour: ".($i + 1)."\n"; undef $H{"right"}; } # сосед слева if ($_->{"x1"} == (($col + 0) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) { # print "No Left Neighbour: ".($i + 1)."\n"; undef $H{"left"}; } } # print ($i + 1); # print ":"; # print "\t".$H{"top"} if defined $H{"top"}; # print "\t".$H{"right"} if defined $H{"right"}; # print "\t".$H{"bot"} if defined $H{"bot"}; # print "\t".$H{"left"} if defined $H{"left"}; push @{$elements[$i]}, $H{"top"} if defined $H{"top"}; push @{$elements[$i]}, $H{"right"} if defined $H{"right"}; push @{$elements[$i]}, $H{"bot"} if defined $H{"bot"}; push @{$elements[$i]}, $H{"left"} if defined $H{"left"}; print "".($i + 1).":\t"; foreach (@{$elements[$i]}) { print $_."\t"; } print "\n"; } # ================================================ # Поиск пути # ================================================ my $start; my $end; my $newElement; my $oldElement; my @solution; # 1. Найдём начало и начнём print "Определяем точки старта и финиша \n"; for ($i = 0; $i < scalar @elements; $i++) { for ($j = 0; $j < scalar @{$elements[$i]}; $j++) { if ($start && @{$elements[$i]}[$j] == 0) { print "End = ".($i + 1)."\n"; $end = $i; last; } if (!$start && @{$elements[$i]}[$j] == 0) { print "Start = ".($i + 1)."\n"; $start = $i; } } } # 2. Вычисляем путь my $discovered = (); # устанавливаем discovered (найденные) в false (все узлы - белые) print "#Nodes: ".(scalar @elements)."\n\n"; for ($i = 0; $i < scalar @elements; $i++) { $discovered[$i] = 0; } # Обработаем соседей начального элемента DFS($start); sub DFS { my ($i) = @_; # Конец лабиринта – отметим все, как посещённые, и добавим решение if (($i + 1) == ($end + 1)) { # Если это решение – добавить в решения и вернуть true push @solution, ($i + 1); $discovered[$i] = 1; return 1; } elsif ($discovered[($_ - 1)] == 1) { # уже посещали - вернуть false return 0; } else { # иначе обработать #print "Node: ".($i + 1)."\n"; $discovered[$i] = 1; # Обработка всех соседей # Если получим true, надо добавить в решение foreach (@{$elements[$i]}) { #print "Neighbour: ".($_)."\n"; # Если сосед 0, вернуть false – это начало или конец! if ($_ != 0) { $result = DFS($_ - 1); if ($result == 1) { push @solution, $_; return 1; } } } # Ничего не возвращаем return 0; } } # Добавить в решения push @solution, ($start + 1); # =============================================================== # Вывод # Рисование линии на основе solutionStack # =============================================================== print "\nStack: "; foreach (@solution) { print "$_ "; } print "\n"; print "<g fill=\"none\" stroke=\"#FF0000\" stroke-width=\"3\" stroke-linecap=\"round\" stroke-linejoin=\"round\">"; for ($i = 0; $i < scalar @solution; $i++) { $x = ((($corners[$solution[$i] - 1]{"right_top_x"} + $corners[$solution[$i] - 1]{"left_top_x"}) / 2) * 16); $y = ((($corners[$solution[$i] - 1]{"right_top_y"} + $corners[$solution[$i] - 1]{"left_top_y"}) / 2) * 16) + 8; if (($i + 1) < scalar @solution) { $x2 = ((($corners[$solution[$i + 1] - 1]{"right_top_x"} + $corners[$solution[$i + 1] - 1]{"left_top_x"}) / 2) * 16); $y2 = ((($corners[$solution[$i + 1] - 1]{"right_top_y"} + $corners[$solution[$i + 1] - 1]{"left_top_y"}) / 2) * 16) + 8; } print "<line x1=\"$x\" y1=\"$y\" x2=\"$x2\" y2=\"$y2\" />\n"; } print "</g>\n"; # # print "Found Solution!";
Выведенное решение необходимо будет добавить в svg-файл:
<g fill="none" stroke="#FF0000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round"><line x1="88" y1="24" x2="88" y2="24" /> <line x1="88" y1="24" x2="88" y2="40" /> <line x1="88" y1="40" x2="72" y2="40" /> <line x1="72" y1="40" x2="72" y2="56" /> <line x1="72" y1="56" x2="72" y2="72" /> <line x1="72" y1="72" x2="56" y2="72" /> <line x1="56" y1="72" x2="40" y2="72" /> <line x1="40" y1="72" x2="40" y2="56" /> <line x1="40" y1="56" x2="24" y2="56" /> <line x1="24" y1="56" x2="24" y2="40" /> <line x1="24" y1="40" x2="24" y2="24" /> <line x1="24" y1="24" x2="40" y2="24" /> <line x1="40" y1="24" x2="40" y2="24" /> </g> 
ссылка на оригинал статьи http://habrahabr.ru/post/257251/
Добавить комментарий