Perl Maze Solution
A classic task when playing in a maze is to find a passage through it from the entrance to the exit. The solution path is drawn on the maze map. In most cases, labyrinths are generated by computers that use algorithms like depth-first search. Interestingly, the labyrinth can be solved using the same algorithm.
Labyrinth can be represented in different formats. We will use SVG, because in this case it will be easy to draw a solution on top of it.
')
We will process the file with two regulars - one for the size and one for the search for lines.
The size:
Lines:
Pass the data to the structure that stores the line, which will look like this:
In the svg-file, all data is based on multipliers 16. Therefore, we divide x and y by 16, and get an increasing sequence.
The last thing we do with the file is to keep the number of rows and columns. This will be the first group obtained from the regular season.
The last thing to do before launching is to make a list of neighbors. This is a list of all items adjacent to the one you need.
Listing the above for the maze above:
This is not such an easy task - you need to take into account the lines of the “walls” that cut off some of our neighbors. To do this, first find all the neighbors. Those to which we can not reach, mark as -1. Others will be indicated by positive numbers.
Then we go through all the lines and exclude those neighbors with whom we have no connection. And at the end we will render the list of all neighbors in an array and output as indicated above.
Having received the lists of neighbors, we will start working with the algorithm.
If there is a graph, we can iterate over nodes by passing through each node. We divide them into three categories:
- black - found nodes
- gray - found, but not processed
- white - not found
Then, starting with a random node, we will go round all its neighbors. We note each neighbor as found, and repeat the indicated steps until we perepered all the nodes.
In pseudocode, it looks like this:
This is the easiest step. Find the center of each cell (lefttop + rightbot2) and draw a line.
The displayed solution will need to be added to the svg-file:
We read the maze
Labyrinth can be represented in different formats. We will use SVG, because in this case it will be easy to draw a solution on top of it.
An example of a maze in 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> ')
We will process the file with two regulars - one for the size and one for the search for lines.
The size:
m/<title>([0-9]*)\sby\s([0-9]*).*/g Lines:
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g Pass the data to the structure that stores the line, which will look like this:
{ "x1" => 0, "y1" => 0, "x2" => 0, "y2" => 0 } In the svg-file, all data is based on multipliers 16. Therefore, we divide x and y by 16, and get an increasing sequence.
The last thing we do with the file is to keep the number of rows and columns. This will be the first group obtained from the regular season.
Compiling a list of neighbors
The last thing to do before launching is to make a list of neighbors. This is a list of all items adjacent to the one you need.
Listing the above for the maze above:
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 This is not such an easy task - you need to take into account the lines of the “walls” that cut off some of our neighbors. To do this, first find all the neighbors. Those to which we can not reach, mark as -1. Others will be indicated by positive numbers.
Then we go through all the lines and exclude those neighbors with whom we have no connection. And at the end we will render the list of all neighbors in an array and output as indicated above.
Having received the lists of neighbors, we will start working with the algorithm.
Depth search
If there is a graph, we can iterate over nodes by passing through each node. We divide them into three categories:
- black - found nodes
- gray - found, but not processed
- white - not found
Then, starting with a random node, we will go round all its neighbors. We note each neighbor as found, and repeat the indicated steps until we perepered all the nodes.
In pseudocode, it looks like this:
// 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; // , } } Conclusion of the decision
This is the easiest step. Find the center of each cell (lefttop + rightbot2) and draw a line.
Code for all of the above
@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!"; The displayed solution will need to be added to the svg-file:
<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> 
Source: https://habr.com/ru/post/257251/
All Articles