Maze generation: Difference between revisions
Content added Content deleted
(→{{header|PureBasic}}: Updated code to add clarity and to generalize it) |
|||
Line 668: | Line 668: | ||
EndDataSection |
EndDataSection |
||
#cellDWidth = 4 |
|||
⚫ | |||
Structure mazeOutput |
|||
vWall.s |
|||
hWall.s |
|||
EndStructure |
|||
⚫ | |||
Global Dim offset.POINT(#numOffsets, #numDirs) |
Global Dim offset.POINT(#numOffsets, #numDirs) |
||
Define i, j |
Define i, j |
||
Line 680: | Line 688: | ||
For i = 0 To #numDirs: Read.i wallvalue(i): Next |
For i = 0 To #numDirs: Read.i wallvalue(i): Next |
||
⚫ | |||
Procedure makeDisplayMazeRow(Array mazeRow.mazeOutput(1), Array maze(2), y) |
|||
⚫ | |||
;modify mazeRow() to produce output of 2 strings showing the vertical walls above and horizontal walls across a given maze row |
|||
⚫ | |||
Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2) |
Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2) |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
mazeRow(0)\vWall = Left(vWall, mazeWidth * #cellDWidth + 1) |
|||
If y <> mazeHeight: mazeRow(0)\hWall = Left(hWall, mazeWidth * #cellDWidth + 1): Else: mazeRow(0)\hWall = "": EndIf |
|||
EndProcedure |
|||
⚫ | |||
Protected x, y, vWall.s, hWall.s, mazeHeight = ArraySize(maze(), 2) |
|||
Protected Dim mazeRow.mazeOutput(0) |
|||
For y = 0 To mazeHeight |
For y = 0 To mazeHeight |
||
makeDisplayMazeRow(mazeRow(), maze(), y) |
|||
⚫ | |||
PrintN(mazeRow(0)\vWall): PrintN(mazeRow(0)\hWall) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
PrintN(Left(vWall, Len(vWall) - 3)) |
|||
If y <> mazeHeight: PrintN(hWall): EndIf |
|||
Next |
Next |
||
EndProcedure |
EndProcedure |
||
Procedure generateMaze(Array maze(2), mazeWidth, mazeHeight) |
Procedure generateMaze(Array maze(2), mazeWidth, mazeHeight) |
||
Dim maze(mazeWidth, mazeHeight) ; |
Dim maze(mazeWidth, mazeHeight) ;Each cell specifies walls present above and to the left of it, |
||
;array includes an extra row and column for the right and bottom walls |
|||
Dim visited(mazeWidth + 1, mazeHeight + 1) ;includes padding for easy border detection |
|||
Dim visited(mazeWidth + 1, mazeHeight + 1) ;Each cell represents a cell of the maze, an extra line of cells are included |
|||
;as padding around the representative cells for easy border detection |
|||
Protected i |
Protected i |
||
;mark outside border as already visited (off limits) |
;mark outside border as already visited (off limits) |
||
For i = |
For i = 0 To mazeWidth |
||
visited(i |
visited(i + offset(#visited, #dir_N)\x, 0 + offset(#visited, #dir_N)\y) = #True |
||
visited(i + offset(#visited, #dir_S)\x, mazeHeight - 1 + offset(#visited, #dir_S)\y) = #True |
|||
Next |
Next |
||
For i = |
For i = 0 To mazeHeight |
||
visited(0 |
visited(0 + offset(#visited, #dir_W)\x, i + offset(#visited, #dir_W)\y) = #True |
||
visited(mazeWidth - 1 + offset(#visited, #dir_E)\x, i + offset(#visited, #dir_E)\y) = #True |
|||
Next |
Next |
||
;generate maze |
;generate maze |
||
Protected x = Random(mazeWidth - 1), y = Random (mazeHeight - 1), cellCount, nextCell |
Protected x = Random(mazeWidth - 1), y = Random (mazeHeight - 1), cellCount, nextCell |
||
visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True |
visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True |
||
PrintN(" |
PrintN("Maze of size " + Str(mazeWidth) + " x " + Str(mazeHeight) + ", generation started at " + Str(x) + " x " + Str(y)) |
||
NewList stack.POINT() |
NewList stack.POINT() |
||
Line 727: | Line 749: | ||
visited(x + offset(#visited, nextCell)\x, y + offset(#visited, nextCell)\y) = #True |
visited(x + offset(#visited, nextCell)\x, y + offset(#visited, nextCell)\y) = #True |
||
maze(x + offset(#wall, nextCell)\x, y + offset(#wall, nextCell)\y) | wallvalue(nextCell) |
maze(x + offset(#wall, nextCell)\x, y + offset(#wall, nextCell)\y) | wallvalue(nextCell) |
||
If cellCount > 1 |
If cellCount > 1 |
||
AddElement(stack()) |
AddElement(stack()) |
||
Line 740: | Line 762: | ||
EndIf |
EndIf |
||
ForEver |
ForEver |
||
; ;mark random entry and exit point |
|||
; x = Random(mazeWidth - 1): y = Random(mazeHeight - 1) |
|||
; maze(x, 0) | wallvalue(#dir_N): maze(mazeWidth, y) | wallvalue(#dir_E) |
|||
ProcedureReturn |
ProcedureReturn |
||
EndProcedure |
EndProcedure |
||
⚫ | |||
Dim maze(0, 0) |
|||
If OpenConsole() |
If OpenConsole() |
||
Dim maze(0, 0) |
|||
Define mazeWidth = Random(5) + 7: mazeHeight = Random(5) + 3 |
|||
generateMaze(maze(), mazeWidth, mazeHeight) |
|||
displayMaze(maze()) |
displayMaze(maze()) |
||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</lang> |
EndIf</lang> |
||
The maze is represented by an array of cells where each cell indicates the walls present above (#dir_N) and to its left (#dir_W). Maze generation is done with a additional array marking the visited cells. Neither an entry nor an exit are created, these were not part of the task. A simple means of doing so is included but has been commented out. |
|||
Sample output: |
Sample output: |
||
<pre> |
<pre>Maze of size 11 x 8, generation started at 9 x 3 |
||
+---+---+---+---+---+---+---+---+---+---+---+ |
+---+---+---+---+---+---+---+---+---+---+---+ |
||
| | | | | |
| | | | | |