Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
 
(42 intermediate revisions by 6 users not shown)
Line 1: Line 1:
This article will describe a technique to build mazes that can grow in all directions.
This article will describe a technique to build mazes that can grow without limits in all directions, differently from a traditional maze that is bounded by its outer walls.
 
Since the maze is not limited to a specific shape, it will end up with a very organic appearance.


=== Example ===
=== Example ===


<pre>
<pre>
############################                 ##################################
$ ./dynamic.pl 250 1419689539
################################   ####   ####################################
######################################################
############################         ##     ##################################
############ ! ! ! !##################################
####################################       ####################################
##########_    _  _!################################
############################         ##     ##################################
############_!_!  _ _! !##############################
################################   ####   ####################################
############_  _!  _  _! !##########################
############################ ##     ##         ##############################
############_    ! ! !_ _  _!########################
############################   ####   ####   ################################
##############_! ! !  !  _ _!###### ! ! ! !##########
########################             ## ##         ##########################
############_  _!_ _! !_  _!## ! !  !    _! ! !####
############################   ########   ####   ############################
############_    _!  _!  _ _!_  _ _!_ _!_ _ _  _!##
########################     ##             ##     ##########################
##############_!  _!  _!    _!_  ! ! !  _ _  !  _ _!##
############################       ####           ############################
##############_  !  _ _!_!  _! !_ _  ! !  _! !    _!##
########################     ## ##     ## ##         ######################
##############_  !  _!##_  _!  _  ! ! !  _ _!_!  _!##
############################   ####   ####   ####   ########################
##############_    _!##_      !  _! ! !_  !  !  _!##
########################     ##      ## ## ##         ######################
################_!_!######_!_!_!_  ! ! !_    !    _!##
############################       ####       ################################
############################_  _ _! !  _!_!_!_!_!####
########################         ##         ## ## ##  ######################
############################_        !  _!############
############################        ####    ####            ####################
##############################_!_!_!_!  _!############
############################  ##  ##      ##              ##  ##  ##############
##################################_    _!############
########################################    ####    ####            ############
######################## ! ! ! ! !_  !_!##############
####################################          ##  ##  ##          ##  ##  ######
#################### !_ _ _  !  _  !  _!##############
############################################            ########            ####
##################_    _  ! !_  !    _! ! !##########
########################################          ##  ##      ##              ##
##################_  !_  ! !_  ! !_!_!  _  _!########
####################################################            ########    ####
##################_  ! ! !_ _! ! !  !  _!  _!########
########  ##################  ##  ##  ##  ##  ##      ##  ##  ##              ##
##################_ _  !_      !  !    _!  _!########
########    ################                                        ####    ####
############ ! !##_  _ _!_!_!_!_!_!_!_!_  _!########
####          ##########  ##      ##              ##  ##  ##          ##  ######
########## !    _! !  _!################_  _!########
########    ############                ####                ####    ############
######## !  _!_ _    _!##############_    _!########
####          ######          ##          ##  ##  ##          ##  ##############
#### ! !  _!    _!_!_!################_  !_!##########
########    ############    ########    ############        ####################
##_  _ _!  _!  _!#### ! ! !########_  _ _! !########
              ######              ##  ##############  ##  ######################
##_ _ _  ! !_  ! ! !_  _  ! ! ! !##_    _  _!######
####    ####################    ################################################
####_  _!  !_        !_    _  ! !##_!_!    _!######
              ######              ##############################################
####_ _  !_!  !_!_!_!_!##_!_! !_  !_     !_!########
####        ############    ####################################################
######_  ! !_!  _!##########_  _ _!_  !_!_!##########
####  ##      ##  ##  ##      ##################################################
######_        _!##########_  _  !    _!############
########    ####            ####################################################
########_!_!_!_!##############_!_    !_!##############
####                          ##################################################
##################################_!_!################
########                    ####################################################
######################################################
########  ##  ##  ##  ##  ######################################################
################################################################################
</pre>
</pre>
== 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 ==
== Source code ==


<div style="background-color:#eeeeee; border:dashed black 1px; padding:1em">
<source lang="perl">
<source lang="perl">
#!/usr/bin/env perl
#!/usr/bin/env perl
Line 71: Line 53:
use warnings;
use warnings;


