feat: add braid maze generator (removes all dead ends)

new file mode 100644

@@ -0,0 +1,66 @@

import random

def generate_braid_maze(width, height):

    """

    Generates a braid maze (no dead ends) by removing all dead ends from a basic grid.

    """

    # Initialize grid with walls (1) and paths (0)

    # Using a 2*N+1 grid for walls between cells

    grid = [[1 for _ in range(width * 2 + 1)] for _ in range(height * 2 + 1)]

    # Start with a simple spanning tree (using Prim's or randomized DFS)

    # For this one-liner/simple style, let's use a basic DFS approach

    stack = [(0, 0)]

    visited = set([(0, 0)])

    grid[1][1] = 0

    while stack:

        cx, cy = stack[-1]

        neighbors = []

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:

            nx, ny = cx + dx, cy + dy

            if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:

                neighbors.append((nx, ny, dx, dy))

        if neighbors:

            nx, ny, dx, dy = random.choice(neighbors)

            visited.add((nx, ny))

            grid[cy * 2 + 1 + dy][cx * 2 + 1 + dx] = 0

            grid[ny * 2 + 1][nx * 2 + 1] = 0

            stack.append((nx, ny))

        else:

            stack.pop()

    # BRAIDING: Find all dead ends and remove them

    # A dead end is a path cell with exactly one path neighbor

    for y in range(height):

        for x in range(width):

            gx, gy = x * 2 + 1, y * 2 + 1

            if grid[gy][gx] == 0:

                neighbors = []

                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:

                    if grid[gy + dy][gx + dx] == 0:

                        neighbors.append((dx, dy))

                if len(neighbors) == 1:

                    # Found a dead end! Pick a random wall neighbor and remove it

                    walls = []

                    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:

                        # Ensure we don't go out of bounds

                        if 1 <= gx + dx < width * 2 and 1 <= gy + dy < height * 2:

                            if grid[gy + dy][gx + dx] == 1:

                                walls.append((dx, dy))

                    if walls:

                        wdx, wdy = random.choice(walls)

                        grid[gy + wdy][gx + wdx] = 0

    return grid

def print_maze(grid):

    for row in grid:

        print("".join(["#" if cell == 1 else " " for cell in row]))

if __name__ == "__main__":

    maze = generate_braid_maze(15, 7)

    print_maze(maze)