Dynamically Sized Maze
Jump to navigation
Jump to search
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.
Since the maze can become very sparse, we use a two-dimensional hash table, instead of an array, to store the cells.
- 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.
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 =
#################### ####################################################
#### ## ## ## ##################################################
#### #### ######## ####################################################
## ## ## ##################################################
#### #### #### #### ################################################
## ## ## ## ##########################################
#### ######################## ########################################
## ## ## ######################################
#### ############ ########################################
#### ## ## ## ## ## ## ######################################
################ ######## ########################################
######## ## ## ## ######################################
############ #### ############ ########################################
######## ## ## ## ## ######################################
############ ######## #### ####################################
############ ## ## ## ##################################
################ ######## ####################################
################ ## ## ## ## ###### ## ############## ## ##############
######################## ############ ################ ############
#################### ###### ## ###### ## ## ## ######
######################## ############ #### #### #### ####
#################### ## ## ## ##
######################## ######## #### #### #### ####
######################## ## ###### ## ## ## ## ## ##
############################ ################ ################ ####
######################## ############## ## ## ############## ##
############################ ############################################ ####
######################## ###################################### ## ##
############################ ######################################## ####
######################## ############################## ## ## ##
############################ ################################ ########
#################### ## ########################## ######
#################### #### ################################ #### ########
################ ########################## ## ## ##########
#################### ################################ ############
#################### ## ## ############################## ##########
################################################################ ############
################################################################ ## ##############
####################################################################################
#################################################### ##################
######################################################## ####################
#################################################### ## ## ## ## ######
######################################################## ####
#################################################### ##
######################################################################## ####
######################################## ## ########## ## ## ##
######################################## ######## ########
#################################### ## ## ## ######
######################################## #### #### ########
#################################### ## ## ## ## ##########
######################################## #### ########################
#################### ## ## ###### ## ######################
#################### ######## ####################################
############ ## ## ## ##########################
############ #### ######## #### ############################
######## ## ###### ## ## ##########################
############ ######## #################### ########################
######## ## ## ###### ######################
################ ######## ################ ########################
############ ## ## ## ## ######################
#################### ######## #### ############################
#### ## ## ## ## ## ## ## ##########################
#### #### #### ############################
## ## ## ## ## ##############################
#### ################ #### ########################################
## ## ## ######################################
################ #### ############################################
#### ## ## ##########################################
######## ######## #### ############################################
#### ## ## ##############################################
######## #### ####################################################
######## ## ## ## ## ##############################################
######################## #### ############################################
#################### ## ##########################################
######################## #### ############################################
#################### ##########################################
######################## ############################################
######################## ## ## ##############################################
################################################################################
######################################################################## ## ## ## ##########
######################################################################## ########
############################################################ ## ## ######
############################################################ #### ######## ########
#################################################### ## ## ## ## ######
#################################################### #### #### ######## ####
############################################ ## ## ## ## ##
############################################ #### ######## #### ############ ####
######################################## ## ## ## ## ##
############################################ #### ######## #### ########
######################################## ## ## ## ## ######
############################################ ############ #### ################
#################################### ## ## ###### ## ## ## ######
#################################### #### #### #################### #### ########
################################ ## ## ############## ## ## ######
#################################### ######## #### #################### ####
################################ ## ## ############## ##
######################################## #### ######################## ####
############################ ## ## ## ## ###### ## ## ##
################################ ######## ############ ######## ########
############################ ## ########## ## ## ######
################################ ################ ######## #### ########
################################ ## ## ########## ## ## ## ##########
######################################## ################ #### ################
######################################## ## ########## ## ## ## ##############
######################################################## ######## #### ############
################################################ ## ## ## ## ##########
################################################ #### #### ########
#################################### ## ## ## ## ## ## ## ######
#################################### #### ############ #### ####
######################## ## ## ## ## ############## ## ## ##
######################## #### ################################ ####
#################### ## ## ## ################################## ## ######
######################## ########################################################
################ ## ## ## ##########################################################
#################### ########################################################################
################ ## ## ##########################################################
######################## #### ########################################################
############ ## ######################################################
################ #### #### ########################################################
############ ## ## ## ##################################################
################ #### ############ ####################################################
############ ## ## ##############################################
################ #### #### #### ################################################
################ ## ## ## ##############################################
######################## ######## ################################################
################ ###### ## ## ##################################################
#################### ####################################################################
######## ## ## ## ######################################################################
######## #### ########################################################################
#### ######################################################################
######## ########################################################################
#### ## ## ## ##########################################################################
######## ####################################################################################
############################## ## ## ##########################################
#### ################################ ########################################
## ############## ## ## ## ## ## ######################################
#### ################ #### ########################################
###### ## ## ## ##################################
######## ######## ############ #### #### ####################################
## ## ## ## ## ## ##################################
#### ######## #### #### ######## #### ####################################
## ## ## ## ## ## ## ##########################
#### #################### #### #### ########################
## ## ## ## ## ## ## ######################
#### #### #### #### ############ ########################
## ## ## ## ## ## ## ## ## ######################
#### #### ############ ################ #### ########################
#### ## ## ## ############## ## ## ## ######################
############ ######## #### ######################## ########################
######## ## ############## ## ## ######################
############ ######################## #### #### ########################
############ ## ## ## ###################### ## ## ######################
#################################################### #### ############################
#################################################### ## ## ##########################
############################################################ ############################
#################################################### ## ##########################
######################################################## ############################
#################################################### ## ## ##########################
######################################################## #### ############################
#################################################### ## ## ## ######################
######################################################## #### ####################
#################################################### ## ##################
######################################################## ######## ####################
######################################################## ## ##################
############################################################ ####################
############################################################ ## ## ## ######################
################################################################################################