Ooops
January 26, 2021, 12:39:30 PM

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

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Maze Generation Using Recursive Backtracker
Author : TomToad
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
  12.         Field Links:TList = CreateList()
  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)
  26.                 Links.AddLast(Cell)
  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
  31.         Method isLinked:Int(Cell:TCell)
  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()
  41.                 If North And North.Links.isEmpty() Then Neighbors.Addlast(North)
  42.                 If East And East.Links.isEmpty() Then Neighbors.AddLast(East)
  43.                 If South And South.Links.isEmpty() Then Neighbors.AddLast(South)
  44.                 If West And West.Links.isEmpty() Then Neighbors.AddLast(West)
  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
  151.                                 Cell.Links.Clear()
  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
  176.                 Local DeltaError:Int=DeltaY             'Counter adder
  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
  186.                         Error:+DeltaError               'Add to counter
  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
  208.                         Cell.Link(Neighbor) 'link te two cells together
  209.                         Queue.AddLast(Neighbor) 'add the neighbor to the queue
  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)


Comments :


Pakz(Posted 1 month ago)

 That book "mazes for programmers" really tought me how a lot of maze generation algorithms work.I like the one where you keep dividing the map in two and leave a passage spot. Only a few lines needed for additional room area's. Recursive division it is called.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal