Difference between revisions of "Dynamically Sized Maze"
Jump to navigation
Jump to search
| Line 138: | Line 138: | ||
== More examples == | == More examples == | ||
<pre> | <pre> | ||
#################### | $ ./dynamic.pl 250 1419687187 | ||
#################### | ################################## ! !######################################## | ||
################ | ################################_ ! ! ! !################################## | ||
################## | ################################_ !_ _ _ _!################################ | ||
############ | ################################_ ! _! _ _!################################ | ||
################ | ################################_ ! _ _!################################## | ||
####### | ##############################_ _! _!_!#################### ! ! !########## | ||
############ | ##############################_ ! ! ! !####################_ _! !###### | ||
######## | ##############################_ !_ _ ! !####################_!_! _!#### | ||
############ | ##############################_ !_ _!################_ !_!_! _! !## | ||
######## | ############################## !_!_! ! _ _!###### ! ! !##_ _!_ !_ _ _ _! | ||
############ | ############################_ _ _ _! _!######_ _ _!_ !_ !_ _ _! | ||
######## | ##########################_ _! _ _! ! ! !## !_ ! _ _!##_!_ ! !_ _ !_!## | ||
#################### | ##########################_ ! _ ! _ _ !_ _ _! _! !_ _ _! !_ _!## | ||
#### | ##########################_ !_ _!_ _! !_ !_ _!_ _ _! _ _! !_!#### | ||
#### | ########################_ _! _ ! !_!_!_ ! _! _ _!_ _!_!###### | ||
########################_ _!_!_!_!_! _!_ !_!_ _ ! !_ _ _!#### | |||
#### | ##########################_!_!_!######## !_! _!##_!_!####_ ! _!#### | ||
################################ ! ! !_ _!############_!_!_!_!_!_!###### | |||
## | ##############################_ _ ! !_!_!################################ | ||
################## ! !########_ ! ! ! !_!#################################### | |||
################_ ! ! !##_ _!_ _ _ _! ! !################################ | |||
################_ ! _ _!_ _ _ _ _ _ _!############################## | |||
################_ !_! ! _!##_! !_ _ _ _! _!############################## | |||
################_ !_ _! ! !_ ! _ !_ _!############################ | |||
############ ! !_ _ ! _ !_ !_!_!_!_ _!############################ | |||
##########_ !_ !_!_!_ _!######_!_!_!############################## | |||
##########_ ! !_!######_!_!_!############################################ | |||
#### ! !##_ !_!_!_!########################################################## | |||
##_ !_ _!############################################################## | |||
_ _!_ !_!################################################################ | |||
_ _ _ !_!_!################################################################## | |||
_ ! _!#################################################################### | |||
_ !_ _!#################################################################### | |||
_ _ !_!###################################################################### | |||
_ _!###################################################################### | |||
##_!_!######################################################################## | |||
</pre> | </pre> | ||
[[Category:Developing]] | [[Category:Developing]] | ||
Revision as of 13:33, 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 ############ ! !###################################################### ##########_ _!#################################################### ###### !_ _! _!#################################################### ## !_ ! ! ! _!#################################################### _ _ _! ! ! _! !#### ! ! ! ! !############## ! !#################### _ _ _ ! _!_ _ _!_ _ _ _ _!##########_ ! ! ! !############## _ _ _!_! !_ _!_ !_ ! _ _!###### !_ ! _ _!############ _ ! _!_ ! ! !_ _ ! ! _!## ! !_ !_!_!_!_ ! !############ ##_!_! !_ _ ! ! _! _! !_ !_ !_!_!######_ _ ! !########## ####_ _! !_!_!_!_!_ ! _!##########_ _ ! !######## ######_!_!_! _!########_!_!_!_!_!_!_!_!############## !_ _!###### ######_ ! !_! ! !############################## ! ! ! _ _!###### ######_ !_ _! _ _!############ ! ! ! !###### ! ! _ _!_!######## ######_ ! ! ! _! !########_ _ _ _! ! ! _! _!############ ########_!_! !_ ! ! _!######_ _ !_ _ _!_!_!############## ##########_ ! !_ _! _!########_!_ _ _!_!_!_!#################### ############_! ! _! _ _!###### ! ! ! ! ! !########################## ##########_ _! _!_ _!####_ _ _ !_ _!########## ! !########## ##########_ ! _ _ _!####_ _ _ ! ! _ _!########_ _!######## ############_!_!_! _!####_ _ ! !_ _! ! !## ! ! !_ ! ! !######## ##################_!_! _! ! ! _ _! ! ! !_ _ ! !_ _!## !## ####################_ ! ! _ _! ! ! !_!_ _ _! _! !_ _! ######################_!_!_! ! !_!_!_!_!_!##_ _ _! _ ! _! ############################_!_!_!_!_!_!############_ !_ ! _! ######################################################_!_!_!_!_ _! ################################################################_!_!##
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 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 ################################## ! !######################################## ################################_ ! ! ! !################################## ################################_ !_ _ _ _!################################ ################################_ ! _! _ _!################################ ################################_ ! _ _!################################## ##############################_ _! _!_!#################### ! ! !########## ##############################_ ! ! ! !####################_ _! !###### ##############################_ !_ _ ! !####################_!_! _!#### ##############################_ !_ _!################_ !_!_! _! !## ############################## !_!_! ! _ _!###### ! ! !##_ _!_ !_ _ _ _! ############################_ _ _ _! _!######_ _ _!_ !_ !_ _ _! ##########################_ _! _ _! ! ! !## !_ ! _ _!##_!_ ! !_ _ !_!## ##########################_ ! _ ! _ _ !_ _ _! _! !_ _ _! !_ _!## ##########################_ !_ _!_ _! !_ !_ _!_ _ _! _ _! !_!#### ########################_ _! _ ! !_!_!_ ! _! _ _!_ _!_!###### ########################_ _!_!_!_!_! _!_ !_!_ _ ! !_ _ _!#### ##########################_!_!_!######## !_! _!##_!_!####_ ! _!#### ################################ ! ! !_ _!############_!_!_!_!_!_!###### ##############################_ _ ! !_!_!################################ ################## ! !########_ ! ! ! !_!#################################### ################_ ! ! !##_ _!_ _ _ _! ! !################################ ################_ ! _ _!_ _ _ _ _ _ _!############################## ################_ !_! ! _!##_! !_ _ _ _! _!############################## ################_ !_ _! ! !_ ! _ !_ _!############################ ############ ! !_ _ ! _ !_ !_!_!_!_ _!############################ ##########_ !_ !_!_!_ _!######_!_!_!############################## ##########_ ! !_!######_!_!_!############################################ #### ! !##_ !_!_!_!########################################################## ##_ !_ _!############################################################## _ _!_ !_!################################################################ _ _ _ !_!_!################################################################## _ ! _!#################################################################### _ !_ _!#################################################################### _ _ !_!###################################################################### _ _!###################################################################### ##_!_!########################################################################