Difference between revisions of "Simple maze"

From RogueBasin
Jump to navigation Jump to search
Line 554: Line 554:
This script implements a [[recursive backtracking]] maze generator in [[Perl]]:
This script implements a [[recursive backtracking]] maze generator in [[Perl]]:


<div style="background-color: #EEEEEE; border-style: dashed; padding: 1em">
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.5em">
<syntaxhighlight lang="perl">
<syntaxhighlight lang="perl">
#!/usr/bin/env perl
#!/usr/bin/env perl

Revision as of 15:03, 26 December 2014

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 Javascript

This is a javascript port of the visual basic version above.

<!DOCTYPE html>
<html>
	<head>
		<meta charset = "utf-8">
		<title>testing code</title>
		<style type = "text/css">
			body {background-color:black;}
			table {background-color:#222222;border-width:1px;}
			td {width:30px;height:30px;}
			th {color:white;}
			div#title       {background-color:#555555;width:100%;height:100%;}
			div#title:hover {background-color:#999999;}
			div#wall        {background-color:#666666;width:100%;height:100%;}
			div#wall:hover  {background-color:#AAAAAA;}
			div#floor       {background-color:#003300;width:100%;height:100%;}
			div#floor:hover {background-color:#006600;}}
		</style>
		<script>
			// Coordinates of N(x,y) S(x,y) E(x,y) W(x,y)
			// it's necessary to have one of each so that if one direction
			// doesn't work properly, we can try each direction until one
			// works, or that we know there isn't a location possible. 
			var cN = [[0,0],[0,0],[0,0],[0,0]];
			var size = 35,x,y,cx,cy;
			var map = new Array(size);
			var randomDir,intDone=0;
			for (var i = 0; i <= size * size; ++i){
				map[i] = new Array(size);
			}
			// Initialize the Map Array to Zeros 
			for (x=1;x<=size;++x){
				for (y=1;y<=size;++y){
					map[x][y]=0;
				} //end for
			} //end for
			do {
				// Roll random x's and y's and make sure the value is odd
				x=2+Math.floor(Math.random()*(size-1));if (x%2!=0) --x;
				y=2+Math.floor(Math.random()*(size-1));if (y%2!=0) --y;
				// Ensure that the first random map location starts the process
				if (intDone==0) map[x][y]=1;
				if (map[x][y]==1){
					//Randomize Directions
					randomDir=Math.floor(Math.random()*4)
					if (randomDir==0){
						cN = [[-1,0],[1,0],[0,-1],[0,1]];
					} else if (randomDir==1){
						cN = [[0,1],[0,-1],[1,0],[-1,0]];
					} else if (randomDir==2){
						cN = [[0,-1],[0,1],[-1,0],[1,0]];
					} else if (randomDir==3){
						cN = [[1,0],[-1,0],[0,1],[0,-1]];
					} //end if
					blnBlocked=1;
					do {
						blnBlocked++;
						for (var intDir=0; intDir<=3; ++intDir){
							// Determine which direction the tile is
							cx=x+cN[intDir][0]*2;
							cy=y+cN[intDir][1]*2;
							//Check to see if the tile can be used
							if (cx<size && cy<size && cx>1 && cy>1){
								if (map[cx][cy]!=1){
									//create destination location
									map[cx][cy]=1;
									//create current location
									map[x][y]=1
									//create inbetween location
									map[x+cN[intDir][0]][y+cN[intDir][1]]=1;
									//set destination location to current
									x=cx;y=cy;
									blnBlocked=0;
									intDone++;
									intDir=4
								} //end if
							} //end if
						} //end for
						//recursive, no directions found, loop back a node
					} while (blnBlocked==1) //end do
				} //end if
			} while (intDone+1<((size-1)*(size-1))/4) //end do
			document.writeln("<table><tr>");
			for (x=1;x<=size;++x){
				for (y=1;y<=size;++y){
					if (map[x][y]==0){
						document.writeln("<td id='cellx"+x+"y"+y+"'><div id='wall'></div></td>");
					} else if (map[x][y]==1){
						document.writeln("<td id='cellx"+x+"y"+y+"'><div id='floor'></div></td>");
					} //end if
				} //end for
				document.writeln("</tr><tr>");
			} //end for
			document.writeln("<th colspan='"+size+"'><div id='title'>Maze Experiment</div></th></tr></table>");
		</script>
	</head>
	<body></body>
</html>

Maze Generator in Perl

This script implements a recursive backtracking maze generator in Perl:

#!/usr/bin/env perl

use strict;
use warnings;

no warnings 'recursion';
no warnings 'uninitialized';

use List::Util qw/shuffle/;

my $map = [ [] ];
my ( $WIDTH, $HEIGHT ) = ( 50, 30 );

my %DELTA = (
    n => { y => -1 },
    s => { y => 1 },
    e => { x => 1 },
    w => { x => -1 },
);

my %OPPOSITE = (
    n => 's',
    s => 'n',
    e => 'w',
    w => 'e',
);

carve( 1, 1, 'e' );
show_map();

sub carve {
    my ( $x0, $y0, $direction ) = @_;

    my $x1 = $x0 + $DELTA{$direction}{x};
    my $y1 = $y0 + $DELTA{$direction}{y};

    return if $x1 == 0 or $x1 == $WIDTH or $y1 == 0 or $y1 == $HEIGHT;

    return if $map->[$x1][$y1];

    $map->[$x0][$y0]{$direction} = 1;
    $map->[$x1][$y1]{ $OPPOSITE{$direction} } = 1;

    for my $dir ( shuffle keys %DELTA ) {
        carve( $x1, $y1, $dir );
    }
}

sub show_map {
    for my $y ( 0 .. $HEIGHT ) {
        for my $x ( 0 .. $WIDTH ) {
            if ( defined $map->[$x][$y] ) {
                print $map->[$x][$y]{s} ? ' ' : '_';
                print $map->[$x][$y]{e} ? ' ' : '|';
            }
            else {
                print '##';
            }
        }
        print "\n";
    }
}

Examples

######################################################################################################
##_ _ _ _  |  _   _  |   |  _   _|  _  |  _ _ _ _   _ _|    _  | |     |_    |  _ _ _ _    |_   _  |##
##  _    | |_|  _| | |_| |  _|_  | | |_ _|_ _ _  | |  _ _| | | | | | |_ _ _| | | |  _ _ _|_ _ _| | |##
##  _| | |_  | |_  |_  |  _|   | | |_ _ _   _   _|_ _  | | |  _|_ _| |  _  | | | | |   |  _  |  _ _|##
## |  _|_|  _|_  |   | | |  _|_  |  _ _ _ _|_  |   | |_  | |_ _  |  _| |_ _| |_  |_ _| |_  |_ _|_  |##
## |_ _  | |_   _| |_| |_| |  _ _| |  _ _ _  |_| | | |  _|_  |_ _ _|  _ _ _ _|  _|   |   |_ _ _ _  |##
## |  _| |_ _ _|  _ _ _|  _|  _|  _| |  _  |_ _ _| |  _|_  |_ _  |  _|_    |_ _ _| | | | |   |_  | |##
## | |   |   | |_  |   | | | |  _| | | |_ _ _ _ _| |  _ _  |_  | |_ _  | |_ _  |  _| |_| | |_ _  | |##
##  _| | | |_ _|  _| |_ _| | |_  | | |  _  |   |  _|_|   |  _ _| | |  _ _|   |_ _|  _|  _|  _  | | |##
## |  _| | |  _ _|   |   | |  _|  _| |_  | | | |_ _ _ _| | |  _ _|  _ _|  _| |_  | |  _|  _|   |_| |##
## |_  |_  |_  |  _| | | |  _|  _|  _|  _|_ _|  _|  _ _ _| |_  | | | |  _ _| |  _|_ _|  _| | |_|  _|##
##_|  _|  _|  _|_  |_| | |_  | |   |_ _  | |  _|  _|  _ _ _ _| |_  | |_  |  _| |    _|_  | |_ _ _| |##
##  _| |  _| |  _ _|  _|_  | | | |_|   |_  |_  | |_ _|  _ _  |_  |  _|  _|_  |  _| |  _ _|    _  | |##
##   |  _|  _|  _ _ _|_  | |_| | |  _| | |_  | |_ _  | |  _|_  | |_|  _|   | | | | | |_ _ _|_  | | |##
## | |_  |_  |_ _ _ _ _  |_ _ _|  _|  _|_   _|_   _|_ _|  _ _ _|  _ _|  _| | | | | |_ _ _ _ _ _| | |##
##_|_  |_ _|_ _ _ _  |_ _|  _  |_  | |   | |_  |_ _ _  |_ _  |_ _  | |_  |_ _|_  |_ _ _ _ _   _|_  |##
##   | |    _ _ _ _|_ _  | |_  |_ _|  _| |  _ _ _|  _ _  | |_ _  |_ _  |_  |  _ _|_  |   |  _|  _ _|##
## |_ _| |_  |  _ _ _ _ _|   |_ _  |_  | |_|   |  _| |  _ _ _|  _|  _ _| | |_  |  _  | |_ _|  _|_  |##
## |  _ _| | | |  _|   |  _| |   |_  |_|_  | |_ _|   | |  _ _ _| |_ _   _|_  |_ _| | |_ _  |_ _  | |##
## |_ _   _| | |_ _ _|_ _ _| | |  _|_ _ _ _| |  _ _| | |_ _  |  _ _|  _|  _ _|   |  _|_  |_ _  |_  |##
##  _  | |  _| |  _ _ _ _ _ _| |_   _  |   | |_  | |_ _  |  _|  _  | | |_  |   |_| |   |  _|   | | |##
##   |_| | |  _|   |   |    _|_  |_  |_ _|_ _| | | |   |_| | |_  |_ _|  _| | |_ _ _ _|_  |  _| | | |##
## |_ _ _|_ _| | |_ _| | |_   _| | | |_ _  |   | | | |_ _ _|_ _ _   _ _|  _|_|   |  _  | | |_ _ _| |##
##_  |  _ _ _  |_  |  _|_  |_  | | | |   |_ _|_ _  | | |  _    | | |  _ _|  _ _| |   | |_| |  _ _ _|##
##  _| |_ _   _ _| | |_  | |  _| | |_ _|_ _ _ _  | | |_   _| | |_  |_ _   _|  _ _|_| |_ _  |_  |  _|##
## |_ _ _  |_|  _ _|   |_  |_  |_  |_ _ _    |  _|_|_  | |  _|_  |_|   |_  |_  |   | |_ _ _|  _|_  |##
##_ _ _  |  _ _|   |_|_  |_  |_ _ _|  _  |_| |_ _ _ _ _|_|_ _  |_  | | |  _| |_ _| |_ _    |_ _ _  |##
## |  _ _|_  |  _|_ _ _ _|  _|  _   _| |_ _ _ _ _ _  |  _ _  |_  |_ _| |_ _ _|   |_ _  | |  _ _ _| |##
##  _|  _  |_|_  |    _ _|_  |_ _| |   |  _   _ _ _| |_ _  |_ _ _|  _|_  |  _ _| |  _ _| | |  _ _ _|##
##_ _ _|_ _ _ _ _|_|_ _ _ _ _ _ _ _|_|_ _ _|_ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _|_ _ _ _|_ _ _|_ _ _ _ _|##
######################################################################################################