Difference between revisions of "Dynamically Sized Maze"
Jump to navigation
Jump to search
m (Foo moved page Dynamically Resized Maze to Dynamically Sized Maze: Better title) |
|||
| Line 63: | Line 63: | ||
== Source code == | == Source code == | ||
<div style="background-color:#eeeeee; border:dashed black 1px; padding:1em"> | |||
<source lang="perl"> | <source lang="perl"> | ||
#!/usr/bin/env perl | #!/usr/bin/env perl | ||
| Line 152: | Line 153: | ||
} | } | ||
</source> | </source> | ||
</div> | |||
== More examples == | == More examples == | ||
Revision as of 16:00, 26 December 2014
This article will describe a technique to build mazes that can grow in all directions.
Since the maze is not limited to a specific shape, it will end up with a very organic appearance.
Example
#################### ## ##################################################################################################################
#################### ## ##################################################################################################################
################ ## ## ## ## ##################################################################################################
#################### ## ## ## ## ## ##################################################################################################
############ ## ##############################################################################################
################ ###################### ##################################################################################################
######## ## ## ###################################################### ## ##################################
############ ###### ########## ###### ########################################################## ## ##################################
######## ## ## ## ## ###### ## ###################################### ##############################
############ ############## ## ## ###### ###### ## ########################################## ## ##################################
######## ## ## ## ## ## ## ################################## ## ## ##############################
############ ## ## ###### ########## ## ###### ## ## ###################################### ## ## ##############################
######## ## ## ## ## ########################## ## ##########################
#################### ## ################################## ################################## ## ###### ##############################
#### ## ## ## ## ## ## ## ############## ## ## ## ## ## ##########################
#### ###### ## ###### ## ############## ## ## ########## ############## ## ## ###### ########## ##############################
## ## ## ## ## ## ## ## ###### ## ## ##########################
#### ###### ###### ############## ## ## ## ###### ###### ## ########## ###### ## ############## ##############################
## ## ## ## ## ## ## ## ## ## ## ## ## ## ###### ## ## ##########
#### ## ###### ############## ## ## ## ## ## ############## ## ###### ###### ###### ###### ## ########## ## ## ##########
#### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
############ ## ## ## ########## ########## ## ## ## ## ###### ########## ################## ###### ###### ###### ## ######
######## ## ## ## ## ## ## ## ## ## ## ## ##
############ ################## ###### ############## ########## ########## ###### ## ## ########################## ###### ######
######## ## ## ## ## ## ## ## ## ## ##
############ ###### ###### ###### ## ###### ## ###### ## ###### ## ###### ###### ############## ## ############## ##########
############ ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
######################## ## ## ## ################## ########## ###### ########## ########## ########## ## ## ###### ##########
################ ## ## ## ## ########## ## ## ## ###### ## ## ##########
################ ## ###### ## ## ################## ## ## ###### ## ###### ## ###### ## ############## ## ##################
############ ## ## ## ############## ## ## ## ## ## ## ## ## ############## ## ##################
############ ## ###### ###### ############################## ## ########## ## ######################################################
######## ## ## ###################### ## ##################################################
############ ###### ## ###### ## ############################## ## ## ## ## ######################################################
######## ## ###### ## ############################## ## ## ## ## ######################################################
############ ## ## ######################################################################################################################
############ ## ## ######################################################################################################################
############################################################################################################################################
Algorithm
The algorithm is a simple recursive backtracker, starting at position {0,0} and growing into all directions.
- Start carving from (x0,y0) into a specific direction.
- Calculate the new coordinates (x1,y1).
- Return if the new position was already visited.
- Repeat the process from the new position, trying all possible directions.
In the normal algorithm the process will terminate when all coordinates were visited.
In our case, however, there is no limit for growth, so we must return after the number of cells reaches the limit.
Since the maze can become very sparse, we use a hash table instead of an array to store the cells.
Source code
#!/usr/bin/env perl
use strict;
use warnings;
no warnings 'recursion';
use List::Util qw/shuffle/;
# Command-line options
my $CELLS = $ARGV[0] || 250;
my $SEED = $ARGV[1] || time();
srand($SEED);
# Constants
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', );
# Variables
my $map = {};
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
my $count = 0;
###
main();
###
sub main {
carve( 0, 0, 'E' );
draw( 0, 0 );
print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
}
sub carve {
my ( $x0, $y0, $direction ) = @_;
my $x1 = $x0 + $DELTA{x}{$direction};
my $y1 = $y0 + $DELTA{y}{$direction};
return if defined $map->{$y1}{$x1}; # already visited
$min_y = $y1 if $y1 < $min_y;
$max_y = $y1 if $y1 > $max_y;
$min_x = $x1 if $x1 < $min_x;
$max_x = $x1 if $x1 > $max_x;
$map->{$y0}{$x0}{$direction} = 1;
$map->{$y1}{$x1} = { $OPPOSITE{$direction} => 1 };
return if $count++ > $CELLS;
for my $new_direction ( shuffle @DIRECTIONS ) {
carve( $x1, $y1, $new_direction );
}
}
sub draw {
my ( $x0, $y0 ) = @_;
for my $y ( $min_y .. $max_y ) {
my ( $line1, $line2 ) = ( '', '' );
for my $x ( $min_x .. $max_x) {
if ( ref $map->{$y}{$x} ) {
$line1 .= $map->{$y}{$x}{E} ? ' ' : ' ##';
$line2 .= $map->{$y}{$x}{S} ? ' ##' : '####';
}
else {
$line1 .= '####';
$line2 .= '####';
}
}
print "$line1\n$line2\n";
}
}
More examples
With few modifications it is possible to transform the maze in a cave, with larger tunnels and circular paths:
#################### ## ##################################################################################################################
#################### ################################################################################################################
################ ## ## ## ## ##################################################################################################
#################### ################################################################################################
############ ## ##############################################################################################
################ #################### ################################################################################################
######## ## ## ###################################################### ## ##################################
############ #### ######## #### ######################################################## ################################
######## ## ## ## ## ###### ## ###################################### ##############################
############ ############ #### #### ######################################## ################################
######## ## ## ## ## ## ## ################################## ## ## ##############################
############ #### ######## #### #################################### ############################
######## ## ## ## ## ########################## ## ##########################
#################### ################################ ################################ #### ############################
#### ## ## ## ## ## ## ## ############## ## ## ## ## ## ##########################
#### #### #### ############ ######## ############ #### ######## ############################
## ## ## ## ## ## ## ## ###### ## ## ##########################
#### #### #### ############ #### #### ######## #### ############ ############################
## ## ## ## ## ## ## ## ## ## ## ## ## ## ###### ## ## ##########
#### #### ############ ############ #### #### #### #### ######## ########
#### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
############ ######## ######## #### ######## ################ #### #### #### ####
######## ## ## ## ## ## ## ## ## ## ## ## ##
############ ################ #### ############ ######## ######## #### ######################## #### ####
######## ## ## ## ## ## ## ## ## ## ##
############ #### #### #### #### #### #### #### #### ############ ############ ########
############ ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
######################## ################ ######## #### ######## ######## ######## #### ########
################ ## ## ## ## ########## ## ## ## ###### ## ## ##########
################ #### ################ #### #### #### ############ ################
############ ## ## ## ############## ## ## ## ## ## ## ## ## ############## ## ##################
############ #### #### ############################ ######## ####################################################
######## ## ## ###################### ## ##################################################
############ #### #### ############################ ####################################################
######## ## ###### ## ############################## ## ## ## ## ######################################################
############ ####################################################################################################################
############ ## ## ######################################################################################################################
############################################################################################################################################