Классическая задача при игре в лабиринте состоит в поиске прохода через него от входа до выхода. Путь-решение рисуется на карте лабиринта. В большинстве случаев лабиринты генерятся компьютерами, которые пользуются алгоритмами вроде поиска в глубину. Интересно, что решать лабиринт можно при помощи того же самого алгоритма.
Лабиринт можно представлять в разных форматах. Мы будем использовать SVG, поскольку в этом случае легко будет нарисовать решение поверх него.
Файл мы будем обрабатывать двумя регулярками – одна для размера, а вторая – для поиска линий.
Размер:
Линии:
Передадим данные в структуру, хранящую линии, которая будет выглядеть так:
В svg-файле все данные основаны на множителях 16. Поэтому мы поделим x и y на 16, и получим увеличивающуюся последовательность.
Последнее, что мы сделаем с файлом – сохраним количество строк и столбцов. Это будет первая группа, полученная из регулярки.
Последнее, что надо сделать перед запуском – составить список соседей. Это список всех элементов, соседних с нужным.
Вывод списка для указанного выше лабиринта:
Это не такая простая задача – нужно учесть линии «стен», которые отсекают от нас некоторых соседей. Для этого сначала найдём всех соседей. Те, до которых мы не можем добраться, пометим как -1. Другие будут обозначены положительными числами.
Затем мы переберём все линии и исключим тех соседей, с которыми у нас нет связи. И в конце мы вынесем список всех соседей в массив и выведем, как указано выше.
Получив списки соседей, мы начнём работать с алгоритмом.
При наличии графа мы можем перебирать узлы, проходя через каждый узел. Разделим их на три категории:
— чёрные – найденные узлы
— серые – найденные, но не обработанные
— белые – не найденные
Затем, начав со случайного узла, обойдём всех его соседей. Каждого соседа отметим, как найденного, и повторим указанные шаги – пока не переберём все узлы.
В псевдокоде это выглядит так:
Это самый простой шаг. Находим центр каждой клетки (lefttop+rightbot2) и рисуем линию.
Выведенное решение необходимо будет добавить в svg-файл:
Читаем лабиринт
Лабиринт можно представлять в разных форматах. Мы будем использовать 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>
Комментарии (6)
Googolplex
05.05.2015 13:16SVG
регулярками
stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454
Поаккуратнее с этим!
andreishe
Поиск в глубину для поиска выхода из лабиринта, мягко говоря, не лучший выбор. Выход-то он, конечно, найдет, но вот длина пути может оказаться далека от оптимальной.
И «парсинг» XML регулярками затея тоже довольно сомнительная.
mickvav
И условие остановки вида 'не осталось нетронутых узлов' хуже в общем случае чем 'нет больше нетронутых соседей'.
Jabher
а разве перл придумали не для того чтобы решать лабиринты в xml регулярками?
andreishe
awk, только awk. Выдумали тут перл какой-то.