ascii-maze-factory

1#!/usr/bin/env python3
2"""
3Recursive Backtracking Maze Generator (Iterative Version)
4
5An iterative implementation of the recursive backtracking algorithm to avoid stack limits.
6"""
7
8import random
9import sys
10
11def generate_maze_iterative(width: int = 21, height: int = 11) -> list[list[str]]:
12    # Ensure odd dimensions
13    width = width if width % 2 == 1 else width + 1
14    height = height if height % 2 == 1 else height + 1
15    
16    maze = [['#' for _ in range(width)] for _ in range(height)]
17    
18    # Use stack for iterative backtracking
19    stack = [(1, 1)]
20    maze[1][1] = ' '
21    
22    while stack:
23        x, y = stack[-1]
24        directions = [(0, -2), (0, 2), (-2, 0), (2, 0)]
25        random.shuffle(directions)
26        
27        found = False
28        for dx, dy in directions:
29            nx, ny = x + dx, y + dy
30            if 0 < nx < width - 1 and 0 < ny < height - 1 and maze[ny][nx] == '#':
31                maze[y + dy // 2][x + dx // 2] = ' '
32                maze[ny][nx] = ' '
33                stack.append((nx, ny))
34                found = True
35                break
36        
37        if not found:
38            stack.pop()
39            
40    # Entrance and Exit
41    maze[0][1] = ' '
42    maze[height - 1][width - 2] = ' '
43    return maze
44
45def print_maze(maze: list[list[str]]) -> None:
46    for row in maze:
47        print(''.join(row))
48
49if __name__ == '__main__':
50    w = int(sys.argv[1]) if len(sys.argv) > 1 else 21
51    h = int(sys.argv[2]) if len(sys.argv) > 2 else 11
52    print_maze(generate_maze_iterative(w, h))
53