ascii-maze-factory

1import random
2
3def generate_braid_maze(width, height):
4    """
5    Generates a braid maze (no dead ends) by removing all dead ends from a basic grid.
6    """
7    # Initialize grid with walls (1) and paths (0)
8    # Using a 2*N+1 grid for walls between cells
9    grid = [[1 for _ in range(width * 2 + 1)] for _ in range(height * 2 + 1)]
10    
11    # Start with a simple spanning tree (using Prim's or randomized DFS)
12    # For this one-liner/simple style, let's use a basic DFS approach
13    stack = [(0, 0)]
14    visited = set([(0, 0)])
15    grid[1][1] = 0
16    
17    while stack:
18        cx, cy = stack[-1]
19        neighbors = []
20        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
21            nx, ny = cx + dx, cy + dy
22            if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:
23                neighbors.append((nx, ny, dx, dy))
24        
25        if neighbors:
26            nx, ny, dx, dy = random.choice(neighbors)
27            visited.add((nx, ny))
28            grid[cy * 2 + 1 + dy][cx * 2 + 1 + dx] = 0
29            grid[ny * 2 + 1][nx * 2 + 1] = 0
30            stack.append((nx, ny))
31        else:
32            stack.pop()
33            
34    # BRAIDING: Find all dead ends and remove them
35    # A dead end is a path cell with exactly one path neighbor
36    for y in range(height):
37        for x in range(width):
38            gx, gy = x * 2 + 1, y * 2 + 1
39            if grid[gy][gx] == 0:
40                neighbors = []
41                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
42                    if grid[gy + dy][gx + dx] == 0:
43                        neighbors.append((dx, dy))
44                
45                if len(neighbors) == 1:
46                    # Found a dead end! Pick a random wall neighbor and remove it
47                    walls = []
48                    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
49                        # Ensure we don't go out of bounds
50                        if 1 <= gx + dx < width * 2 and 1 <= gy + dy < height * 2:
51                            if grid[gy + dy][gx + dx] == 1:
52                                walls.append((dx, dy))
53                    
54                    if walls:
55                        wdx, wdy = random.choice(walls)
56                        grid[gy + wdy][gx + wdx] = 0
57
58    return grid
59
60def print_maze(grid):
61    for row in grid:
62        print("".join(["#" if cell == 1 else " " for cell in row]))
63
64if __name__ == "__main__":
65    maze = generate_braid_maze(15, 7)
66    print_maze(maze)
67