Code archives/Algorithms/Maze Generation Using Recursive Backtracker

SuperStrict

'This is the TCell class.  It describes one cell in the grid.
Type TCell
	'these fields point to neighboring cells.
	Field North:TCell, South:TCell, East:TCell, West:TCell
	
	'These fields point to the row and column in the grid which contains this cell
	Field Row:Int, Column:Int
	
	'This list conatins all cells that this one links to, i.e. there is a path connecting the two
	Field Links:TList = CreateList()
	
	'Constructor function for creating the cell
	Function Create:TCell(Row:Int, Column:Int)
		Local Cell:TCell = New TCell
		Cell.Row = Row
		Cell.Column = Column
		Return Cell
	End Function
	
	'This method will link this cell with another one, i.e. create a path between them
	'  It will call the same method for the linked cell with bidi = true so the link will
	'  be bi-directional
	Method Link(Cell:TCell, bidi:Int = True)
		Links.AddLast(Cell)
		If bidi Then Cell.Link(Self,False) 'pass false to prevent endless loop
	End Method
	
	'This methid will check if there is a link between two cells
	Method isLinked:Int(Cell:TCell)
		For Local Test:TCell = EachIn Links
			If Test = Cell Then Return True
		Next
		Return False
	End Method
	
	'This method will return a list of neighbors which do not currently link to any other cell
	Method Unvisited:TList()
		Local Neighbors:TList = CreateList()
		If North And North.Links.isEmpty() Then Neighbors.Addlast(North)
		If East And East.Links.isEmpty() Then Neighbors.AddLast(East)
		If South And South.Links.isEmpty() Then Neighbors.AddLast(South)
		If West And West.Links.isEmpty() Then Neighbors.AddLast(West)
		Return Neighbors
	End Method
End Type

'The grid class holds a grid of cells representing the entire maze
Type TGrid
	'This array of arrays holds the grid of cells.  I chose an array of arrays instead of a 2 dimentional
	'  as some types of mazes, such as circular ones, might have different number of columns per row.  Even
	'  though this example only uses rectangular mazes, I am using array of arrays so there will be minimal
	'  modifications to the class when porting to other types of mazes
	Field Cells:TCell[][]
	
	'number of rows and columns in the grid
	Field Rows:Int, Columns:Int
	
	'The constructor function
	Function Create:TGrid(Rows:Int, Columns:Int)
		Local Grid:TGrid = New TGrid
		Grid.Rows = Rows
		Grid.Columns = Columns
		Grid.Init()
		Return Grid
	End Function
	
	'Initializes the grid, creates the cells and defines the cells' neighbors
	Method Init()
		'create the grid and populate with cells
		Cells = New TCell[][Rows]
		For Local Row:Int = 0 Until Rows
			Cells[Row] = New TCell[Columns]
			For Local Column:Int = 0 Until Columns
				Cells[Row][Column] = TCell.Create(Row,Column)
			Next
		Next
		
		'Go through the cells and point to the neighbors
		For Local Row:Int = 0 Until Rows
			For Local Column:Int = 0 Until Columns
				Local Cell:TCell = getCell(Row,Column)
				Cell.North = getCell(Row-1,Column)
				Cell.East = getCell(Row,Column+1)
				Cell.South = getCell(Row+1,Column)
				Cell.West = getCell(Row,Column-1)
			Next
		Next
	End Method
	
	'Gets a cell from the grid.  Does bounds checking and returns Null if out of bounds
	Method getCell:TCell(row:Int,column:Int)
		If row < 0 Or row >= rows Or column < 0 Or column >= columns Then Return Null
		Return Cells[row][column]
	End Method
	
	'return a random cell from the grid
	Method getRandom:TCell()
		Local Cell:TCell
		Repeat
			Local Row:Int = Rand(0,Rows-1)
			Local Column:Int = Rand(0,Cells[Row].Length-1)
			Cell = Cells[Row][Column]
		Until Cell
		Return Cell
	End Method
	
	'this method will create a pixmap representation of the maze. background and wall are in ARGB order
	Method ToPixmap:TPixmap(background:Int, wall:Int, size:Int = 10)
		Local imgWidth:Int = size*Columns+1
		Local imgHeight:Int = size*rows+1
		
		'create the pixmap and clear to the background color
		Local img:TPixmap = CreatePixmap(imgWidth, imgHeight, PF_RGBA8888)
		img.ClearPixels(background)
		
		For Local row:Int = 0 Until rows
			For Local column:Int = 0 Until columns
				Local Cell:TCell = getCell(row,column)
				'calculate the four corners of the cell
				Local x1:Int = column*size
				Local x2:Int = x1+size
				Local y1:Int = row*size
				Local y2:Int = y1 + size
				
				'Check if on north or west border, draw a wall if so
				If Not Cell.North Then PixmapLine(img,x1,y1,x2,y1,Wall)
				If Not Cell.West Then PixmapLine(img,x1,y1,x1,y2,Wall)
				
				'check if there is a wall on the East and south
				If Not Cell.isLinked(Cell.East) Then PixmapLine(img,x2,y1,x2,y2,Wall)
				If Not Cell.isLinked(Cell.South) Then PixmapLine(img,x1,y2,x2,y2,Wall)
			Next
		Next
		Return img
	End Method
	
	'Our grid type is filled with TCells all containing circular references.  BlitzMAX garbage collector
	'  does not do well with circular references, so when we are through with the type, we need to make
	'  sure they are cleaned up.  Not so important on this small example, but can be a source of a memory
	'  leak on bigger projects.
	Method Clean()
		For Local row:Int = 0 Until rows
			For Local column:Int = 0 Until columns
				Local Cell:TCell = getCell(row,column)
				Cell.North = Null
				Cell.East = Null
				Cell.South = Null
				Cell.West = Null
				Cell.Links.Clear()
				Cells = Null
			Next
		Next
	End Method
	
	'This method is called when the type is GCed. It will in turn call Clean if it hasn't been cleaned already
	Method Delete()
		If Cells Then Clean
	End Method
