Simple maze

From RogueBasin
Jump to navigation Jump to search

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 ($w, $h) = (53, 17);
my $bMaze = generateMaze(w=>$w, h=>$h);

for (my $y = 0; $y < $h; ++$y) {
        for (my $x = 0; $x < $w; ++$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;
}