Spaces:
Sleeping
Sleeping
| import random | |
| from collections import deque | |
| def generate_maze(w, h, seed=0): | |
| """ | |
| Generate a randomized perfect maze using depth-first search. | |
| Args: | |
| w (int): width of the maze in cells (number of columns). | |
| h (int): height of the maze in cells (number of rows). | |
| Returns: | |
| list[list[int]]: 2D grid representing the maze where 1 indicates a wall | |
| and 0 indicates an open cell. The start is at (0,0) and the goal is at (w-1,h-1). | |
| """ | |
| maze = [[1]*w for _ in range(h)] | |
| rng = random.Random(seed) if seed else None | |
| def dfs(x, y): | |
| maze[y][x] = 0 | |
| dirs = [(0,2),(2,0),(0,-2),(-2,0)] | |
| (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs)) | |
| for dx,dy in dirs: | |
| nx,ny = x+dx,y+dy | |
| if 0<=nx<w and 0<=ny<h and maze[ny][nx]: | |
| maze[y+dy//2][x+dx//2] = 0 | |
| dfs(nx,ny) | |
| # occasional extra random connection (10%) to introduce loops and increase difficulty | |
| if (rng.random() if rng is not None else random.random()) < 0.1: | |
| extra_dirs = [d for d in dirs if d != (dx,dy)] | |
| (rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs)) | |
| for edx, edy in extra_dirs: | |
| enx, eny = x+edx, y+edy | |
| # ensure within bounds and target already open | |
| if 0<=enx<w and 0<=eny<h and maze[eny][enx]==0: | |
| # open the wall between (x,y) and (enx,eny) if it's closed | |
| wx, wy = x+edx//2, y+edy//2 | |
| if maze[wy][wx]: | |
| maze[wy][wx] = 0 | |
| break | |
| dfs(0,0) | |
| maze[0][0] = maze[h-1][w-1] = 0 | |
| # ensure starting cell has one extra open neighbour if possible (not an external wall) | |
| dirs = [(0,2),(2,0),(0,-2),(-2,0)] | |
| random.shuffle(dirs) | |
| for dx,dy in dirs: | |
| nx,ny = dx,dy | |
| if 0<=nx<w and 0<=ny<h and maze[ny][nx]==1: | |
| # open the intermediate wall and the target cell | |
| maze[dy//2][dx//2] = 0 | |
| maze[ny][nx] = 0 | |
| break | |
| return maze | |
| def generate_maze_iterative(w, h, seed=0): | |
| """ | |
| Generate a randomized perfect maze using an explicit stack (iterative DFS). | |
| Args: | |
| w (int): width of the maze in cells (number of columns). | |
| h (int): height of the maze in cells (number of rows). | |
| Returns: | |
| list[list[int]]: 2D grid representing the maze where 1 indicates a wall | |
| and 0 indicates an open cell. | |
| """ | |
| maze = [[1]*w for _ in range(h)] | |
| rng = random.Random(seed) if seed else None | |
| stack = [(0, 0)] | |
| maze[0][0] = 0 | |
| dirs = [(0,2),(2,0),(0,-2),(-2,0)] | |
| while stack: | |
| x,y = stack[-1] | |
| (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs)) | |
| for dx,dy in dirs: | |
| nx,ny = x+dx,y+dy | |
| if 0<=nx<w and 0<=ny<h and maze[ny][nx]: | |
| maze[y+dy//2][x+dx//2] = 0 | |
| maze[ny][nx] = 0 | |
| stack.append((nx,ny)) | |
| # occasional extra random connection (10%) to introduce loops and increase difficulty | |
| if (rng.random() if rng is not None else random.random()) < 0.1: | |
| extra_dirs = [d for d in dirs if d != (dx,dy)] | |
| (rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs)) | |
| for edx, edy in extra_dirs: | |
| enx, eny = x+edx, y+edy | |
| if 0<=enx<w and 0<=eny<h and maze[eny][enx]==0: | |
| wx, wy = x+edx//2, y+edy//2 | |
| if maze[wy][wx]: | |
| maze[wy][wx] = 0 | |
| break | |
| break | |
| else: | |
| stack.pop() | |
| maze[0][0] = maze[h-1][w-1] = 0 | |
| # ensure starting cell has one extra open neighbour if possible (not an external wall) | |
| dirs = [(0,2),(2,0),(0,-2),(-2,0)] | |
| (rng.shuffle(dirs) if rng is not None else random.shuffle(dirs)) | |
| for dx,dy in dirs: | |
| nx,ny = 0+dx, 0+dy | |
| if 0<=nx<w and 0<=ny<h and maze[ny][nx]==1: | |
| # open the intermediate wall and the target cell | |
| maze[dy//2][dx//2] = 0 | |
| maze[ny][nx] = 0 | |
| break | |
| return maze | |
| def solve_maze(maze): | |
| """ | |
| Solve a maze grid using breadth-first search to produce the shortest path. | |
| Args: | |
| maze (list[list[int]]): 2D grid where 1 indicates a wall and 0 indicates open space. | |
| Returns: | |
| list[tuple[int,int]]: list of (x, y) coordinates from start (0,0) to goal (w-1,h-1). | |
| """ | |
| h,w = len(maze),len(maze[0]) | |
| q = deque([(0,0)]) | |
| parent = {(0,0):None} | |
| while q: | |
| x,y = q.popleft() | |
| if (x,y)==(w-1,h-1): | |
| break | |
| for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]: | |
| nx,ny = x+dx,y+dy | |
| if 0<=nx<w and 0<=ny<h and maze[ny][nx]==0 and (nx,ny) not in parent: | |
| parent[(nx,ny)] = (x,y) | |
| q.append((nx,ny)) | |
| path = [] | |
| at = (w-1,h-1) | |
| while at: | |
| path.append(at) | |
| at = parent.get(at) | |
| return path[::-1] | |