Solving a maze with Perl
Mazes are really famous puzzles where the goal is to find the exit starting from an entrance. We can see these kind of puzzles as a labyrinth. When we found the solution we then draw over them to mark the path that we have to find.
Most of the time these puzzles are generated by computer programs, these computer programs then use algorithms such as depth-first searching to create the mazes. We can however also solve these puzzles by using the same algorithm.
This article will cover the solving of a maze, there will be more efficient methods to solve these mazes but I will just explain one of the many.
Reading in the maze
Reading in the maze can be done in several different file formats. We will use a SVG format here because this lets us draw the solution on top of it easily.
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>
To process this file we will use 2 regexes, one regex that will get the size and another regex to get the lines.
Regex for the size:
m/<title>([0-9]*)\sby\s([0-9]*).*/g
Regex for the lines:
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g
We then process the file into a specific data structure to hold the lines, one that looks like this:
{
"x1" => 0,
"y1" => 0,
"x2" => 0,
"y2" => 0
}
A second thing that we can see in the svg files is that everything is based in a magnitude of 16. We therefor will divide the x and y values by 16 so that we have an incremental sequence.
The last thing that we will do with the file is save the number of columns and rows. This is done by getting the first group of the regex.
Creating the adjacency list (neighbour list)
A last thing that we have to do before we can start applying our algorithm explained below this section is to create a adjacency list (commonly referred as a neighbour list). This list is a indication of every element with it’s neighbour.
Output of the neighbour list for the maze given 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 however is not as easy as it seems. We will have to take the lines that remove some of the neighbours into consideration. To do this we will first start finding all the neighbours. The neighbours that we can not reach will be noted down as a -1. The others will be the numbers.
After that we will go through every line and rule out the neighbours that not connected. As a last step we will then push all these neighbours on an array and print them out as stated above.
Now we have the neighbours and we can start with our algorithm to find the solution.
Depth-first searching
When we have a graph, we can iterate over the nodes of this graph and go over every node. To do this we will see these nodes as 3 different categories:
- Black nodes, these are the discovered nodes
- Grey nodes, these are the discovered but not yet processed nodes
- White nodes, these are the nodes that are not yet discovered.
We then start at a random node and will go through all of it’s neighbours. For every of these neighbours we will then mark them as discovered and repeat these steps until we went through all the nodes.
In pseudo code this looks like this:
// Discovered nodes
discovered = array();
// Init White nodes
for (i = 0; i < discovered.size(); i++)
discovered[i] = false;
// Start
endIdx = someEndIndex;
start_node_idx = someStartNodeIndex;
DFS(start_node_idx);
// Algorithm
void DFS(nodeIdx) {
if (nodeIdx == endIdx) {
// If end, mark discovered and return true
discovered[nodeIdx] = true;
return true;
} else if (discovered[nodeIdx]) {
// If already discovered, return false
return false;
} else {
// Else, mark as discovered and process it's neighbours
discovered[nodeIdx] = true;
foreach (neighbour i of nodeIdx) {
result = DFS(i);
if (result) {
return true; // Solution found, return
}
}
return false; // Nothing found, cancel
}
}
We will use this later on in our perl code to solve the maze. Printing the solution
Printing the solution is the most easy step to do. We will find the center of each point ($\frac{left top + right bot}{2}$) and then we will just draw a line from point to point while printing it out. Putting it all together in perl code
After we have put all the above steps together we get this as a solution:
@ARGV = ("/PATH/05.svg"); # We can also remove this and call the program with the path as an argument.
undef $/;
$input=(<>);
$idx = 1;
my $rows;
my $cols;
# ====================
# Reading in the lines
# ====================
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++;
# Set row and col count
#if ($y2 > $rows + 1) { $rows = $y2 - 1; }
#if ($x2 > $cols + 1) { $cols = $x2 - 1; }
# Add to lines
push @lines, \%H;
}
# ================================================
# Getting the neighbours for each element
# HASH[EL + 1][top|right|bot|left] = value;
# ================================================
$elCount = $rows * $cols;
# For every element, get the border
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 and column
$row = int($i / $cols) + 1;
$col = int($i % $cols) + 1;
# Boundaries
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), # Set left top corner
"left_top_y" => (($row + 0) * $mult),
"right_top_x" => (($col + 1) * $mult), # Set right top corner
"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";
# Check if top neighbour
if ($_->{"y1"} == (($row + 0) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) {
# print "No Top Neighbour: ".($i + 1)."\n";
undef $H{"top"};
}
# Check if bot neighbour
if ($_->{"y1"} == (($row + 1) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) {
# print "No Bot Neighbour: ".($i + 1)."\n";
undef $H{"bot"};
}
# Check if right neighbour
if ($_->{"x1"} == (($col + 1) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) {
# print "No Right Neighbour: ".($i + 1)."\n";
undef $H{"right"};
}
# Check if left neighbour
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";
}
# ================================================
# Finding a path
# ================================================
my $start;
my $end;
my $newElement;
my $oldElement;
my @solution;
# 1. Find start and start
print "Determining start and end point\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. Calculate path from start to end
# We see that in the lines above that we created a neighbour list graph
# To solve the maze we will therefor use a popular algorithm called depth first search
# Depth search will go through the neighbours by setting them discovered or not
my $discovered = ();
# Set discovered on false (all white nodes)
print "#Nodes: ".(scalar @elements)."\n\n";
for ($i = 0; $i < scalar @elements; $i++) {
$discovered[$i] = 0;
}
# Start for the neighbours of our start element
DFS($start);
sub DFS {
my ($i) = @_;
# If this is the end of the maze, set as visited and add to solution
if (($i + 1) == ($end + 1)) { # If solution, add to solution and return true
push @solution, ($i + 1);
$discovered[$i] = 1;
return 1;
} elsif ($discovered[($_ - 1)] == 1) { # If visited already, return false
return 0;
} else { # Else process
#print "Node: ".($i + 1)."\n";
$discovered[$i] = 1;
# For every neighbour, process it
# If this returns true, then add it to the solution
foreach (@{$elements[$i]}) {
#print "Neighbour: ".($_)."\n";
# If neighbour is 0, return false this is start or end!
if ($_ != 0) {
$result = DFS($_ - 1);
if ($result == 1) {
push @solution, $_;
return 1;
}
}
}
# Else return nothing
return 0;
}
}
# Also push the solution
push @solution, ($start + 1);
# ===============================================================
# Printing
# Create lines from start to end depending on the 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!";
This will print out the lines that we will need to add to our svg files.
<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>
We just add these and we will get our solution. Have fun solving mazes!
Member discussion