Untitled
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