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 coordinates were already visited. 4. Repeat the process from (x1,y1), trying all possible directions.

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

In our case, however, there are no limits for growth, so the algorithm would continue forever.

For that reason we defined a counter, and start backtracking after counter > width * height. This is our exit condition.

Source code

#!/usr/bin/env perl

use strict;
use warnings;

no warnings 'recursion';

use List::Util qw/shuffle/;

# Command-line options

my $WIDTH  = $ARGV[0] || 30;
my $HEIGHT = $ARGV[1] || 20;
my $SEED   = $ARGV[2] || 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 $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, $direction ) = @_;

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

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

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

    return if $count > $WIDTH * $HEIGHT;

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

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";
    }
}