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 'uninitialized';
no warnings 'recursion';
no warnings 'recursion';
 
use List::Util qw/shuffle/;
use List::Util qw/min max 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


Line 89: Line 90:
     W => { dx => -1, opposite => 'E' },
     W => { dx => -1, opposite => '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
# Code
 
carve( 0, 0, 'E' );
carve( 0, 0, 'E' );
draw( 0, 0 );
draw( 0, 0 );
print "$0 $CELLS $SEED # => ( $min_x, $min_y, $max_x, $max_y )\n";
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 + $DIRECTIONS{$direction}{dx};
     my $x1 = $x0 + $DIRECTIONS{$direction}{dx};
     my $y1 = $y0 + $DIRECTIONS{$direction}{dy};
     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_x = min( $min_x, $x1 );
     $max_y = $y1 if $y1 > $max_y;
     $max_x = max( $max_x, $x1 );
 
     $min_x = $x1 if $x1 < $min_x;
     $min_y = min( $min_y, $y1 );
     $max_x = $x1 if $x1 > $max_x;
     $max_y = max( $max_y, $y1 );
 
     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y0}{$x0}{$direction} = 1;
     $map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite}} = 1;
     $map->{$y1}{$x1}{ $DIRECTIONS{$direction}{opposite} } = 1;
 
     return if $count++ > $CELLS;
     return if $count++ > $CELLS;
 
     for my $new_direction ( shuffle keys %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 ) = ( '', '' );
         for my $x ( $min_x .. $max_x) {
         for my $x ( $min_x .. $max_x ) {
             if ( ref $map->{$y}{$x} ) {
             if ( ref $map->{$y}{$x} ) {
                 $line1 .= $map->{$y}{$x}{E} ? '    ' : '  ##';
                 $line1 .= $map->{$y}{$x}{E} ? '    ' : '  ##';

Revision as of 13:24, 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

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

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

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=39473"