Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
Line 81: Line 81:
########_!############################################################################################################
########_!############################################################################################################
</pre>
</pre>
== Algorithm ==
The algorithm is a simple [[recursive backtracker]], starting at position {0,0} and growing into all directions.
# Start carving from (x0,y0) into a specific direction.
# Calculate the new coordinates (x1,y1).
# Return if the new position was already visited.
# Repeat the process from the new position, trying all possible directions.
In a regular recursive backtracker, 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 ==
== Source code ==
Line 183: Line 168:
</div>
</div>


== Usage ==
=== Description ===
 
This is a simple [[recursive backtracker]] that starts at position {0,0} and can grow into all directions.
 
# Start carving from (x0,y0) into a specific direction.
# Calculate the new coordinates (x1,y1).
# Return if the new position was already visited.
# Repeat the process from the new position, trying all possible directions.
 
In most mazes, the process terminates when all coordinates were visited; but in our case there is no limit for growth, so we must terminate after an arbitrary limit.
 
Another important point is that, since the maze can become very sparse, we use a hash table instead of an array to store the cells.
 
=== Usage ===


<pre>
<pre>
Line 189: Line 187:
</pre>
</pre>


== More examples ==
=== More examples ===


<pre>
<pre>
Line 272: Line 270:
########_    !_!_!######################################################
########_    !_!_!######################################################
##########_!_!##########################################################
##########_!_!##########################################################
</pre>
<pre>
$ ./dynamic.pl 250 1419687903
############## ! !######################################################################################################
########## ! !    _!####################################################################################################
########_  _ _!  _!####################################################################################################
########_ _ _  !_  _! !######################################################## ! !####################################
########_  _ _ _! !    _!############################################## ! ! ! !    _!##################################
########_  ! !  _ _! !  _! ! ! !###### ! ! ! !######## ! ! ! !######## !  !  _  !    _! ! ! ! !########################
########_ _  !_  !  _! !  !    _! ! !  _    _! !##_  _ _  _!####_  _!    _!_!_!            _!######################
######## ! ! !  _!  _! ! !_  !    !  _ _!_!      _! !  _!  _ _!####_  _!_!_!######_!_!_!_!_!    _!########## ! ! ! !##
###### !  _ _!_ _ _ _!    _!_!_!_!    _!####_!_!        _! !    _!##_  ! ! !##################_!    _! !####_  _ _  _!
####_  _! ! ! ! ! !##_!_!########_!_!##########_!_!_!_!_    !    _! ! !    _!##################_!      _! !_  _!    _!
####_ _ _  !  _ _  _!####################################_!_!_!    !_ _!  _!####################_!_!      _! !  _!_!##
######_  _!_  ! !  _!##########################################_!_!        _!########################_!_! !  _!_  _!##
###### !_ _ _ _!  _ _!##############################################_!_!_!_!############################_    !      _!##
## ! !    _!  !_  _!################################################################################## !_!_! !_!_!####
_      !    ! !  _ _!################################################################################_    !    _!######
##_!_!_!_!_!_!    _!################################################################################_  _! ! !_!########
##############_!_!##################################################################################_  !_    _!########
####################################################################################################_    !_!_! ! !######
######################################################################################################_! !  !    _!####
######################################################################################################_    ! ! !  _!####
################################################################################################ ! ! !##_!_!_  !_  _!##
##############################################################################################_  _  !_  _  ! ! !  _!##
################################################################################################_!_      !_  ! ! !  _!##
####################################################################################################_!_!_! ! ! ! !  _!##
########################################################################################################_  _! ! !  _!##
########################################################################################################_ _  !_  !  _!##
##########################################################################################################_ _  !_!  _!##
############################################################################################################_      _!##
##############################################################################################################_!_!_!####
</pre>
</pre>


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

