Pygame深度优先算法生成迷宫

### 使用 Pygame 和深度优先搜索 (DFS) 算法生成迷宫 为了实现基于 DFS 的迷宫生成器，可以按照以下方式构建程序。此方法不仅展示了如何利用 Python 中的 `pygame` 库绘制图形界面，同时也实现了经典的栈式递归版本的深度优先搜索逻辑。 #### 导入必要的库 ```python import pygame from collections import deque import random ``` #### 初始化设置与参数定义 ```python width, height = 800, 600 # 设置窗口大小 cell_size = 40 # 单元格尺寸 cols = width // cell_size # 列数 rows = height // cell_size# 行数 stack = [] # 存储访问过的节点 visited = [[False]*cols for _ in range(rows)] # 记录是否已访问过该位置 directions = [(0,-1), (-1,0), (0,1), (1,0)] # 定义四个方向向量 screen = pygame.display.set_mode((width, height)) clock = pygame.time.Clock() ``` #### 创建网格类 GridCell 来表示每一个单元格的状态 ```python class GridCell(): def __init__(self, i, j): self.i = i self.j = j self.walls = {'top':True,'right':True,'bottom':True,'left':True} def draw(self): x,y=self.i*cell_size,self.j*cell_size if not visited[self.j][self.i]: color=(255,255,255) else: color=(200,200,200) rect=pygame.Rect(x,y,cell_size,cell_size) pygame.draw.rect(screen,color,rect) if self.walls['top']: pygame.draw.line(screen,(0,0,0),(x,y),(x+cell_size,y)) if self.walls['right']: pygame.draw.line(screen,(0,0,0),(x+cell_size,y),(x+cell_size,y+cell_size)) if self.walls['bottom']: pygame.draw.line(screen,(0,0,0),(x,y+cell_size),(x+cell_size,y+cell_size)) if self.walls['left']: pygame.draw.line(screen,(0,0,0),(x,y),(x,y+cell_size)) grid=[[GridCell(i,j)for i in range(cols)]for j in range(rows)] current_cell=grid[0][0] ``` #### 主循环函数 dfs_maze_generator ```python def dfs_maze_generator(current_cell=current_cell): global stack current_cell_index=(current_cell.i,current_cell.j) visited[current_cell.j][current_cell.i]=True neighbors=[] for d in directions: ni,nj=d[0]+current_cell.i,d[1]+current_cell.j if 0<=ni<cols and 0<=nj<rows and not visited[nj][ni]: neighbor=grid[nj][ni] dx,dy=abs(ni-current_cell.i),abs(nj-current_cell.j) if dx==1 or dy==1:# 只考虑相邻的邻居 if dx>0: direction='leftright'[::(-1)**(neighbor.i<current_cell.i)] elif dy>0: direction='updown'[::(-1)**(neighbor.j<current_cell.j)] opposite={'left':'right','right':'left', 'up':'bottom','down':'top'} current_cell.walls[direction]=False neighbor.walls[opposite[direction]]=False neighbors.append(neighbor) if neighbors: next_neighbor=random.choice(neighbors) stack.append(current_cell) dfs_maze_generator(next_neighbor) elif stack: backtrack_to=stack.pop() dfs_maze_generator(backtrack_to) ``` #### 渲染和事件监听部分 ```python running=True while running: clock.tick(30) screen.fill((0,0,0)) for row in grid: for cell in row: cell.draw() for e in pygame.event.get(): if e.type == pygame.QUIT: running=False if all([all(row)for row in visited]): pass else: dfs_maze_generator() pygame.display.flip() pygame.quit() ``` 上述代码片段描述了一个完整的迷宫生成过程[^1]。通过调用 `dfs_maze_generator()` 函数启动深度优先搜索算法，在每次迭代过程中移除当前方块与其随机选取的一个未被探索过的邻接方块之间的墙壁，并将其加入到待回溯列表中；当没有更多可用邻居时，则返回到最后一次分支处继续尝试其他路径直到整个地图都被覆盖为止。