Dungeon maze generation

Community Forums/Developer Stations/Dungeon maze generation
col	(Posted 2015) [#1]
While not really into the dungeon game scene... I was scanning around other forums and blogs today and thought that this blog gives a good explanation of generating a pretty good dungeon maze. I thought it may be of interest to some of the folks here.
Zethrax
(Posted 2015) [#2]
Here's an early version of some procedural dungeon generation code I'm working on in Blitz3D. It needs more work to remove unwanted corridors and link corridors to rooms. It's based on the discussion in the blog you linked ( http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ ).

The code is adapted from my maze generation code in the code archives ( http://www.blitzbasic.com/codearcs/codearcs.php?code=3178 ) (3D version: http://www.blitzbasic.com/codearcs/codearcs.php?code=3179 ).

Basically I've taken the maze code, added some code to generate rooms, and modified the 'DoRandomWalk' function to allow island corridor sections to form where the walk-path is blocked (not really required with this code as rooms are setup so they can't butt up against each other or against the outside of the array).

EDIT: Fixed a couple of bugs. Added the 'RemoveAllUnloopedCorridors' function, which removes all corridor sections that dead-end (currently it removes the entire corridor maze, as there are no loops). Added the 'DecreaseMazeDensity' function, which removes the end cell of any corridor sections that dead-end for each iteration (the 'attempts' parameter specifies how many iteration attempts will be run).

EDIT2: Fixed another couple of bugs and added regions (with color coding). Regions are needed to test where to place doorways and other connections to connect the whole dungeon together.

Public domain code. Use it however you want.
; This library uses Wilson's algorithm to create a 2D maze of a specified width and height.
; The maze will be fully connected (no isolated sections or unconnected cells) and will not contain any loops.
; The maze is stored in the 'A_maze' array with data for the maze cells stored in 'T_maze_cell' custom type objects.
; 
; Note that in the demo you can change the value of the 'G_demo_mode' global to alter how the maze building process is displayed. The following settings are available:-
; 
; * 'G_demo_mode = 2' shows the maze being created dynamically with the loop-erased random walk path displayed (the purple line wiggling about). This mode will take a while to build the maze as it needs to be slowed down enough for people to get an idea of how the process works.
; 
; * 'G_demo_mode = 1' shows the maze being created without the walk path displayed. The display is updated after each finished path is added to the maze, so it's a lot quicker than mode 2 but still intended to be slow enough to see what's going on.
; 
; * 'G_demo_mode = 0' just creates the maze and then displays it. Use this mode if you just want to see the finished maze.
; 
; 
; DEMO CODE NOTES:-
; Change the value of the 'G_demo_mode' global in the demo code to use different demo modes.
; - 0 = No dynamic demo. 1 = Draw maze but not walkpath. 2 = Draw maze and walkpath.
; The 'DoRandomWalk' function includes lines required to draw the maze for the demo. These lines are marked with '; **** DEMO CODE ****'. Remove or comment out these lines for non-demo code.
; Note that in the demo the lines are the maze path, not the space between the lines.
; 
; 
; EXTERNAL LIBRARY FUNCTIONS:-
; SetupMaze - Creates a blank maze and initializes it. Call this before calling 'GenerateMaze'.
; GenerateMaze - Generates the maze structure (the connections between cells). Call this after calling 'SetupMaze'.
; DestroyMaze - Destroys the maze to free up the memory used by it.
; 
; INTERNAL LIBRARY FUNCTIONS:-
; DoRandomWalk - Called by 'GenerateMaze' to create the paths for the maze.
; ConnectMazeCells - Called by 'DoRandomWalk' to create connections between maze cells.
; 
; REQUIRES:-
; T_maze_cell (type)
; A_maze (array)
; C_TOP, C_RIGHT, C_BOTTOM, C_LEFT (constants)
; 
; ADDITIONAL FUNCTIONS:-
; SaveMaze - Saves the maze to a text file. See the function's definition for the structure of the saved data.
; LoadMaze - Loads a saved maze.
; InputMaze - Creates the maze using the specified' string.
; HexToDec - Accepts a hexadecimal string and converts and returns it as a decimal integer. Used by the load/save functions.
; DrawMaze - Draws the maze with white lines representing horizontal connections.
; ForceMazePath
; CountEstablishedMazeCells - Counts the number of cells that have been added to the established maze structure. Just used for debugging, but I've left it in as it shows how to iterate the maze structure.
; 
; NOTES:-
; The maze is a connected graph so there will be a path between any two cells in the maze. For the beginning and end of the maze just pick any two cells.
; The number of cells in the array (width * height) set in 'SetupMaze' must be larger than the value set for 'start_limit' in 'GenerateMaze'.
; 
; REFERENCES:-
; Wilson’s algorithm
; <a href="http://bl.ocks.org/mbostock/11357811" target="_blank">http://bl.ocks.org/mbostock/11357811</a>
; <a href="http://www.pixieland.org.uk/2014/wilsons-algorithm/" target="_blank">http://www.pixieland.org.uk/2014/wilsons-algorithm/</a>
; <a href="https://eventuallyalmosteverywhere.wordpress.com/tag/wilsons-algorithm/" target="_blank">https://eventuallyalmosteverywhere.wordpress.com/tag/wilsons-algorithm/</a>
; <a href="http://en.wikipedia.org/wiki/Loop-erased_random_walk" target="_blank">http://en.wikipedia.org/wiki/Loop-erased_random_walk</a>
; 
; Minimum spanning tree (with decent definitions and summary) (BlitzMax code)
; <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2870" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2870</a>
; 
; Some interesting summaries of maze algorithms
; <a href="http://www.astrolog.org/labyrnth/algrithm.htm" target="_blank">http://www.astrolog.org/labyrnth/algrithm.htm</a>



;----------


Const C_CELL_SIZE = 8 ; The total pixel width and height used for a drawn cell.
Const C_CELL_SEP = 2 ; The pixel width used for the space not taken up by corridor cells.
;Const C_CORRIDOR_WIDTH = C_CELL_SIZE - ( C_CELL_SEP * 2 ) ; The total pixel width and height used for a drawn cell.

Const C_LINE_LENGTH = C_CELL_SIZE + C_CELL_SIZE - C_CELL_SEP - C_CELL_SEP ; Assumes that the line is aligned horizontally.
Const C_LINE_THICKNESS = C_CELL_SIZE - C_CELL_SEP - C_CELL_SEP ; Assumes that the line is aligned horizontally.

; Declare the constants used to index directional connections between maze cells.
Const C_TOP = 0
Const C_RIGHT = 1
Const C_BOTTOM = 2
Const C_LEFT = 3


Type T_room
	Field index ; Zero-based index number used to identify the room.
End Type


Type T_region
	;Field index ; Zero-based index number used to identify the room.
	Field red, green, blue ; The RGB components of the color used to highlight the region.
End Type


; Declare the type definition for the maze cells
Type T_maze_cell
	Field cell_type ; 0 = undefined. 1 = part of the established maze. 2 = part of a random walk path. 3 = part of a room.
	Field room.T_room
	Field region.T_region
	Field x, y ; The coordinate of the cell within the maze array.
	Field connections.T_maze_cell[ 3 ] ; Connections with adjoining cells (Null = no connection). Slots: 0 = top, 1 = right, 2 = bottom, 3 = left.
	Field previous_cell.T_maze_cell ; The previous cell in a random walk path. Used to backtrack when erasing loops and adding a walk path to the maze.
End Type

; Declare the array used to store the maze cells.
Dim A_maze.T_maze_cell( 0, 0 )

Global G_maze_width, G_maze_height ; Hold the width and height of the maze.

Global G_random_seed ; Holds the starting random seed value. Note that the value returned by 'RndSeed()' will change each time a random number is generated, so it's necessary to cache it when it is first set in order to be able to reproduce results from a given seed.



Function CreateRegion.T_region()
	Local region.T_region

	; Get a unique random color.
	Repeat
		end_loop = True
		red = Rand( 50, 255 )
		green = Rand( 50, 255 )
		blue = Rand( 50, 255 )		
		For region = Each T_region
			If ( red = region\red ) And ( green = region\green ) And ( blue = region\blue )
				end_loop = False
			EndIf
		Next
	Until end_loop		

	region = New T_region

	region\red = red
	region\green = green
	region\blue = blue

	Return region
End Function



Function ResetMazeCell( maze_cell.T_maze_cell )
	; Resets the specified maze cell to be an undefined cell.

	maze_cell\cell_type = 0
	maze_cell\room = Null
	maze_cell\connections.T_maze_cell[ 0 ] = Null
	maze_cell\connections.T_maze_cell[ 1 ] = Null
	maze_cell\connections.T_maze_cell[ 2 ] = Null
	maze_cell\connections.T_maze_cell[ 3 ] = Null
	maze_cell\previous_cell = Null
End Function



Function SetupMaze( width, height, seed = 0 )
	; Creates and initializes the data objects that the maze will be stored in.
	; No actual maze structure is created by this function. 'GenerateMaze' should be called after this function to generate the maze structure.

	; PARAMETERS:-
	; width - The width of the maze (the total number of cells on the X axis of the maze array).
	; height - The height of the maze (the total number of cells on the Y axis of the maze array).
	; seed - The value to use when seeding the random number generator. 0 = Don't set a new random seed.

	; RETURNS:-
	; Nothing is returned by this function.
	
	; NOTES:-
	; This function can be called with an existing maze to clear all its data and resize the maze (if required) in preparation for generating a new maze.

	If seed Then SeedRnd seed ; Seed the random number generator if 'seed' is non-zero.
	G_random_seed = RndSeed()
	
	Delete Each T_maze_cell ; Delete any existing maze cells from a previously created maze.
	G_maze_width = width
	G_maze_height = height
	Local xmax = width - 1, ymax = height - 1
	Local x, y, maze_cell.T_maze_cell	
	Dim A_maze( xmax, ymax ) ; Dimension the array used to store the maze cells.
	
	; Setup and initialize the maze array.
	For y = 0 To ymax
		For x = 0 To xmax
			maze_cell = New T_maze_cell
			A_maze( x, y ) = maze_cell
			maze_cell\x = x
			maze_cell\y = y
		Next
	Next
End Function



Function GenerateMaze( start_limit = 100, mode = 0 )
; Generates the structure of the maze.
; The 'SetupMaze' function or a substitute helper function should have been called first to create the maze.
; If you want to generate a new maze to overwrite an existing one then 'SetupMaze' should be called first to clear the data in the existing maze. Calling 'GenerateMaze' directly won't work as the maze will still have data left over from the previous maze.

; PARAMETERS:-
; start_limit - The length of the starting path. Must be less than the total number of cells in the array. If this is a zero then its value will be set using the width parameter. If this is a negative number then it will be assumed that the starting path has been created by a helper function and that this contains the length of that starting path as a negative number.
; mode - 0 = Randomly select the start point for the walk paths. 1 = Use the first undefined cell found for the walk paths relative to the top-left corner.

; RETURNS:-
; Nothing is returned by this function.


Local xmax = G_maze_width - 1, ymax = G_maze_height - 1, sx, sy, x, y, do_exit

Local num_undefined_cells; = G_maze_width * G_maze_height ; Calculate and store the total number of cells in the array. Once this counts down to zero the function is finished.


If start_limit = 0 Then start_limit = G_maze_width ; If start_limit is a zero then set its value using the width parameter.

If start_limit > 0 ; start_limit is a positive number so the starting path has not yet been created by a helper function.
	Select mode
		Case 0 ; Start the first path from a random point.
			sx = Rand( 0, xmax ) : sy = Rand( 0, ymax ) ; You can replace this select block with this line if you just want to start the path from a random point.
		Case 1 ; Start the first path from the top-left corner (0, 0).
			sx = 0 : sy = 0 ; You can replace this select block with this line if you just want to start the path from the top-left corner.
	End Select	
	; Generate a starting walk path with a specific number of cells.
	;num_undefined_cells = num_undefined_cells - DoRandomWalk( sx, sy, start_limit )
	DoRandomWalk( sx, sy, start_limit )
;Else ; start_limit is a negative number so the starting path has already been created by a helper function.
;	num_undefined_cells = num_undefined_cells + start_limit ; start_limit holds the length of the starting path created by a helper function as a negative number, so we just add it to num_undefined_cells.
EndIf

; Calculate and store the total number of cells in the array. Once this counts down to zero the function is finished.
num_undefined_cells = G_maze_width * G_maze_height

; Subtract the 'num_undefined_cells' taken up by rooms and the starting path.
For x = 0 To xmax
	For y = 0 To ymax
		If A_maze( x, y )\cell_type <> 0 Then num_undefined_cells = num_undefined_cells - 1
	Next
Next

Local search_x = 0, search_y = 0 ; Variables used to store the start of a new search for a start point the new walk path.

;region = CreateRegion() ; Create the starting region.

While num_undefined_cells > 0

	Select mode
	
		Case 0 ; Start the new path from a randomly selected undefined cell.
			; -- You can replace this select block with the code below if you just want to start the new path from a randomly selected undefined cell.
			Repeat
				sx = Rand( 0, xmax ) : sy = Rand( 0, ymax )
			Until A_maze( sx, sy )\cell_type = 0
			;---
			
		Case 1 ; Start the new path from the first undefined cell found in the array.
			 ; -- You can replace this select block with the code below if you just want to start the new path from the first undefined cell found in the array.
			do_exit = False
			For y = search_y To ymax
				For x = search_x To xmax
					If A_maze( x, y )\cell_type = 0
						sx = x : sy = y
						search_x = x : search_y = y
						do_exit = True
						Exit
					EndIf
				Next
				If do_exit
					Exit
				Else
					search_x = 0
				EndIf
			Next
			;---
			
	End Select
		
	; Do the random walk until the path reconnects with the established maze
	num_undefined_cells = num_undefined_cells - DoRandomWalk( sx, sy )

Wend

; At this point the maze should be finished.

End Function



Function DoRandomWalk( x, y, limit = 0 )
	; This function does a loop-erased random walk operation.
	; Called by 'GenerateMaze' when generating the structure of the maze.
	
	; PARAMETERS:-
	; x, y - The coordinates of the maze cell to begin the random walk operation at. It will be assumed that this cell has already been confirmed as being undefined.
	; limit - (0 = unlimited) The limit on the number of cells the path can grow to. Once this limit is reached the function exits. This is used when establishing the first path in the maze.
	
	; RETURNS:-
	; (Int) The number of new cells added to the maze is returned.

	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	Local nx, ny, nextcell_id, cell_type
	Local current_cell.T_maze_cell, prev_cell.T_maze_cell, restart_cell.T_maze_cell
	
	Local num_cells = 1 ; Set the cell counter to one to factor in the starting cell.
	
	A_maze( x, y )\cell_type = 2 ; Set the starting cell type to be a walk path type.
	
	Repeat; Loop while the next adjoining cell in the walk path is out of the array bounds.
			
		If G_demo_mode = 2 Then DrawMaze( A_maze( x, y ) ) ; **** DEMO CODE **** (Comment out or remove this line when using this function in a live program.)
		
		nextcell_id = Rand( 0, 3 )
		Select nextcell_id
			Case C_TOP; Top adjoining cell.
				nx = x
				ny = y - 1
			Case C_RIGHT ; Right adjoining cell.
				nx = x + 1
				ny = y
			Case C_BOTTOM ; Bottom adjoining cell.
				nx = x
				ny = y + 1
			Case C_LEFT ; Left adjoining cell.
				nx = x - 1
				ny = y
		End Select
	
		If ( ( nx >= 0 ) And ( nx <= xmax ) ) And ( ( ny >= 0 ) And ( ny <= ymax ) ) ; If the coordinates for the new adjoining cell are within the bounds of the array...
		
			If A_maze( nx, ny ) <> A_maze( x, y )\previous_cell ; If the new adjoining cell is not a double-back to the cell on the path before the current one...

				current_cell = A_maze( nx, ny )
				cell_type = current_cell\cell_type
	
				; - Manage the cell count limiter for the first path set in the maze.
				If limit ; If the specified limit is non-zero (a zero limit flags that there is no limit).
					If cell_type < 2 ; If the path hasn't looped and isn't part of a room, etc...
						If num_cells = limit - 1 ; If the specified cell count limit has been reached... (The limit needs to be -1 as the current cell has not yet been added to the count.)
							cell_type = 1 ; Force the path to be set as the beginning of the established maze.
							current_cell\region = CreateRegion() ; Create a new region for this segment. This will be the first region.
							num_cells = num_cells + 1 ; Add the current cell to the count. This needs to be added here instead of in 'Case 1' below as additional random walks will add the cell from the established maze to the walk path - which would throw off the count. 
						EndIf
					EndIf
				EndIf

				; Check if the walk path is completely blocked from proceeding. If so then set the path to terminate at the current cell and become an isolated section of the established maze structure.
				If cell_type = 0 ; If the new cell type is undefined.
					num_blocked = 0
					num_blocked = num_blocked + IsBlocked( nx - 1, ny, current_cell ) ; Left direction.
					num_blocked = num_blocked + IsBlocked( nx + 1, ny, current_cell ) ; Right direction.
					num_blocked = num_blocked + IsBlocked( nx, ny - 1, current_cell ) ; Up direction.
					num_blocked = num_blocked + IsBlocked( nx, ny + 1, current_cell ) ; Down direction.
					If num_blocked = 4 ; If the walk path is blocked in all four directions...
						cell_type = 1 ; Force the path to be set as part of the established maze even though it doesn't actually join with the maze.
						current_cell\region = CreateRegion() ; Create a new region for this island segment.
					EndIf
				EndIf
				
				Select cell_type ; Select an action depending on the cell type of the selected adjoining cell.
				
					Case 0 ; New cell type is undefined.
						; Add the new cell to the walk path.
						current_cell\cell_type = 2 ; Set the cell type to be a walk path type.
						current_cell\previous_cell = A_maze( x, y ) ; Store a link back to the current (now previous) cell in the walk path.
						x = nx : y = ny ; Set the new cell to be the current cell.
						num_cells = num_cells + 1 ; Increment the cell count for the walk path.
						
					Case 1 ; New cell type is part of the established maze.
						; Set all the cells in the walk path to be part of the established maze and then set a flag to exit the function.
						;A_maze( nx, ny )\region
						current_cell\previous_cell = A_maze( x, y ) ; Link the cell found from the established maze to the walk path so that its connections will be updated to join with the path.
						;current_cell = A_maze( nx, ny ) ; Set the walk path integration to start with the cell found from the established maze.					
						Repeat ; Work back along the walk path while integrating the cells in the walk path with the established maze.
							prev_cell = current_cell\previous_cell ; Grab the link to the previous cell. This can potentially be a null link.
							current_cell\previous_cell = Null ; Null the pointer to the previous cell to avoid conflicts.
							current_cell\cell_type = 1 ; Set the cell type to be part of the established maze.
							If prev_cell <> Null
								ConnectMazeCells( current_cell, prev_cell ) ; If we're not at the end of the path then connect the current cell with the previos cell in the walk path.
								prev_cell\region = current_cell\region ; Set the walkpath cell to be the same region as the established maze section being linked to.
							EndIf
							current_cell = prev_cell ; Move to the next cell back along the walk path. If the cell doesn't exist then 'current_cell' will end up with a null value.
						Until current_cell = Null ; The starting cell in the walk path has been found and updated, so exit the loop.
						;all_done = True ; Flag that it's time to exit the function.
						Exit ; Exit the loop and function.; The adjoining cell was within the array bounds and not a double-back so exit the current loop.
						
					Case 2 ; New cell type is part of a random walk path.
						; Erase the resulting loop.
						; Note that nx and ny will hold the index to the cell that was looped back onto (the random walk will begin again from this cell once the loop has been erased).
						; Note that no connections will have been set for cells in the walk path yet, so there is no need to erase them.
						restart_cell = current_cell ; Grab the link to the cell to restart the walk operation at. Mostly because it's quicker and cleaner using this than an array access.
						current_cell = A_maze( x, y ) ; Set the loop erasure to start with the current cell.
						x = nx : y = ny ; Set the coordinates of the cell to restart the walk operation at.
						Repeat
							prev_cell = current_cell\previous_cell ; Grab the link to the previous cell.
							current_cell\previous_cell = Null ; Null the pointer to the previous cell to avoid conflicts.
							current_cell\cell_type = 0 ; Set the cell type back to undefined.
							current_cell = prev_cell ; Move to the next cell back along the walk path.
							num_cells = num_cells - 1 ; Decrement the cell count for the walk path.
						Until current_cell = restart_cell ; All the cells in the looped section of the walk path have been erased, so exit the loop.

					;Case 3 ; New cell type is part of a room.
				End Select
				
			EndIf
			
		EndIf
		
	Forever
	
	If G_demo_mode = 1 Then DrawMaze( A_maze( x, y ) ) ; **** DEMO CODE **** (Comment out or remove this line when using this function in a live program.)
	
	Return num_cells
End Function



Function IsBlocked( x, y, current_cell.T_maze_cell )
	; Tests to see if the specified cell coordinate is one that the walk path can branch to or link with.
	; Returns 1 if the walk path is blocked from branching to the specified cell, or 0 if the path is not blocked.
	
	Local blocked = 1
	If ( ( x >= 0 ) And ( x < G_maze_width ) ) And ( ( y >= 0 ) And ( y < G_maze_height ) ) ; If the coordinates for the checked cell are within the bounds of the array...
		If ( A_maze( x, y )\cell_type = 0 ) Or ( A_maze( x, y )\cell_type = 1 ) Or ( ( A_maze( x, y )\cell_type = 2 ) And ( A_maze( x, y ) <> current_cell ) ) ; If the checked cell is either undefined, an established part of the maze that can be linked up with, or a walkpath cell that is not the current cell being tested for blockage (allows for walkpath loop erasure)...
			blocked = 0
		EndIf
	EndIf
	Return blocked
End Function



Function ConnectMazeCells( cell_1.T_maze_cell, cell_2.T_maze_cell )
	Local x1 = cell_1\x, y1 = cell_1\y
	Local x2 = cell_2\x, y2 = cell_2\y
	
	If ( x2 = x1 ) And ( y2 < y1 ) ; cell_2 is on top of cell_1.
		cell_1\connections[ C_TOP ] = cell_2
		cell_2\connections[ C_BOTTOM ] = cell_1
		Return
	EndIf
	
	If ( x2 > x1 ) And ( y2 = y1 ) ; cell_2 is to the right of cell_1.
		cell_1\connections[ C_RIGHT ] = cell_2
		cell_2\connections[ C_LEFT ] = cell_1
		Return
	EndIf
	
	If ( x2 = x1 ) And ( y2 > y1 ) ; cell_2 is on the bottom of cell_1.
		cell_1\connections[ C_BOTTOM ] = cell_2
		cell_2\connections[ C_TOP ] = cell_1
		Return
	EndIf
	
	If ( x2 < x1 ) And ( y2 = y1 ) ; cell_2 is to the left of cell_1.
		cell_1\connections[ C_LEFT ] = cell_2
		cell_2\connections[ C_RIGHT ] = cell_1
		Return
	EndIf
End Function



Function DestroyMaze()
	; Destroys the maze to free up the memory used by it.
	; This function can be called irregardless of whether a maze was previously created.

	Delete Each T_maze_cell ; Delete all the maze cells.
	Delete Each T_room ; Delete all the rooms.
	Delete Each T_region ; Delete all the regions.
	Dim A_maze( 0, 0 ) ; Re-dimension the maze array back to its minimum size.
End Function



Function DecreaseMazeDensity()
	
	Local x, y, i, a, maze_cell.T_maze_cell, connected_count, num_processed = 0
	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
		
		; Find all the dead-end corridor cells.
		For y = 0 To ymax
			For x = 0 To xmax	
			maze_cell = A_maze( x, y )					
			If maze_cell\cell_type = 1 ; If the maze cell is a corridor cell...		
				;-- Count the number of connections to other corridor cells.
				connected_count = 0
				For i = 0 To 3
					If maze_cell\connections[ i ] <> Null
							connected_count = connected_count + 1
					EndIf
				Next
				;--
				;-- If the corridor cell is a dead-end then reset it to an empty state.
				If connected_count = 1
					ResetMazeCell( maze_cell )
					num_processed = num_processed + 1
				EndIf
				;--
			EndIf	
			Next
		Next
		
		; Null all the maze cell connectors that are now pointing to empty cells.
		For y = 0 To ymax
			For x = 0 To xmax
				maze_cell = A_maze( x, y )
				For i = 0 To 3
					If maze_cell\connections[ i ] <> Null
						If maze_cell\connections[ i ]\cell_type = 0
							maze_cell\connections[ i ] = Null
						EndIf
					EndIf
				Next
			Next
		Next
	
	Return num_processed
End Function



Function RemoveAllUnloopedCorridors()

	Local x, y, maze_cell.T_maze_cell, connected.T_maze_cell, connected_direction, connected_count, num_deadends_found
	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	
	Repeat ; (This loop is probably not required. Best to be safe though.)
		
		num_deadends_found = 0
		For y = 0 To ymax
			For x = 0 To xmax

				maze_cell = A_maze( x, y )
				
				If maze_cell\cell_type = 1 ; If the maze cell is a corridor cell...
					
					; Count the number of connections to other corridor cells.
					connected_count = 0
					For i = 0 To 3
						If maze_cell\connections[ i ] <> Null
							;If maze_cell\connections[ i ]\cell_type = 1 ; If the connected cell is another corridor cell... (Not really required, but here for future-proofing)
								connected_count = connected_count + 1
								connected = maze_cell\connections[ i ]
								connected_direction = i
							;EndIf
						EndIf
					Next
					
					If connected_count = 1
						; Disconnect the connected maze cell.
						Select connected_direction
							Case C_TOP
								connected\connections[ C_BOTTOM ] = Null
							Case C_RIGHT
								connected\connections[ C_LEFT ] = Null
							Case C_BOTTOM
								connected\connections[ C_TOP ] = Null
							Case C_LEFT
								connected\connections[ C_RIGHT ] = Null
						End Select
						ResetMazeCell( maze_cell )
						num_deadends_found = num_deadends_found + 1
					EndIf
				
				EndIf
				
			Next
		Next

	Until num_deadends_found = 0
End Function



Function GenerateRooms( min_width, max_width, max_attempts )

Local xmax, ymax
Local region.T_region

For i = 1 To max_attempts
	width = Rand( min_width, max_width )
	height = Rand( min_width, max_width )
	
	test_width = width + 2
	test_height = height + 2
	
	xmax = G_maze_width - 1 - test_width
	ymax = G_maze_height - 1 - test_height
	
	pos_x = Rand( 0, xmax )
	pos_y = Rand( 0, ymax )
	xmax = pos_x + test_width - 1
	ymax = pos_y + test_height - 1
	
	overlap = False
	For x = pos_x To xmax
		For y = pos_y To ymax
			If A_maze( x, y )\cell_type = 3 Then overlap = True : Exit
		Next
		If overlap Then Exit
	Next
	
	If Not overlap
		room.T_room = New T_room
		pos_x = pos_x + 1
		pos_y = pos_y + 1
		xmax = pos_x + width - 1
		ymax = pos_y + height - 1
		region = CreateRegion()
		For x = pos_x To xmax
			For y = pos_y To ymax
				A_maze( x, y )\cell_type = 3
				A_maze( x, y )\room = room
				A_maze( x, y )\region = region
				If x > pos_x ; If we're not on the first column...
					; Connect the current and previous horizontally aligned room cells.
					A_maze( x, y )\connections[ C_LEFT ] = A_maze( x - 1, y )
					A_maze( x - 1, y )\connections[ C_RIGHT ] = A_maze( x, y )
				EndIf
				If y > pos_y ; If we're not on the first row...
					; Connect the current and previous vertically aligned room cells.
					A_maze( x, y )\connections[ C_TOP ] = A_maze( x, y - 1 )
					A_maze( x, y - 1 )\connections[ C_BOTTOM ] = A_maze( x, y )
				EndIf
			Next
		Next
	EndIf
	
Next

End Function



; === DEMO and HELPER FUNCTIONS ===



Function DrawMaze( walk_path_cell.T_maze_cell )
	; Draws the maze.
	; Note that this function draws the maze structure as a set of lines. The lines are the maze structure, not the space between the lines.

	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	Local dx, dy
	Local x1, y1, x2, y2
	Local previous_cell.T_maze_cell, maze_cell.T_maze_cell

	Cls
	
;	If walk_path_cell <> Null
;		Color 255,255,255
;	Else
;		Color 0,255,0
;	EndIf

	; Rect x, y, width, height, solid
	For y = 0 To ymax
		For x = 0 To xmax

			maze_cell = A_maze( x, y )

			Select maze_cell\cell_type
	
				Case 1 ; 1 = part of the established maze.
				
					dx = ( x * C_CELL_SIZE ) + C_CELL_SEP
					dy = ( y * C_CELL_SIZE ) + C_CELL_SEP

					; If the cell has a region set then use the color for that, otherwise use a predefined color.
					If maze_cell\region <> Null
						Color maze_cell\region\red, maze_cell\region\green, maze_cell\region\blue
					Else
						Color 255,255,255
					EndIf
		
		;			Rect dx + C_CELL_SEP, dy + C_CELL_SEP, C_CORRIDOR_WIDTH, C_CORRIDOR_WIDTH, True
					
		;			If maze_cell\connections[ 0 ] <> Null ; Verical ; up
		;;				Line dx, dy, dx, dy - C_CELL_SIZE
		;;				Line dx + 1, dy, dx + 1, dy - C_CELL_SIZE
		;;				Line dx + 2, dy, dx + 2, dy - C_CELL_SIZE
		;;				Line dx + 3, dy, dx + 3, dy - C_CELL_SIZE
		;				Rect dx + C_CELL_SEP, dy, C_CORRIDOR_WIDTH, C_CELL_SIZE, True
		;			EndIf
					
					If maze_cell\connections[ 1 ] <> Null ; Horizontal ; right
		;				Line dx, dy, dx + C_CELL_SIZE, dy
		;				Line dx, dy + 1, dx + C_CELL_SIZE, dy + 1
		;				Line dx, dy + 2, dx + C_CELL_SIZE, dy + 2
		;				Line dx, dy + 3, dx + C_CELL_SIZE, dy + 3
						Rect dx, dy, C_LINE_LENGTH, C_LINE_THICKNESS, True
					EndIf
					
					If maze_cell\connections[ 2 ] <> Null ; Verical ; down
						;Line dx, dy, dx, dy + C_CELL_SIZE
						Rect dx, dy, C_LINE_THICKNESS, C_LINE_LENGTH, True
		
					EndIf
					
		;			If maze_cell\connections[ 3 ] <> Null ; left
		;				Line dx, dy, dx - C_CELL_SIZE, dy
		;				;Rect dx, dy + C_CELL_SEP, C_CELL_SIZE, C_CORRIDOR_WIDTH, True
		;			EndIf
	
				Case 3 ; 3 = part of a room.
				
					dx = x * C_CELL_SIZE
					dy = y * C_CELL_SIZE

					; If the cell has a region set then use the color for that, otherwise use a predefined color.
					If maze_cell\region <> Null
						Color maze_cell\region\red, maze_cell\region\green, maze_cell\region\blue
					Else
						Color 0,150,0
					EndIf

					;Color 0,150,0
					Rect dx, dy, C_CELL_SIZE, C_CELL_SIZE, True;, False

					;Color 0,100,0
					;Rect dx + 1, dy + 1, C_CELL_SIZE - 2, C_CELL_SIZE - 2, True

			End Select
			
		Next
	Next
	If walk_path_cell <> Null
		If G_demo_mode = 2
			; -- Draw the walkpath.
			Color 176,98,255	
			Repeat
				previous_cell = walk_path_cell\previous_cell
				If previous_cell <> Null
					x1 = walk_path_cell\x * C_CELL_SIZE + C_CELL_SEP
					y1 = walk_path_cell\y * C_CELL_SIZE + C_CELL_SEP
					x2 = previous_cell\x * C_CELL_SIZE + C_CELL_SEP
					y2 = previous_cell\y * C_CELL_SIZE + C_CELL_SEP
					Line x1, y1, x2, y2
				Else
					Exit
				EndIf		
				walk_path_cell = previous_cell
			Forever
			;---
		EndIf
	EndIf
	
	Flip; False
	WaitTimer G_timer
	If KeyHit( 1 ) Then End
End Function



; === DEMO CODE ===



Global G_timer = CreateTimer( 60 )

; Set the width and height of the maze.
maze_width = 50
maze_height = 30

; Calculate the width and height of the graphics display (sets a minimum or it won't display correctly).
graphics_width = ( maze_width * C_CELL_SIZE ); + ( C_CELL_SEP * 2 )
graphics_height = ( maze_height * C_CELL_SIZE ) + 100 ; + ( C_CELL_SEP * 2 )
If graphics_width < 300 Then graphics_width = 400
If graphics_height < 300 Then graphics_height = 400


Graphics graphics_width, graphics_height, 0, 2
SetBuffer BackBuffer()

Global G_demo_mode = 0 ; 0 = No dynamic demo. 1 = Draw maze but not walkpath. 2 = Draw maze and walkpath.

Repeat

time_taken = MilliSecs()

; Create and initialize the maze (no structure is created for the maze).
SetupMaze( maze_width, maze_height, MilliSecs() ) ; width, height, random seed



GenerateRooms( 2, 10, 1000 ) ; Min room width and height, max room width and height, number of attempts to generate and place a room. 

; Generate the structure of the maze.
GenerateMaze( 100, 1 ) ; length of starting path, path start point mode

;RemoveAllUnloopedCorridors()

;While DecreaseMazeDensity() : DrawMaze( Null ) : Wend

time_taken = MilliSecs() - time_taken

; Draws the finished maze.
DrawMaze( Null )
SetBuffer FrontBuffer()
Color 255, 255, 255
Text 10, GraphicsHeight() - 90, "Click the screen to generate a new dungeon."
Text 10, GraphicsHeight() - 60, "Random Seed Used: " + G_random_seed
Text 10, GraphicsHeight() - 30, "Generation Time (millisecs): " + time_taken
SetBuffer BackBuffer()

; Destroys the maze to free up the memory used by it.
DestroyMaze()

FlushMouse
FlushKeys
Repeat
	If KeyHit( 1 ) Then End
	If MouseHit( 1 ) Then Exit
	Delay 100
Forever

Forever