Решение лабиринтов на Perl05.05.2015 12:18
Классическая задача при игре в лабиринте состоит в поиске прохода через него от входа до выхода. Путь-решение рисуется на карте лабиринта. В большинстве случаев лабиринты генерятся компьютерами, которые пользуются алгоритмами вроде поиска в глубину. Интересно, что решать лабиринт можно при помощи того же самого алгоритма.Читаем лабиринтЛабиринт можно представлять в разных форматах. Мы будем использовать SVG, поскольку в этом случае легко будет нарисовать решение поверх него.Пример лабиринта в SVG:
5 by 4 orthogonal maze
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Файл мы будем обрабатывать двумя регулярками — одна для размера, а вторая — для поиска линий.Размер:
m/
([0–9]*)\sby\s ([0–9]*).*/g
Линии: </p><p>
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g
Передадим данные в структуру, хранящую линии, которая будет выглядеть так: </p><p>
{
«x1» => 0,
«y1» => 0,
«x2» => 0,
«y2» => 0
}
В svg-файле все данные основаны на множителях 16. Поэтому мы поделим x и y на 16, и получим увеличивающуюся последовательность.</p>
<p>Последнее, что мы сделаем с файлом — сохраним количество строк и столбцов. Это будет первая группа, полученная из регулярки.</p><p>Составляем список соседей
Последнее, что надо сделать перед запуском — составить список соседей. Это список всех элементов, соседних с нужным.Вывод списка для указанного выше лабиринта: </p><p>
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. Другие будут обозначены положительными числами.</p>
<p>Затем мы переберём все линии и исключим тех соседей, с которыми у нас нет связи. И в конце мы вынесем список всех соседей в массив и выведем, как указано выше.</p>
<p>Получив списки соседей, мы начнём работать с алгоритмом.</p><p>Поиск в глубину
При наличии графа мы можем перебирать узлы, проходя через каждый узел. Разделим их на три категории: — чёрные — найденные узлы— серые — найденные, но не обработанные— белые — не найденные</p>
<p>Затем, начав со случайного узла, обойдём всех его соседей. Каждого соседа отметим, как найденного, и повторим указанные шаги — пока не переберём все узлы.</p>
<p>В псевдокоде это выглядит так: </p><p>
// найденные узлы
discovered = array (); </p>
<p>// инициализация белых узлов
for (i = 0; i < discovered.size(); i++)
discovered[i] = false;</p>
<p>// старт
endIdx = someEndIndex;
start_node_idx = someStartNodeIndex;
DFS (start_node_idx); </p>
<p>// алгоритм
void DFS (nodeIdx) {
if (nodeIdx == endIdx) {
// конец — отметить найденным и вернуть true
discovered[nodeIdx] = true; </p>
<p> return true;
} else if (discovered[nodeIdx]) {
// если уже найденный, вернуть false
return false;
} else {
// иначе отметить найденным и обработать соседей
discovered[nodeIdx] = true; </p>
<p> foreach (neighbour i of nodeIdx) {
result = DFS (i); </p>
<p> if (result) {
return true; // решение найдено, возвращаемся
}
}</p>
<p> return false; // ничего не нашли, отбой
}
}
Вывод решения
Это самый простой шаг. Находим центр каждой клетки (lefttop+rightbot2) и рисуем линию.Код для всего вышеописанного
@ARGV = (»/PATH/05.svg»); </p>
<p>undef $/; </p>
<p>$input=(<>); </p>
<p>$idx = 1; </p>
<p>my $rows;
my $cols; </p>
<p># ====================
# Считываем строчки
# ====================
while ($input =~ m/<title>([0–9]*)\sby\s ([0–9]*).*/g) {
($colCount, $rowCount) = ($1, $2); </p>
<p> $rows = $rowCount;
$cols = $colCount; </p>
<p> print «Rows: $rows Cols: $cols\n»;
}</p>
<p>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); </p>
<p> my %H = (
«x1» => $x1,
«x2» => $x2,
«y1» => $y1,
«y2» => $y2
); </p>
<p> #print »#$idx: X1:».$H{«x1»}.» X2: $x2 Y1: $y1 Y2: $y2\n»;
$idx++; </p>
<p> # Установим счётчики строк и столбцов
#if ($y2 > $rows + 1) { $rows = $y2 — 1; }
#if ($x2 > $cols + 1) { $cols = $x2 — 1; }</p>
<p> # Добавляем к строкам
push @lines, \%H;
}</p>
<p># ================================================
# Поиск соседей
# HASH[EL + 1][top|right|bot|left] = value;
# ================================================
$elCount = $rows * $cols; </p>
<p># Получаем границы каждого элемента
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
); </p>
<p> # Строки и столбцы
$row = int ($i / $cols) + 1;
$col = int ($i % $cols) + 1; </p>
<p> # Границы
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; }</p>
<p> #print «Row: $row Col: $col\n»; </p>
<p> $mult = 1;
#print «El: #».($i + 1).» \n»; </p>
<p> @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)
}; </p>
<p> #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»; </p>
<p> foreach (@lines) {
#print »(».$_→{«x1»}.»,».$_→{«y1»}.») → (».$_→{«x2»}.»,».$_→{«y2»}.»)\n»; </p>
<p> # сосед сверху
if ($_→{«y1»} == (($row + 0) * $mult) && (($col + 0) * $mult) >= $_→{«x1»} && (($col + 1) * $mult) <= $_->{«x2»}) {
# print «No Top Neighbour:».($i + 1).»\n»;
undef $H{«top»};
}</p>
<p> # сосед снизу
if ($_→{«y1»} == (($row + 1) * $mult) && (($col + 0) * $mult) >= $_→{«x1»} && (($col + 1) * $mult) <= $_->{«x2»}) {
# print «No Bot Neighbour:».($i + 1).»\n»;
undef $H{«bot»};
}</p>
<p> # сосед справа
if ($_→{«x1»} == (($col + 1) * $mult) && (($row + 0) * $mult) >= $_→{«y1»} && (($row + 1) * $mult) <= $_->{«y2»}) {
# print «No Right Neighbour:».($i + 1).»\n»;
undef $H{«right»};
}</p>
<p> # сосед слева
if ($_→{«x1»} == (($col + 0) * $mult) && (($row + 0) * $mult) >= $_→{«y1»} && (($row + 1) * $mult) <= $_->{«y2»}) {
# print «No Left Neighbour:».($i + 1).»\n»;
undef $H{«left»};
}
}</p>
<p> # 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»}; </p>
<p> 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»}; </p>
<p> print ».($i + 1).»:\t»;
foreach (@{$elements[$i]}) {
print $_.»\t»;
}</p>
<p> print »\n»;
}</p>
<p># ================================================
# Поиск пути
# ================================================
my $start;
my $end;
my $newElement;
my $oldElement;
my @solution; </p>
<p># 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;</p>
<p> last;
}</p>
<p> if (!$start && @{$elements[$i]}[$j] == 0) {
print «Start = ».($i + 1).»\n»;
$start = $i;
}
}
}</p>
<p># 2. Вычисляем путь
my $discovered = (); </p>
<p># устанавливаем discovered (найденные) в false (все узлы — белые)
print »#Nodes:».(scalar @elements).»\n\n»;
for ($i = 0; $i < scalar @elements; $i++) {
$discovered[$i] = 0;
}</p>
<p># Обработаем соседей начального элемента
DFS ($start); </p>
<p>sub DFS {
my ($i) = @_; </p>
<p> # Конец лабиринта — отметим все, как посещённые, и добавим решение
if (($i + 1) == ($end + 1)) { # Если это решение — добавить в решения и вернуть true
push @solution, ($i + 1); </p>
<p> $discovered[$i] = 1; </p>
<p> return 1;
} elsif ($discovered[($_ — 1)] == 1) { # уже посещали — вернуть false
return 0;
} else { # иначе обработать
#print «Node:».($i + 1).»\n»; </p>
<p> $discovered[$i] = 1; </p>
<p> # Обработка всех соседей
# Если получим true, надо добавить в решение
foreach (@{$elements[$i]}) {
#print «Neighbour:».($_).»\n»; </p>
<p> # Если сосед 0, вернуть false — это начало или конец!
if ($_ != 0) {
$result = DFS ($_ — 1); </p>
<p> if ($result == 1) {
push @solution, $_; </p>
<p> return 1;
}
}
}</p>
<p> # Ничего не возвращаем
return 0;
}
}</p>
<p># Добавить в решения
push @solution, ($start + 1); </p>
<p># ===============================================================
# Вывод
# Рисование линии на основе solutionStack
# ===============================================================
print »\nStack:»;
foreach (@solution) {
print »$_ »;
}
print »\n»; </p>
<p>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;</p>
<p> 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;
}</p>
<p> print »<line x1=\"$x\" y1=\"$y\" x2=\"$x2\" y2=\"$y2\" />\n»;
}
print »</g>\n»;
#
# print «Found Solution!»;
Выведенное решение необходимо будет добавить в svg-файл: </p><p>
<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>
<img src="http://habrastorage.org/files/948/501/de8/948501de81de488cbe6ab56e40880198.png" alt="948501de81de488cbe6ab56e40880198.png" /></p>
<p class="copyrights"><span class="source">© <a target="_blank" rel="nofollow" href="http://habrahabr.ru/post/257251/">Habrahabr.ru</a></span></p>
</div>
<br>
<!--<div align="left">
<script type="text/topadvert">
load_event: page_load
feed_id: 12105
pattern_id: 8187
tech_model:
</script><script type="text/javascript" charset="utf-8" defer="defer" async="async" src="//loader.topadvert.ru/load.js"></script>
</div>
<br>-->
<div style="padding-left: 20px;">
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-2514821055276660"
crossorigin="anonymous"></script>
<!-- PCNews 336x280 -->
<ins class="adsbygoogle"
style="display:block"
data-ad-client="ca-pub-2514821055276660"
data-ad-slot="1200562049"
data-ad-format="auto"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
</div>
<!-- comments -->
<noindex>
<div style="margin: 25px;" id="disqus_thread"></div>
<script type="text/javascript">
var disqus_shortname = 'pcnewsru';
var disqus_identifier = '620688';
var disqus_title = 'Решение лабиринтов на Perl';
var disqus_url = 'http://pcnews.ru/blogs/resenie_labirintov_na_perl-620688.html';
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<!--<noscript>Please enable JavaScript to view the <a rel="nofollow" href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>-->
<!--<a href="http://disqus.com" rel="nofollow" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>-->
</noindex>
</div>
<br class="clearer"/>
</div>
<br class="clearer"/>
<div id="footer-2nd"></div>
<div id="footer">
<br/><br/>
<ul class="horz-menu">
<li class="about"><a href="/info/about.html" title="О проекте">О
проекте</a></li>
<li class="additional-menu"><a href="/archive.html" title="Архив материалов">Архив</a>
</li>
<li class="additional-menu"><a href="/info/reklama.html"
title="Реклама" class="menu-item"><strong>Реклама</strong></a>
<a href="/info/partners.html" title="Партнёры"
class="menu-item">Партнёры</a>
<a href="/info/legal.html" title="Правовая информация"
class="menu-item">Правовая информация</a>
<a href="/info/contacts.html" title="Контакты"
class="menu-item">Контакты</a>
<a href="/feedback.html" title="Обратная связь" class="menu-item">Обратная
связь</a></li>
<li class="email"><a href="mailto:pcnews@pcnews.ru" title="Пишите нам на pcnews@pcnews.ru"><img
src="/media/i/email.gif" alt="e-mail"/></a></li>
<li style="visibility: hidden">
<noindex>
<!-- Rating@Mail.ru counter -->
<script type="text/javascript">
var _tmr = window._tmr || (window._tmr = []);
_tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()});
(function (d, w, id) {
if (d.getElementById(id)) return;
var ts = d.createElement("script");
ts.type = "text/javascript";
ts.async = true;
ts.id = id;
ts.src = (d.location.protocol == "https:" ? "https:" : "http:") + "//top-fwz1.mail.ru/js/code.js";
var f = function () {
var s = d.getElementsByTagName("script")[0];
s.parentNode.insertBefore(ts, s);
};
if (w.opera == "[object Opera]") {
d.addEventListener("DOMContentLoaded", f, false);
} else {
f();
}
})(document, window, "topmailru-code");
</script>
<noscript>
<div style="position:absolute;left:-10000px;">
<img src="//top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;" height="1"
width="1" alt="Рейтинг@Mail.ru"/>
</div>
</noscript>
<!-- //Rating@Mail.ru counter -->
</noindex>
</li>
</ul>
</div>
<!--[if lte IE 7]>
<iframe id="popup-iframe" frameborder="0" scrolling="no"></iframe>
<![endif]-->
<!--<div id="robot-image"><img class="rbimg" src="i/robot-img.png" alt="" width="182" height="305" /></div>-->
<!--[if IE 6]>
<script>DD_belatedPNG.fix('#robot-image, .rbimg');</script><![endif]-->
</div>
<!--[if lte IE 7]>
<iframe id="ie-popup-iframe" frameborder="0" scrolling="no"></iframe>
<![endif]-->
<div id="footer-adlinks"></div>
<noindex>
<!--LiveInternet counter--><script type="text/javascript">
document.write("<a rel='nofollow' href='//www.liveinternet.ru/click' "+
"target=_blank><img src='//counter.yadro.ru/hit?t45.6;r"+
escape(document.referrer)+((typeof(screen)=="undefined")?"":
";s"+screen.width+"*"+screen.height+"*"+(screen.colorDepth?
screen.colorDepth:screen.pixelDepth))+";u"+escape(document.URL)+
";"+Math.random()+
"' alt='' title='LiveInternet' "+
"border='0' width='1' height='1'><\/a>")
</script><!--/LiveInternet-->
<!-- Rating@Mail.ru counter -->
<script type="text/javascript">
var _tmr = window._tmr || (window._tmr = []);
_tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()});
(function (d, w, id) {
if (d.getElementById(id)) return;
var ts = d.createElement("script"); ts.type = "text/javascript"; ts.async = true; ts.id = id;
ts.src = "https://top-fwz1.mail.ru/js/code.js";
var f = function () {var s = d.getElementsByTagName("script")[0]; s.parentNode.insertBefore(ts, s);};
if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); }
})(document, window, "topmailru-code");
</script><noscript><div>
<img src="https://top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;position:absolute;left:-9999px;" alt="Top.Mail.Ru" />
</div></noscript>
<!-- //Rating@Mail.ru counter -->
<!-- Yandex.Metrika counter -->
<script type="text/javascript">
(function (d, w, c) {
(w[c] = w[c] || []).push(function () {
try {
w.yaCounter23235610 = new Ya.Metrika({
id: 23235610,
clickmap: true,
trackLinks: true,
accurateTrackBounce: true,
webvisor: true,
trackHash: true
});
} catch (e) {
}
});
var n = d.getElementsByTagName("script")[0],
s = d.createElement("script"),
f = function () {
n.parentNode.insertBefore(s, n);
};
s.type = "text/javascript";
s.async = true;
s.src = "https://mc.yandex.ru/metrika/watch.js";
if (w.opera == "[object Opera]") {
d.addEventListener("DOMContentLoaded", f, false);
} else {
f();
}
})(document, window, "yandex_metrika_callbacks");
</script>
<noscript>
<div><img src="https://mc.yandex.ru/watch/23235610" style="position:absolute; left:-9999px;" alt=""/>
</div>
</noscript>
<!-- /Yandex.Metrika counter -->
<!-- Default Statcounter code for PCNews.ru http://pcnews.ru-->
<script type="text/javascript">
var sc_project=9446204;
var sc_invisible=1;
var sc_security="14d6509a";
</script>
<script type="text/javascript"
src="https://www.statcounter.com/counter/counter.js"
async></script>
<!-- End of Statcounter Code -->
<script>
(function (i, s, o, g, r, a, m) {
i['GoogleAnalyticsObject'] = r;
i[r] = i[r] || function () {
(i[r].q = i[r].q || []).push(arguments)
}, i[r].l = 1 * new Date();
a = s.createElement(o),
m = s.getElementsByTagName(o)[0];
a.async = 1;
a.src = g;
m.parentNode.insertBefore(a, m)
})(window, document, 'script', '//www.google-analytics.com/analytics.js', 'ga');
ga('create', 'UA-46280051-1', 'pcnews.ru');
ga('send', 'pageview');
</script>
<script async="async" src="/assets/uptolike.js?pid=49295"></script>
</noindex>
<!--<div id="AdwolfBanner40x200_842695" ></div>-->
<!--AdWolf Asynchronous Code Start -->
<script type="text/javascript" src="https://pcnews.ru/js/blockAdblock.js"></script>
<script type="text/javascript" src="/assets/jquery.min.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.json.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.form.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.easing.1.2.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/jquery/effects.core.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/browser-sniff.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/scripts.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-utils.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-auth.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-fiximg.js"></script>
<script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-infobox.js"></script>
</body>
</html>
