Spaces:
Sleeping
Sleeping
File size: 5,249 Bytes
737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 d780047 6d196f1 d780047 6d196f1 d780047 737fab6 d780047 737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 d780047 6d196f1 d780047 6d196f1 d780047 737fab6 d780047 6d196f1 d780047 737fab6 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | 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]
|