Revision as of 13:45, 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 500 1419687417
############################################################################################## ! ! !##################
############################################################################################_   _   _!################
############################################################################################_  ! ! ! !################
######################################################################################## !_   _! !_  ! !##############
######################################################################################_    ! !_ _  !_  ! ! !##########
#################################################################################### !_  !_ _!    _ _! !    _!########
##################################################################################_   _ _!  _  !_!  _ _! !  _!########
##################################################################################_    ! !_  !_ _ _!  _ _!  _!########
#################### ! ! ! ! !## ! ! ! !############################################_! !_ _ _  ! !_ _  !  _ _!########
##################_       _  !_     _   _!##########################################_        ! !       !_   _!########
##################_  !_!_!_  !   !_!_  ! ! !##########################################_!_!_! !   !_!_!_! !  _!########
##################_   _!##_    !_!##_   _   _!########################################_   _  !_!_!####_   _ _!########
############## ! !_   _!####_!_!######_!_  ! ! ! !####################################_    !_! !######_   _!##########
############_    !    _!################_ _  !   ! !############ ! !####################_!  _   _!####_  ! ! !########
##########_   _!_ _!_!####################_    !_  ! !########_    ! ! !#### ! !#### ! ! !_!    _!####_   _  ! ! ! !##
##########_    !    _!######################_!_!_ _  ! !######_  ! !   ! !_    ! !_          !_!########_!_   _ _   _!
############_!_ _!  _!############################_ _   _!####_  ! ! !_ _ _ _!_  !_  !_!_!_!_!##############_!_   _ _!
##########_   _  !    _!#################### ! ! ! !  _ _!##_   _! !_    !_ _  ! !_   _!#################### ! !_   _!
############_!_  !_!    _!################_   _ _  !_   _!_    !_ _  !_!  _  ! !_ _ _ _!##################_   _     _!
##############_  ! !_!  _!################_ _ _  !_ _ _ _!_  !_!##_  ! !_!  _! !  _   _!######## ! ! ! ! ! !  _!_!_!##
##############_ _  !_   _!################ ! ! ! !_    ! !_ _   _!_  !  _ _!   ! ! !  _! !#### !   !  _       _!######
################_       _!##############_   _ _ _!_  !          _! !_ _! !  _! ! ! ! !    _! !  _! !  _!_!_!_!########
##################_!_!_!################_       _  ! !_!_!_!_!_!_   _ _     _! ! ! !_  !        _!    _!##############
##########################################_!_!_!_     _!######## !_   _!_!_!_  !_   _!_!_!_!_!_!##_!_!################
##################################################_!_!########_    !  _!####_       _!################################
############################################################ ! ! !_   _!######_!_!_!##################################
##########################################################_   _   _!_!################################################
########################################################## !  _!_!####################################################
########################################################_   _ _!######################################################
########################################################_   _!########################################################
########################################################_   _!########################################################
########################################################_  ! !########################################################
########################################################_ _   _!######################################################
##########################################################_   _!######################################################
################################################## ! !#### !  _!######################################################
################################################_     _! !  _ _!######################################################
################################################ ! !_       _!########################################################
##############################################_   _ _!_!_!_!##########################################################
##############################################_  ! !##################################################################
##############################################_ _  ! !################################################################
################################## ! ! ! ! ! ! !_ _   _!##############################################################
################################_   _ _ _ _ _   _! !  _!##############################################################
################################_     _  !_  !_  !  _! !##############################################################
##################################_!_!_ _ _  !  _!_ _   _!############################################################
#################################### ! ! ! ! !_  !  _   _!############################################################
##################################_   _ _    !   ! ! !_!##############################################################
################################## !_   _!_!_! !_!_   _!##############################################################
############################ ! !_   _   _!##_   _!_   _!##############################################################
##########################_     _!  _!_!####_   _! ! ! !##############################################################
#################### ! ! ! ! !  _!  _!####_   _!   !_   _!############################################################
##################_   _ _  ! !  _!  _!####_      !      _!############################################################
##################_ _ _  ! ! !  _!  _!######_!_!_!_!_!_!##############################################################
################## ! !  _!   !      _!################################################################################
################_   _   _!_!_!_!_!_!##################################################################################
############## ! !  _!_!##############################################################################################
############_   _ _ _!################################################################################################
############ !_ _  ! !################################################################################################
########## !    _!_   _!##############################################################################################
########_   _!_ _ _   _!##############################################################################################
########_  !  _   _!_!################################################################################################
########_   _!  _ _!##################################################################################################
##########_!_ _   _!##################################################################################################
############_   _ _!##################################################################################################
############ !  _!####################################################################################################
##########_   _ _!####################################################################################################
## ! ! ! ! !  _!######################################################################################################
_   _ _ _  !  _!######################################################################################################
_   _  !  _!  _!######################################################################################################
##_!_  ! !  _ _!######################################################################################################
####_  !_ _ _!########################################################################################################
####_ _   _!##########################################################################################################
######_   _!##########################################################################################################
########_!############################################################################################################

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' );
print output();

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 output {
    my $output = '';
    for my $y ( $min_y .. $max_y ) {
        for my $x ( $min_x .. $max_x ) {
            if ( ref $map->{$y}{$x} ) {
                $output .= $map->{$y}{$x}{S} ? ' ' : '_';
                $output .= $map->{$y}{$x}{E} ? ' ' : '!';
            }
            else {
                $output .= '##';
            }
        }
        $output .= "\n";
    }
    return $output;
}

Description

This is a simple recursive backtracker that starts at position {0,0} and can grow 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 most mazes, the process terminates when all coordinates were visited; but in our case there is no limit for growth, so we must terminate after an arbitrary limit.

Another important point is that, since the maze can become very sparse, we use a hash table instead of an array to store the cells.

Usage

$ ./dynamic.pl [length] [random seed]

More examples

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