Create 2D maze in an array

This code has been declared by its author to be Public Domain code.

Create 2D maze in an array by Zethrax

2015

*** Blitz3D Code ***

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.
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
http://bl.ocks.org/mbostock/11357811
http://www.pixieland.org.uk/2014/wilsons-algorithm/
https://eventuallyalmosteverywhere.wordpress.com/tag/wilsons-algorithm/
http://en.wikipedia.org/wiki/Loop-erased_random_walk

Minimum spanning tree (with decent definitions and summary) (BlitzMax code)
http://www.blitzbasic.com/codearcs/codearcs.php?code=2870

Some interesting summaries of maze algorithms
http://www.astrolog.org/labyrnth/algrithm.htm

; 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>



;----------



; 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


; 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.
	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.



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.
	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 )
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

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.

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...
			
				cell_type = A_maze( nx, ny )\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...
						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.
							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
				
				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.
						A_maze( nx, ny )\cell_type = 2 ; Set the cell type to be a walk path type.
						A_maze( nx, ny )\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 )\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 Then 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.
							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.
						current_cell = A_maze( x, y ) ; Set the loop erasure to start with the current cell.
						restart_cell = A_maze( nx, ny ) ; 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.
						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.
				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 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.
	Dim A_maze( 0, 0 ) ; Re-dimension the maze array back to its minimum size.
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

	Cls
	
	If walk_path_cell <> Null
		Color 255,255,255
	Else
		Color 0,255,0
	EndIf
		
	For y = 0 To ymax
		For x = 0 To xmax
			dx = x * 6 + 3
			dy = y * 6 + 3
			If A_maze( x, y )\connections[ 0 ] <> Null ; up
				Line dx, dy, dx, dy - 6
			EndIf
			
			If A_maze( x, y )\connections[ 1 ] <> Null ; right
				Line dx, dy, dx + 6, dy
			EndIf
			
			If A_maze( x, y )\connections[ 2 ] <> Null ; down
				Line dx, dy, dx, dy + 6
			EndIf
			
			If A_maze( x, y )\connections[ 3 ] <> Null ; left
				Line dx, dy, dx - 6, dy
			EndIf
		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 * 6 + 3
					y1 = walk_path_cell\y * 6 + 3
					x2 = previous_cell\x * 6 + 3
					y2 = previous_cell\y * 6 + 3
					Line x1, y1, x2, y2
				Else
					Exit
				EndIf		
				walk_path_cell = previous_cell
			Forever
			;---
		EndIf
	EndIf
	
	Flip
	WaitTimer G_timer
	If KeyHit( 1 ) Then End
End Function



Function CountEstablishedMazeCells()
	; Counts the number of maze cells that have been set as part of the established maze and returns the count.
	
	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	Local counter = 0, x, y
	For y = 0 To ymax
		For x = 0 To xmax
			If A_maze( x, y )\cell_type = 1 Then counter = counter + 1
		Next
	Next
	Return counter
End Function



Function SaveMaze( filepath$ )
	; Saves the maze as a text string to the specified file.
	; Returns a zero if there was a file error, or non-zero for a successful operation.
	; The data is saved as hexadecimal values.
	; The first set of eight hexadecimal characters hold the maze width. The second set of eight hexadecimal characters hold the maze height.
	; Each of the remaining single hex characters holds a nybble (4 bits) of information representing the connections from the current maze cell to its adjoining cells.
	; Bit 0 (value=1) - Connection exists to cell above the current one (x, y-1).
	; Bit 1 (value=2) - Connection exists to cell to the right of the current one (x+1, y).
	; Bit 2 (value=4) - Connection exists to cell below the current one (x, y+1).
	; Bit 3 (value=8) - Connection exists to cell to the left of the current one (x-1, y).
	
	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	Local x, y, file, mazedata$, n
	
	file = WriteFile( filepath$ )
	If file
		mazedata$ = mazedata$ + Hex( G_maze_width ) ; Store the maze width.
		mazedata$ = mazedata$ + Hex( G_maze_height ) ; Store the maze height.
		; Store the maze cell connections.
		For y = 0 To ymax
			For x = 0 To xmax
				n = 0
				If A_maze( x, y )\connections[ 0 ] <> Null Then n = 1 ; up
				If A_maze( x, y )\connections[ 1 ] <> Null Then n = n + 2 ; right
				If A_maze( x, y )\connections[ 2 ] <> Null Then n = n + 4 ; down
				If A_maze( x, y )\connections[ 3 ] <> Null Then n = n + 8 ; left
				mazedata$ = mazedata$ + Right( Hex( n ), 1 )
			Next
		Next
		WriteLine file, mazedata$
		CloseFile file
	EndIf
	Return file
