# 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.

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