no warnings 'uninitialized';
no warnings 'recursion';
no warnings 'recursion';


use List::Util qw/shuffle/;
use List::Util qw/min max shuffle/;


# Command-line options
# Command-line options
Line 84: Line 67:
# Constants
# Constants


my @DIRECTIONS = qw/N S E W/;
my %DIRECTIONS = (
 
     N => { dy => -1, opposite => 'S' },
my %DELTA = (
    S => { dy => 1, opposite => 'N' },
     y => { N => -1, S => 1, E => 0, W => 0 },
     E => { dx => 1opposite => 'W' },
     x => { N => 0S => 0, E => 1, W => -1 },
    W => { dx => -1, opposite => 'E' },
);
);
my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', );


# Variables
# Variables
Line 99: Line 80:
my $count = 0;
my $count = 0;


###
# Code


main();
carve( 0, 0, 'E' );
print output();


###
print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
 
sub main {
    carve( 0, 0, 'E' );
    draw( 0, 0 );
    print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
}


sub carve {
sub carve {
     my ( $x0, $y0, $direction ) = @_;
     my ( $x0, $y0, $direction ) = @_;


     my $x1 = $x0 + $DELTA{x}{$direction};
     my $x1 = $x0 + $DIRECTIONS{$direction}{dx};
     my $y1 = $y0 + $DELTA{y}{$direction};
     my $y1 = $y0 + $DIRECTIONS{$direction}{dy};


     return if defined $map->{$y1}{$x1};    # already visited
     return if defined $map->{$y1}{$x1};    # already visited


     $min_y = $y1 if $y1 < $min_y;
     $min_x = min( $min_x, $x1 );
     $max_y = $y1 if $y1 > $max_y;
     $max_x = max( $max_x, $x1 );


     $min_x = $x1 if $x1 < $min_x;
     $min_y = min( $min_y, $y1 );
     $max_x = $x1 if $x1 > $max_x;
     $max_y = max( $max_y, $y1 );


     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y1}{$x1} = { $OPPOSITE{$direction} => 1 };
     $map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite} } = 1;


     return if $count++ > $CELLS;
     return if $count++ > $CELLS;


     for my $new_direction ( shuffle @DIRECTIONS ) {
     for my $new_direction ( shuffle keys %DIRECTIONS ) {
         carve( $x1, $y1, $new_direction );
         carve( $x1, $y1, $new_direction );
     }
     }
}
}


sub draw {
sub output {
     my ( $x0, $y0 ) = @_;
     my $output = '';
 
     for my $y ( $min_y - 1 .. $max_y + 1 ) {
     for my $y ( $min_y .. $max_y ) {
         for my $x ( $min_x - 1 .. $max_x + 1 ) {
        my ( $line1, $line2 ) = ( '', '' );
         for my $x ( $min_x .. $max_x) {
             if ( ref $map->{$y}{$x} ) {
             if ( ref $map->{$y}{$x} ) {
                 $line1 .= $map->{$y}{$x}{E} ? '   ' : ' ##';
                 $output .= $map->{$y}{$x}{S} ? ' ' : '_';
                 $line2 .= $map->{$y}{$x}{S} ? '   ' : '####';
                 $output .= $map->{$y}{$x}{E} ? ' ' : '!';
             }
             }
             else {
             else {
                 $line1 .= '####';
                 $output .= '##';
                $line2 .= '####';
             }
             }
         }
         }
         print "$line1\n$line2\n";
         $output .= "\n";
     }
     }
    return $output;
}
}
</source>
</source>
</div>
=== Description ===
# Start carving from (x0,y0) into a random 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.
It is important to count the number of steps ($count), so we can exit the routine when the maze reaches the desired size ($CELLS). (Otherwise the maze would keep growing forever). Since the maze can become very sparse, we store the positions in a hash table instead of an array.
=== Usage ===
<pre>
$ ./dynamic.pl [length] [random seed]
</pre>


=== More examples ===
=== More examples ===


