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

$ ./dynamic.pl 250 1419687078
############ ! !######################################################
##########_     _!####################################################
###### !_   _!  _!####################################################
## !_    ! ! !  _!####################################################
_   _ _! ! !  _! !#### ! ! ! ! !############## ! !####################
_ _ _  !  _!_ _   _!_   _ _ _   _!##########_    ! ! ! !##############
_   _ _!_!   !_   _!_  !_  !  _ _!###### !_    !    _   _!############
_      !  _!_  ! ! !_ _  ! !  _!## ! !_      !_!_!_!_  ! !############
##_!_! !_ _  ! !        _!  _! !_    !_  !_!_!######_ _  ! !##########
####_       _! !_!_!_!_!_          !      _!##########_ _  ! !########
######_!_!_!    _!########_!_!_!_!_!_!_!_!############## !_   _!######
######_    ! !_! ! !############################## ! ! !  _   _!######
######_  !_ _!  _   _!############ ! ! ! !###### !   !  _ _!_!########
######_      ! ! !  _! !########_   _ _   _! ! !  _!    _!############
########_!_! !_  ! !    _!######_   _  !_ _       _!_!_!##############
##########_    ! !_ _!  _!########_!_ _   _!_!_!_!####################
############_! !  _!  _ _!###### ! ! ! ! ! !##########################
##########_   _!  _!_   _!####_   _ _  !_   _!########## ! !##########
##########_      !  _ _ _!####_ _ _  ! !  _ _!########_     _!########
############_!_!_!      _!####_ _  ! !_ _! ! !## ! ! !_  ! ! !########
##################_!_!  _! ! !  _ _! !   !   !_     _  ! !_   _!## !##
####################_        ! !  _ _! !   !     !_!_ _ _!  _! !_   _!
######################_!_!_!   !       !_!_!_!_!_!##_   _ _!  _  !  _!
############################_!_!_!_!_!_!############_        !_  !  _!
######################################################_!_!_!_!_     _!
################################################################_!_!##

Algorithm

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

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.

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

Source code

#!/usr/bin/env perl

use strict;
use warnings;

no warnings 'uninitialized';
no warnings 'recursion';

use List::Util qw/min max shuffle/;

# Command-line options

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

srand($SEED);

# Constants

my %DIRECTIONS = (
    N => { dy => -1, opposite => 'S' },
    S => { dy => 1,  opposite => 'N' },
    E => { dx => 1,  opposite => 'W' },
    W => { dx => -1, opposite => 'E' },
);

# Variables

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

# Code

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 + $DIRECTIONS{$direction}{dx};
    my $y1 = $y0 + $DIRECTIONS{$direction}{dy};

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

    $min_x = min( $min_x, $x1 );
    $max_x = max( $max_x, $x1 );

    $min_y = min( $min_y, $y1 );
    $max_y = max( $max_y, $y1 );

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

    return if $count++ > $CELLS;

    for my $new_direction ( shuffle keys %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

$ ./dynamic.pl 250 1419687187
################################## ! !########################################
################################_    ! ! ! !##################################
################################_  !_ _ _   _!################################
################################_  !  _!  _ _!################################
################################_  !  _   _!##################################
##############################_   _!  _!_!#################### ! ! !##########
##############################_  ! ! ! !####################_       _! !######
##############################_  !_ _  ! !####################_!_!      _!####
##############################_      !_   _!################_    !_!_!  _! !##
############################## !_!_! !  _ _!###### ! ! !##_   _!_  !_ _ _   _!
############################_   _ _ _!  _!######_   _   _!_    !_  !_   _   _!
##########################_   _!  _ _! ! ! !## !_  !  _ _!##_!_  ! !_ _  !_!##
##########################_  !  _  !  _ _  !_   _ _!  _! !_   _ _! !_     _!##
##########################_  !_ _!_ _!   !_    !_   _!_   _ _!  _ _!   !_!####
########################_   _!  _      !   !_!_!_  !    _!  _ _!_   _!_!######
########################_       _!_!_!_!_!    _!_    !_!_ _  !   !_ _   _!####
##########################_!_!_!######## !_!  _!##_!_!####_    !        _!####
################################ ! ! !_       _!############_!_!_!_!_!_!######
##############################_   _  !   !_!_!################################
################## ! !########_  ! ! ! !_!####################################
################_    ! ! !##_   _!_ _ _ _! ! !################################
################_  !  _   _!_   _ _   _ _ _   _!##############################
################_  !_! !  _!##_!   !_ _ _ _!  _!##############################
################_  !_   _! ! !_  !      _  !_   _!############################
############ ! !_ _  !    _  !_  !_!_!_!_       _!############################
##########_    !_    !_!_!_       _!######_!_!_!##############################
##########_  !     !_!######_!_!_!############################################
#### ! !##_  !_!_!_!##########################################################
##_    !_     _!##############################################################
_   _!_    !_!################################################################
_ _ _  !_!_!##################################################################
_    !  _!####################################################################
_  !_   _!####################################################################
_ _  !_!######################################################################
_     _!######################################################################
##_!_!########################################################################

$ ./dynamic.pl 250 1419687341
######## ! !############################################################
#### !_     _!##########################################################
##_   _ _! ! ! ! !######################################################
_   _!_ _     _  ! ! ! ! !##############################################
_        !_!_!_     _ _  ! ! ! !########################################
##_!_!_!  _! !##_!_!_   _!  _   _!######################################
######_       _!####_  !  _!  _! ! !####################################
########_!_!    _!##_   _!  _!  _   _!#################### ! !##########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
############ !_!  _!####_   _ _!  _!##########_    ! ! !_  !          _!
######## !_       _!######_!_   _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
######_      !_!_!########## !_   _!##_   _  !   !_!_   _!  _!##########
####_    !_!_!######## ! ! !   !  _!##_    !   !_!##_       _!##########
####_  !_! !########_   _ _ _!_ _ _!####_! !_!_!######_!_!_!############
####_       _!######_   _  ! ! ! ! ! ! !_   _!##########################
######_!_!  _!########_!_           _  !    _!##########################
########_   _!############_!_!_!_!_!_    !_!############################
######_   _ _!#### ! ! ! ! !##########_!_!##############################
######_ _   _!##_   _       _!##########################################
####_   _ _ _! ! !  _!_!_!  _!##########################################
####_ _ _  !  _   _ _! !_   _!##########################################
####_     _!  _!_!  _       _!##########################################
####_  !_!  _ _!_    !_!_!_!############################################
####_       _!####_!  _!################################################
######_!_!_!####_   _ _!################################################
################_ _   _!################################################
###### ! ! ! !##_     _!################################################
## !_     _  !_   _!_!##################################################
_   _  !_!_  !_ _ _   _!################################################
_    !_! !_  !  _  !  _!################################################
##_!    _  ! ! ! ! !  _! !##############################################
####_!_!  _!_ _!  _!  _   _!############################################
######_ _!   !  _!_ _!    _!############################################
####_   _ _!_ _!_    ! !_!##############################################
####_   _  !   !_  !    _!##############################################
######_!_  ! ! !   !_!_!################################################
########_  ! !   !_!####################################################
########_    !_!_!######################################################
##########_!_!##########################################################