Dynamically Sized Maze

This article will describe a technique to build mazes that can grow in all directions.

Since the maze is not circumscribed into a specific shape, it will end up with a very organic appearance.

Here's one example:

################          ##  ##############              ##########################
########################        ################    ################################
####################              ##########              ##########################
############################    ################        ############################
########################          ##############  ##          ######  ##  ##########
############################    ####################        ########        ########
################  ##  ##  ##      ##################  ##      ##  ##          ######
################                ########################    ####            ########
############                      ##################          ##      ##      ######
################    ####        ########################    ####    ####    ########
############      ##  ##  ##  ##################  ##                  ##      ######
################        ########################    ####    ############    ########
############              ##################          ##  ##      ##          ######
####################    ########################        ####        ####    ########
########  ##  ##          ##################      ##          ##      ##      ######
########            ############################    ################        ########
  ##  ##      ##      ##################          ##                  ##  ##  ##  ##
                    ################################    ################            
          ##          ##################  ##  ##      ##              ##  ##        
    ####################################        ####        ####                ####
  ##              ##  ##  ##  ##  ##              ##  ##      ##  ##  ##  ##  ##    
####        ####                    ####        ####        ####                ####
  ##  ##  ##      ##                  ##  ##  ##  ##  ##  ##      ##      ##        
            ####                ####                    ####    ####################
      ##  ##          ##  ##  ##          ##      ##          ##                    
########    ########################        ####    ############        ############
      ##      ##          ##########  ##  ##      ##      ##      ##  ##      ##    
####                    ########################    ####            ####        ####
      ##  ##      ##          ##############          ##      ##          ##  ##    
####    ################    ########################    ####    ############        
                              ##################          ##      ##      ##      ##
####                        ############################    ########            ####
####  ##  ##  ##  ##  ##  ##########################              ##  ##  ##  ##    
########################################################    ####            ####    
########################################################  ##          ##          ##
################################################################                    
################################################################  ##  ##  ##  ##  ##
####################################################################################

Algorithm

The algorithm is a simple [Recursive backtracker], starting at position {0,0} and allowed to grow into any direction.

One important thing to note is that the maze can become very sparse; for this reason we use a two-dimensional hash table, instead of array, to store the cells.

Code

1. !/usr/bin/env perl

use strict; use warnings;

no warnings 'recursion';

use List::Util qw/shuffle/;

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

srand($SEED);

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', );

my $map = {};

my $count = 0; carve( 0, 0, 'E' );

draw( 0, 0 );

print "$0 $WIDTH $HEIGHT $SEED # resulting in $count cells\n";

sub carve {

   my ( $x0, $y0, $dir ) = @_;

   my $x1 = $x0 + $DELTA{x}{$dir};
   my $y1 = $y0 + $DELTA{y}{$dir};

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

   $map->{$y0}{$x0}{$dir} = 1;
   $map->{$y1}{$x1} = { $OPPOSITE{$dir} => 1 };
   $count++;

   return if $count > $WIDTH * $HEIGHT;

   for my $d ( shuffle @DIRECTIONS ) {
       carve( $x1, $y1, $d );
   }

}

sub draw {

   my ( $x0, $y0 ) = @_;
   for my $y ( $y0 - $HEIGHT / 2 .. $y0 + $HEIGHT / 2 ) {
       my ( $line1, $line2 ) = ( ,  );
       for my $x ( $x0 - $WIDTH / 2 .. $y0 + $WIDTH / 2 ) {
           if ( ref $map->{$y}{$x} ) {
               $line1 .= $map->{$y}{$x}{E} ? '    ' : '  ##';
               $line2 .= $map->{$y}{$x}{S} ? '    ' : '####';
           }
           else {
               $line1 .= '####';
               $line2 .= '####';
           }
       }
       print "$line1\n$line2\n";
   }

}