<pre>
<pre>
####################           ####################################################
$ ./dynamic.pl 250 1419687187
#### ## ##         ##         ##################################################
################################## ! !########################################
####       ####   ########   ####################################################
################################_    ! ! ! !##################################
              ##     ##     ## ##################################################
################################_  !_ _ _  _!################################
####   ####   ####       ####   ################################################
################################_  !  _!  _ _!################################
      ##             ##         ## ## ##########################################
################################_  !  _  _!##################################
####   ########################           ########################################
##############################_  _!  _!_!#################### ! ! !##########
              ##             ## ##         ######################################
##############################_  ! ! ! !####################_      _! !######
####           ############               ########################################
##############################_  !_ _  ! !####################_!_!      _!####
#### ##  ##     ##         ## ## ##     ######################################
##############################_      !_  _!################_    !_!_! _! !##
################       ########           ########################################
############################## !_!_! !  _ _!###### ! ! !##_  _!_  !_ _ _  _!
########         ##             ## ##     ######################################
############################_  _ _ _!  _!######_  _  _!_    !_  !_  _  _!
############   ####   ############       ########################################
##########################_  _!  _ _! ! ! !## !_  !  _ _!##_!_  ! !_ _  !_!##
########         ##         ##     ## ## ######################################
##########################_  !  _  !  _ _  !_  _ _!  _! !_  _ _! !_    _!##
############       ########       ####       ####################################
##########################_  !_ _!_ _!  !_    !_  _!_  _ _!  _ _!  !_!####
############ ##         ##     ##             ##################################
########################_  _!  _      !  !_!_!_  !    _!  _ _!_  _!_!######
################                   ########   ####################################
########################_      _!_!_!_!_!    _!_    !_!_ _  !  !_ _  _!####
################ ## ## ## ## ###### ##     ############## ##  ##############
##########################_!_!_!######## !_!  _!##_!_!####_    !        _!####
########################   ############       ################       ############
################################ ! ! !_      _!############_!_!_!_!_!_!######
####################         ######         ## #######         ## #######
##############################_  _  !  !_!_!################################
########################    ############   ####   ####   ####               ####
################## ! !########_  ! ! ! !_!####################################
####################             ##             ##             ##             ##
################_    ! ! !##_  _!_ _ _ _! ! !################################
########################       ########   ####   ####               ####   ####
################_  ! _  _!_  _ _  _ _ _  _!##############################
########################  ##     ###### ##             ## ## ## ##         ##
################_  !_! !  _!##_!  !_ _ _ _!  _!##############################
############################   ################           ################   ####
################_  !_  _! ! !_  !      _  !_  _!############################
########################         ############## ## ## ##############         ##
############ ! !_ _  !    _  !_  !_!_!_!_      _!############################
############################   ############################################   ####
##########_    !_    !_!_!_      _!######_!_!_!##############################
########################         ###################################### ##     ##
##########_  !    !_!######_!_!_!############################################
############################   ########################################       ####
#### ! !##_ !_!_!_!##########################################################
########################         ##############################  ## ##          ##
##_    !_    _!##############################################################
############################    ################################            ########
_  _!_    !_!################################################################
####################  ##          ##########################                  ######
_ _ _  !_!_!##################################################################
####################    ####    ################################    ####    ########
_    !  _!####################################################################
################                  ##########################      ##  ##  ##########
_  !_  _!####################################################################
####################            ################################        ############
_ _ !_!######################################################################
####################  ##  ##  ##############################              ##########
_    _!######################################################################
################################################################       ############
##_!_!########################################################################
################################################################  ##  ##############
####################################################################################
</pre>
</pre>


