Perfect Maze Generation

[impixiParticipant]

The following example generates a “perfect maze” within a 2d bool array using an iterative, depth-first technique. (I sometimes use the approach as a basis for some types of procedural dungeons.)

Monkey

'Perfect Maze Generation Example #Import "<std>" #Import "<mojo>" Using std.. Using mojo.. Function Main() New AppInstance New MyWindow App.Run() End Class MyWindow Extends Window Field _maze:Bool[,] Field _cols:Int, _rows:Int Field _cellWidth:Int, _cellHeight:Int Method New(title:String = "Perfect Maze Generation Example", width:Int = 640, height:Int = 480, flags:WindowFlags = Null) Super.New(title, width, height, flags) _cellWidth = 16 _cellHeight = 16 _cols = Width / _cellWidth _rows = Height / _cellHeight _maze = New Bool[_cols, _rows] GenerateMaze() End Method GenerateMaze:Void() GenerateMaze2d(_maze) End Method RenderMaze:Void(canvas:Canvas) canvas.Clear(Color.Blue) canvas.Color = Color.Yellow For Local c := 0 Until _cols For Local r := 0 Until _rows If _maze[c, r] Then canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next End Method OnRender( canvas:Canvas ) Override App.RequestRender() RenderMaze(canvas) canvas.Color = Color.Black canvas.DrawText("Left Click to generate new maze.", _cellWidth, 0) canvas.Flush() End Method OnKeyEvent(event:KeyEvent) Override If event.Type = EventType.KeyDown And event.Key = Key.Escape Then App.Terminate() End Method OnMouseEvent(event:MouseEvent) Override If event.Type = EventType.MouseClick Then GenerateMaze() End End '========================== Struct Cell Public Field North:Bool = True Field East:Bool = True Field South:Bool = True Field West:Bool = True End 'Generate a perfect maze within a 2d Bool array using an iterative, depth-first technique. '(Overwrites existing array data.) Function GenerateMaze2d:Void(arr2d:Bool[,]) If Not arr2d Then Return 'Expecting columns x rows grid format. One wall per cell. Local cols:Int = arr2d.GetSize(0) Local rows:Int = arr2d.GetSize(1) '--- Create a grid of Cell structures with dimensions ~half those of the passed in arr2d. '(Because the maze generation code uses "NESW wall-surrounded" cells rather than the '"block per cell" format of the passed arr2d.) Local cellCols:Int If (cols Mod 2 <> 0) Then cellCols = Floor(cols / 2) Else cellCols = Floor((cols - 1) / 2) Local cellRows:Int If (rows Mod 2 <> 0) Then cellRows = Floor(rows / 2) Else cellRows = Floor((rows - 1) / 2) Local cellMaze:= New Cell[cellCols, cellRows] '--- 'Store the path coordinates in a 1d array. '(Could use a Stack<Vec2i>.) Local totalCells:Int = cellRows * cellCols Local track := New Vec2i[totalCells] 'track[i].X is column, track[i].Y is row Local tri:Int = 0 'track index Local curCoord:Vec2i Local visited:int, i:Int, mazei:Int, nbi:Int, r:Int, c:Int 'Initialize the maze-related data structures. For r = 0 Until cellRows For c = 0 Until cellCols cellMaze[c, r] = New Cell() i = (r * cellCols) + c track[i] = New Vec2i Next Next '4 directions Local dir:= New Vec2i[4] Local nextCoord := New Vec2i[4] For i = 0 Until dir.Length dir[i] = New Vec2i nextCoord[i] = New Vec2i Next dir[0].Y = -1 'north dir[1].X = 1 'east dir[2].Y = 1 'south dir[3].X = -1 'west curCoord.Y = Floor(Rnd(0, cellRows)) curCoord.X = Floor(Rnd(0, cellCols)) visited = 1 'counter While (visited < totalCells) nbi = 0 For i = 0 Until dir.Length r = curCoord.Y + dir[i].Y c = curCoord.X + dir[i].X If (r >= 0) And (r < cellRows) And (c >= 0) And (c < cellCols) If (cellMaze[c, r].North) And (cellMaze[c, r].East) And (cellMaze[c, r].South) And (cellMaze[c, r].West) nextCoord[nbi].Y = r nextCoord[nbi].X = c nbi += 1 Endif Endif Next if (nbi >= 1) i = Floor(Rnd(0, nbi)) If (nextCoord[i].Y - curCoord.Y) = 0 Then r = nextCoord[i].Y If nextCoord[i].X > curCoord.X Then c = curCoord.X cellMaze[c, r].East = False c = nextCoord[i].X cellMaze[c, r].West = False else c = curCoord.X cellMaze[c, r].West = False c = nextCoord[i].X cellMaze[c, r].East = False endif else c = nextCoord[i].X If nextCoord[i].Y > curCoord.Y Then r = curCoord.Y cellMaze[c, r].South = False r = nextCoord[i].Y cellMaze[c, r].North = False Else r = curCoord.Y cellMaze[c, r].North = False r = nextCoord[i].Y cellMaze[c, r].South = false endif Endif tri += 1 track[tri].Y = curCoord.Y track[tri].X = curCoord.X curCoord.Y = nextCoord[i].Y curCoord.X = nextCoord[i].X visited += 1 Else curCoord.Y = track[tri].Y curCoord.X = track[tri].X tri -= 1 Endif Wend '--- Remap maze cells to 2d Bool array. 'True = Wall/Block cell. 'False = Empty cell. 'Initialise all cells as blocked. For Local r := 0 Until rows For Local c := 0 Until cols arr2d[c, r] = True Next Next Local mazer:Int, mazec:Int For Local r := 0 Until cellRows mazer = (r * 2) + 1 For Local c := 0 Until cellCols mazec = (c * 2) + 1 arr2d[mazec, mazer] = False 'West/East and North/South overlap, so only need to check one of each. If (Not cellMaze[c, r].West) Then arr2d[mazec - 1, mazer] = False If (Not cellMaze[c, r].North) Then arr2d[mazec, mazer - 1] = False Next Next '--- End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233

