# 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.
*   [[programming/python/modules/argparse-module|argparse]]: To handle command-line arguments for maze dimensions.

## The Algorithm

1.  Start at a random cell (or a fixed starting point).
2.  Mark the current cell as visited.
3.  Randomly select an unvisited neighbor.
4.  Remove the wall between the current cell and the chosen neighbor.
5.  Recursively call the function for the chosen neighbor.
6.  If a cell has no unvisited neighbors, backtrack.

## The Code

Save this as `maze_gen.py`.

```python
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

```bash
python maze_gen.py 30 15
```

[[programming/python/python]]