Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
Line 262: Line 262:
##############################################################################################################_!_!_!####
##############################################################################################################_!_!_!####
</pre>
</pre>
=== Advantages ===
The main advantage is that a player with a pick axe can never know for sure if he can shortcut the maze by carving into a random direction.
The fact that the cells are stored in a hash allows the maze to grow infinitely, as the memory usage grows one cell at a time.


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

Revision as of 19:50, 27 February 2015

This article will describe a technique to build mazes that can grow without limits in all directions, differently from a traditional maze that is bounded by its outer walls.

Example

$ ./dynamic.pl 250 1419689539
######################################################
############ ! ! ! !##################################
##########_     _   _!################################
############_!_!  _ _! !##############################
############_   _!  _   _! !##########################
############_    ! ! !_ _   _!########################
##############_! ! !   !  _ _!###### ! ! ! !##########
############_   _!_ _! !_   _!## ! !   !    _! ! !####
############_     _!  _!  _ _!_   _ _!_ _!_ _ _   _!##
##############_!  _!  _!    _!_  ! ! !  _ _  !  _ _!##
##############_  !  _ _!_!  _! !_ _  ! !  _! !    _!##
##############_  !  _!##_   _!  _  ! ! !  _ _!_!  _!##
##############_     _!##_      !  _! ! !_  !   !  _!##
################_!_!######_!_!_!_  ! ! !_    !    _!##
############################_   _ _! !  _!_!_!_!_!####
############################_        !  _!############
##############################_!_!_!_!  _!############
##################################_     _!############
######################## ! ! ! ! !_  !_!##############
#################### !_ _ _  !  _  !  _!##############
##################_     _  ! !_  !    _! ! !##########
##################_  !_  ! !_  ! !_!_!  _   _!########
##################_  ! ! !_ _! ! !   !  _!  _!########
##################_ _  !_      !   !    _!  _!########
############ ! !##_   _ _!_!_!_!_!_!_!_!_   _!########
########## !    _! !  _!################_   _!########
######## !  _!_ _     _!##############_     _!########
#### ! !  _!    _!_!_!################_  !_!##########
##_   _ _!  _!  _!#### ! ! !########_   _ _! !########
##_ _ _  ! !_  ! ! !_   _  ! ! ! !##_     _   _!######
####_   _!   !_        !_     _  ! !##_!_!    _!######
####_ _  !_!   !_!_!_!_!##_!_! !_  !_      !_!########
######_  ! !_!  _!##########_   _ _!_  !_!_!##########
######_         _!##########_   _  !    _!############
########_!_!_!_!##############_!_    !_!##############
##################################_!_!################
######################################################

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

Description

  1. Start carving from (x0,y0) into a random 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.

It is important to count the number of steps ($count), so we can exit the routine when the maze reaches the desired size ($CELLS). (Otherwise the maze would keep growing forever). Since the maze can become very sparse, we store the positions in a hash table instead of an array.

Usage

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

More examples

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

Advantages

The main advantage is that a player with a pick axe can never know for sure if he can shortcut the maze by carving into a random direction.

The fact that the cells are stored in a hash allows the maze to grow infinitely, as the memory usage grows one cell at a time.