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

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

(The complete maze is larger than the rectangular viewport shown above)

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 the algorithm must be interrupted. We do that using a counter (return if $count > $WIDTH * $HEIGHT).

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