Difference between revisions of "Dynamically Sized Maze"

From RogueBasin
Jump to navigation Jump to search
Line 66: Line 66:
<source lang="perl">
<source lang="perl">
#!/usr/bin/env perl
#!/usr/bin/env perl
 
use strict;
use strict;
use warnings;
use warnings;
 
no warnings 'recursion';
no warnings 'recursion';
 
use List::Util qw/shuffle/;
use List::Util qw/shuffle/;
 
# Command-line options
# Command-line options
 
my $CELLS = $ARGV[0] || 250;
my $CELLS = $ARGV[0] || 250;
my $SEED  = $ARGV[1] || time();
my $SEED  = $ARGV[1] || time();
 
srand($SEED);
srand($SEED);
 
# Constants
# Constants


my @DIRECTIONS = qw/N S E W/;
my %DIRECTIONS = (
 
     N => { dy => -1, opposite => 'S' },
my %DELTA = (
    S => { dy => 1, opposite => 'N' },
     y => { N => -1, S => 1, E => 0, W => 0 },
     E => { dx => 1,  opposite => 'W' },
     x => { N => 0,  S => 0, E => 1, W => -1 },
    W => { dx => -1, opposite => 'E' },
);
);
 
my %OPPOSITE = ( N => 'S', S => 'N', E => 'W', W => 'E', );
 
# Variables
# Variables
 
my $map = {};
my $map = {};
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
my ( $min_x, $min_y, $max_x, $max_y ) = ( 0, 0, 0, 0 );
my $count = 0;
my $count = 0;
 
###
# Code
 
main();
carve( 0, 0, 'E' );
 
draw( 0, 0 );
###
print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
 
sub main {
    carve( 0, 0, 'E' );
    draw( 0, 0 );
    print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
}
 
sub carve {
sub carve {
     my ( $x0, $y0, $direction ) = @_;
     my ( $x0, $y0, $direction ) = @_;
 
     my $x1 = $x0 + $DELTA{x}{$direction};
     my $x1 = $x0 + $DIRECTIONS{$direction}{dx};
     my $y1 = $y0 + $DELTA{y}{$direction};
     my $y1 = $y0 + $DIRECTIONS{$direction}{dy};
 
     return if defined $map->{$y1}{$x1};    # already visited
     return if defined $map->{$y1}{$x1};    # already visited
 
     $min_y = $y1 if $y1 < $min_y;
     $min_y = $y1 if $y1 < $min_y;
     $max_y = $y1 if $y1 > $max_y;
     $max_y = $y1 if $y1 > $max_y;
 
     $min_x = $x1 if $x1 < $min_x;
     $min_x = $x1 if $x1 < $min_x;
     $max_x = $x1 if $x1 > $max_x;
     $max_x = $x1 if $x1 > $max_x;
 
     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y1}{$x1} = { $OPPOSITE{$direction} => 1 };
     $map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite}} = 1;
 
     return if $count++ > $CELLS;
     return if $count++ > $CELLS;
 
     for my $new_direction ( shuffle @DIRECTIONS ) {
     for my $new_direction ( shuffle keys %DIRECTIONS ) {
         carve( $x1, $y1, $new_direction );
         carve( $x1, $y1, $new_direction );
     }
     }
}
}
 
sub draw {
sub draw {
     my ( $x0, $y0 ) = @_;
     my ( $x0, $y0 ) = @_;
 
     for my $y ( $min_y .. $max_y ) {
     for my $y ( $min_y .. $max_y ) {
         my ( $line1, $line2 ) = ( '', '' );
         my ( $line1, $line2 ) = ( '', '' );

Revision as of 16:11, 26 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

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

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 'recursion';
 
use List::Util qw/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_y = $y1 if $y1 < $min_y;
    $max_y = $y1 if $y1 > $max_y;
 
    $min_x = $x1 if $x1 < $min_x;
    $max_x = $x1 if $x1 > $max_x;
 
    $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

With few modifications it is possible to transform the maze in a cave, with larger tunnels and circular paths: 

####################  ##  ##################################################################################################################
####################        ################################################################################################################
################          ##  ##  ##  ##  ##################################################################################################
####################                        ################################################################################################
############          ##                      ##############################################################################################
################    ####################    ################################################################################################
########          ##                  ##      ######################################################  ##  ##################################
############    ####    ########    ####    ########################################################        ################################
########      ##              ##  ##      ##  ######  ##  ######################################              ##############################
############    ############            ####    ####        ########################################        ################################
########      ##      ##      ##      ##      ##          ##  ##################################      ##  ##  ##############################
############            ####    ########        ####            ####################################            ############################
########          ##      ##              ##          ##          ##########################          ##          ##########################
####################        ################################    ################################        ####    ############################
####  ##          ##  ##  ##                  ##  ##          ##  ##############  ##  ##  ##      ##  ##          ##########################
####    ####        ####        ############            ########    ############            ####    ########    ############################
      ##      ##      ##          ##      ##  ##      ##          ##  ######              ##          ##          ##########################
####    ####    ####    ############                ####    ####        ########    ####        ############    ############################
              ##  ##              ##  ##  ##  ##  ##      ##          ##  ##      ##      ##          ##  ##      ######  ##  ##  ##########
####        ####    ############                        ############        ####    ####    ####    ####        ########            ########
####  ##  ##  ##      ##          ##  ##      ##  ##  ##  ##  ##  ##      ##          ##          ##          ##  ##              ##  ######
############                ########    ########                    ####    ########    ################    ####    ####    ####        ####
########          ##      ##          ##      ##      ##              ##          ##      ##          ##                  ##  ##          ##
############    ################    ####    ############    ########    ########    ####            ########################    ####    ####
########              ##          ##  ##                  ##      ##          ##          ##  ##                              ##          ##
############    ####    ####    ####        ####        ####        ####        ####    ####    ############        ############    ########
############  ##          ##  ##  ##          ##  ##  ##      ##      ##  ##      ##  ##  ##              ##  ##      ##              ######
########################                ################    ########    ####    ########    ########    ########            ####    ########
################  ##      ##  ##  ##      ##########              ##              ##  ##                  ######  ##          ##  ##########
################        ####            ################            ####        ####        ####        ############        ################
############  ##      ##      ##          ##############  ##  ##      ##  ##  ##  ##          ##  ##  ##############  ##  ##################
############        ####    ####    ############################        ########        ####################################################
########          ##      ##              ######################  ##                      ##################################################
############    ####        ####        ############################                    ####################################################
########              ##  ######  ##  ##############################  ##  ##  ##  ##  ######################################################
############            ####################################################################################################################
############  ##  ##  ######################################################################################################################
############################################################################################################################################
Retrieved from "http://roguebasin.com/index.php?title=Dynamically_Sized_Maze&oldid=39451"