End Type

'this function will draw lines on the pixmap using besenehams algorithm.  This has been modified from the 
'  code archives submitted by ImaginaryHuman [https://www.blitzbasic.com/codearcs/codearcs.php?code=1465]
Function PixmapLine(pixmap:TPixmap,x1:Int,y1:Int,x2:Int,y2:Int,color:Int)
	'convert the color to proper endiness to speed up rendering a bit
		'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
	 	Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1)			'Boolean
		If Steep
			Local Temp:Int=X1; X1=Y1; Y1=Temp		'Swap X1,Y1
			Temp=X2; X2=Y2; Y2=Temp		'Swap X2,Y2
		EndIf
		Local DeltaX:Int=Abs(X2-X1)		'X Difference
		Local DeltaY:Int=Abs(Y2-Y1)		'Y Difference
		Local Error:Int=0		'Overflow counter
		Local DeltaError:Int=DeltaY		'Counter adder
		Local X:Int=X1		'Start at X1,Y1
		Local Y:Int=Y1		
		Local XStep:Int
		Local YStep:Int
		If X1<X2 Then XStep=1 Else XStep=-1	'Direction
		If Y1<Y2 Then YStep=1 Else YStep=-1	'Direction
		If Steep Then WritePixel(pixmap,Y,X,color) Else WritePixel(pixmap,X,Y,color)		'Draw
		While X<>X2
			X:+XStep		'Move in X
			Error:+DeltaError		'Add to counter
			If (Error Shl 1)>DeltaX		'Would it overflow?
				Y:+YStep		'Move in Y
				Error=Error-DeltaX		'Overflow/wrap the counter
			EndIf
			If Steep Then WritePixel(pixmap,Y,X,color) Else WritePixel(pixmap,X,Y,color)		'Draw
		Wend
End Function

'This function will connect paths into a grid using Recursive Backtracker algorythm
Function RecursiveBacktracker(Grid:TGrid)	
	Local Queue:TList = CreateList() 'queue of cells to be tested
	Queue.AddLast(Grid.getRandom()) 'push a random cell onto the queue
	
	While Not Queue.isEmpty() 'the maze is done when there are no more cells on the queue
		Local Cell:TCell = TCell(Queue.Last()) 'get the last cell on the queue
		
		Local Neighbors:TList = Cell.Unvisited() 'get a list of unvisited cells
		If Neighbors.isEmpty() 'there are no unvisited cells
			Queue.RemoveLast() 'remove this cell from the queue
		Else
			Local Neighbor:TCell = TCell(Neighbors.ValueAtIndex(Rand(0,Neighbors.Count()-1))) 'pick a random neighbor
			Cell.Link(Neighbor) 'link te two cells together
			Queue.AddLast(Neighbor) 'add the neighbor to the queue
		End If
	Wend
	
	'The grid now contains the completed maze
End Function

'select the filename to which we will save our maze
Local Filename:String = RequestFile("Save maze as...","Portable Netwrok Graphic(png):png",True)
If Not Filename Then End

SeedRnd(MilliSecs())
Local Grid:TGrid = TGrid.Create(20,20) 'Create the grid
RecursiveBacktracker(Grid) 'Create the maze

Local img:TPixmap = Grid.ToPixmap($FFFFFFFF,$FF000000,20) 'Render the maze to a pixmap
SavePixmapPNG(img,Filename)