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
######################################################################## ## ## ## ##########
######################################################################## ########
############################################################ ## ## ######
############################################################ #### ######## ########
#################################################### ## ## ## ## ######
#################################################### #### #### ######## ####
############################################ ## ## ## ## ##
############################################ #### ######## #### ############ ####
######################################## ## ## ## ## ##
############################################ #### ######## #### ########
######################################## ## ## ## ## ######
############################################ ############ #### ################
#################################### ## ## ###### ## ## ## ######
#################################### #### #### #################### #### ########
################################ ## ## ############## ## ## ######
#################################### ######## #### #################### ####
################################ ## ## ############## ##
######################################## #### ######################## ####
############################ ## ## ## ## ###### ## ## ##
################################ ######## ############ ######## ########
############################ ## ########## ## ## ######
################################ ################ ######## #### ########
################################ ## ## ########## ## ## ## ##########
######################################## ################ #### ################
######################################## ## ########## ## ## ## ##############
######################################################## ######## #### ############
################################################ ## ## ## ## ##########
################################################ #### #### ########
#################################### ## ## ## ## ## ## ## ######
#################################### #### ############ #### ####
######################## ## ## ## ## ############## ## ## ##
######################## #### ################################ ####
#################### ## ## ## ################################## ## ######
######################## ########################################################
################ ## ## ## ##########################################################
#################### ########################################################################
################ ## ## ##########################################################
######################## #### ########################################################
############ ## ######################################################
################ #### #### ########################################################
############ ## ## ## ##################################################
################ #### ############ ####################################################
############ ## ## ##############################################
################ #### #### #### ################################################
################ ## ## ## ##############################################
######################## ######## ################################################
################ ###### ## ## ##################################################
#################### ####################################################################
######## ## ## ## ######################################################################
######## #### ########################################################################
#### ######################################################################
######## ########################################################################
#### ## ## ## ##########################################################################
######## ####################################################################################
############################## ## ## ##########################################
#### ################################ ########################################
## ############## ## ## ## ## ## ######################################
#### ################ #### ########################################
###### ## ## ## ##################################
######## ######## ############ #### #### ####################################
## ## ## ## ## ## ##################################
#### ######## #### #### ######## #### ####################################
## ## ## ## ## ## ## ##########################
#### #################### #### #### ########################
## ## ## ## ## ## ## ######################
#### #### #### #### ############ ########################
## ## ## ## ## ## ## ## ## ######################
#### #### ############ ################ #### ########################
#### ## ## ## ############## ## ## ## ######################
############ ######## #### ######################## ########################
######## ## ############## ## ## ######################
############ ######################## #### #### ########################
############ ## ## ## ###################### ## ## ######################
#################################################### #### ############################
#################################################### ## ## ##########################
############################################################ ############################
#################################################### ## ##########################
######################################################## ############################
#################################################### ## ## ##########################
######################################################## #### ############################
#################################################### ## ## ## ######################
######################################################## #### ####################
#################################################### ## ##################
######################################################## ######## ####################
######################################################## ## ##################
############################################################ ####################
############################################################ ## ## ## ######################
################################################################################################