Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
Line 177: Line 177:
_    _!######################################################################
_    _!######################################################################
##_!_!########################################################################
##_!_!########################################################################
</pre>
<pre>
$ ./dynamic.pl 250 1419687341
######## ! !############################################################
#### !_    _!##########################################################
##_  _ _! ! ! ! !######################################################
_  _!_ _    _  ! ! ! ! !##############################################
_        !_!_!_    _ _  ! ! ! !########################################
##_!_!_!  _! !##_!_!_  _!  _  _!######################################
######_      _!####_  !  _!  _! ! !####################################
########_!_!    _!##_  _!  _!  _  _!#################### ! !##########
############_!    _!##_!_  !_  !  _ _!########## ! !####_    ! ! ! ! !##
############ !_!  _!####_  _ _!  _!##########_    ! ! !_  !          _!
######## !_      _!######_!_  _ _!#### ! ! !_  !  _ _  ! !_!_!_!_!_!##
######_      !_!_!########## !_  _!##_  _  !  !_!_  _!  _!##########
####_    !_!_!######## ! ! !  !  _!##_    !  !_!##_      _!##########
####_  !_! !########_  _ _ _!_ _ _!####_! !_!_!######_!_!_!############
####_      _!######_  _  ! ! ! ! ! ! !_  _!##########################
######_!_!  _!########_!_          _  !    _!##########################
########_  _!############_!_!_!_!_!_    !_!############################
######_  _ _!#### ! ! ! ! !##########_!_!##############################
######_ _  _!##_  _      _!##########################################
####_  _ _ _! ! !  _!_!_!  _!##########################################
####_ _ _  !  _  _ _! !_  _!##########################################
####_    _!  _!_!  _      _!##########################################
####_  !_!  _ _!_    !_!_!_!############################################
####_      _!####_!  _!################################################
######_!_!_!####_  _ _!################################################
################_ _  _!################################################
###### ! ! ! !##_    _!################################################
## !_    _  !_  _!_!##################################################
_  _  !_!_  !_ _ _  _!################################################
_    !_! !_  !  _  !  _!################################################
##_!    _  ! ! ! ! !  _! !##############################################
####_!_!  _!_ _!  _!  _  _!############################################
######_ _!  !  _!_ _!    _!############################################
####_  _ _!_ _!_    ! !_!##############################################
####_  _  !  !_  !    _!##############################################
######_!_  ! ! !  !_!_!################################################
########_  ! !  !_!####################################################
########_    !_!_!######################################################
##########_!_!##########################################################
</pre>
</pre>


[[Category:Developing]]
[[Category:Developing]]

Revision as of 13:36, 27 December 2014

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