用python实现迷宫
由于迷宫的生成和求解都是比较复杂的算法,因此本文只提供一种简单的迷宫生成和求解方法。
生成迷宫
首先,我们需要生成迷宫。我们可以使用递归分割法来生成迷宫。具体步骤如下:
1.初始化一个空地图,全部填充为墙壁。
2.从某一点开始,将墙壁拆除,形成两个房间。
3.对于每个房间,随机选择一面墙,将其拆除,连接两个房间。
4.重复步骤3,直到所有的房间都被连接。
下面是代码实现:
import random
def generate_maze(width, height): # 初始化地图 maze = [] for i in range(height): row = [] for j in range(width): row.append('#') maze.append(row)
# 递归分割法生成迷宫
divide(maze, 0, 0, width-1, height-1)
return maze
def divide(maze, x1, y1, x2, y2): if x2-x1 < 2 or y2-y1 < 2: return
# 随机选择一面墙
if x2-x1 > y2-y1:
wall_x = random.randint(x1+1, x2-1)
for y in range(y1, y2+1):
maze[y][wall_x] = ' '
# 在墙上开一个门
gap_y = random.randint(y1, y2)
maze[gap_y][wall_x] = '#'
# 递归处理两个房间
divide(maze, x1, y1, wall_x-1, y2)
divide(maze, wall_x+1, y1, x2, y2)
else:
wall_y = random.randint(y1+1, y2-1)
for x in range(x1, x2+1):
maze[wall_y][x] = ' '
gap_x = random.randint(x1, x2)
maze[wall_y][gap_x] = '#'
divide(maze, x1, y1, x2, wall_y-1)
divide(maze, x1, wall_y+1, x2, y2)
maze = generate_maze(10, 10) for row in maze: print(''.join(row))
这里我们生成了一个10x10的迷宫,并输出到控制台上。
求解迷宫
接下来,我们需要求解迷宫。我们可以使用深度优先搜索算法来求解迷宫。具体步骤如下:
1.从起点开始,将其标记为已访问。
2.对于当前位置,依次尝试向上、下、左、右四个方向移动。
3.如果发现可以移动到一个未访问的位置,就将其标记为已访问,并将当前位置入栈。
4.重复步骤2和3,直到到达终点。
5.如果无法继续移动,就从栈顶弹出一个位置,回溯到上一个位置,重复步骤2和3。
下面是代码实现:
def solve_maze(maze, start, end): stack = [start] visited = set() visited.add(start) path = []
while stack:
cur = stack[-1]
if cur == end:
path = stack.copy()
break
x, y = cur
found = False
for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
new_x, new_y = x+dx, y+dy
if 0 <= new_x < len(maze[0]) and 0 <= new_y < len(maze) and maze[new_y][new_x] == ' ' and (new_x, new_y) not in visited:
stack.append((new_x, new_y))
visited.add((new_x, new_y))
found = True
break
if not found:
stack.pop()
return path
start = (0, 0) end = (9, 9) path = solve_maze(maze, start, end)
将路径标记为*
for x, y in path: maze[y][x] = '*'
输出求解后的迷宫
for row in maze: print(''.join(row))
这里我们将起点设为(0,0),终点设为(9,9),并输出求解后的迷宫,其中路径标记为*。