End Function



Function LoadMaze( filepath$ )
	; Loads the maze data from the specified file and uses it to create the maze.
	; The maze data file is in the format described in the 'SaveMaze' function.
	; Returns a zero if there was a file error, or non-zero for a successful operation.
	
	Local file, mazedata$

	file = ReadFile( filepath$ )
	If file
		mazedata$ = ReadLine( file )
		CloseFile file
		InputMaze( mazedata$ )
	EndIf
	Return file
End Function



Function InputMaze( mazedata$ )
	; Creates the maze using the specified 'mazedata$' string.
	; The 'mazedata$' string is in the format described in the 'SaveMaze' function.
	
	Local x, y, pos = 17, v

	SetupMaze( HexToDec( Mid( mazedata$, 1, 8 ) ), HexToDec( Mid( mazedata$, 9, 8 ) ) )
	
	Local xmax = G_maze_width - 1
	Local ymax = G_maze_height - 1
	
	For y = 0 To ymax
		For x = 0 To xmax
			v = HexToDec( Mid( mazedata$, pos, 1 ) )
			If v And 1 Then A_maze( x, y )\connections[ 0 ] = A_maze( x, y - 1 ) ; up
			If v And 2 Then A_maze( x, y )\connections[ 1 ] = A_maze( x + 1, y ) ; right
			If v And 4 Then A_maze( x, y )\connections[ 2 ] = A_maze( x, y + 1 ) ; down
			If v And 8 Then A_maze( x, y )\connections[ 3 ] = A_maze( x - 1, y ) ; left
			A_maze( x, y )\cell_type = 1
			A_maze( x, y )\x = x
			A_maze( x, y )\y = y
			pos = pos + 1
		Next
	Next
End Function



Function HexToDec( hexval$ )
	; Converts a hexadecimal string into a decimal integer.
	; Note that the letters in the hex value must be uppercase.
	; This function assumes that the hex value has already been sanitized, if required.
	
	Local l = Len( hexval$ ), i, decval, v
	For i = 1 To l
		v = Asc( Mid( hexval$, i, 1 ) ) - 48
		If v > 9 Then v = v - 7
		decval = ( decval Shl 4 ) + v
	Next
	Return decval
End Function



; === DEMO CODE ===



Global G_timer = CreateTimer( 60 )

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

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


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

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

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

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

; Loads a saved maze.
;LoadMaze( "mymaze.txt" )

; Creates the maze from a string (see the 'SaveMaze' function for the string format).
;m$ = "0000001400000014"
;m$ = m$ + "42C2AEAAAC6C2AC6EC445452A9684793AC39557D7BD6C6969386ABAE911512FD3D2F84412C6B86C56A95456FA97EEBBC2D3D"
;m$ = m$ + "168553956811786BAD2D2D2FD42D52AC52D469692BC1578152C3F87916D4469453C6B87EF83EC1157B87FEBD4411146D3EE9"
;m$ = m$ + "3AAD17C13FC2E911293C2AE969168516BC46C2AD44387AC7EFEB853956AD3FAC783D11542BEAD3C16F8112E96C156ED416B8"
;m$ = m$ + "5142EABA912D513D2FAC3EBA946A842B9445296D6942C5786BC6C553C29556D693F854793BFEBEAD39392ABAB93AA8138129"
;InputMaze( m$ )

; Draws the finished maze.
DrawMaze( Null )

; Saves an existing maze.
;SaveMaze( "mymaze.txt" )

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

WaitKey
End

The code can be found at: http://www.blitzbasic.com/codearcs/codearcs.php?code=3178

Comments

videz

2015

This looks interesting Zethrax. But I don't see any maze if I set your demo to 2. in options 0 it shows up though..

Zethrax

2015

'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.

I'll add this explanation to the summary.

Code Archives Forum