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.

Source code

#!/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;

main();

###

sub main {
    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";
    }
}