制作迷宫地图和行走路线（2）-轻识

说在前面

上节课我们介绍了“使用深度优先搜索算法生成不含环迷宫”的方法，该程序只完成了构造随机迷宫图案的功能，却没有记录通道行进路线。这样只能通过肉眼观察迷宫，手动绘制从起点到终点的路线，而不能让电脑自动绘制行走路线。我们可以在绘制迷宫通道的同时，把通道前进的方向也记录下来，为后期遍历迷宫做好准备工作。

今天我们就在上节课代码的基础上，增加记录迷宫路线的功能；并实现给定任意起点和终点坐标，让电脑自动绘制行走路线的功能。

第2节 使用深度优先搜索算法生成迷宫并寻找路径

成品效果图

1.使用深度优先搜索来生成不含环迷宫，并记录通道走向：

第1节课介绍的程序只完成了构造随机迷宫图案的功能，却没有记录通道行进路线。这样只能通过肉眼观察迷宫，手动绘制从起点到终点的路线，而不能让电脑自动绘制行走路线。我们可以在绘制迷宫通道的同时，使用二维数组route记录迷宫路线，其中route[r][c]的值是一个列表，存储了与格子(r, c)连通的相邻格子的行列下标(i, j)，有几个格子与(r, c)相邻且连通，route[r][c]就有几个元素。

'''函数功能：使用深度优先搜索来生成不含环迷宫，并记录通道走向函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组maze和route当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。''' def dfs(r, c):    # 标记(r, c)来过    maze[r][c] = 1    # 走到(r, c)    tt.goto(start_x+c*size, start_y-r*size)    # (r, c)的上下左右位置    d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]    # 打乱位置，下一个位置是随机的    random.shuffle(d)    for (i, j) in d:        # 选所有可以走的下一个点，如果此点在范围内并且没去过        if 0<=iand 0<=jand maze[i][j]==0:            route[r][c].append((i, j)) # 记录与(r, c)连通的位置(i, j)            route[i][j].append((r, c)) # 记录与(i, j)连通的位置(r, c)            # 递归去走下一个点            dfs(i, j)            # 回溯到(r, c)            tt.goto(start_x+c*size, start_y-r*size)

2.使用深度优先搜索来寻找路径

有了二维数组route记录的通道行进信息，就可以给定任意起点和终点坐标，让电脑自动绘制行走路线。我们先将maze归零，以便重新遍历地图。同时定义列表ans来存储行走路径，先将终点加入到ans中，之后逆序添加各个格子的行列下标。

那么使用什么方法来遍历地图呢？

最容易想到的方法是模仿构造迷宫地图，使用深度优先搜索算法。我们可以定义函数dfs_ans(r, c)，把列表maze和ans当做全局变量（因为列表是可变对象，即使不声明为global变量，仍可以修改其元素值），若从当前格子出发能够到达终点，返回True，否则False。

函数遍历与当前格子(r, c)连通的相邻格子route[r][c]，递归处理通道上的每一个格子，直到终点。若当前格子与终点连通，将当前格子行列下标添加到ans，并返回True，否则返回False。

'''函数功能：使用深度优先搜索来寻找路径函数名：dfs_ans(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把列表maze和ans当做全局变量，若从当前格子出发能够到达终点，返回True，否则False。''' def dfs_ans(r, c):    if r==r2 and c==c2:        return True    for (i, j) in route[r][c]:        if maze[i][j] == 0: # 如果没有去过该点，则递归搜索该点            maze[i][j] = 1  # 标记该点已经来过            # 递归去走下一个点            if dfs_ans(i, j): #若当前格子与终点连通，将当前格子行列下标加入到ans                ans.append((r, c))                return True    return False

3.绘制使用深度优先搜索获得的路径

有了列表ans存储的路径信息，就可以绘制行走路线了。因为ans的元素值是采用回溯算法依次添加的，所以离终点越近的格子越早添加到ans中。因此我们需要逆序遍历ans，才可以顺序输出从起点到终点的路线。我们定义函数display_ans()实现该功能，参考代码如下：

'''函数功能：根据ans的值，绘制使用深度优先搜索获得的路径函数名：display_ans()参数表：直接使用列表ans的元素值，不需要任何参数。返回值：直接利用画笔绘制路线，不需要返回值。''' def display_ans():    tt.speed(1)    tt.pensize(size*0.5) # 路线粗细    tt.color("red")    tt.penup()    tt.goto(start_x+ans[-1][1]*size, start_y-ans[-1][0]*size)    tt.pendown()    for (r, c) in ans[-2::-1]: #逆序遍历ans，刚好可以顺序输出从起点到终点的路线        tt.goto(start_x+c*size, start_y-r*size)

4.主函数部分代码

tt.TurtleScreen._RUNNING = True  # 启动绘图，在IDE中运行加这句可避免报错tt.ht()#隐藏笔头tt.bgcolor('black')tt.color("white") # 路线颜色tt.speed(3)w, h = 20, 20 # 迷宫宽和高size = 30 # 每格大小tt.pensize(size*0.8) # 路线粗细maze = [[0] * w for i in range(h)]route = [[[] for j in range(w)] for i in range(h)] #记录迷宫路线
start_x = -w / 2 * sizestart_y = h / 2 * size# 让画笔到左上角位置tt.penup()tt.goto(start_x, start_y)tt.pendown()# 从左上角(0, 0)开始走dfs(0, 0) # 使用深度优先搜索来生成不含环迷宫
# 使用深度优先搜索来寻找路径r1, c1 = [int(i) for i in input("起点行列下标：").split()]r2, c2 = [int(i) for i in input("终点行列下标：").split()]maze = [[0] * w for _ in range(h)] # 将maze归零，重新遍历地图maze[r1][c1] = 1  # 标记起点已经去过了ans = [(r2, c2)]  # 先将终点加入到ans中，之后逆序添加各个格子dfs_ans(r1, c1)   # 使用深度优先搜索来寻找路径display_ans()     # 绘制使用深度优先搜索获得的路径
tt.done()  # 结束绘图，这将不会关闭窗口

代码说明：

与第1节课的程序相比，本节课程序在主函数中增加了一个二维数组route，用来记录记录迷宫路线。还增加了使用深度优先搜索来寻找路径的功能：先从键盘依次读入起点行、列下标（用空格隔开）和终点行、列下标，然后将maze归零，以便重新遍历地图。定义列表ans，并将终点的行列下标(r2, c2)作为ans的第一个元素，之后调用函数dfs_ans()，使用深度优先搜索算法逆序添加各个格子信息到ans中。最后调用函数display_ans()绘制使用深度优先搜索获得的路径。

至此，我们就完成了使用深度优先搜索算法生成迷宫并寻找路径功能。因为迷宫通道把所有的格子都连通了，所以你可以将任意格子当作起点或终点，从键盘输入它们的行、列坐标后，观察红色画笔的行进路线。

课后练习

本节课介绍的程序是使用深度优先搜索算法来寻找路径的，除此之外，我们还可以使用广度优先搜索算法来寻找路径。请查阅广度优先搜索算法相关知识，设置自定义函数，实现给定任意起点和终点坐标，使用广度优先搜索算法来寻找路径、并绘制行走路线的功能。

需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类