Difference between revisions of "Dynamically Sized Maze"
Jump to navigation
Jump to search
(Created page with "This article will describe a technique to build mazes that can grow in all directions. Since the maze is not circumscribed into a specific shape, it will end up with a very o...") |
|||
| Line 45: | Line 45: | ||
#################################################################################### | #################################################################################### | ||
</pre> | </pre> | ||
== Algorithm == | |||
The algorithm is a simple [Recursive backtracker], starting at position {0,0} and allowed to grow into any direction. | |||
One important thing to note is that the maze can become very sparse; for this reason we use a two-dimensional hash table, instead of array, to store the cells. | |||
== Code == | |||
<code lang="perl"> | |||
#!/usr/bin/env perl | |||
use strict; | |||
use warnings; | |||
no warnings 'recursion'; | |||
use List::Util qw/shuffle/; | |||
my $WIDTH = $ARGV[0] || 30; | |||
my $HEIGHT = $ARGV[1] || 20; | |||
my $SEED = $ARGV[2] || time(); | |||
srand($SEED); | |||
my @DIRECTIONS = qw/N S E W/; | |||
my %DELTA = ( | |||
y => { N => -1, S => 1, E => 0, W => 0 }, | |||
x => { N => 0, S => 0, E => 1, W => -1 }, | |||
); | |||
my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', ); | |||
my $map = {}; | |||
my $count = 0; | |||
carve( 0, 0, 'E' ); | |||
draw( 0, 0 ); | |||
print "$0 $WIDTH $HEIGHT $SEED # resulting in $count cells\n"; | |||
### | |||
sub carve { | |||
my ( $x0, $y0, $dir ) = @_; | |||
my $x1 = $x0 + $DELTA{x}{$dir}; | |||
my $y1 = $y0 + $DELTA{y}{$dir}; | |||
return if defined $map->{$y1}{$x1}; | |||
$map->{$y0}{$x0}{$dir} = 1; | |||
$map->{$y1}{$x1} = { $OPPOSITE{$dir} => 1 }; | |||
$count++; | |||
return if $count > $WIDTH * $HEIGHT; | |||
for my $d ( shuffle @DIRECTIONS ) { | |||
carve( $x1, $y1, $d ); | |||
} | |||
} | |||
sub draw { | |||
my ( $x0, $y0 ) = @_; | |||
for my $y ( $y0 - $HEIGHT / 2 .. $y0 + $HEIGHT / 2 ) { | |||
my ( $line1, $line2 ) = ( '', '' ); | |||
for my $x ( $x0 - $WIDTH / 2 .. $y0 + $WIDTH / 2 ) { | |||
if ( ref $map->{$y}{$x} ) { | |||
$line1 .= $map->{$y}{$x}{E} ? ' ' : ' ##'; | |||
$line2 .= $map->{$y}{$x}{S} ? ' ' : '####'; | |||
} | |||
else { | |||
$line1 .= '####'; | |||
$line2 .= '####'; | |||
} | |||
} | |||
print "$line1\n$line2\n"; | |||
} | |||
} | |||
</code> | |||
Revision as of 18:49, 2 October 2014
This article will describe a technique to build mazes that can grow in all directions.
Since the maze is not circumscribed into a specific shape, it will end up with a very organic appearance.
Here's one example:
################ ## ############## ##########################
######################## ################ ################################
#################### ########## ##########################
############################ ################ ############################
######################## ############## ## ###### ## ##########
############################ #################### ######## ########
################ ## ## ## ################## ## ## ## ######
################ ######################## #### ########
############ ################## ## ## ######
################ #### ######################## #### #### ########
############ ## ## ## ################## ## ## ######
################ ######################## #### ############ ########
############ ################## ## ## ## ######
#################### ######################## #### #### ########
######## ## ## ################## ## ## ## ######
######## ############################ ################ ########
## ## ## ################## ## ## ## ## ##
################################ ################
## ################## ## ## ## ## ##
#################################### #### #### ####
## ## ## ## ## ## ## ## ## ## ## ## ##
#### #### #### #### #### ####
## ## ## ## ## ## ## ## ## ## ## ##
#### #### #### ####################
## ## ## ## ## ## ## ##
######## ######################## #### ############ ############
## ## ########## ## ## ## ## ## ## ##
#### ######################## #### #### ####
## ## ## ############## ## ## ## ##
#### ################ ######################## #### ############
################## ## ## ## ##
#### ############################ ######## ####
#### ## ## ## ## ## ########################## ## ## ## ##
######################################################## #### ####
######################################################## ## ## ##
################################################################
################################################################ ## ## ## ## ##
####################################################################################
Algorithm
The algorithm is a simple [Recursive backtracker], starting at position {0,0} and allowed to grow into any direction.
One important thing to note is that the maze can become very sparse; for this reason we use a two-dimensional hash table, instead of array, to store the cells.
Code
- !/usr/bin/env perl
use strict;
use warnings;
no warnings 'recursion';
use List::Util qw/shuffle/;
my $WIDTH = $ARGV[0] || 30;
my $HEIGHT = $ARGV[1] || 20;
my $SEED = $ARGV[2] || time();
srand($SEED);
my @DIRECTIONS = qw/N S E W/;
my %DELTA = (
y => { N => -1, S => 1, E => 0, W => 0 },
x => { N => 0, S => 0, E => 1, W => -1 },
);
my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', );
my $map = {};
my $count = 0;
carve( 0, 0, 'E' );
draw( 0, 0 );
print "$0 $WIDTH $HEIGHT $SEED # resulting in $count cells\n";
sub carve {
my ( $x0, $y0, $dir ) = @_;
my $x1 = $x0 + $DELTA{x}{$dir};
my $y1 = $y0 + $DELTA{y}{$dir};
return if defined $map->{$y1}{$x1};
$map->{$y0}{$x0}{$dir} = 1;
$map->{$y1}{$x1} = { $OPPOSITE{$dir} => 1 };
$count++;
return if $count > $WIDTH * $HEIGHT;
for my $d ( shuffle @DIRECTIONS ) {
carve( $x1, $y1, $d );
}
}
sub draw {
my ( $x0, $y0 ) = @_;
for my $y ( $y0 - $HEIGHT / 2 .. $y0 + $HEIGHT / 2 ) {
my ( $line1, $line2 ) = ( , );
for my $x ( $x0 - $WIDTH / 2 .. $y0 + $WIDTH / 2 ) {
if ( ref $map->{$y}{$x} ) {
$line1 .= $map->{$y}{$x}{E} ? ' ' : ' ##';
$line2 .= $map->{$y}{$x}{S} ? ' ' : '####';
}
else {
$line1 .= '####';
$line2 .= '####';
}
}
print "$line1\n$line2\n";
}
}