Dynamically Sized Maze

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

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

Example

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

Algorithm

The algorithm is a simple recursive backtracker, starting at position {0,0} and growing into all directions.

Since the maze can become very sparse, we use a two-dimensional hash table, instead of an array, to store the cells.

1. Start carving from (x0,y0) into a specific 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.

In the normal algorithm the process will terminate when all coordinates were visited.

In our case, however, there is no limit for growth, so we must return after the number of cells reaches the limit.

Source code

#!/usr/bin/env perl

use strict;
use warnings;

no warnings 'recursion';

use List::Util qw/shuffle/;

# Command-line options

my $CELLS = $ARGV[0] || 250;
my $SEED  = $ARGV[1] || time();

srand($SEED);

# Constants

my @DIRECTIONS = qw/N S E W/;

my %DELTA = (
    y => { N => -1, S => 1, E => 0, W => 0 },
    x => { N => 0,  S => 0, E => 1, W => -1 },
);

my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', );

# Variables

my $map = {};
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
my $count = 0;

###

main();

###

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

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

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

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

    $min_y = $y1 if $y1 < $min_y;
    $max_y = $y1 if $y1 > $max_y;

    $min_x = $x1 if $x1 < $min_x;
    $max_x = $x1 if $x1 > $max_x;

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

    return if $count++ > $CELLS;

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

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

    for my $y ( $min_y .. $max_y ) {
        my ( $line1, $line2 ) = ( '', '' );
        for my $x ( $min_x .. $max_x) {
            if ( ref $map->{$y}{$x} ) {
                $line1 .= $map->{$y}{$x}{E} ? '    ' : '  ##';
                $line2 .= $map->{$y}{$x}{S} ? '    ' : '####';
            }
            else {
                $line1 .= '####';
                $line2 .= '####';
            }
        }
        print "$line1\n$line2\n";
    }
}

More examples =

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

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

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