<pre>
<pre>
####################################################         ##################
$ ./dynamic.pl 250 1419687341
########################################################   ####################
######## ! !############################################################
####################################################     ## ## ## ## ######
#### !_    _!##########################################################
########################################################                   ####
##_  _ _! ! ! ! !######################################################
####################################################                         ##
_  _!_ _    _  ! ! ! ! !##############################################
########################################################################   ####
_        !_!_!_    _ _  ! ! ! !########################################
########################################  ##  ##########  ##     ##         ##
##_!_!_!  _! !##_!_!_  _!  _  _!######################################
########################################       ########               ########
######_      _!####_  !  _!  _! ! !####################################
####################################             ## ##     ##          ######
########_!_!    _!##_  _!  _!  _  _!#################### ! !##########
########################################       ####       ####       ########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
####################################     ##     ##         ## ## ##########
############ !_! _!####_  _ _! _!##########_    ! ! !_ !          _!
########################################       ####   ########################
######## !_      _!######_!_  _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
#################### ## ## ######     ##             ######################
######_      !_!_!########## !_  _!##_  _  !  !_!_  _!  _!##########
####################           ########   ####################################
####_    !_!_!######## ! ! !  !  _!##_    !  !_!##_      _!##########
############ ## ##             ##                 ##########################
####_  !_! !########_  _ _ _!_ _ _!####_! !_!_!######_!_!_!############
############           ####   ########    ####   ############################
####_      _!######_  _  ! ! ! ! ! ! !_  _!##########################
########             ##         ###### ##     ##  ##########################
######_!_!  _!########_!_          _  !    _!##########################
############   ########   ####################       ########################
########_  _!############_!_!_!_!_!_    !_!############################
########         ## ##             ######             ######################
######_  _ _!#### ! ! ! ! !##########_!_!##############################
################       ########   ################   ########################
######_ _  _!##_  _      _!##########################################
############         ##     ##         ## ##         ######################
####_  _ _ _! ! !  _!_!_!  _!##########################################
####################       ########   ####       ############################
####_ _ _  !  _  _ _! !_  _!##########################################
#### ## ## ## ## ## ##         ##             ##########################
####_    _!  _!_!  _      _!##########################################
####                               ####   ####   ############################
####_  !_!  _ _!_   !_!_!_!############################################
                      ## ## ## ##         ## ##############################
####_      _!####_! _!################################################
####   ################       ####   ########################################
######_!_!_!####_  _ _!################################################
                  ##     ## ##         ######################################
################_ _  _!################################################
################   ####           ############################################
###### ! ! ! !##_    _!################################################
####             ##     ##         ##########################################
## !_    _  !_  _!_!##################################################
########   ########       ####   ############################################
_  _  !_!_  !_ _ _  _!################################################
####                 ##     ## ##############################################
_    !_! !_  !  _  !  _!################################################
########           ####   ####################################################
##_!    _  ! ! ! ! !  _! !##############################################
########  ##  ##  ##          ##  ##############################################
####_!_!  _!_ _!  _!  _  _!############################################
########################    ####    ############################################
######_ _!  !  _!_ _!    _!############################################
####################      ##          ##########################################
####_  _ _!_ _!_    ! !_!##############################################
########################    ####    ############################################
####_  _  !  !_  !    _!##############################################
####################                  ##########################################
######_!_  ! ! !  !_!_!################################################
########################            ############################################
########_  ! !  !_!####################################################
########################  ##  ##  ##############################################
########_    !_!_!######################################################
################################################################################
##########_!_!##########################################################
</pre>
</pre>


<pre>
<pre>
######################################################################## ## ## ## ##########
$ ./dynamic.pl 250 1419687903
########################################################################               ########
############## ! !######################################################################################################
############################################################ ## ##                     ######
########## ! !    _!####################################################################################################
############################################################       ####   ########   ########
########_  _ _!  _!####################################################################################################
#################################################### ##             ## ##         ## ######
########_ _ _  !_  _! !######################################################## ! !####################################
####################################################   ####    ####           ########   ####
########_  _ _ _! !   _!############################################## ! ! ! !    _!##################################
############################################ ##             ##     ## ##                 ##
########_  ! !  _ _! !  _! ! ! !###### ! ! ! !######## ! ! ! !######## !  !  _  !    _! ! ! ! !########################
############################################   ####   ########   ####   ############    ####
########_ _  !_  !  _! !  !   _! ! !  _    _! !##_  _ _  _!####_  _!    _!_!_!            _!######################
########################################             ##         ##     ##     ##         ##
######## ! ! !  _!  _! ! !_  !    !  _ _!_!      _! !  _!  _ _!####_  _!_!_!######_!_!_!_!_!    _!########## ! ! ! !##
############################################           ####   ########       ####   ########
###### !  _ _!_ _ _ _!    _!_!_!_!    _!####_!_!        _! !    _!##_  ! ! !##################_!    _! !####_  _ _  _!
########################################     ## ## ##                 ##             ######
####_  _! ! ! ! ! !##_!_!########_!_!##########_!_!_!_!_    !    _! ! !    _!##################_!      _! !_  _!    _!
############################################   ############           ####   ################
####_ _ _  !  _ _  _!####################################_!_!_!    !_ _!  _!####################_!_!      _! !  _!_!##
#################################### ##         ## ###### ## ## ##                 ######
######_  _!_  ! !  _!##########################################_!_!        _!########################_!_! !  _!_  _!##
####################################   ####    ####    ####################   ####   ########
###### !_ _ _ _!  _ _!##############################################_!_!_!_!############################_   !      _!##
################################             ##         ## ############## ##     ##  ######
## ! !   _!  !_  _!################################################################################## !_!_! !_!_!####
####################################   ########       ####   ####################       ####
_      !    ! ! _ _!################################################################################_    !    _!######
################################         ##     ##             ##############             ##
##_!_!_!_!_!_!    _!################################################################################_  _! ! !_!########
########################################       ####           ########################   ####
##############_!_!##################################################################################_  !_    _!########
############################             ##     ## ## ##         ###### ## ##         ##
####################################################################################################_    !_!_! ! !######
################################   ########   ############       ########           ########
######################################################################################################_! !  !    _!####
############################             ##     ########## ##     ##                 ######
######################################################################################################_    ! ! !  _!####
################################               ################   ########   ####   ########
################################################################################################ ! ! !##_!_!_  !_  _!##
################################ ## ##         ##########         ## ##     ## ##########
##############################################################################################_  _  !_  _  ! ! !  _!##
########################################       ################   ####       ################
################################################################################################_!_      !_ ! ! ! _!##
######################################## ## ########## ##         ##     ## ##############
####################################################################################################_!_!_! ! ! ! ! _!##
########################################################   ########       ####   ############
########################################################################################################_  _! ! ! _!##
################################################ ##                 ## ##     ## ##########
########################################################################################################_ _  !_  !  _!##
################################################   ####           ####               ########
##########################################################################################################_ _  !_!  _!##
####################################  ## ##             ## ## ##         ##     ## ######
############################################################################################################_      _!##
####################################       ####           ############       ####       ####
##############################################################################################################_!_!_!####
########################  ## ##                  ##  ##  ############## ## ##             ##
########################       ####               ################################       ####
####################                 ##  ## ##  ################################## ## ######
########################               ########################################################
################         ## ### ##########################################################
####################   ########################################################################
################             ## ## ##########################################################
########################    ####        ########################################################
############          ##                  ######################################################
################        ####    ####    ########################################################
############      ##      ##      ##          ##################################################
################    ####    ############    ####################################################
############          ##              ##          ##############################################
################        ####    ####    ####    ################################################
################  ##      ##  ##                  ##############################################
########################    ########            ################################################
################              ######  ##  ##  ##################################################
####################        ####################################################################
########  ##  ##      ##  ######################################################################
########        ####    ########################################################################
####                      ######################################################################
########                ########################################################################
####      ##  ##  ##  ##########################################################################
########    ####################################################################################
              ##############################  ##  ##  ##########################################
####        ################################            ########################################
      ##  ##############  ##  ##  ##  ##  ##              ######################################
####    ################                        ####    ########################################
              ######  ##                  ##      ##          ##################################
########    ########        ############    ####    ####    ####################################
              ##  ##      ##      ##          ##      ##      ##################################
####    ########        ####    ####    ########    ####    ####################################
      ##                      ##      ##      ##  ##          ##  ##  ##########################
####        ####################    ####                    ####        ########################
      ##      ##                  ##      ##      ##  ##  ##              ######################
####    ####                    ####    ####            ############    ########################
              ##  ##  ##  ##  ##          ##  ##  ##              ##      ######################
####        ####    ############    ################        ####        ########################
####  ##  ##          ##              ##############  ##  ##      ##      ######################
############    ########    ####    ########################            ########################
########                      ##  ##############              ##  ##      ######################
############                ########################    ####    ####    ########################
############  ##  ##  ##  ######################          ##  ##          ######################
####################################################        ####    ############################
####################################################  ##      ##      ##########################
############################################################        ############################
####################################################          ##      ##########################
########################################################            ############################
####################################################      ##  ##      ##########################
########################################################    ####    ############################
####################################################          ##  ##  ##  ######################
########################################################    ####            ####################
####################################################          ##              ##################
########################################################        ########    ####################
########################################################  ##                  ##################
############################################################                ####################
############################################################  ##  ##  ##  ######################
################################################################################################
</pre>
</pre>


[[Category:Developing]]
=== Advantages ===
 
The main advantage of this technique is that, since cells are stored in a hash, memory usage grows only one cell at a time.
 
It is also easily customizable because this technique is just one (recursive backtracker covered by one cell long dead-ends) of the many possible implementations of the Growing tree algorithm described by Walter D. Pullen on Think Labyrinth [http://www.astrolog.org/labyrnth/algrithm.htm]. With only a few minor changes, the results can be very different. "For example, if you always pick the most recent cell added to it, this algorithm turns into the recursive backtracker. If you always pick cells at random, this will behave similarly but not exactly to Prim's algorithm. If you always pick the oldest cells added to the list, this will create Mazes with about as low a river factor as possible, even lower than Prim's algorithm. If you usually pick the most recent cell, but occasionally pick a random cell, the Maze will have a high river factor but a short direct solution. If you randomly pick among the most recent cells, the Maze will have a low river factor but a long windy solution."
 
If you remove the inner walls, you get a [[Dynamically Sized Cave]].
 
[[Category:Developing]][[Category:Articles]][[Category:Maps]]

Latest revision as of 15:25, 14 April 2021

This article will describe a technique to build mazes that can grow without limits in all directions, differently from a traditional maze that is bounded by its outer walls.

Example

$ ./dynamic.pl 250 1419689539
######################################################
############ ! ! ! !##################################
##########_     _   _!################################
############_!_!  _ _! !##############################
############_   _!  _   _! !##########################
############_    ! ! !_ _   _!########################
##############_! ! !   !  _ _!###### ! ! ! !##########
############_   _!_ _! !_   _!## ! !   !    _! ! !####
############_     _!  _!  _ _!_   _ _!_ _!_ _ _   _!##
##############_!  _!  _!    _!_  ! ! !  _ _  !  _ _!##
##############_  !  _ _!_!  _! !_ _  ! !  _! !    _!##
##############_  !  _!##_   _!  _  ! ! !  _ _!_!  _!##
##############_     _!##_      !  _! ! !_  !   !  _!##
################_!_!######_!_!_!_  ! ! !_    !    _!##
############################_   _ _! !  _!_!_!_!_!####
############################_        !  _!############
##############################_!_!_!_!  _!############
##################################_     _!############
######################## ! ! ! ! !_  !_!##############
#################### !_ _ _  !  _  !  _!##############
##################_     _  ! !_  !    _! ! !##########
##################_  !_  ! !_  ! !_!_!  _   _!########
##################_  ! ! !_ _! ! !   !  _!  _!########
##################_ _  !_      !   !    _!  _!########
############ ! !##_   _ _!_!_!_!_!_!_!_!_   _!########
########## !    _! !  _!################_   _!########
######## !  _!_ _     _!##############_     _!########
#### ! !  _!    _!_!_!################_  !_!##########
##_   _ _!  _!  _!#### ! ! !########_   _ _! !########
##_ _ _  ! !_  ! ! !_   _  ! ! ! !##_     _   _!######
####_   _!   !_        !_     _  ! !##_!_!    _!######
####_ _  !_!   !_!_!_!_!##_!_! !_  !_      !_!########
######_  ! !_!  _!##########_   _ _!_  !_!_!##########
######_         _!##########_   _  !    _!############
########_!_!_!_!##############_!_    !_!##############
##################################_!_!################
######################################################

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 - 1 .. $max_y + 1 ) {
        for my $x ( $min_x - 1 .. $max_x + 1 ) {
            if ( ref $map->{$y}{$x} ) {
                $output .= $map->{$y}{$x}{S} ? ' ' : '_';
                $output .= $map->{$y}{$x}{E} ? ' ' : '!';
            }
            else {
                $output .= '##';
            }
        }
        $output .= "\n";
    }
    return $output;
}

Description

  1. Start carving from (x0,y0) into a random direction.
  2. Calculate the new coordinates (x1,y1).
  3. Return if the new position was already visited.
  4. Repeat the process from the new position, trying all possible directions.

It is important to count the number of steps ($count), so we can exit the routine when the maze reaches the desired size ($CELLS). (Otherwise the maze would keep growing forever). Since the maze can become very sparse, we store the positions in a hash table instead of an array.

Usage

$ ./dynamic.pl [length] [random seed]

More examples

$ ./dynamic.pl 250 1419687187
################################## ! !########################################
################################_    ! ! ! !##################################
################################_  !_ _ _   _!################################
################################_  !  _!  _ _!################################
################################_  !  _   _!##################################
##############################_   _!  _!_!#################### ! ! !##########
##############################_  ! ! ! !####################_       _! !######
##############################_  !_ _  ! !####################_!_!      _!####
##############################_      !_   _!################_    !_!_!  _! !##
############################## !_!_! !  _ _!###### ! ! !##_   _!_  !_ _ _   _!
############################_   _ _ _!  _!######_   _   _!_    !_  !_   _   _!
##########################_   _!  _ _! ! ! !## !_  !  _ _!##_!_  ! !_ _  !_!##
##########################_  !  _  !  _ _  !_   _ _!  _! !_   _ _! !_     _!##
##########################_  !_ _!_ _!   !_    !_   _!_   _ _!  _ _!   !_!####
########################_   _!  _      !   !_!_!_  !    _!  _ _!_   _!_!######
########################_       _!_!_!_!_!    _!_    !_!_ _  !   !_ _   _!####
##########################_!_!_!######## !_!  _!##_!_!####_    !        _!####
################################ ! ! !_       _!############_!_!_!_!_!_!######
##############################_   _  !   !_!_!################################
################## ! !########_  ! ! ! !_!####################################
################_    ! ! !##_   _!_ _ _ _! ! !################################
################_  !  _   _!_   _ _   _ _ _   _!##############################
################_  !_! !  _!##_!   !_ _ _ _!  _!##############################
################_  !_   _! ! !_  !      _  !_   _!############################
############ ! !_ _  !    _  !_  !_!_!_!_       _!############################
##########_    !_    !_!_!_       _!######_!_!_!##############################
##########_  !     !_!######_!_!_!############################################
#### ! !##_  !_!_!_!##########################################################
##_    !_     _!##############################################################
_   _!_    !_!################################################################
_ _ _  !_!_!##################################################################
_    !  _!####################################################################
_  !_   _!####################################################################
_ _  !_!######################################################################
_     _!######################################################################
##_!_!########################################################################
$ ./dynamic.pl 250 1419687341
######## ! !############################################################
#### !_     _!##########################################################
##_   _ _! ! ! ! !######################################################
_   _!_ _     _  ! ! ! ! !##############################################
_        !_!_!_     _ _  ! ! ! !########################################
##_!_!_!  _! !##_!_!_   _!  _   _!######################################
######_       _!####_  !  _!  _! ! !####################################
########_!_!    _!##_   _!  _!  _   _!#################### ! !##########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
############ !_!  _!####_   _ _!  _!##########_    ! ! !_  !          _!
######## !_       _!######_!_   _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
######_      !_!_!########## !_   _!##_   _  !   !_!_   _!  _!##########
####_    !_!_!######## ! ! !   !  _!##_    !   !_!##_       _!##########
####_  !_! !########_   _ _ _!_ _ _!####_! !_!_!######_!_!_!############
####_       _!######_   _  ! ! ! ! ! ! !_   _!##########################
######_!_!  _!########_!_           _  !    _!##########################
########_   _!############_!_!_!_!_!_    !_!############################
######_   _ _!#### ! ! ! ! !##########_!_!##############################
######_ _   _!##_   _       _!##########################################
####_   _ _ _! ! !  _!_!_!  _!##########################################
####_ _ _  !  _   _ _! !_   _!##########################################
####_     _!  _!_!  _       _!##########################################
####_  !_!  _ _!_    !_!_!_!############################################
####_       _!####_!  _!################################################
######_!_!_!####_   _ _!################################################
################_ _   _!################################################
###### ! ! ! !##_     _!################################################
## !_     _  !_   _!_!##################################################
_   _  !_!_  !_ _ _   _!################################################
_    !_! !_  !  _  !  _!################################################
##_!    _  ! ! ! ! !  _! !##############################################
####_!_!  _!_ _!  _!  _   _!############################################
######_ _!   !  _!_ _!    _!############################################
####_   _ _!_ _!_    ! !_!##############################################
####_   _  !   !_  !    _!##############################################
######_!_  ! ! !   !_!_!################################################
########_  ! !   !_!####################################################
########_    !_!_!######################################################
##########_!_!##########################################################
$ ./dynamic.pl 250 1419687903
############## ! !######################################################################################################
########## ! !    _!####################################################################################################
########_   _ _!  _!####################################################################################################
########_ _ _  !_   _! !######################################################## ! !####################################
########_   _ _ _! !    _!############################################## ! ! ! !    _!##################################
########_  ! !  _ _! !  _! ! ! !###### ! ! ! !######## ! ! ! !######## !   !  _  !    _! ! ! ! !########################
########_ _  !_  !  _! !   !    _! ! !  _     _! !##_   _ _   _!####_   _!    _!_!_!            _!######################
######## ! ! !  _!  _! ! !_  !     !  _ _!_!      _! !  _!  _ _!####_   _!_!_!######_!_!_!_!_!    _!########## ! ! ! !##
###### !  _ _!_ _ _ _!    _!_!_!_!    _!####_!_!        _! !    _!##_  ! ! !##################_!    _! !####_   _ _   _!
####_   _! ! ! ! ! !##_!_!########_!_!##########_!_!_!_!_    !    _! ! !    _!##################_!      _! !_   _!    _!
####_ _ _  !  _ _   _!####################################_!_!_!     !_ _!  _!####################_!_!      _! !  _!_!##
######_   _!_  ! !  _!##########################################_!_!        _!########################_!_! !  _!_   _!##
###### !_ _ _ _!  _ _!##############################################_!_!_!_!############################_    !      _!##
## ! !    _!   !_   _!################################################################################## !_!_! !_!_!####
_      !     ! !  _ _!################################################################################_    !    _!######
##_!_!_!_!_!_!    _!################################################################################_   _! ! !_!########
##############_!_!##################################################################################_  !_     _!########
####################################################################################################_    !_!_! ! !######
######################################################################################################_! !   !    _!####
######################################################################################################_    ! ! !  _!####
################################################################################################ ! ! !##_!_!_  !_   _!##
##############################################################################################_   _  !_   _  ! ! !  _!##
################################################################################################_!_      !_  ! ! !  _!##
####################################################################################################_!_!_! ! ! ! !  _!##
########################################################################################################_   _! ! !  _!##
########################################################################################################_ _  !_  !  _!##
##########################################################################################################_ _  !_!  _!##
############################################################################################################_       _!##
##############################################################################################################_!_!_!####

Advantages

The main advantage of this technique is that, since cells are stored in a hash, memory usage grows only one cell at a time.

It is also easily customizable because this technique is just one (recursive backtracker covered by one cell long dead-ends) of the many possible implementations of the Growing tree algorithm described by Walter D. Pullen on Think Labyrinth [1]. With only a few minor changes, the results can be very different. "For example, if you always pick the most recent cell added to it, this algorithm turns into the recursive backtracker. If you always pick cells at random, this will behave similarly but not exactly to Prim's algorithm. If you always pick the oldest cells added to the list, this will create Mazes with about as low a river factor as possible, even lower than Prim's algorithm. If you usually pick the most recent cell, but occasionally pick a random cell, the Maze will have a high river factor but a short direct solution. If you randomly pick among the most recent cells, the Maze will have a low river factor but a long windy solution."

If you remove the inner walls, you get a Dynamically Sized Cave.