Difference between revisions of "Simple maze"
Jump to navigation
Jump to search
(added perl version) |
|||
| Line 437: | Line 437: | ||
== Maze Generator in Perl == | == Maze Generator in Perl == | ||
This is a perl port of the visual basic version above. | |||
<pre> | <pre> | ||
| Line 451: | Line 453: | ||
} | } | ||
# options are: w (width), h (height) and rand (randomness) | # named options are: w (width), h (height) and rand (randomness) | ||
sub generateMaze { | sub generateMaze { | ||
Revision as of 07:48, 21 January 2009
Maze Generator in C++
Simple maze generator written in 10 minutes :) The source code is public domain.
// Simple Maze Generator in C++ by Jakub Debski '2006
#include <time.h>
#include <vector>
#include <list>
using namespace std;
int main()
{
srand(time(0));
const int maze_size_x=80;
const int maze_size_y=25;
vector < vector < bool > > maze;
list < pair < int, int> > drillers;
maze.resize(maze_size_y);
for (size_t y=0;y<maze_size_y;y++)
maze[y].resize(maze_size_x);
for (size_t x=0;x<maze_size_x;x++)
for (size_t y=0;y<maze_size_y;y++)
maze[y][x]=false;
drillers.push_back(make_pair(maze_size_x/2,maze_size_y/2));
while(drillers.size()>0)
{
list < pair < int, int> >::iterator m,_m,temp;
m=drillers.begin();
_m=drillers.end();
while (m!=_m)
{
bool remove_driller=false;
switch(rand()%4)
{
case 0:
(*m).second-=2;
if ((*m).second<0 || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second+1][(*m).first]=true;
break;
case 1:
(*m).second+=2;
if ((*m).second>=maze_size_y || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second-1][(*m).first]=true;
break;
case 2:
(*m).first-=2;
if ((*m).first<0 || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second][(*m).first+1]=true;
break;
case 3:
(*m).first+=2;
if ((*m).first>=maze_size_x || maze[(*m).second][(*m).first])
{
remove_driller=true;
break;
}
maze[(*m).second][(*m).first-1]=true;
break;
}
if (remove_driller)
m = drillers.erase(m);
else
{
drillers.push_back(make_pair((*m).first,(*m).second));
// uncomment the line below to make the maze easier
// if (rand()%2)
drillers.push_back(make_pair((*m).first,(*m).second));
maze[(*m).second][(*m).first]=true;
++m;
}
}
}
// Done
for (size_t y=0;y<maze_size_y;y++)
for (size_t x=0;x<maze_size_x;x++)
{
if (maze[y][x]==true)
printf(".");
else
printf("#");
}
return 0;
}
Examples
######.........#.#.......#.....#...#.....#.........#.#...#.#.......#.......##### ######.#.###.#.#.#.#######.#.#####.#.###.#.#.#####.#.###.#.#.#######.########### .....#.#.#...#.#.........#.#.#.....#.###...#.#.....#.......#.......#.....####### .#.#.###.#.#####.#.#.#######.#.#.#.#.#####################.#.###.#######.####### .#.#.#...#...#...#.#...#.#.#.#.#.#.#.........#.....#...........#.#.............# ####.#.#######.#######.#.#.#.#.#.#######.#.#.#.#.#.#.#######.#######.#######.#.# ##...#...#####.#.#####.#...#...#.#...#.#.#.#...#.#...###...#.#.......#.......#.# ####.###.#####.#.#####.#.###.#.###.###.#.#.###.#########.#####.###.############# .........###.#.....###.#...#.#.#.#.......#.#...#...#.#.#.#.......#.###...#.....# ########.###.#.#.#.###.#.#.###.#.#.#####.#.###.#.###.#.#.#.#.###.#####.###.#.### .......#.....#.#.#.#...#.#...........#...#.#.....#.......#.#...#.#.........#...# ####.#.#.#####.#.###.#######.#######.###.#.#.###.#.#####.#.#####.#.#.#####.##### ...#.#.#.......#...#.....#.....#.#...#####.#...#.......#.#...#.....#...#.#.....# ##.###.#.#.#.###.#####.#.#####.#.#.#######.#####.#####.#.###.#.###.#####.#####.# ##...#...#.#.#.......#.#.....#...#.......#...#...#.....#.....#...#...........#.# ####.#.###########.###.#.###.#####.#######.###.###########.###.###.#####.###.### ####...###.....#...#.#.#...#...........###...#.###...#.###.###...#.....#.#.....# ####.#####.#######.#.###.###.#.#####.#.#############.#.###.#####.#####.#.###.### ####.........#.#...#.....#.#.#.#.....#.###.#...#.............#...#####.#...#...# ######.#.#####.#.###.#.#.#.###.#######.###.#.#####.###.#################.####### ######.#...#.#.....#.#.#.#...#...###...###.....#...#.......#########...#.......# ######.###.#.#####.#####.#.###.#.###.#.###.#.###.###.#####.#########.#########.# ######.#.#.#...###...#...#.#.#.#...#.#.....#.#.#...#.###...#########...#.......# ########.#.###.#######.#.#.#.###.#######.###.#.#####.###############.#.###.##### ########...###.........#.#.......#######.#.....#####.......#########.#.........#
With little changes you can get cool results, f.e.
else
{
// drillers.push_back(make_pair((*m).first,(*m).second));
// drillers.push_back(make_pair((*m).first,(*m).second));
// change to
for (size_t index=0;index<10;index++)
drillers.push_front(make_pair((*m).first,(*m).second));
gives "star-like" effect:
.#.#...#...#.....#...#...#...#.#...#...#.....#...#...#.......#...#.....#.....#.# .#.###.###.#####.###.###.###.#.###.###.#.#####.###.###.#######.###.#####.#####.# ...#.#...#...#...#.#...#...#...#.#...#.....#...#.......#.............#.#...#...# ##.#.###.###.###.#.###.###.###.#.###.#.#####.###.#######.#############.#.###.### .......#...#.#.#.....#.#.#.......#.#.....#...#...#.#...#...#...#.#.#.#...#...#.# ######.###.#.#.#####.#.#.#######.#.###.###.###.###.#.###.###.###.#.#.#.###.###.# ...#.#...#...#...#.......#.#...#.....#.....#...#.....#...#...#.#.......#...#...# ##.#.###.###.###.#######.#.###.#####.#.#####.###.#####.###.###.#.#######.###.### .#...#.#.#.#...#.#.#.....#.#.#...#.......#...#.#...#.#.#...#.#...#.#...#.#...#.# .###.#.#.#.###.#.#.#####.#.#.###.#####.###.###.#.###.#.#.###.#.###.#.###.#.###.# .................#...#...#.#.#.#...#...#.......................................# ####.###.###.###.###.###.#.#.#.###.###.#.###.###.###.###.###.###.###.###.###.### .#.#.#.#.#.#.#...........................#.#.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.# .#.###.###.#####.#.#.#####.#####.#.###.#.#.###.###.###.###.###.#######.###.###.# .................#.#.#.....#.....#.#...#.......................................# ##.###.#.###.#.###.#####.###.#.#.#####.###.#.#.###.#.###.###.#.#.###.#.###.#.#.# ...#...#.#...#.#...#.....#...#.#.#.......#.#.#...#.#...#...#.#.#...#.#...#.#.#.# .###.#.###.#.###.#.#######.#.#.#####.#.#####.###.###.#.#######.###.###.#.###.### .#...#.#...#.#...#.#.......#.#.#.....#.....#...#...#.#.......#...#...#.#...#...# ##.#.#####.###.#.###.###.###.#####.###.#.#.###.###.###.#.###.###.#.#####.#####.# ...#.#.....#...#.#...#...#...#.....#...#.#...#...#...#.#...#...#.#.....#.....#.# .#.###.#.#####.###.###.###.###.#.###.#.###.#.###.###.###.#####.###.###.###.#.### .#.#...#.#.....#...#...#...#...#.#...#...#.#...#...#...#.....#...#...#...#.#...# .#####.#####.###.###.###.###.#.###.###.#####.#.###.###.###.#.###.#.#.###.###.### .#.....#.....#...#...#...#...#.#...#.......#.#...#...#...#.#...#.#.#...#...#...#
or
(*m).second-=2;
// if ((*m).second<0 || maze[(*m).second][(*m).first])
// change to
if ((*m).second<0 || (maze[(*m).second][(*m).first] && rand()%5))
allows loops (sample loop top left corner is marked with comas):
.......#,,,,,,,,.#####.....#####...#...............#...#.###.....###...#.#.#.### .#######,#####.#,#######.#######.#.#############.#.###.#.###.#########.#.#.#.### .#...#..,,,,,#.#,,,###...#######.#.#...#.........#.....#.......................# .#.###.#####,#####,###.#.#########.#.#########.#####.#.#.###.#.#########.#.#.#.# .#.....#....,,,,,,,....#.#######.....#...#...#...###.#.......#.###.#.....#.#...# .#.#.#####.#.#.###.#################.#.#.###.#######.#####.###.###.#.#####.##### .#...#.....#.....#.#...#.......#.#...#.#.....#######...#...#...#.#.#.###...#.### .#.###.###.#.###.#.###.#.#######.#.#.###.#.#.#######.###########.#.#######.#.### ...#...#.#.#.#...#.....#.....#...#.#.....#...#.#####.......#.....#.........#...# ####.#.#.#.#####.#.#.#.###.#.###.#######.#.#.#.#######.#.#.#.#.#.###.#######.### ...#.#.#.....#.....#.#.#...#.#...#.....#.#.#...#...#...#.#...#.#...............# .###.###.#####.#######.###.#.###.#.###.###.#.#.#.#####.#######.###.#######.#.#.# .....#.#.#...#...#...#.#...#...........#.....#.........#.#####.#...#...###...#.# ##.###.#.#.#.#.#.#.#########.#.###.###.#.###.#######.###.#####.###.#.#.###.##### ...#.......#...#...#.......#.#.#...#...#...#.#.#...#.#.....#...#...#.#.#...#...# ####.#.#######.#.#.#.###.###.#.#.#####.#####.#.#.#####.#.#.#.#.#######.#####.### .......#...#...#.#.....#.#...#...#...............#.....#.#...#...........#...### ##.#####.###########.#####.#########.#.###.###.#.#########.###.###.#.#.###.#.### .......#...#.#.......#.....#.....#...#.#.....#.#.#...........#...#.....#.#.#...# ##.#.###.###.#.#.###.#######.#.#.#####.###.#####.###.#.#.#####.###.#.###.###.### ##.#...#.......#...#.........#.#.......#...###.#.....#...#####...#.............# ########.###.#.#.#########.#####.#.#####.#####.#.#####.#.#####.#####.#.#.####### ##.........#.#...#.#...#...#...#.....#.....#...#.....#.#.#####.....#...#.....### ######.###.#.#.###.#.###.#.#.###.#.#.#.#.#.###.#####.#.#######.#.#.###.######### ##.......#.#...........#.#.....#.#.#.#.#.#.....###...#.###.......#...#...#######
Maze Generator in Visual Basic 6
''''''''''''''''''''''''''
' Perfect Maze Generator '
' Icey '
' Oct 2006 '
' Public Domain '
''''''''''''''''''''''''''
' this code is designed to be run from a module, using sub main
' all variables are declared
Option Explicit
' 0 is the most random, randomisation gets lower after that
' less randomisation means more straight corridors
Private Const RANDOMISATION As Integer = 5
' the spaces across - this must be an odd number
Private Const MAZE_X As Integer = 53
' the spaces down - this must be an odd number
Private Const MAZE_Y As Integer = 17
' used for storing the current square and squares potentially to move to
Private Type COORDS
X As Integer
Y As Integer
End Type
' stores the directions that corridors go in
Dim cDir(3) As COORDS
' these can be any odd numbers
Dim blnMaze(MAZE_X, MAZE_Y) As Boolean
Private Sub GenerateMaze()
Dim cN As COORDS, cS As COORDS
Dim intDir As Integer, intDone As Integer
Dim blnBlocked As Boolean
Randomize
Erase blnMaze
Do
' this code is used to make sure the numbers are odd
cS.X = 2 + (Int(((MAZE_X - 1) * Rnd) / 2) * 2)
cS.Y = 2 + (Int(((MAZE_Y - 1) * Rnd) / 2) * 2)
' first one is free!
If intDone = 0 Then blnMaze(cS.X, cS.Y) = True
If blnMaze(cS.X, cS.Y) Then
' always randomisation directions to start
RandomDirections
Do
' only randomisation directions, based on the constant
If Int(RANDOMISATION * Rnd) = 0 Then RandomDirections
blnBlocked = True
' loop through order of directions
For intDir = 0 To 3
' work out where this direction is
cN.X = cS.X + (cDir(intDir).X * 2)
cN.Y = cS.Y + (cDir(intDir).Y * 2)
' check if the tile can be used
If IsFree(cN) Then
' create a path
blnMaze(cN.X, cN.Y) = True
' and the square inbetween
blnMaze(cS.X + cDir(intDir).X, cS.Y + cDir(intDir).Y) = True
' this is now the current square
cS.X = cN.X
cS.Y = cN.Y
blnBlocked = False
' increment paths created
intDone = intDone + 1
Exit For
End If
Next
' loop until a path was created
Loop Until blnBlocked
End If
' create enough paths to fill the whole grid
Loop While intDone + 1 < ((MAZE_X - 1) * (MAZE_Y - 1)) / 4
End Sub
' this changes the direction to go from the current square, to the next available
Private Sub RandomDirections()
' clear the array
Erase cDir
' four possible sets of directions
Select Case Int(3 * Rnd)
Case 0
cDir(0).X = -1: cDir(1).X = 1
cDir(2).Y = -1: cDir(3).Y = 1
Case 1
cDir(3).X = -1: cDir(2).X = 1
cDir(1).Y = -1: cDir(0).Y = 1
Case 2
cDir(2).X = -1: cDir(3).X = 1
cDir(0).Y = -1: cDir(1).Y = 1
Case 3
cDir(1).X = -1: cDir(0).X = 1
cDir(3).Y = -1: cDir(2).Y = 1
End Select
End Sub
' checks if a tile is free for use
Private Function IsFree(cF As COORDS) As Boolean
' check it's within the grid
If cF.X < MAZE_X And cF.X > 1 And cF.Y < MAZE_Y And cF.Y > 1 Then
' check it hasn't been used yet
IsFree = (blnMaze(cF.X, cF.Y) = False)
End If
End Function
' this code should be run from a module
' go to Project > [projectname] Properties
' and then select Sub Main from the Startup Object list
Sub Main()
' the maze is added to this string, which is then copied to the clipboard
Dim strOutput As String
GenerateMaze
Dim A As Integer, B As Integer
' loop through squares
For A = 1 To MAZE_Y
For B = 1 To MAZE_X
' check if a path was created here
If blnMaze(B, A) Then
' empty
strOutput = strOutput & " "
Else
' wall
strOutput = strOutput & "#"
End If
Next
' go down to the next row
strOutput = strOutput & vbNewLine
Next
Clipboard.Clear
Clipboard.SetText strOutput
' tell the user what has happened
MsgBox "Maze copied to the clipboard.", vbInformation, "Maze generator"
End Sub
Examples
Randomisation: 0 ########################################### # # # # # # # ### # ##### # # ##### ### ### # ### ##### # # # # # # # # # # # # # # # # # # # # # # ##### ##### # # # # ##### # # # # # # # # # # # # # # # # ##### # # # ### # ### ######### ##### # # # # # # # # # # # # # # # # # ### ### # # ### # ### # # # # # ##### ### # # # # # # # # # # # # # # # # # ### # # # ### # # ### ########### ### # # # # # # # # # # # # # # # ######### # ######### # # # ### # # ### # # # # # # # # # # # # # # # # # # # # ### # # ### ### # ### # # ### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # ### # ### # # ##### # # # # # # # # # # # # # # # # # # # ### # # # # # # ### # ### ##### # # # # # # # # # # # # # # # # # ####### # # # ######### ### ########### # # # # # # ###########################################
Randomisation: 5 ##################################################### # # # # # # # ############### # # # # ##################### # # # # # # # # # # # # # # ####### # # # # # # # # ######################### # # # # # # # # # # # # # # # # # # # # ### ##### # # # # # ################### # # # # # # # # # # # # # # # # # # # # # # # # # # ### # # # # # ### ######### # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # ##### ##### # # # # ######### # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # ########### # # ######### # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ### # # # # # # # # # # # # # # # # # #####################################################
Randomisation: 25 ################################################### # # # # # # # ### # # # # # # # # # # ######################### # # # # # # # # # # # # # # ##### # # # # # # ### ############### ######### # # # # # # # # # # # # # # # # # # # ##### # # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ### # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # ### # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # ##### # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # ### # # ####### # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ###################################################
Maze Generator in Perl
This is a perl port of the visual basic version above.
use strict;
use warnings;
my $bMaze = generateMaze(w=>53, h=>17);
for (my $y = 0; $y < 17; ++$y) {
for (my $x = 0; $x < 53; ++$x) {
print $bMaze->[$x][$y] ? '.' : '#';
}
print "\n";
}
# named options are: w (width), h (height) and rand (randomness)
sub generateMaze {
my %opts = @_;
my ($cNx,$cNy, $cSx, $cSy);
my $intDir;
my $intDone = 0;
my $blnBlocked;
use constant X => 0;
use constant Y => 1;
$opts{rand} = 5 if !$opts{rand};
warn("Must specify width and height of maze") && return undef
if (!$opts{w} || !$opts{h});
$opts{w} -= 1 if !$opts{w}%2;
$opts{h} -= 1 if !$opts{h}%2;
# stores the directions that corridors go in
my @cDir;
my @blnMaze;
do {
# this code is used to make sure the numbers are odd
$cSx = 1 + (int((($opts{w} - 1) * rand()) / 2) * 2);
$cSy = 1 + (int((($opts{h} - 1) * rand()) / 2) * 2);
# first opening is free!
$blnMaze[$cSx][$cSy] = 1 if !$intDone;
if ($blnMaze[$cSx][$cSy]) {
# randomize directions to start
@cDir = &getRandomDirections();
do {
# only randomisation directions, based on the constant
@cDir = &getRandomDirections() if !int($opts{rand} * rand());
$blnBlocked = 1;
# loop through order of directions
for ($intDir = 0; $intDir < 4; ++$intDir) {
# work out where this direction is
$cNx = $cSx + ($cDir[$intDir][X] * 2);
$cNy = $cSy + ($cDir[$intDir][Y] * 2);
# check if the tile can be used
my $isFree;
if ($cNx < ($opts{w}-1) && $cNx >= 1 && $cNy < ($opts{h}-1) && $cNy >= 1) {
# true if it hasn't been used yet
$isFree = !$blnMaze[$cNx][$cNy];
}
if ($isFree) {
# create a path
$blnMaze[$cNx][$cNy] = 1;
# and the square inbetween
$blnMaze[$cSx + $cDir[$intDir][X]][$cSy + $cDir[$intDir][Y]] = 1;
# this is now the current square
$cSx = $cNx;
$cSy = $cNy;
$blnBlocked = 0;
# increment paths created
$intDone = $intDone + 1;
last;
}
}
# loop until a path was created
} while (!$blnBlocked)
}
} while ( $intDone + 1 < ( (($opts{w} - 1) * ($opts{h} - 1)) / 4 ) );
# create enough paths to fill the whole grid
# this changes the direction to go from the current square, to the next available
sub getRandomDirections {
# clear the array
my @a = ([-1,0],[1,0],[0,-1],[0,1]);
my @b;
while (@a) {
push @b, splice(@a, rand()*scalar(@a), 1);
}
return @b;
}
# return a ref to the boolean maze... walls are "false"
return \@blnMaze;
}