GSmGpE6CwX2y9JjB25B8
We use cookies on this site to enhance your user experience

Recursive Backtracker

Recursive Backtracker

Aug 29 2019, 9:30 AM PST

The Recursive Backtracker algorithm is a Articles/Maze Generation algorithm that traces back its path when it hits a dead end to find more places to carve passageways. It is very similar to Articles/Prim's Algorithm.

Procedure

  • Choose a random cell as a starting point.
  • Choose an adjacent non-visited cell and carve a path to it. This is now the current cell.
  • If all adjacent cells have been visited, return back to the previous cell and check for non-visited cells.
  • Once you are back at your starting cell, the algorithm terminates.

Pseudocode

-- Create a table of cells, starting with just one random one
local Cells = {Vector2.new(math.random(MazeSizeX), math.random(MazeSizeY))}
repeat
     -- Select the most recent cell from the cells list (see note at bottom)
     local CurCellIndex = #Cells
     local CurCell = Cells[CurCellIndex]
     -- Make sure that this cell has unvisited neighbors
     if HasUnvisitedNeighbors(CurCell) then
          -- Collect all unvisited neighbors...
          local UnvisitedNeighbors = GetUnvisitedNeighbors(CurCell)
          -- ...and select a random one.
          local WallToDelete = UnvisitedNeighbors[math.random(#UnvisitedNeighbors)]
          -- Then carve a path to it by deleting the wall between them
          DeleteWall(WallToDelete)
          -- Add the neighbor to the end of the list of cells to make sure it is picked as the current one
          table.insert(Cells, NewCell)
     else
          -- If the current cell has only visited neighbors, remove it from the list.
          table.remove(Cells, CurCellIndex)
     end
until #Cells == 0

Note: you can easily turn this into Articles/Prim's Algorithm by selecting a random cell rather than the most recent.

See Also

*Articles/Maze Generation
*Articles/Prim's Algorithm