'Perfect Maze Generation Example   #Import "<std>" #Import "<mojo>"   Using std.. Using mojo..   Function Main() New AppInstance New MyWindow App.Run() End   Class MyWindow Extends Window   Field _maze:Bool[,] Field _cols:Int, _rows:Int Field _cellWidth:Int, _cellHeight:Int   Method New(title:String = "Perfect Maze Generation Example", width:Int = 640, height:Int = 480, flags:WindowFlags = Null) Super.New(title, width, height, flags) _cellWidth = 16 _cellHeight = 16 _cols = Width / _cellWidth _rows = Height / _cellHeight _maze = New Bool[_cols, _rows] GenerateMaze() End   Method GenerateMaze:Void() GenerateMaze2d(_maze) End   Method RenderMaze:Void(canvas:Canvas) canvas.Clear(Color.Blue) canvas.Color = Color.Yellow For Local c := 0 Until _cols For Local r := 0 Until _rows If _maze[c, r] Then canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next End   Method OnRender( canvas:Canvas ) Override App.RequestRender() RenderMaze(canvas) canvas.Color = Color.Black canvas.DrawText("Left Click to generate new maze.", _cellWidth, 0) canvas.Flush() End Method OnKeyEvent(event:KeyEvent) Override If event.Type = EventType.KeyDown And event.Key = Key.Escape Then App.Terminate() End Method OnMouseEvent(event:MouseEvent) Override If event.Type = EventType.MouseClick Then GenerateMaze() End End     '==========================     Struct Cell   Public Field North:Bool = True Field East:Bool = True Field South:Bool = True Field West:Bool = True End   'Generate a perfect maze within a 2d Bool array using an iterative, depth-first technique. '(Overwrites existing array data.)   Function GenerateMaze2d:Void(arr2d:Bool[,]) If Not arr2d Then Return   'Expecting columns x rows grid format. One wall per cell. Local cols:Int = arr2d.GetSize(0) Local rows:Int = arr2d.GetSize(1) '--- Create a grid of Cell structures with dimensions ~half those of the passed in arr2d. '(Because the maze generation code uses "NESW wall-surrounded" cells rather than the '"block per cell" format of the passed arr2d.) Local cellCols:Int If (cols Mod 2 <> 0) Then cellCols = Floor(cols / 2) Else cellCols = Floor((cols - 1) / 2) Local cellRows:Int If (rows Mod 2 <> 0) Then cellRows = Floor(rows / 2) Else cellRows = Floor((rows - 1) / 2)   Local cellMaze:= New Cell[cellCols, cellRows] '--- 'Store the path coordinates in a 1d array. '(Could use a Stack<Vec2i>.) Local totalCells:Int = cellRows * cellCols Local track := New Vec2i[totalCells] 'track[i].X is column, track[i].Y is row Local tri:Int = 0 'track index Local curCoord:Vec2i Local visited:int, i:Int, mazei:Int, nbi:Int, r:Int, c:Int 'Initialize the maze-related data structures.     For r = 0 Until cellRows         For c = 0 Until cellCols          cellMaze[c, r] = New Cell()          i = (r * cellCols) + c          track[i] = New Vec2i         Next     Next   '4 directions Local dir:= New Vec2i[4] Local nextCoord := New Vec2i[4] For i = 0 Until dir.Length dir[i] = New Vec2i nextCoord[i] = New Vec2i Next     dir[0].Y = -1 'north     dir[1].X = 1 'east     dir[2].Y = 1 'south     dir[3].X = -1 'west curCoord.Y = Floor(Rnd(0, cellRows)) curCoord.X = Floor(Rnd(0, cellCols)) visited = 1 'counter While (visited < totalCells)         nbi = 0         For i = 0 Until dir.Length             r = curCoord.Y + dir[i].Y             c = curCoord.X + dir[i].X             If (r >= 0) And (r < cellRows) And (c >= 0) And (c < cellCols)                 If (cellMaze[c, r].North) And (cellMaze[c, r].East) And (cellMaze[c, r].South) And (cellMaze[c, r].West)                     nextCoord[nbi].Y = r                     nextCoord[nbi].X = c                     nbi += 1                 Endif             Endif         Next                  if (nbi >= 1)             i = Floor(Rnd(0, nbi))             If (nextCoord[i].Y - curCoord.Y) = 0 Then                     r = nextCoord[i].Y                 If nextCoord[i].X > curCoord.X Then                           c = curCoord.X                     cellMaze[c, r].East = False                     c = nextCoord[i].X                     cellMaze[c, r].West = False                 else                                                     c = curCoord.X                     cellMaze[c, r].West = False                     c = nextCoord[i].X                     cellMaze[c, r].East = False                 endif             else                                                     c = nextCoord[i].X                 If nextCoord[i].Y > curCoord.Y Then                           r = curCoord.Y                     cellMaze[c, r].South = False                     r = nextCoord[i].Y                     cellMaze[c, r].North = False                 Else                                                     r = curCoord.Y                     cellMaze[c, r].North = False                     r = nextCoord[i].Y                     cellMaze[c, r].South = false                 endif             Endif               tri += 1             track[tri].Y = curCoord.Y             track[tri].X = curCoord.X               curCoord.Y = nextCoord[i].Y             curCoord.X = nextCoord[i].X                        visited += 1         Else             curCoord.Y = track[tri].Y             curCoord.X = track[tri].X             tri -= 1         Endif     Wend   '--- Remap maze cells to 2d Bool array. 'True = Wall/Block cell. 'False = Empty cell. 'Initialise all cells as blocked. For Local r := 0 Until rows For Local c := 0 Until cols arr2d[c, r] = True Next Next Local mazer:Int, mazec:Int   For Local r := 0 Until cellRows mazer = (r * 2) + 1 For Local c := 0 Until cellCols mazec = (c * 2) + 1 arr2d[mazec, mazer] = False 'West/East and North/South overlap, so only need to check one of each. If (Not cellMaze[c, r].West) Then arr2d[mazec - 1, mazer] = False If (Not cellMaze[c, r].North) Then arr2d[mazec, mazer - 1] = False Next Next   '---   End

Theory:

https://en.wikipedia.org/wiki/Maze_generation_algorithm

[EthernautParticipant]

Yay, code snippets! Thanks for sharing.

[peteswansenParticipant]

Thanks Impixi, this is the first piece of Monky 2 code I was ever able to compile!

The mazes it makes are not quite complete- they have numerous “dead” ends and there is no single complete path from one side to the other-  in other words, there is not one entrance and one exit.

A shame there  is only 10 examples of code and over 1800 posts looking for help with Monkey 2.

[impixiParticipant]

@peteswansen:

The mazes it makes are not quite complete- they have numerous “dead” ends and there is no single complete path from one side to the other- in other words, there is not one entrance and one exit.

The code generates “perfect” mazes, meaning every coordinate is reachable from every other coordinate within the maze. There are many types of mazes. See here:

http://www.astrolog.org/labyrnth/algrithm.htm

A shame there is only 10 examples of code and over 1800 posts looking for help with Monkey 2.

The “Monkey 2 Code Library” forum is only a week old. More examples will be posted over time. Personally I have more examples to post when I tidy up my code, but at the moment I’m too busy working on other projects.

[Author]

Posts