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)
