Table of Contents

Recursive Backtracking Algorithm #

Basic Idea #

This is a simple depth-first search Algorithm, which can generate mazes by carving walls between adjacent cells randomly, and Backtracking when it reaches a dead end.

Making the grid #

The grid was the easiest part, a 1D list that contained a Cell object

grid = []
for i in range(ROWS):
    for j in range(ROWS):
        grid.append(Cell(i, j, gridSize))

The cell class just has an i and j and a size.

The Algorithm #

Maze — Recursive Backtracking Psuedocode

The Algorithm is pretty simple to implement.

For Step 2:

Step 1 #

A function is defined for checking neighbors, which just checks if the cell and exists and if it has been visited

# For the top cell
try:
    top = grid[index(i, j-1)]
except:
    top = None

# Check
if top and not top.visited:
    neighbors.append(top)

# Do this for all neighbors

# Return random neighbor
if len(neighbors) > 0:
    return random.choice(neighbors)
else:
    return None

# In the main loop
new = check_neighbors(current.i, current.j)
    if new:
    new.visited = True

Step 2 #

Define a stack at the top, and append to it (Just a list in python)

stack = []
# After setting new to visited
stack.append(new)

Step 3 #

This step removes walls from the carving direction For example, the left of current wall and right of new wall is removed, if the current is to the right of the new one.

x = current.i - new.i
if x == 1:
current.walls[3] = False
new.walls[1] = False

Step 4 #

Set this as current

current = new

If stack not empty #

elif len(stack) > 0:
    current = stack.pop(-1)

Conclusion #

This works easily to build a perfect maze, and is pretty fast

The repository is here