Dynamically Sized Maze

From RogueBasin
Revision as of 13:37, 27 December 2014 by Jamala (talk | contribs) (→‎Example)
Jump to navigation Jump to search

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 500 1419687417
############################################################################################## ! ! !##################
############################################################################################_   _   _!################
############################################################################################_  ! ! ! !################
######################################################################################## !_   _! !_  ! !##############
######################################################################################_    ! !_ _  !_  ! ! !##########
#################################################################################### !_  !_ _!    _ _! !    _!########
##################################################################################_   _ _!  _  !_!  _ _! !  _!########
##################################################################################_    ! !_  !_ _ _!  _ _!  _!########
#################### ! ! ! ! !## ! ! ! !############################################_! !_ _ _  ! !_ _  !  _ _!########
##################_       _  !_     _   _!##########################################_        ! !       !_   _!########
##################_  !_!_!_  !   !_!_  ! ! !##########################################_!_!_! !   !_!_!_! !  _!########
##################_   _!##_    !_!##_   _   _!########################################_   _  !_!_!####_   _ _!########
############## ! !_   _!####_!_!######_!_  ! ! ! !####################################_    !_! !######_   _!##########
############_    !    _!################_ _  !   ! !############ ! !####################_!  _   _!####_  ! ! !########
##########_   _!_ _!_!####################_    !_  ! !########_    ! ! !#### ! !#### ! ! !_!    _!####_   _  ! ! ! !##
##########_    !    _!######################_!_!_ _  ! !######_  ! !   ! !_    ! !_          !_!########_!_   _ _   _!
############_!_ _!  _!############################_ _   _!####_  ! ! !_ _ _ _!_  !_  !_!_!_!_!##############_!_   _ _!
##########_   _  !    _!#################### ! ! ! !  _ _!##_   _! !_    !_ _  ! !_   _!#################### ! !_   _!
############_!_  !_!    _!################_   _ _  !_   _!_    !_ _  !_!  _  ! !_ _ _ _!##################_   _     _!
##############_  ! !_!  _!################_ _ _  !_ _ _ _!_  !_!##_  ! !_!  _! !  _   _!######## ! ! ! ! ! !  _!_!_!##
##############_ _  !_   _!################ ! ! ! !_    ! !_ _   _!_  !  _ _!   ! ! !  _! !#### !   !  _       _!######
################_       _!##############_   _ _ _!_  !          _! !_ _! !  _! ! ! ! !    _! !  _! !  _!_!_!_!########
##################_!_!_!################_       _  ! !_!_!_!_!_!_   _ _     _! ! ! !_  !        _!    _!##############
##########################################_!_!_!_     _!######## !_   _!_!_!_  !_   _!_!_!_!_!_!##_!_!################
##################################################_!_!########_    !  _!####_       _!################################
############################################################ ! ! !_   _!######_!_!_!##################################
##########################################################_   _   _!_!################################################
########################################################## !  _!_!####################################################
########################################################_   _ _!######################################################
########################################################_   _!########################################################
########################################################_   _!########################################################
########################################################_  ! !########################################################
########################################################_ _   _!######################################################
##########################################################_   _!######################################################
################################################## ! !#### !  _!######################################################
################################################_     _! !  _ _!######################################################
################################################ ! !_       _!########################################################
##############################################_   _ _!_!_!_!##########################################################
##############################################_  ! !##################################################################
##############################################_ _  ! !################################################################
################################## ! ! ! ! ! ! !_ _   _!##############################################################
################################_   _ _ _ _ _   _! !  _!##############################################################
################################_     _  !_  !_  !  _! !##############################################################
##################################_!_!_ _ _  !  _!_ _   _!############################################################
#################################### ! ! ! ! !_  !  _   _!############################################################
##################################_   _ _    !   ! ! !_!##############################################################
################################## !_   _!_!_! !_!_   _!##############################################################
############################ ! !_   _   _!##_   _!_   _!##############################################################
##########################_     _!  _!_!####_   _! ! ! !##############################################################
#################### ! ! ! ! !  _!  _!####_   _!   !_   _!############################################################
##################_   _ _  ! !  _!  _!####_      !      _!############################################################
##################_ _ _  ! ! !  _!  _!######_!_!_!_!_!_!##############################################################
################## ! !  _!   !      _!################################################################################
################_   _   _!_!_!_!_!_!##################################################################################
############## ! !  _!_!##############################################################################################
############_   _ _ _!################################################################################################
############ !_ _  ! !################################################################################################
########## !    _!_   _!##############################################################################################
########_   _!_ _ _   _!##############################################################################################
########_  !  _   _!_!################################################################################################
########_   _!  _ _!##################################################################################################
##########_!_ _   _!##################################################################################################
############_   _ _!##################################################################################################
############ !  _!####################################################################################################
##########_   _ _!####################################################################################################
## ! ! ! ! !  _!######################################################################################################
_   _ _ _  !  _!######################################################################################################
_   _  !  _!  _!######################################################################################################
##_!_  ! !  _ _!######################################################################################################
####_  !_ _ _!########################################################################################################
####_ _   _!##########################################################################################################
######_   _!##########################################################################################################
########_!############################################################################################################

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
######## ! !############################################################
#### !_     _!##########################################################
##_   _ _! ! ! ! !######################################################
_   _!_ _     _  ! ! ! ! !##############################################
_        !_!_!_     _ _  ! ! ! !########################################
##_!_!_!  _! !##_!_!_   _!  _   _!######################################
######_       _!####_  !  _!  _! ! !####################################
########_!_!    _!##_   _!  _!  _   _!#################### ! !##########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
############ !_!  _!####_   _ _!  _!##########_    ! ! !_  !          _!
######## !_       _!######_!_   _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
######_      !_!_!########## !_   _!##_   _  !   !_!_   _!  _!##########
####_    !_!_!######## ! ! !   !  _!##_    !   !_!##_       _!##########
####_  !_! !########_   _ _ _!_ _ _!####_! !_!_!######_!_!_!############
####_       _!######_   _  ! ! ! ! ! ! !_   _!##########################
######_!_!  _!########_!_           _  !    _!##########################
########_   _!############_!_!_!_!_!_    !_!############################
######_   _ _!#### ! ! ! ! !##########_!_!##############################
######_ _   _!##_   _       _!##########################################
####_   _ _ _! ! !  _!_!_!  _!##########################################
####_ _ _  !  _   _ _! !_   _!##########################################
####_     _!  _!_!  _       _!##########################################
####_  !_!  _ _!_    !_!_!_!############################################
####_       _!####_!  _!################################################
######_!_!_!####_   _ _!################################################
################_ _   _!################################################
###### ! ! ! !##_     _!################################################
## !_     _  !_   _!_!##################################################
_   _  !_!_  !_ _ _   _!################################################
_    !_! !_  !  _  !  _!################################################
##_!    _  ! ! ! ! !  _! !##############################################
####_!_!  _!_ _!  _!  _   _!############################################
######_ _!   !  _!_ _!    _!############################################
####_   _ _!_ _!_    ! !_!##############################################
####_   _  !   !_  !    _!##############################################
######_!_  ! ! !   !_!_!################################################
########_  ! !   !_!####################################################
########_    !_!_!######################################################
##########_!_!##########################################################