How to become an author
Search
Write a publication
Pull to refresh

Решение лабиринтов на Perl

Reading time11 min
Views7.6K
Perl*Programming*Algorithms*
Классическая задача при игре в лабиринте состоит в поиске прохода через него от входа до выхода. Путь-решение рисуется на карте лабиринта. В большинстве случаев лабиринты генерятся компьютерами, которые пользуются алгоритмами вроде поиска в глубину. Интересно, что решать лабиринт можно при помощи того же самого алгоритма.

Читаем лабиринт


Лабиринт можно представлять в разных форматах. Мы будем использовать 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>


Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 15: ↑10 and ↓5+5
Comments6
976
Karma
161.5
Rating
Вячеслав Голованов @SLY_G

Научпоп. Проповедую в храме науки.

Send message
WebsiteWebsiteWebsiteTwitterVK

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr