Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
 
(46 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 the algorithm must be interrupted. We do that using a counter (return if $count > $WIDTH * $HEIGHT).


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


my $WIDTH  = $ARGV[0] || 30;
my $CELLS = $ARGV[0] || 250;
my $HEIGHT = $ARGV[1] || 20;
my $SEED  = $ARGV[1] || time();
my $SEED  = $ARGV[2] || time();


srand($SEED);
srand($SEED);
Line 85: 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 => 1,  opposite => 'W' },
     x => { N => 0,  S => 0, E => 1, W => -1 },
    W => { dx => -1, opposite => 'E' },
);
);
my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', );


# Variables
# Variables


my $map   = {};
my $map = {};
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
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 $WIDTH $HEIGHT $SEED # resulting in $count cells\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_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->{$y0}{$x0}{$direction} = 1;
     $map->{$y1}{$x1} = { $OPPOSITE{$direction} => 1 };
     $map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite} } = 1;
    $count++;


     return if $count > $WIDTH * $HEIGHT;
     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 ( $y0 - $HEIGHT / 2 .. $y0 + $HEIGHT / 2 ) {
         for my $x ( $min_x - 1 .. $max_x + 1 ) {
        my ( $line1, $line2 ) = ( '', '' );
         for my $x ( $x0 - $WIDTH / 2 .. $y0 + $WIDTH / 2 ) {
             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 ===
<pre>
$ ./dynamic.pl 250 1419687187
################################## ! !########################################
################################_    ! ! ! !##################################
################################_  !_ _ _  _!################################
################################_  !  _!  _ _!################################
################################_  !  _  _!##################################
##############################_  _!  _!_!#################### ! ! !##########
##############################_  ! ! ! !####################_      _! !######
##############################_  !_ _  ! !####################_!_!      _!####
##############################_      !_  _!################_    !_!_!  _! !##
############################## !_!_! !  _ _!###### ! ! !##_  _!_  !_ _ _  _!
############################_  _ _ _!  _!######_  _  _!_    !_  !_  _  _!
##########################_  _!  _ _! ! ! !## !_  !  _ _!##_!_  ! !_ _  !_!##
##########################_  !  _  !  _ _  !_  _ _!  _! !_  _ _! !_    _!##
##########################_  !_ _!_ _!  !_    !_  _!_  _ _!  _ _!  !_!####
########################_  _!  _      !  !_!_!_  !    _!  _ _!_  _!_!######
########################_      _!_!_!_!_!    _!_    !_!_ _  !  !_ _  _!####
##########################_!_!_!######## !_!  _!##_!_!####_    !        _!####
################################ ! ! !_      _!############_!_!_!_!_!_!######
##############################_  _  !  !_!_!################################
################## ! !########_  ! ! ! !_!####################################
################_    ! ! !##_  _!_ _ _ _! ! !################################
################_  !  _  _!_  _ _  _ _ _  _!##############################
################_  !_! !  _!##_!  !_ _ _ _!  _!##############################
################_  !_  _! ! !_  !      _  !_  _!############################
############ ! !_ _  !    _  !_  !_!_!_!_      _!############################
##########_    !_    !_!_!_      _!######_!_!_!##############################
##########_  !    !_!######_!_!_!############################################
#### ! !##_  !_!_!_!##########################################################
##_    !_    _!##############################################################
_  _!_    !_!################################################################
_ _ _  !_!_!##################################################################
_    !  _!####################################################################
_  !_  _!####################################################################
_ _  !_!######################################################################
_    _!######################################################################
##_!_!########################################################################
</pre>
<pre>
$ ./dynamic.pl 250 1419687341
######## ! !############################################################
#### !_    _!##########################################################
##_  _ _! ! ! ! !######################################################
_  _!_ _    _  ! ! ! ! !##############################################
_        !_!_!_    _ _  ! ! ! !########################################
##_!_!_!  _! !##_!_!_  _!  _  _!######################################
######_      _!####_  !  _!  _! ! !####################################
########_!_!    _!##_  _!  _!  _  _!#################### ! !##########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
############ !_!  _!####_  _ _!  _!##########_    ! ! !_  !          _!
######## !_      _!######_!_  _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
######_      !_!_!########## !_  _!##_  _  !  !_!_  _!  _!##########
####_    !_!_!######## ! ! !  !  _!##_    !  !_!##_      _!##########
####_  !_! !########_  _ _ _!_ _ _!####_! !_!_!######_!_!_!############
####_      _!######_  _  ! ! ! ! ! ! !_  _!##########################
######_!_!  _!########_!_          _  !    _!##########################
########_  _!############_!_!_!_!_!_    !_!############################
######_  _ _!#### ! ! ! ! !##########_!_!##############################
######_ _  _!##_  _      _!##########################################
####_  _ _ _! ! !  _!_!_!  _!##########################################
####_ _ _  !  _  _ _! !_  _!##########################################
####_    _!  _!_!  _      _!##########################################
####_  !_!  _ _!_    !_!_!_!############################################
####_      _!####_!  _!################################################
######_!_!_!####_  _ _!################################################
################_ _  _!################################################
###### ! ! ! !##_    _!################################################
## !_    _  !_  _!_!##################################################
_  _  !_!_  !_ _ _  _!################################################
_    !_! !_  !  _  !  _!################################################
##_!    _  ! ! ! ! !  _! !##############################################
####_!_!  _!_ _!  _!  _  _!############################################
######_ _!  !  _!_ _!    _!############################################
####_  _ _!_ _!_    ! !_!##############################################
####_  _  !  !_  !    _!##############################################
######_!_  ! ! !  !_!_!################################################
########_  ! !  !_!####################################################
########_    !_!_!######################################################
##########_!_!##########################################################
</pre>
<pre>
$ ./dynamic.pl 250 1419687903
############## ! !######################################################################################################
########## ! !    _!####################################################################################################
########_  _ _!  _!####################################################################################################
########_ _ _  !_  _! !######################################################## ! !####################################
########_  _ _ _! !    _!############################################## ! ! ! !    _!##################################
########_  ! !  _ _! !  _! ! ! !###### ! ! ! !######## ! ! ! !######## !  !  _  !    _! ! ! ! !########################
########_ _  !_  !  _! !  !    _! ! !  _    _! !##_  _ _  _!####_  _!    _!_!_!            _!######################
######## ! ! !  _!  _! ! !_  !    !  _ _!_!      _! !  _!  _ _!####_  _!_!_!######_!_!_!_!_!    _!########## ! ! ! !##
###### !  _ _!_ _ _ _!    _!_!_!_!    _!####_!_!        _! !    _!##_  ! ! !##################_!    _! !####_  _ _  _!
####_  _! ! ! ! ! !##_!_!########_!_!##########_!_!_!_!_    !    _! ! !    _!##################_!      _! !_  _!    _!
####_ _ _  !  _ _  _!####################################_!_!_!    !_ _!  _!####################_!_!      _! !  _!_!##
######_  _!_  ! !  _!##########################################_!_!        _!########################_!_! !  _!_  _!##
###### !_ _ _ _!  _ _!##############################################_!_!_!_!############################_    !      _!##
## ! !    _!  !_  _!################################################################################## !_!_! !_!_!####
_      !    ! !  _ _!################################################################################_    !    _!######
##_!_!_!_!_!_!    _!################################################################################_  _! ! !_!########
##############_!_!##################################################################################_  !_    _!########
####################################################################################################_    !_!_! ! !######
######################################################################################################_! !  !    _!####
######################################################################################################_    ! ! !  _!####
################################################################################################ ! ! !##_!_!_  !_  _!##
##############################################################################################_  _  !_  _  ! ! !  _!##
################################################################################################_!_      !_  ! ! !  _!##
####################################################################################################_!_!_! ! ! ! !  _!##
########################################################################################################_  _! ! !  _!##
########################################################################################################_ _  !_  !  _!##
##########################################################################################################_ _  !_!  _!##
############################################################################################################_      _!##
##############################################################################################################_!_!_!####
</pre>
=== 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: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.

Retrieved from "http://roguebasin.com/index.php?title=Dynamically_Sized_Maze&oldid=50519"