Dynamically Sized Maze
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
With few modifications it is possible to transform the maze in a cave, with larger tunnels and circular paths:
#################### ## ##################################################################################################################
#################### ################################################################################################################
################ ## ## ## ## ##################################################################################################
#################### ################################################################################################
############ ## ##############################################################################################
################ #################### ################################################################################################
######## ## ## ###################################################### ## ##################################
############ #### ######## #### ######################################################## ################################
######## ## ## ## ## ###### ## ###################################### ##############################
############ ############ #### #### ######################################## ################################
######## ## ## ## ## ## ## ################################## ## ## ##############################
############ #### ######## #### #################################### ############################
######## ## ## ## ## ########################## ## ##########################
#################### ################################ ################################ #### ############################
#### ## ## ## ## ## ## ## ############## ## ## ## ## ## ##########################
#### #### #### ############ ######## ############ #### ######## ############################
## ## ## ## ## ## ## ## ###### ## ## ##########################
#### #### #### ############ #### #### ######## #### ############ ############################
## ## ## ## ## ## ## ## ## ## ## ## ## ## ###### ## ## ##########
#### #### ############ ############ #### #### #### #### ######## ########
#### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
############ ######## ######## #### ######## ################ #### #### #### ####
######## ## ## ## ## ## ## ## ## ## ## ## ##
############ ################ #### ############ ######## ######## #### ######################## #### ####
######## ## ## ## ## ## ## ## ## ## ##
############ #### #### #### #### #### #### #### #### ############ ############ ########
############ ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ######
######################## ################ ######## #### ######## ######## ######## #### ########
################ ## ## ## ## ########## ## ## ## ###### ## ## ##########
################ #### ################ #### #### #### ############ ################
############ ## ## ## ############## ## ## ## ## ## ## ## ## ############## ## ##################
############ #### #### ############################ ######## ####################################################
######## ## ## ###################### ## ##################################################
############ #### #### ############################ ####################################################
######## ## ###### ## ############################## ## ## ## ## ######################################################
############ ####################################################################################################################
############ ## ## ######################################################################################################################
############################################################################################################################################