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
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
Comments