Random Maze Generator (DFS)
This utility generates a random maze using the Depth-First Search (Recursive Backtracker) algorithm. It creates a grid where walls are represented by 1 and paths by 0, then renders it to the console using ASCII characters.
Modules Used:
random: To randomly select directions during the maze generation.sys: To increase the recursion limit for larger mazes.- argparse: To handle command-line arguments for maze dimensions.
The Algorithm
- Start at a random cell (or a fixed starting point).
- Mark the current cell as visited.
- Randomly select an unvisited neighbor.
- Remove the wall between the current cell and the chosen neighbor.
- Recursively call the function for the chosen neighbor.
- If a cell has no unvisited neighbors, backtrack.
The Code
Save this as maze_gen.py.
import random
import sys
import argparse
# Increase recursion depth for larger mazes
sys.setrecursionlimit(10000)
def create_maze(width, height):
# 1. Initialize Grid
# We use a grid of (2*width+1) x (2*height+1) to represent walls and cells
# 1 = Wall, 0 = Path
# Initialize everything as a wall
maze = [[1 for _ in range(2 * width + 1)] for _ in range(2 * height + 1)]
def walk(x, y):
maze[y][x] = 0 # Mark current cell as visited (path)
# Define possible directions: (dx, dy)
# We jump 2 steps to move from cell to cell, skipping the wall in between
directions = [(0, -2), (0, 2), (-2, 0), (2, 0)]
random.shuffle(directions)
for dx, dy in directions:
nx, ny = x + dx, y + dy
# Check bounds
if 0 < nx < 2 * width + 1 and 0 < ny < 2 * height + 1:
# If neighbor is unvisited (still a wall)
if maze[ny][nx] == 1:
# Knock down the wall in between
maze[y + dy // 2][x + dx // 2] = 0
# Recursively visit the neighbor
walk(nx, ny)
# Start DFS from the first cell (1, 1)
walk(1, 1)
# Add Entrance (Top Left) and Exit (Bottom Right)
maze[1][0] = 0
maze[2 * height - 1][2 * width] = 0
return maze
def print_maze(maze):
for row in maze:
# Use '##' for walls to make them look square in terminal
print("".join("##" if cell else " " for cell in row))
if __name__ == "__main__":
parser = argparse.ArgumentParser(description="DFS Maze Generator")
parser.add_argument("width", type=int, nargs="?", default=20, help="Width of the maze")
parser.add_argument("height", type=int, nargs="?", default=10, help="Height of the maze")
args = parser.parse_args()
maze = create_maze(args.width, args.height)
print_maze(maze)Usage
python maze_gen.py 30 15