Difference between revisions of "Dynamically Sized Maze"
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
<pre> | <pre> | ||
$ ./dynamic.pl 250 | $ ./dynamic.pl 250 1419689379 | ||
## | ## ! ! ! ! ! !################################################ | ||
## | __ ____ __ _!############################################## | ||
____ _!_!__ _!############################################## | |||
__ _! !####_!################################################ | |||
## | __ __ ! !#################################################### | ||
#### | ##_!____ _!######## ! ! !#################################### | ||
# | #### ! ___!######__ __ ! ! !#### ! !######################## | ||
## | ##__ _! ! ! ! !##____ ! __ ! !__ _!###################### | ||
###### | ##____ ! __ ! !__ !_!_________! _!###################### | ||
######_ | ####__ !_!____ !__ !_!#### ! _! _!###################### | ||
###### | ######_!_!####__ _!##__ _!__ _!###################### | ||
###### | ################_!_!_!####____ _!_!_!######################## | ||
######## | ############################__ ! !############################ | ||
###### | ############################____ _!###### ! ! ! !############ | ||
#### | ##############################__ ! ! ! !__ __ _!########## | ||
## !_ | ##############################__ !_!__ _!########## | ||
############################ ! !_!_!_!_!_!_!##__ _!########## | |||
#################### ! ! ! ! _!############__ _!########## | |||
##_!_!_! | ##################__ __ ! ! _! !##########__ _!########## | ||
########## | ##################__ _!_! _! ! _!########__ ! !########## | ||
########### | ########## ! ! ! ! ! ! !##_! _! ! _! !######____ _!######## | ||
################_ | ########__ ______ !__ _!__ ! __ _!######__ _!######## | ||
##################_! | ########__ !____ !_______!##_!_!_!_! _! ! ! ! ! _!######## | ||
#################### | ########__ ! ! _!##########__ !_! __ _!######## | ||
###################################################### | ########__ ! ! !_! ! _!##########__ _!_!_!_!_!########## | ||
########################################################_!_!_!###### | ########__ _! ! _! _!############_!_!_!#################### | ||
##########_!_____! _! ! !#################################### | |||
##############__ _! __ ! ! ! ! !## ! !###################### | |||
##############__ _! _! ____ !__ _!#################### | |||
################_!_!__ ___! ___! _! ! !#################### | |||
######################_! ! ! ! !____ _!################## | |||
######################__ ___! !_!_!##__ ! ! !################ | |||
######################__ _!####__ __ _!############## | |||
########################_!_!_!_!########_!__ _!## ! !######## | |||
##########################################__ ! !__ ! !###### | |||
##########################################____ ! _!__ _!#### | |||
############################################_____! __ _!#### | |||
############################################## ! ___!_!###### | |||
############################################__ _! ! ! ! !#### | |||
############################################__ ! ______ ! !## | |||
############################################ ! ! __ ! _! _! | |||
##########################################__ _!___! !__ ! _! | |||
##########################################__ !__ !__ _! | |||
##########################################__ !_!_!##_!_!## | |||
############################################_!_!_!############ | |||
</pre> | </pre> | ||
Revision as of 14:10, 27 December 2014
This article will describe a technique to build mazes that can grow in all directions, creating a very organic appearance.
Example
$ ./dynamic.pl 250 1419689379 ## ! ! ! ! ! !################################################ __ ____ __ _!############################################## ____ _!_!__ _!############################################## __ _! !####_!################################################ __ __ ! !#################################################### ##_!____ _!######## ! ! !#################################### #### ! ___!######__ __ ! ! !#### ! !######################## ##__ _! ! ! ! !##____ ! __ ! !__ _!###################### ##____ ! __ ! !__ !_!_________! _!###################### ####__ !_!____ !__ !_!#### ! _! _!###################### ######_!_!####__ _!##__ _!__ _!###################### ################_!_!_!####____ _!_!_!######################## ############################__ ! !############################ ############################____ _!###### ! ! ! !############ ##############################__ ! ! ! !__ __ _!########## ##############################__ !_!__ _!########## ############################ ! !_!_!_!_!_!_!##__ _!########## #################### ! ! ! ! _!############__ _!########## ##################__ __ ! ! _! !##########__ _!########## ##################__ _!_! _! ! _!########__ ! !########## ########## ! ! ! ! ! ! !##_! _! ! _! !######____ _!######## ########__ ______ !__ _!__ ! __ _!######__ _!######## ########__ !____ !_______!##_!_!_!_! _! ! ! ! ! _!######## ########__ ! ! _!##########__ !_! __ _!######## ########__ ! ! !_! ! _!##########__ _!_!_!_!_!########## ########__ _! ! _! _!############_!_!_!#################### ##########_!_____! _! ! !#################################### ##############__ _! __ ! ! ! ! !## ! !###################### ##############__ _! _! ____ !__ _!#################### ################_!_!__ ___! ___! _! ! !#################### ######################_! ! ! ! !____ _!################## ######################__ ___! !_!_!##__ ! ! !################ ######################__ _!####__ __ _!############## ########################_!_!_!_!########_!__ _!## ! !######## ##########################################__ ! !__ ! !###### ##########################################____ ! _!__ _!#### ############################################_____! __ _!#### ############################################## ! ___!_!###### ############################################__ _! ! ! ! !#### ############################################__ ! ______ ! !## ############################################ ! ! __ ! _! _! ##########################################__ _!___! !__ ! _! ##########################################__ !__ !__ _! ##########################################__ !_!_!##_!_!## ############################################_!_!_!############
Source code
#!/usr/bin/env perl
use strict;
use warnings;
no warnings 'uninitialized';
no warnings 'recursion';
use List::Util qw/min max shuffle/;
# Command-line options
my $CELLS = $ARGV[0] || 250;
my $SEED = $ARGV[1] || time();
srand($SEED);
# Constants
my %DIRECTIONS = (
N => { dy => -1, opposite => 'S' },
S => { dy => 1, opposite => 'N' },
E => { dx => 1, opposite => 'W' },
W => { dx => -1, opposite => 'E' },
);
# Variables
my $map = {};
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
my $count = 0;
# Code
carve( 0, 0, 'E' );
print output();
print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
sub carve {
my ( $x0, $y0, $direction ) = @_;
my $x1 = $x0 + $DIRECTIONS{$direction}{dx};
my $y1 = $y0 + $DIRECTIONS{$direction}{dy};
return if defined $map->{$y1}{$x1}; # already visited
$min_x = min( $min_x, $x1 );
$max_x = max( $max_x, $x1 );
$min_y = min( $min_y, $y1 );
$max_y = max( $max_y, $y1 );
$map->{$y0}{$x0}{$direction} = 1;
$map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite} } = 1;
return if $count++ > $CELLS;
for my $new_direction ( shuffle keys %DIRECTIONS ) {
carve( $x1, $y1, $new_direction );
}
}
sub output {
my $output = '';
for my $y ( $min_y .. $max_y ) {
for my $x ( $min_x .. $max_x ) {
if ( ref $map->{$y}{$x} ) {
$output .= $map->{$y}{$x}{S} ? ' ' : '_';
$output .= $map->{$y}{$x}{E} ? ' ' : '!';
}
else {
$output .= '##';
}
}
$output .= "\n";
}
return $output;
}
Description
This is a simple recursive backtracker that starts at position {0,0} and can grow 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 most mazes, the process terminates when all coordinates were visited; but in our case there is no limit for growth, so we must terminate after an arbitrary limit.
Another important point is that, since the maze can become very sparse, we use a hash table instead of an array to store the cells.
Usage
$ ./dynamic.pl [length] [random seed]
More examples
$ ./dynamic.pl 250 1419687187 ################################## ! !######################################## ################################_ ! ! ! !################################## ################################_ !_ _ _ _!################################ ################################_ ! _! _ _!################################ ################################_ ! _ _!################################## ##############################_ _! _!_!#################### ! ! !########## ##############################_ ! ! ! !####################_ _! !###### ##############################_ !_ _ ! !####################_!_! _!#### ##############################_ !_ _!################_ !_!_! _! !## ############################## !_!_! ! _ _!###### ! ! !##_ _!_ !_ _ _ _! ############################_ _ _ _! _!######_ _ _!_ !_ !_ _ _! ##########################_ _! _ _! ! ! !## !_ ! _ _!##_!_ ! !_ _ !_!## ##########################_ ! _ ! _ _ !_ _ _! _! !_ _ _! !_ _!## ##########################_ !_ _!_ _! !_ !_ _!_ _ _! _ _! !_!#### ########################_ _! _ ! !_!_!_ ! _! _ _!_ _!_!###### ########################_ _!_!_!_!_! _!_ !_!_ _ ! !_ _ _!#### ##########################_!_!_!######## !_! _!##_!_!####_ ! _!#### ################################ ! ! !_ _!############_!_!_!_!_!_!###### ##############################_ _ ! !_!_!################################ ################## ! !########_ ! ! ! !_!#################################### ################_ ! ! !##_ _!_ _ _ _! ! !################################ ################_ ! _ _!_ _ _ _ _ _ _!############################## ################_ !_! ! _!##_! !_ _ _ _! _!############################## ################_ !_ _! ! !_ ! _ !_ _!############################ ############ ! !_ _ ! _ !_ !_!_!_!_ _!############################ ##########_ !_ !_!_!_ _!######_!_!_!############################## ##########_ ! !_!######_!_!_!############################################ #### ! !##_ !_!_!_!########################################################## ##_ !_ _!############################################################## _ _!_ !_!################################################################ _ _ _ !_!_!################################################################## _ ! _!#################################################################### _ !_ _!#################################################################### _ _ !_!###################################################################### _ _!###################################################################### ##_!_!########################################################################
$ ./dynamic.pl 250 1419687341 ######## ! !############################################################ #### !_ _!########################################################## ##_ _ _! ! ! ! !###################################################### _ _!_ _ _ ! ! ! ! !############################################## _ !_!_!_ _ _ ! ! ! !######################################## ##_!_!_! _! !##_!_!_ _! _ _!###################################### ######_ _!####_ ! _! _! ! !#################################### ########_!_! _!##_ _! _! _ _!#################### ! !########## ############_! _!##_!_ !_ ! _ _!########## ! !####_ ! ! ! ! !## ############ !_! _!####_ _ _! _!##########_ ! ! !_ ! _! ######## !_ _!######_!_ _ _!#### ! ! !_ ! _ _ ! !_!_!_!_!_!## ######_ !_!_!########## !_ _!##_ _ ! !_!_ _! _!########## ####_ !_!_!######## ! ! ! ! _!##_ ! !_!##_ _!########## ####_ !_! !########_ _ _ _!_ _ _!####_! !_!_!######_!_!_!############ ####_ _!######_ _ ! ! ! ! ! ! !_ _!########################## ######_!_! _!########_!_ _ ! _!########################## ########_ _!############_!_!_!_!_!_ !_!############################ ######_ _ _!#### ! ! ! ! !##########_!_!############################## ######_ _ _!##_ _ _!########################################## ####_ _ _ _! ! ! _!_!_! _!########################################## ####_ _ _ ! _ _ _! !_ _!########################################## ####_ _! _!_! _ _!########################################## ####_ !_! _ _!_ !_!_!_!############################################ ####_ _!####_! _!################################################ ######_!_!_!####_ _ _!################################################ ################_ _ _!################################################ ###### ! ! ! !##_ _!################################################ ## !_ _ !_ _!_!################################################## _ _ !_!_ !_ _ _ _!################################################ _ !_! !_ ! _ ! _!################################################ ##_! _ ! ! ! ! ! _! !############################################## ####_!_! _!_ _! _! _ _!############################################ ######_ _! ! _!_ _! _!############################################ ####_ _ _!_ _!_ ! !_!############################################## ####_ _ ! !_ ! _!############################################## ######_!_ ! ! ! !_!_!################################################ ########_ ! ! !_!#################################################### ########_ !_!_!###################################################### ##########_!_!##########################################################
$ ./dynamic.pl 250 1419687903 ############## ! !###################################################################################################### ########## ! ! _!#################################################################################################### ########_ _ _! _!#################################################################################################### ########_ _ _ !_ _! !######################################################## ! !#################################### ########_ _ _ _! ! _!############################################## ! ! ! ! _!################################## ########_ ! ! _ _! ! _! ! ! !###### ! ! ! !######## ! ! ! !######## ! ! _ ! _! ! ! ! !######################## ########_ _ !_ ! _! ! ! _! ! ! _ _! !##_ _ _ _!####_ _! _!_!_! _!###################### ######## ! ! ! _! _! ! !_ ! ! _ _!_! _! ! _! _ _!####_ _!_!_!######_!_!_!_!_! _!########## ! ! ! !## ###### ! _ _!_ _ _ _! _!_!_!_! _!####_!_! _! ! _!##_ ! ! !##################_! _! !####_ _ _ _! ####_ _! ! ! ! ! !##_!_!########_!_!##########_!_!_!_!_ ! _! ! ! _!##################_! _! !_ _! _! ####_ _ _ ! _ _ _!####################################_!_!_! !_ _! _!####################_!_! _! ! _!_!## ######_ _!_ ! ! _!##########################################_!_! _!########################_!_! ! _!_ _!## ###### !_ _ _ _! _ _!##############################################_!_!_!_!############################_ ! _!## ## ! ! _! !_ _!################################################################################## !_!_! !_!_!#### _ ! ! ! _ _!################################################################################_ ! _!###### ##_!_!_!_!_!_! _!################################################################################_ _! ! !_!######## ##############_!_!##################################################################################_ !_ _!######## ####################################################################################################_ !_!_! ! !###### ######################################################################################################_! ! ! _!#### ######################################################################################################_ ! ! ! _!#### ################################################################################################ ! ! !##_!_!_ !_ _!## ##############################################################################################_ _ !_ _ ! ! ! _!## ################################################################################################_!_ !_ ! ! ! _!## ####################################################################################################_!_!_! ! ! ! ! _!## ########################################################################################################_ _! ! ! _!## ########################################################################################################_ _ !_ ! _!## ##########################################################################################################_ _ !_! _!## ############################################################################################################_ _!## ##############################################################################################################_!_!_!####