Python实现迷宫

### Python 实现迷宫算法

#### 使用深度优先搜索(DFS)生成迷宫
通过深度优先搜索可以创建随机连通的迷宫。此方法从任意位置开始，沿着未访问过的路径前进直到无法继续为止。

import random

def create_maze(width, height):
    maze = [[1] * width + [0] for _ in range(height)] + [[1] * (width + 1)]
    
    def walk(x, y):
        directions = [(x + dx, y + dy) for dx, dy in ((-2, 0), (2, 0), (0, -2), (0, 2)) \
                      if 1 <= x + dx < width and 1 <= y + dy < height]
        random.shuffle(directions)

        for nx, ny in directions:
            if maze[ny][nx]:
                continue
            
            maze[y + (ny-y)//2][x + (nx-x)//2] = 0
            maze[ny][nx] = 0
            walk(nx, ny)
            
    start_x, start_y = 1, 1
    maze[start_y][start_x] = 0
    walk(start_x, start_y)

    return maze[:-1]

maze = create_maze(8, 5)
for row in maze:
    print(''.join(['#' if cell else ' ' for cell in row]))

这段代码展示了如何利用递归的方式构建一个简单的二维数组表示的迷宫[^1]。

#### 解决迷宫问题——广度优先搜索(BFS)
对于求解最短路径的问题来说，BFS是一个不错的选择因为它能够找到到达目标节点的第一条路径即为最短路径。

from collections import deque

def solve_maze(maze, start=(0, 0)):
    queue = deque([start])
    visited = set()
    predecessors = {start: None}
    
    while queue:
        current_position = queue.popleft()

        if is_goal(current_position): break
        
        neighbors = get_neighbors(*current_position)
        
        for neighbor in neighbors:
            if neighbor not in visited and can_move_to(*neighbor):
                queue.append(neighbor)
                visited.add(neighbor)
                predecessors[neighbor] = current_position
                
    path = []
    position = goal
    
    while position:
        path.insert(0, position)
        position = predecessors.get(position)
        
    return path


def is_goal(pos):
    global goal
    return pos == goal


def get_neighbors(x, y):
    moves = [(0,-1),(0,1),(-1,0),(1,0)]
    result = []

    for move in moves:
        new_pos = (x+move[0], y+move[1])

        if all((c >= 0 and c<len(maze[i]) for i,c in enumerate(new_pos))):
            result.append(new_pos)

    return result
    

def can_move_to(x,y):
    try:
        return maze[y][x]==0
    except IndexError:
        return False

goal = (len(maze)-2,len(maze[-1])-2)
path = solve_maze(maze=maze,start=(1,1))
print(path)

上述程序实现了基于队列的数据结构来进行层次遍历从而找出从起点到终点的一系列坐标点组成的列表作为解决方案[^2]。