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

With a few modifications it is possible to transform the maze in a cave, replacing the dead-ends with larger tunnels and circular paths:

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