 January 26, 2021, 12:39:30 PM

### Author Topic: [bmx] Maze Generation Using Recursive Backtracker by TomToad [ 1 month ago ]  (Read 791 times)

#### BlitzBot

• Jr. Member
•  • Posts: 1 ##### [bmx] Maze Generation Using Recursive Backtracker by TomToad [ 1 month ago ]
« on: June 29, 2017, 12:28:38 AM »
Title : Maze Generation Using Recursive Backtracker
Posted : 1 month ago

Description : This maze generator creates rectangular mazes using the <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker" target="_blank">recursive backtracker[/url] algorithm.  When you run it, it will ask for a place and filename to save the resulting png image.

Code :
Code: BlitzMax
1. SuperStrict
2.
3. 'This is the TCell class.  It describes one cell in the grid.
4. Type TCell
5.         'these fields point to neighboring cells.
6.         Field North:TCell, South:TCell, East:TCell, West:TCell
7.
8.         'These fields point to the row and column in the grid which contains this cell
9.         Field Row:Int, Column:Int
10.
11.         'This list conatins all cells that this one links to, i.e. there is a path connecting the two
13.
14.         'Constructor function for creating the cell
15.         Function Create:TCell(Row:Int, Column:Int)
16.                 Local Cell:TCell = New TCell
17.                 Cell.Row = Row
18.                 Cell.Column = Column
19.                 Return Cell
20.         End Function
21.
22.         'This method will link this cell with another one, i.e. create a path between them
23.         '  It will call the same method for the linked cell with bidi = true so the link will
24.         '  be bi-directional
25.         Method Link(Cell:TCell, bidi:Int = True)
27.                 If bidi Then Cell.Link(Self,False) 'pass false to prevent endless loop
28.         End Method
29.
30.         'This methid will check if there is a link between two cells
32.                 For Local Test:TCell = EachIn Links
33.                         If Test = Cell Then Return True
34.                 Next
35.                 Return False
36.         End Method
37.
38.         'This method will return a list of neighbors which do not currently link to any other cell
39.         Method Unvisited:TList()
40.                 Local Neighbors:TList = CreateList()
45.                 Return Neighbors
46.         End Method
47. End Type
48.
49. 'The grid class holds a grid of cells representing the entire maze
50. Type TGrid
51.         'This array of arrays holds the grid of cells.  I chose an array of arrays instead of a 2 dimentional
52.         '  as some types of mazes, such as circular ones, might have different number of columns per row.  Even
53.         '  though this example only uses rectangular mazes, I am using array of arrays so there will be minimal
54.         '  modifications to the class when porting to other types of mazes
55.         Field Cells:TCell[][]
56.
57.         'number of rows and columns in the grid
58.         Field Rows:Int, Columns:Int
59.
60.         'The constructor function
61.         Function Create:TGrid(Rows:Int, Columns:Int)
62.                 Local Grid:TGrid = New TGrid
63.                 Grid.Rows = Rows
64.                 Grid.Columns = Columns
65.                 Grid.Init()
66.                 Return Grid
67.         End Function
68.
69.         'Initializes the grid, creates the cells and defines the cells' neighbors
70.         Method Init()
71.                 'create the grid and populate with cells
72.                 Cells = New TCell[][Rows]
73.                 For Local Row:Int = 0 Until Rows
74.                         Cells[Row] = New TCell[Columns]
75.                         For Local Column:Int = 0 Until Columns
76.                                 Cells[Row][Column] = TCell.Create(Row,Column)
77.                         Next
78.                 Next
79.
80.                 'Go through the cells and point to the neighbors
81.                 For Local Row:Int = 0 Until Rows
82.                         For Local Column:Int = 0 Until Columns
83.                                 Local Cell:TCell = getCell(Row,Column)
84.                                 Cell.North = getCell(Row-1,Column)
85.                                 Cell.East = getCell(Row,Column+1)
86.                                 Cell.South = getCell(Row+1,Column)
87.                                 Cell.West = getCell(Row,Column-1)
88.                         Next
89.                 Next
90.         End Method
91.
92.         'Gets a cell from the grid.  Does bounds checking and returns Null if out of bounds
93.         Method getCell:TCell(row:Int,column:Int)
94.                 If row < 0 Or row >= rows Or column < 0 Or column >= columns Then Return Null
95.                 Return Cells[row][column]
96.         End Method
97.
98.         'return a random cell from the grid
99.         Method getRandom:TCell()
100.                 Local Cell:TCell
101.                 Repeat
102.                         Local Row:Int = Rand(0,Rows-1)
103.                         Local Column:Int = Rand(0,Cells[Row].Length-1)
104.                         Cell = Cells[Row][Column]
105.                 Until Cell
106.                 Return Cell
107.         End Method
108.
109.         'this method will create a pixmap representation of the maze. background and wall are in ARGB order
110.         Method ToPixmap:TPixmap(background:Int, wall:Int, size:Int = 10)
111.                 Local imgWidth:Int = size*Columns+1
112.                 Local imgHeight:Int = size*rows+1
113.
114.                 'create the pixmap and clear to the background color
115.                 Local img:TPixmap = CreatePixmap(imgWidth, imgHeight, PF_RGBA8888)
116.                 img.ClearPixels(background)
117.
118.                 For Local row:Int = 0 Until rows
119.                         For Local column:Int = 0 Until columns
120.                                 Local Cell:TCell = getCell(row,column)
121.                                 'calculate the four corners of the cell
122.                                 Local x1:Int = column*size
123.                                 Local x2:Int = x1+size
124.                                 Local y1:Int = row*size
125.                                 Local y2:Int = y1 + size
126.
127.                                 'Check if on north or west border, draw a wall if so
128.                                 If Not Cell.North Then PixmapLine(img,x1,y1,x2,y1,Wall)
129.                                 If Not Cell.West Then PixmapLine(img,x1,y1,x1,y2,Wall)
130.
131.                                 'check if there is a wall on the East and south
132.                                 If Not Cell.isLinked(Cell.East) Then PixmapLine(img,x2,y1,x2,y2,Wall)
133.                                 If Not Cell.isLinked(Cell.South) Then PixmapLine(img,x1,y2,x2,y2,Wall)
134.                         Next
135.                 Next
136.                 Return img
137.         End Method
138.
139.         'Our grid type is filled with TCells all containing circular references.  BlitzMAX garbage collector
140.         '  does not do well with circular references, so when we are through with the type, we need to make
141.         '  sure they are cleaned up.  Not so important on this small example, but can be a source of a memory
142.         '  leak on bigger projects.
143.         Method Clean()
144.                 For Local row:Int = 0 Until rows
145.                         For Local column:Int = 0 Until columns
146.                                 Local Cell:TCell = getCell(row,column)
147.                                 Cell.North = Null
148.                                 Cell.East = Null
149.                                 Cell.South = Null
150.                                 Cell.West = Null
152.                                 Cells = Null
153.                         Next
154.                 Next
155.         End Method
156.
157.         'This method is called when the type is GCed. It will in turn call Clean if it hasn't been cleaned already
158.         Method Delete()
159.                 If Cells Then Clean
160.         End Method
161. End Type
162.
163. 'this function will draw lines on the pixmap using besenehams algorithm.  This has been modified from the
164. '  code archives submitted by ImaginaryHuman [https://www.blitzbasic.com/codearcs/codearcs.php?code=1465]
165. Function PixmapLine(pixmap:TPixmap,x1:Int,y1:Int,x2:Int,y2:Int,color:Int)
166.         'convert the color to proper endiness to speed up rendering a bit
167.                 'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
168.                 Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1)                 'Boolean
169.                 If Steep
170.                         Local Temp:Int=X1; X1=Y1; Y1=Temp               'Swap X1,Y1
171.                         Temp=X2; X2=Y2; Y2=Temp         'Swap X2,Y2
172.                 EndIf
173.                 Local DeltaX:Int=Abs(X2-X1)             'X Difference
174.                 Local DeltaY:Int=Abs(Y2-Y1)             'Y Difference
175.                 Local Error:Int=0               'Overflow counter
177.                 Local X:Int=X1          'Start at X1,Y1
178.                 Local Y:Int=Y1
179.                 Local XStep:Int
180.                 Local YStep:Int
181.                 If X1<X2 Then XStep=1 Else XStep=-1     'Direction
182.                 If Y1<Y2 Then YStep=1 Else YStep=-1     'Direction
183.                 If Steep Then WritePixel(pixmap,Y,X,color) Else WritePixel(pixmap,X,Y,color)            'Draw
184.                 While X<>X2
185.                         X:+XStep                'Move in X
187.                         If (Error Shl 1)>DeltaX         'Would it overflow?
188.                                 Y:+YStep                'Move in Y
189.                                 Error=Error-DeltaX              'Overflow/wrap the counter
190.                         EndIf
191.                         If Steep Then WritePixel(pixmap,Y,X,color) Else WritePixel(pixmap,X,Y,color)            'Draw
192.                 Wend
193. End Function
194.
195. 'This function will connect paths into a grid using Recursive Backtracker algorythm
196. Function RecursiveBacktracker(Grid:TGrid)
197.         Local Queue:TList = CreateList() 'queue of cells to be tested
198.         Queue.AddLast(Grid.getRandom()) 'push a random cell onto the queue
199.
200.         While Not Queue.isEmpty() 'the maze is done when there are no more cells on the queue
201.                 Local Cell:TCell = TCell(Queue.Last()) 'get the last cell on the queue
202.
203.                 Local Neighbors:TList = Cell.Unvisited() 'get a list of unvisited cells
204.                 If Neighbors.isEmpty() 'there are no unvisited cells
205.                         Queue.RemoveLast() 'remove this cell from the queue
206.                 Else
207.                         Local Neighbor:TCell = TCell(Neighbors.ValueAtIndex(Rand(0,Neighbors.Count()-1))) 'pick a random neighbor
210.                 End If
211.         Wend
212.
213.         'The grid now contains the completed maze
214. End Function
215.
216. 'select the filename to which we will save our maze
217. Local Filename:String = RequestFile("Save maze as...","Portable Netwrok Graphic(png):png",True)
218. If Not Filename Then End
219.
220. SeedRnd(MilliSecs())
221. Local Grid:TGrid = TGrid.Create(20,20) 'Create the grid
222. RecursiveBacktracker(Grid) 'Create the maze
223.
224. Local img:TPixmap = Grid.ToPixmap(\$FFFFFFFF,\$FF000000,20) 'Render the maze to a pixmap
225. SavePixmapPNG(img,Filename)