Untitled

 avatar
unknown
plain_text
2 months ago
2.8 kB
6
Indexable
def create_labyrinth(width, height):
    """Generate a random maze using recursive backtracking algorithm.
    
    Args:
        width: Width of the labyrinth (will be made odd if even)
        height: Height of the labyrinth (will be made odd if even)
    
    Returns:
        2D list representing the labyrinth (1=wall, 0=path)
    """
    # Make sure width and height are odd
    if width % 2 == 0:
        width += 1
    if height % 2 == 0:
        height += 1
    
    # Create a grid filled with walls
    maze = [[1 for _ in range(width)] for _ in range(height)]
    
    def carve_passages(x, y, visited=None):
        if visited is None:
            visited = set()
            
        visited.add((x, y))
        maze[y][x] = 0  # Carve current cell
        
        # Directions: right, down, left, up
        directions = [(2, 0), (0, 2), (-2, 0), (0, -2)]
        random.shuffle(directions)
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # Check if the new position is within bounds and not visited
            if (0 <= nx < width and 0 <= ny < height and 
                (nx, ny) not in visited and maze[ny][nx] == 1):
                
                # Carve passage between cells
                maze[y + dy//2][x + dx//2] = 0
                carve_passages(nx, ny, visited)
    
    # Start from a random point with odd coordinates
    start_x = random.randrange(1, width, 2)
    start_y = random.randrange(1, height, 2)
    
    # Generate the maze with a limit on recursion
    # Use iterative approach instead to avoid stack overflow
    stack = [(start_x, start_y)]
    visited = set()
    
    while stack:
        x, y = stack[-1]
        visited.add((x, y))
        maze[y][x] = 0  # Carve current cell
        
        # Find unvisited neighbors
        neighbors = []
        for dx, dy in [(2, 0), (0, 2), (-2, 0), (0, -2)]:  # right, down, left, up
            nx, ny = x + dx, y + dy
            if (0 <= nx < width and 0 <= ny < height and 
                (nx, ny) not in visited and maze[ny][nx] == 1):
                neighbors.append((nx, ny, dx, dy))
        
        if neighbors:
            # Choose a random unvisited neighbor
            nx, ny, dx, dy = random.choice(neighbors)
            
            # Carve passage between cells
            maze[y + dy//2][x + dx//2] = 0
            
            # Add the neighbor to the stack to explore next
            stack.append((nx, ny))
        else:
            # Backtrack
            stack.pop()
    
    # Create entrance and exit
    maze[0][1] = 0  # Entrance at top
    maze[height-1][width-2] = 0  # Exit at bottom
    
    return maze
Editor is loading...
Leave a Comment