Difference between revisions of "Dynamically Sized Maze"
Jump to navigation
Jump to search
| Line 91: | Line 91: | ||
# Repeat the process from the new position, trying all possible directions. | # Repeat the process from the new position, trying all possible directions. | ||
In | In a regular recursive backtracker, 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. | In our case, however, there is no limit for growth, so we must return after the number of cells reaches the limit. | ||
Revision as of 13:38, 27 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
./dynamic.pl 500 1419687417 ############################################################################################## ! ! !################## ############################################################################################_ _ _!################ ############################################################################################_ ! ! ! !################ ######################################################################################## !_ _! !_ ! !############## ######################################################################################_ ! !_ _ !_ ! ! !########## #################################################################################### !_ !_ _! _ _! ! _!######## ##################################################################################_ _ _! _ !_! _ _! ! _!######## ##################################################################################_ ! !_ !_ _ _! _ _! _!######## #################### ! ! ! ! !## ! ! ! !############################################_! !_ _ _ ! !_ _ ! _ _!######## ##################_ _ !_ _ _!##########################################_ ! ! !_ _!######## ##################_ !_!_!_ ! !_!_ ! ! !##########################################_!_!_! ! !_!_!_! ! _!######## ##################_ _!##_ !_!##_ _ _!########################################_ _ !_!_!####_ _ _!######## ############## ! !_ _!####_!_!######_!_ ! ! ! !####################################_ !_! !######_ _!########## ############_ ! _!################_ _ ! ! !############ ! !####################_! _ _!####_ ! ! !######## ##########_ _!_ _!_!####################_ !_ ! !########_ ! ! !#### ! !#### ! ! !_! _!####_ _ ! ! ! !## ##########_ ! _!######################_!_!_ _ ! !######_ ! ! ! !_ ! !_ !_!########_!_ _ _ _! ############_!_ _! _!############################_ _ _!####_ ! ! !_ _ _ _!_ !_ !_!_!_!_!##############_!_ _ _! ##########_ _ ! _!#################### ! ! ! ! _ _!##_ _! !_ !_ _ ! !_ _!#################### ! !_ _! ############_!_ !_! _!################_ _ _ !_ _!_ !_ _ !_! _ ! !_ _ _ _!##################_ _ _! ##############_ ! !_! _!################_ _ _ !_ _ _ _!_ !_!##_ ! !_! _! ! _ _!######## ! ! ! ! ! ! _!_!_!## ##############_ _ !_ _!################ ! ! ! !_ ! !_ _ _!_ ! _ _! ! ! ! _! !#### ! ! _ _!###### ################_ _!##############_ _ _ _!_ ! _! !_ _! ! _! ! ! ! ! _! ! _! ! _!_!_!_!######## ##################_!_!_!################_ _ ! !_!_!_!_!_!_ _ _ _! ! ! !_ ! _! _!############## ##########################################_!_!_!_ _!######## !_ _!_!_!_ !_ _!_!_!_!_!_!##_!_!################ ##################################################_!_!########_ ! _!####_ _!################################ ############################################################ ! ! !_ _!######_!_!_!################################## ##########################################################_ _ _!_!################################################ ########################################################## ! _!_!#################################################### ########################################################_ _ _!###################################################### ########################################################_ _!######################################################## ########################################################_ _!######################################################## ########################################################_ ! !######################################################## ########################################################_ _ _!###################################################### ##########################################################_ _!###################################################### ################################################## ! !#### ! _!###################################################### ################################################_ _! ! _ _!###################################################### ################################################ ! !_ _!######################################################## ##############################################_ _ _!_!_!_!########################################################## ##############################################_ ! !################################################################## ##############################################_ _ ! !################################################################ ################################## ! ! ! ! ! ! !_ _ _!############################################################## ################################_ _ _ _ _ _ _! ! _!############################################################## ################################_ _ !_ !_ ! _! !############################################################## ##################################_!_!_ _ _ ! _!_ _ _!############################################################ #################################### ! ! ! ! !_ ! _ _!############################################################ ##################################_ _ _ ! ! ! !_!############################################################## ################################## !_ _!_!_! !_!_ _!############################################################## ############################ ! !_ _ _!##_ _!_ _!############################################################## ##########################_ _! _!_!####_ _! ! ! !############################################################## #################### ! ! ! ! ! _! _!####_ _! !_ _!############################################################ ##################_ _ _ ! ! _! _!####_ ! _!############################################################ ##################_ _ _ ! ! ! _! _!######_!_!_!_!_!_!############################################################## ################## ! ! _! ! _!################################################################################ ################_ _ _!_!_!_!_!_!################################################################################## ############## ! ! _!_!############################################################################################## ############_ _ _ _!################################################################################################ ############ !_ _ ! !################################################################################################ ########## ! _!_ _!############################################################################################## ########_ _!_ _ _ _!############################################################################################## ########_ ! _ _!_!################################################################################################ ########_ _! _ _!################################################################################################## ##########_!_ _ _!################################################################################################## ############_ _ _!################################################################################################## ############ ! _!#################################################################################################### ##########_ _ _!#################################################################################################### ## ! ! ! ! ! _!###################################################################################################### _ _ _ _ ! _!###################################################################################################### _ _ ! _! _!###################################################################################################### ##_!_ ! ! _ _!###################################################################################################### ####_ !_ _ _!######################################################################################################## ####_ _ _!########################################################################################################## ######_ _!########################################################################################################## ########_!############################################################################################################
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 a regular recursive backtracker, 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 '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' );
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 + $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 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
$ ./dynamic.pl 250 1419687187 ################################## ! !######################################## ################################_ ! ! ! !################################## ################################_ !_ _ _ _!################################ ################################_ ! _! _ _!################################ ################################_ ! _ _!################################## ##############################_ _! _!_!#################### ! ! !########## ##############################_ ! ! ! !####################_ _! !###### ##############################_ !_ _ ! !####################_!_! _!#### ##############################_ !_ _!################_ !_!_! _! !## ############################## !_!_! ! _ _!###### ! ! !##_ _!_ !_ _ _ _! ############################_ _ _ _! _!######_ _ _!_ !_ !_ _ _! ##########################_ _! _ _! ! ! !## !_ ! _ _!##_!_ ! !_ _ !_!## ##########################_ ! _ ! _ _ !_ _ _! _! !_ _ _! !_ _!## ##########################_ !_ _!_ _! !_ !_ _!_ _ _! _ _! !_!#### ########################_ _! _ ! !_!_!_ ! _! _ _!_ _!_!###### ########################_ _!_!_!_!_! _!_ !_!_ _ ! !_ _ _!#### ##########################_!_!_!######## !_! _!##_!_!####_ ! _!#### ################################ ! ! !_ _!############_!_!_!_!_!_!###### ##############################_ _ ! !_!_!################################ ################## ! !########_ ! ! ! !_!#################################### ################_ ! ! !##_ _!_ _ _ _! ! !################################ ################_ ! _ _!_ _ _ _ _ _ _!############################## ################_ !_! ! _!##_! !_ _ _ _! _!############################## ################_ !_ _! ! !_ ! _ !_ _!############################ ############ ! !_ _ ! _ !_ !_!_!_!_ _!############################ ##########_ !_ !_!_!_ _!######_!_!_!############################## ##########_ ! !_!######_!_!_!############################################ #### ! !##_ !_!_!_!########################################################## ##_ !_ _!############################################################## _ _!_ !_!################################################################ _ _ _ !_!_!################################################################## _ ! _!#################################################################### _ !_ _!#################################################################### _ _ !_!###################################################################### _ _!###################################################################### ##_!_!########################################################################
$ ./dynamic.pl 250 1419687341 ######## ! !############################################################ #### !_ _!########################################################## ##_ _ _! ! ! ! !###################################################### _ _!_ _ _ ! ! ! ! !############################################## _ !_!_!_ _ _ ! ! ! !######################################## ##_!_!_! _! !##_!_!_ _! _ _!###################################### ######_ _!####_ ! _! _! ! !#################################### ########_!_! _!##_ _! _! _ _!#################### ! !########## ############_! _!##_!_ !_ ! _ _!########## ! !####_ ! ! ! ! !## ############ !_! _!####_ _ _! _!##########_ ! ! !_ ! _! ######## !_ _!######_!_ _ _!#### ! ! !_ ! _ _ ! !_!_!_!_!_!## ######_ !_!_!########## !_ _!##_ _ ! !_!_ _! _!########## ####_ !_!_!######## ! ! ! ! _!##_ ! !_!##_ _!########## ####_ !_! !########_ _ _ _!_ _ _!####_! !_!_!######_!_!_!############ ####_ _!######_ _ ! ! ! ! ! ! !_ _!########################## ######_!_! _!########_!_ _ ! _!########################## ########_ _!############_!_!_!_!_!_ !_!############################ ######_ _ _!#### ! ! ! ! !##########_!_!############################## ######_ _ _!##_ _ _!########################################## ####_ _ _ _! ! ! _!_!_! _!########################################## ####_ _ _ ! _ _ _! !_ _!########################################## ####_ _! _!_! _ _!########################################## ####_ !_! _ _!_ !_!_!_!############################################ ####_ _!####_! _!################################################ ######_!_!_!####_ _ _!################################################ ################_ _ _!################################################ ###### ! ! ! !##_ _!################################################ ## !_ _ !_ _!_!################################################## _ _ !_!_ !_ _ _ _!################################################ _ !_! !_ ! _ ! _!################################################ ##_! _ ! ! ! ! ! _! !############################################## ####_!_! _!_ _! _! _ _!############################################ ######_ _! ! _!_ _! _!############################################ ####_ _ _!_ _!_ ! !_!############################################## ####_ _ ! !_ ! _!############################################## ######_!_ ! ! ! !_!_!################################################ ########_ ! ! !_!#################################################### ########_ !_!_!###################################################### ##########_!_!##########################################################