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

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