Difference between revisions of "Simple maze"
Jump to navigation
Jump to search
| Line 566: | Line 566: | ||
use List::Util qw/shuffle/; | use List::Util qw/shuffle/; | ||
my $map | my $map; | ||
my ( $WIDTH, $HEIGHT ) = ( 50, 30 ); | my ( $WIDTH, $HEIGHT ) = ( 50, 30 ); | ||
| Line 576: | Line 576: | ||
); | ); | ||
carve( | carve( $WIDTH / 2, $HEIGHT / 2, 'E' ); | ||
show_map( | show_map(); | ||
sub carve { | sub carve { | ||
my ( | my ( $x0, $y0, $direction ) = @_; | ||
my $x1 = $x0 + $DIRECTION{$direction}{dx}; | my $x1 = $x0 + $DIRECTION{$direction}{dx}; | ||
| Line 591: | Line 591: | ||
$map->[$x1][$y1]{ $DIRECTION{$direction}{opposite} } = 1; | $map->[$x1][$y1]{ $DIRECTION{$direction}{opposite} } = 1; | ||
carve( | carve( $x1, $y1, $_ ) for shuffle keys %DIRECTION; | ||
} | } | ||
sub show_map { | sub show_map { | ||
for my $y ( 0 .. $HEIGHT ) { | for my $y ( 0 .. $HEIGHT ) { | ||
for my $x ( 0 .. $WIDTH ) { | for my $x ( 0 .. $WIDTH ) { | ||
Revision as of 15:41, 26 December 2014
Maze Generator in C++
Simple maze generator written in 10 minutes :) The source code is public domain.
// Simple Maze Generator in C++ by Jakub Debski '2006
#include <time.h>
#include <vector>
#include <list>
using namespace std;
int main()
{
srand(time(0));
const int maze_size_x=80;
const int maze_size_y=25;
vector < vector < bool > > maze;
list < pair < int, int> > drillers;
maze.resize(maze_size_y);
for (size_t y=0;y<maze_size_y;y++)
maze[y].resize(maze_size_x);
for (size_t x=0;x<maze_size_x;x++)
for (size_t y=0;y<maze_size_y;y++)
maze[y][x]=false;
drillers.push_back(make_pair(maze_size_x/2,maze_size_y/2));
while(drillers.size()>0)
{
list < pair < int, int> >::iterator m,_m,temp;
m=drillers.begin();
_m=drillers.end();
while (m!=_m)
{
bool remove_driller=false;
switch(rand()%4)
{
case 0:
(*m).second-=2;
if ((*m).second<0 || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second+1][(*m).first]=true;
break;
case 1:
(*m).second+=2;
if ((*m).second>=maze_size_y || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second-1][(*m).first]=true;
break;
case 2:
(*m).first-=2;
if ((*m).first<0 || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second][(*m).first+1]=true;
break;
case 3:
(*m).first+=2;
if ((*m).first>=maze_size_x || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second][(*m).first-1]=true;
break;
}
if (remove_driller)
m = drillers.erase(m);
else
{
drillers.push_back(make_pair((*m).first,(*m).second));
// uncomment the line below to make the maze easier
// if (rand()%2)
drillers.push_back(make_pair((*m).first,(*m).second));
maze[(*m).second][(*m).first]=true;
++m;
}
}
}
// Done
for (size_t y=0;y<maze_size_y;y++)
for (size_t x=0;x<maze_size_x;x++)
{
if (maze[y][x]==true)
printf(".");
else
printf("#");
}
return 0;
}
Examples
######.........#.#.......#.....#...#.....#.........#.#...#.#.......#.......##### ######.#.###.#.#.#.#######.#.#####.#.###.#.#.#####.#.###.#.#.#######.########### .....#.#.#...#.#.........#.#.#.....#.###...#.#.....#.......#.......#.....####### .#.#.###.#.#####.#.#.#######.#.#.#.#.#####################.#.###.#######.####### .#.#.#...#...#...#.#...#.#.#.#.#.#.#.........#.....#...........#.#.............# ####.#.#######.#######.#.#.#.#.#.#######.#.#.#.#.#.#.#######.#######.#######.#.# ##...#...#####.#.#####.#...#...#.#...#.#.#.#...#.#...###...#.#.......#.......#.# ####.###.#####.#.#####.#.###.#.###.###.#.#.###.#########.#####.###.############# .........###.#.....###.#...#.#.#.#.......#.#...#...#.#.#.#.......#.###...#.....# ########.###.#.#.#.###.#.#.###.#.#.#####.#.###.#.###.#.#.#.#.###.#####.###.#.### .......#.....#.#.#.#...#.#...........#...#.#.....#.......#.#...#.#.........#...# ####.#.#.#####.#.###.#######.#######.###.#.#.###.#.#####.#.#####.#.#.#####.##### ...#.#.#.......#...#.....#.....#.#...#####.#...#.......#.#...#.....#...#.#.....# ##.###.#.#.#.###.#####.#.#####.#.#.#######.#####.#####.#.###.#.###.#####.#####.# ##...#...#.#.#.......#.#.....#...#.......#...#...#.....#.....#...#...........#.# ####.#.###########.###.#.###.#####.#######.###.###########.###.###.#####.###.### ####...###.....#...#.#.#...#...........###...#.###...#.###.###...#.....#.#.....# ####.#####.#######.#.###.###.#.#####.#.#############.#.###.#####.#####.#.###.### ####.........#.#...#.....#.#.#.#.....#.###.#...#.............#...#####.#...#...# ######.#.#####.#.###.#.#.#.###.#######.###.#.#####.###.#################.####### ######.#...#.#.....#.#.#.#...#...###...###.....#...#.......#########...#.......# ######.###.#.#####.#####.#.###.#.###.#.###.#.###.###.#####.#########.#########.# ######.#.#.#...###...#...#.#.#.#...#.#.....#.#.#...#.###...#########...#.......# ########.#.###.#######.#.#.#.###.#######.###.#.#####.###############.#.###.##### ########...###.........#.#.......#######.#.....#####.......#########.#.........#
With little changes you can get cool results, f.e.
else
{
// drillers.push_back(make_pair((*m).first,(*m).second));
// drillers.push_back(make_pair((*m).first,(*m).second));
// change to
for (size_t index=0;index<10;index++)
drillers.push_front(make_pair((*m).first,(*m).second));
gives "star-like" effect:
.#.#...#...#.....#...#...#...#.#...#...#.....#...#...#.......#...#.....#.....#.# .#.###.###.#####.###.###.###.#.###.###.#.#####.###.###.#######.###.#####.#####.# ...#.#...#...#...#.#...#...#...#.#...#.....#...#.......#.............#.#...#...# ##.#.###.###.###.#.###.###.###.#.###.#.#####.###.#######.#############.#.###.### .......#...#.#.#.....#.#.#.......#.#.....#...#...#.#...#...#...#.#.#.#...#...#.# ######.###.#.#.#####.#.#.#######.#.###.###.###.###.#.###.###.###.#.#.#.###.###.# ...#.#...#...#...#.......#.#...#.....#.....#...#.....#...#...#.#.......#...#...# ##.#.###.###.###.#######.#.###.#####.#.#####.###.#####.###.###.#.#######.###.### .#...#.#.#.#...#.#.#.....#.#.#...#.......#...#.#...#.#.#...#.#...#.#...#.#...#.# .###.#.#.#.###.#.#.#####.#.#.###.#####.###.###.#.###.#.#.###.#.###.#.###.#.###.# .................#...#...#.#.#.#...#...#.......................................# ####.###.###.###.###.###.#.#.#.###.###.#.###.###.###.###.###.###.###.###.###.### .#.#.#.#.#.#.#...........................#.#.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.# .#.###.###.#####.#.#.#####.#####.#.###.#.#.###.###.###.###.###.#######.###.###.# .................#.#.#.....#.....#.#...#.......................................# ##.###.#.###.#.###.#####.###.#.#.#####.###.#.#.###.#.###.###.#.#.###.#.###.#.#.# ...#...#.#...#.#...#.....#...#.#.#.......#.#.#...#.#...#...#.#.#...#.#...#.#.#.# .###.#.###.#.###.#.#######.#.#.#####.#.#####.###.###.#.#######.###.###.#.###.### .#...#.#...#.#...#.#.......#.#.#.....#.....#...#...#.#.......#...#...#.#...#...# ##.#.#####.###.#.###.###.###.#####.###.#.#.###.###.###.#.###.###.#.#####.#####.# ...#.#.....#...#.#...#...#...#.....#...#.#...#...#...#.#...#...#.#.....#.....#.# .#.###.#.#####.###.###.###.###.#.###.#.###.#.###.###.###.#####.###.###.###.#.### .#.#...#.#.....#...#...#...#...#.#...#...#.#...#...#...#.....#...#...#...#.#...# .#####.#####.###.###.###.###.#.###.###.#####.#.###.###.###.#.###.#.#.###.###.### .#.....#.....#...#...#...#...#.#...#.......#.#...#...#...#.#...#.#.#...#...#...#
or
(*m).second-=2;
// if ((*m).second<0 || maze[(*m).second][(*m).first])
// change to
if ((*m).second<0 || (maze[(*m).second][(*m).first] && rand()%5))
allows loops (sample loop top left corner is marked with comas):
.......#,,,,,,,,.#####.....#####...#...............#...#.###.....###...#.#.#.### .#######,#####.#,#######.#######.#.#############.#.###.#.###.#########.#.#.#.### .#...#..,,,,,#.#,,,###...#######.#.#...#.........#.....#.......................# .#.###.#####,#####,###.#.#########.#.#########.#####.#.#.###.#.#########.#.#.#.# .#.....#....,,,,,,,....#.#######.....#...#...#...###.#.......#.###.#.....#.#...# .#.#.#####.#.#.###.#################.#.#.###.#######.#####.###.###.#.#####.##### .#...#.....#.....#.#...#.......#.#...#.#.....#######...#...#...#.#.#.###...#.### .#.###.###.#.###.#.###.#.#######.#.#.###.#.#.#######.###########.#.#######.#.### ...#...#.#.#.#...#.....#.....#...#.#.....#...#.#####.......#.....#.........#...# ####.#.#.#.#####.#.#.#.###.#.###.#######.#.#.#.#######.#.#.#.#.#.###.#######.### ...#.#.#.....#.....#.#.#...#.#...#.....#.#.#...#...#...#.#...#.#...............# .###.###.#####.#######.###.#.###.#.###.###.#.#.#.#####.#######.###.#######.#.#.# .....#.#.#...#...#...#.#...#...........#.....#.........#.#####.#...#...###...#.# ##.###.#.#.#.#.#.#.#########.#.###.###.#.###.#######.###.#####.###.#.#.###.##### ...#.......#...#...#.......#.#.#...#...#...#.#.#...#.#.....#...#...#.#.#...#...# ####.#.#######.#.#.#.###.###.#.#.#####.#####.#.#.#####.#.#.#.#.#######.#####.### .......#...#...#.#.....#.#...#...#...............#.....#.#...#...........#...### ##.#####.###########.#####.#########.#.###.###.#.#########.###.###.#.#.###.#.### .......#...#.#.......#.....#.....#...#.#.....#.#.#...........#...#.....#.#.#...# ##.#.###.###.#.#.###.#######.#.#.#####.###.#####.###.#.#.#####.###.#.###.###.### ##.#...#.......#...#.........#.#.......#...###.#.....#...#####...#.............# ########.###.#.#.#########.#####.#.#####.#####.#.#####.#.#####.#####.#.#.####### ##.........#.#...#.#...#...#...#.....#.....#...#.....#.#.#####.....#...#.....### ######.###.#.#.###.#.###.#.#.###.#.#.#.#.#.###.#####.#.#######.#.#.###.######### ##.......#.#...........#.#.....#.#.#.#.#.#.....###...#.###.......#...#...#######
Maze Generator in Visual Basic 6
''''''''''''''''''''''''''
' Perfect Maze Generator '
' Icey '
' Oct 2006 '
' Public Domain '
''''''''''''''''''''''''''
' this code is designed to be run from a module, using sub main
' all variables are declared
Option Explicit
' 0 is the most random, randomisation gets lower after that
' less randomisation means more straight corridors
Private Const RANDOMISATION As Integer = 5
' the spaces across - this must be an odd number
Private Const MAZE_X As Integer = 53
' the spaces down - this must be an odd number
Private Const MAZE_Y As Integer = 17
' used for storing the current square and squares potentially to move to
Private Type COORDS
X As Integer
Y As Integer
End Type
' stores the directions that corridors go in
Dim cDir(3) As COORDS
' these can be any odd numbers
Dim blnMaze(MAZE_X, MAZE_Y) As Boolean
Private Sub GenerateMaze()
Dim cN As COORDS, cS As COORDS
Dim intDir As Integer, intDone As Integer
Dim blnBlocked As Boolean
Randomize
Erase blnMaze
Do
' this code is used to make sure the numbers are odd
cS.X = 2 + (Int(((MAZE_X - 1) * Rnd) / 2) * 2)
cS.Y = 2 + (Int(((MAZE_Y - 1) * Rnd) / 2) * 2)
' first one is free!
If intDone = 0 Then blnMaze(cS.X, cS.Y) = True
If blnMaze(cS.X, cS.Y) Then
' always randomisation directions to start
RandomDirections
Do
' only randomisation directions, based on the constant
If Int(RANDOMISATION * Rnd) = 0 Then RandomDirections
blnBlocked = True
' loop through order of directions
For intDir = 0 To 3
' work out where this direction is
cN.X = cS.X + (cDir(intDir).X * 2)
cN.Y = cS.Y + (cDir(intDir).Y * 2)
' check if the tile can be used
If IsFree(cN) Then
' create a path
blnMaze(cN.X, cN.Y) = True
' and the square inbetween
blnMaze(cS.X + cDir(intDir).X, cS.Y + cDir(intDir).Y) = True
' this is now the current square
cS.X = cN.X
cS.Y = cN.Y
blnBlocked = False
' increment paths created
intDone = intDone + 1
Exit For
End If
Next
' loop until a path was created
Loop Until blnBlocked
End If
' create enough paths to fill the whole grid
Loop While intDone + 1 < ((MAZE_X - 1) * (MAZE_Y - 1)) / 4
End Sub
' this changes the direction to go from the current square, to the next available
Private Sub RandomDirections()
' clear the array
Erase cDir
' four possible sets of directions
Select Case Int(3 * Rnd)
Case 0
cDir(0).X = -1: cDir(1).X = 1
cDir(2).Y = -1: cDir(3).Y = 1
Case 1
cDir(3).X = -1: cDir(2).X = 1
cDir(1).Y = -1: cDir(0).Y = 1
Case 2
cDir(2).X = -1: cDir(3).X = 1
cDir(0).Y = -1: cDir(1).Y = 1
Case 3
cDir(1).X = -1: cDir(0).X = 1
cDir(3).Y = -1: cDir(2).Y = 1
End Select
End Sub
' checks if a tile is free for use
Private Function IsFree(cF As COORDS) As Boolean
' check it's within the grid
If cF.X < MAZE_X And cF.X > 1 And cF.Y < MAZE_Y And cF.Y > 1 Then
' check it hasn't been used yet
IsFree = (blnMaze(cF.X, cF.Y) = False)
End If
End Function
' this code should be run from a module
' go to Project > [projectname] Properties
' and then select Sub Main from the Startup Object list
Sub Main()
' the maze is added to this string, which is then copied to the clipboard
Dim strOutput As String
GenerateMaze
Dim A As Integer, B As Integer
' loop through squares
For A = 1 To MAZE_Y
For B = 1 To MAZE_X
' check if a path was created here
If blnMaze(B, A) Then
' empty
strOutput = strOutput & " "
Else
' wall
strOutput = strOutput & "#"
End If
Next
' go down to the next row
strOutput = strOutput & vbNewLine
Next
Clipboard.Clear
Clipboard.SetText strOutput
' tell the user what has happened
MsgBox "Maze copied to the clipboard.", vbInformation, "Maze generator"
End Sub
Examples
Randomisation: 0
########################################### # # # # # # # ### # ##### # # ##### ### ### # ### ##### # # # # # # # # # # # # # # # # # # # # # # ##### ##### # # # # ##### # # # # # # # # # # # # # # # # ##### # # # ### # ### ######### ##### # # # # # # # # # # # # # # # # # ### ### # # ### # ### # # # # # ##### ### # # # # # # # # # # # # # # # # # ### # # # ### # # ### ########### ### # # # # # # # # # # # # # # # ######### # ######### # # # ### # # ### # # # # # # # # # # # # # # # # # # # # ### # # ### ### # ### # # ### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # ### # ### # # ##### # # # # # # # # # # # # # # # # # # # ### # # # # # # ### # ### ##### # # # # # # # # # # # # # # # # # ####### # # # ######### ### ########### # # # # # # ###########################################
Randomisation: 5
##################################################### # # # # # # # ############### # # # # ##################### # # # # # # # # # # # # # # ####### # # # # # # # # ######################### # # # # # # # # # # # # # # # # # # # # ### ##### # # # # # ################### # # # # # # # # # # # # # # # # # # # # # # # # # # ### # # # # # ### ######### # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # ##### ##### # # # # ######### # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # ########### # # ######### # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ### # # # # # # # # # # # # # # # # # #####################################################
Randomisation: 25
################################################### # # # # # # # ### # # # # # # # # # # ######################### # # # # # # # # # # # # # # ##### # # # # # # ### ############### ######### # # # # # # # # # # # # # # # # # # # ##### # # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # ### # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # ##### # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # ### # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ###################################################
Maze Generator in Javascript
This is a javascript port of the visual basic version above.
<!DOCTYPE html>
<html>
<head>
<meta charset = "utf-8">
<title>testing code</title>
<style type = "text/css">
body {background-color:black;}
table {background-color:#222222;border-width:1px;}
td {width:30px;height:30px;}
th {color:white;}
div#title {background-color:#555555;width:100%;height:100%;}
div#title:hover {background-color:#999999;}
div#wall {background-color:#666666;width:100%;height:100%;}
div#wall:hover {background-color:#AAAAAA;}
div#floor {background-color:#003300;width:100%;height:100%;}
div#floor:hover {background-color:#006600;}}
</style>
<script>
// Coordinates of N(x,y) S(x,y) E(x,y) W(x,y)
// it's necessary to have one of each so that if one direction
// doesn't work properly, we can try each direction until one
// works, or that we know there isn't a location possible.
var cN = [[0,0],[0,0],[0,0],[0,0]];
var size = 35,x,y,cx,cy;
var map = new Array(size);
var randomDir,intDone=0;
for (var i = 0; i <= size * size; ++i){
map[i] = new Array(size);
}
// Initialize the Map Array to Zeros
for (x=1;x<=size;++x){
for (y=1;y<=size;++y){
map[x][y]=0;
} //end for
} //end for
do {
// Roll random x's and y's and make sure the value is odd
x=2+Math.floor(Math.random()*(size-1));if (x%2!=0) --x;
y=2+Math.floor(Math.random()*(size-1));if (y%2!=0) --y;
// Ensure that the first random map location starts the process
if (intDone==0) map[x][y]=1;
if (map[x][y]==1){
//Randomize Directions
randomDir=Math.floor(Math.random()*4)
if (randomDir==0){
cN = [[-1,0],[1,0],[0,-1],[0,1]];
} else if (randomDir==1){
cN = [[0,1],[0,-1],[1,0],[-1,0]];
} else if (randomDir==2){
cN = [[0,-1],[0,1],[-1,0],[1,0]];
} else if (randomDir==3){
cN = [[1,0],[-1,0],[0,1],[0,-1]];
} //end if
blnBlocked=1;
do {
blnBlocked++;
for (var intDir=0; intDir<=3; ++intDir){
// Determine which direction the tile is
cx=x+cN[intDir][0]*2;
cy=y+cN[intDir][1]*2;
//Check to see if the tile can be used
if (cx<size && cy<size && cx>1 && cy>1){
if (map[cx][cy]!=1){
//create destination location
map[cx][cy]=1;
//create current location
map[x][y]=1
//create inbetween location
map[x+cN[intDir][0]][y+cN[intDir][1]]=1;
//set destination location to current
x=cx;y=cy;
blnBlocked=0;
intDone++;
intDir=4
} //end if
} //end if
} //end for
//recursive, no directions found, loop back a node
} while (blnBlocked==1) //end do
} //end if
} while (intDone+1<((size-1)*(size-1))/4) //end do
document.writeln("<table><tr>");
for (x=1;x<=size;++x){
for (y=1;y<=size;++y){
if (map[x][y]==0){
document.writeln("<td id='cellx"+x+"y"+y+"'><div id='wall'></div></td>");
} else if (map[x][y]==1){
document.writeln("<td id='cellx"+x+"y"+y+"'><div id='floor'></div></td>");
} //end if
} //end for
document.writeln("</tr><tr>");
} //end for
document.writeln("<th colspan='"+size+"'><div id='title'>Maze Experiment</div></th></tr></table>");
</script>
</head>
<body></body>
</html>
Maze Generator in Perl
This is a complete recursive backtracking maze generator in Perl:
#!/usr/bin/env perl
use strict;
use warnings;
no warnings 'recursion';
no warnings 'uninitialized';
use List::Util qw/shuffle/;
my $map;
my ( $WIDTH, $HEIGHT ) = ( 50, 30 );
my %DIRECTION = (
N => { dy => -1, opposite => 'S' },
S => { dy => 1, opposite => 'N' },
E => { dx => 1, opposite => 'W' },
W => { dx => -1, opposite => 'E' },
);
carve( $WIDTH / 2, $HEIGHT / 2, 'E' );
show_map();
sub carve {
my ( $x0, $y0, $direction ) = @_;
my $x1 = $x0 + $DIRECTION{$direction}{dx};
my $y1 = $y0 + $DIRECTION{$direction}{dy};
return if $x1 == 0 or $x1 == $WIDTH or $y1 == 0 or $y1 == $HEIGHT;
return if $map->[$x1][$y1];
$map->[$x0][$y0]{$direction} = 1;
$map->[$x1][$y1]{ $DIRECTION{$direction}{opposite} } = 1;
carve( $x1, $y1, $_ ) for shuffle keys %DIRECTION;
}
sub show_map {
for my $y ( 0 .. $HEIGHT ) {
for my $x ( 0 .. $WIDTH ) {
if ( defined $map->[$x][$y] ) {
print $map->[$x][$y]{S} ? ' ' : '_';
print $map->[$x][$y]{E} ? ' ' : '|';
}
else {
print '##';
}
}
print "\n";
}
}
The essence of the script is the carve function, which tries to carve into a given direction, and, if it is not possible, backtracks -- which means going one step back and trying other directions.
Examples
$ perl-generator.pl ###################################################################################################### ## | | _ _ _ | _ _| _ | _ _ _| | _ | _ _ _ _ | _ _ _ _ |_ _ _ | _ _| |## ## |_ _|_ _ _ |_ _|_ _ _ _ _| _| | | _ _|_ _| | |_ |_ |_ |_|_ | |_ _| | _| _| | _ _ _| |## ## | _ | | _ _ _| |_ _ | |_ _ | _ _|_ | | | |_ _ | |_ |_ |_ _| | _ _|_ _ _| |## ## | | | | |_|_ _| | | | |_ | | | | _ _|_ | _ _|_ _|_ | |_ _| |_ | _| |_ _ | _ | |_|## ## |_ _| |_ _ _ _ | | |_ _| | | _| |_ _ | |_ | _ _ | | |_ |_ | | | _| _ |_ _| _| |## ## | | _ _ _ |_ _|_ _ | _|_| | | | | | | | |_ _|_| _| | _| |_ _ |_ | |_ | | _| |## ## |_ _| | _ _ _ _ _| | |_ _ _ _|_ _|_|_ |_| |_| | |_ _ _ _| _|_ |_ |_ _ _| |_ _ _| | | _|## ##_ _ | |_| _ _ _ _ | |_ _ _ _ _ _ | | | _| _| |_ | | _|_ | _|_ _ | _| _ _ _| |_ |## ## _ _| _ _| _ _ | | | |_ _|_ _|_ _|_ |_ |_ _ | | | _ _ _|_| _| | | _| | _ _| |## ## | |_| _ _| | |_|_ _| |_ |_ _| _ |_ _ _|_ | | |_ _| | _ _| | _| | |_ _|_ _| | |## ##_ _|_ _ _| | |_|_ | |_ |_ | _ _| | |_ _ _ _ | | | | _ _| | _| |_ | |_ _ _ _ _ _|_ |## ## _ _ _ _|_ _| |_ _|_ _ _| _| | _ _| | _ _| |_ _|_ _ _| _| | _|_ _| | _ _| _ _ | _|## ##_ _ _| | _ _ _| _ _| _ |_ |_| |_ _ | |_ | _| _ _ _ |_ _ |_ | | | | _ _| | | | |## ## _ | _| |_ _|_ _ _ _|_ _ _ _| |_ _ |_ _ |_ _ |_ _ _ |_ _| | |_ _|_ | | |_ _|_ |## ## | _|_ | |_ _ _ _ |_| _ _ | | _ _|_ _ | |_ |_ | _| | |_ _ _|_ _ _ | |_| |_ _ _ _ _|## ## | |_ _ _|_ _ | |_ _ _| | _|_|_ | | _ _| | _| |_ | _| |_ _ _| _ _ _ _ _|_ | | _ _ |## ## |_ _ _ _ _|_ _|_ |_ _ | | _ |_ |_ |_ _| | _| _|_ |_ _ _ |_ |_ _ _| | _|_ | _|## ## | _ _ |_ _ | |_ | | |_ |_ _ _| |_ _ _ _| |_ | _| |_ | |_| _ _ _|_ _ | |_ |## ## |_| _ _| | | |_ | | |_|_ _ _| _| _ _ | _ _| | _| | _| | | | |_|_ | | | _ |_| | _|## ##_ _| _ _| | | | _| | | _ _ _ _ _| | |_ _|_ _| _|_ _| |_ |_ | _|_ _| | | |_ _ _| | |## ## _| _|_ _| | |_ _ _| |_ _|_ _ | _| |_ _ _| | _| _ _ _| _ _| | |_ | _| | _ _| | |## ## _| | |_ _ _| | _ _ _| _ _|_ |_ | _ | _|_ _| | _ _ | | _ _|_ | | | _| | _| _| |## ## | _| |_ _ _ _ _| | _ | |_ _ _ |_ | | | _|_ | _ _|_ | |_| | | _| |_ _| _|_ | | |## ## |_ | | _ _ _ _ _ _| | |_ _ _ _|_ | |_| | _| _|_ | _ _| |_| _| | |_ |_ _ _|_ _ _|_ _| |## ## | |_ _|_| _ _ _ | _ _| _ | _ |_ _ _|_| _| _ _| | _|_ _ _| _|_ | | | _ _ _ _| |## ##_ | _ _| _ | |_ |_ | _ _|_ | _ _ _ _| | | | _ _ _ _| | | | |_| _| | | _ _|## ## _|_ _|_ | | |_ _|_ _ _ _|_| _ |_|_ | _ _| |_ _|_ _|_|_ | _ _ _|_| | |_ |_ _ _| | | | |## ## |_ _ _ _|_ _ _ _ _ | _ |_ |_ _ _ _| | |_ _ | _ | _| | _ _ _|_ _|_ _ _ | | |_ _| |## ##_ _ _|_ _ _ _ _ _ _ _ _ _|_ _ _ _|_ _ _ _ _ _|_ _ _ _ _|_ _ _|_ _|_ _ _ _ _ _ _ _ _ _ _|_|_ _ _ _|## ######################################################################################################