制作迷宫地图和行走路线（5）
说在前面
前4节课我们都是直接绘制随机迷宫图案，没有存储迷宫中各坐标点是通道还是墙壁的信息，这与通常的迷宫地图不一样。本节课我们使用传统的方法来绘制迷宫地图，即利用二维数组存储迷宫各坐标点信息，再根据二维数组绘制迷宫地图。
程序先生成随机二维数组，然后手动修改坐标点信息，以便绘制想要的地图。有了二维数组之后，就可以采用深度优先搜索算法来绘制地图了。地图绘制好了后，可以输入起点和终点坐标，根据深度优先搜索或者广度优先搜索算法寻找行走路线，其中使用广度优先搜索算法获得的是最短路径。
第5节 使用深度优先搜索算法绘制二维迷宫
我们在主函数中定义二维数组maze来表示地图，maze的元素值只有两种情况，1表示通道，0表示墙壁。先为maze随机赋值，输出其值后，复制粘贴回代码中，可以直观地看到各元素值，再手动修改坐标点信息，以便绘制想要的地图。
除了存储地图信息的二维数组maze，我们还定义了一个二维数组book，用来标记某个位置是否已经去过，以免重复访问同一位置。
参考代码如下：
w, h = 20, 20maze = [[random.randint(0,1) for j in range(w)] for i in range(h)]for i in range(h):print(maze[i])maze = [[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]book = [[0] * w for i in range(h)] #标记该位置是否已经去过
2.使用深度优先搜索算法绘制迷宫地图：
根据maze存储的地图信息，我们可以调用函数dfs()，采用深度优先搜索算法来绘制迷宫地图。因为地图中所有通道不一定都是连通的，也就是说一次深搜不一定能把所有的通道都绘制出来，所以需要遍历每一个位置，每遇到未被访问过的通道，都要调用函数dfs()。直到把所有的通道都绘制出来。
主函数中调用函数的代码如下：
for i in range(h):for j in range(w):if maze[i][j] == 1 and book[i][j] == 0:tt.penup()dfs(i, j)
自定义函数dfs()有两个参数r和c，分别表示当前格子在二维数组maze中的行、列下标。若当前位置(r, c)为未访问过的通道，则调用函数draw_rectangle()在该处绘制白色矩形。接下来遍历(r, c)的周围位置，若能走通，则递归去绘制下一个点，否则回溯到上一个位置。
自定义函数及函数头说明如下：
'''函数功能：以(x, y)作为左上角坐标，绘制宽、高分别为w、h的矩形，并填充颜色c函数名：draw_rectangle(x, y, w, h)参数表：x,y -- 表示矩形在屏幕中的左上角坐标；w,h -- 表示矩形的宽和高；c -- 表示矩形的填充颜色。返回值：直接使用画笔绘制并填充矩形，不需要返回值。'''def draw_rectangle(x, y, w, h, c):tt.penup()tt.goto(x, y)tt.pendown()tt.color(c)tt.begin_fill()for i in range(2):tt.forward(w)tt.right(90)tt.forward(h)tt.right(90)tt.end_fill()'''函数功能：使用深度优先搜索来生成迷宫函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组book当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。'''def dfs(r, c):# 标记(r, c)来过book[r][c]= 1# 绘制(r, c)draw_rectangle(start_x+c*size-size//2, start_y-r*size+size//2, size, size, 'white')# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:# 选所有可以走的下一个点，如果此点在范围内并且没去过if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: # 递归去走下一个点dfs(i, j)
3.使用深度优先搜索寻找并绘制路径：
绘制好迷宫地图以后，就可以输入起点和终点坐标，寻找连接二者的路径了。因为在绘制地图过程中，二维数组book的值发生了变化，所以需要先将book归零，以便重新遍历地图。
我们从起点(r1, c1)开始，调用函数dfs_ans()，使用深度优先搜索算法来寻找路径。设置全局变量ans用来逆序存储路线上的各个格子的行列下标。待找到从起点到终点的路径以后，再调用函数display_ans()绘制路径。
主函数中调用函数的代码如下：
tt.delay(1)r1, c1 = [int(i) for i in input("起点行列下标：").split()]r2, c2 = [int(i) for i in input("终点行列下标：").split()]book = [[0] * w for i in range(h)] # 将book归零，重新遍历地图book[r1][c1] = 1ans = []dfs_ans(r1, c1)ans.append((r1, c1))display_ans()tt.done()
自定义函数dfs_ans()与函数dfs()的结构相似，都是两个参数r和c，用来表示当前格子在二维数组maze中的行、列下标。若当前位置(r, c)恰好为终点，则直接返回True；否则遍历其周围的格子，递归处理下一个可通行的位置。若当前格子与终点连通，将当前格子行列下标加入到ans，并返回True。
程序有一个有趣的地方，就是随机打乱数组d的元素顺序，这样遍历d时，下一个位置是随机的，从而导致每次运行程序时可以得到不同的搜索路线。
自定义函数display_ans()根据ans的值，绘制使用深度优先搜索获得的路径。因为列表ans是按照从终点到起点的顺序存储位置坐标的，故在绘制路径时，需要逆序遍历ans，才能绘制从起点到终点的路径。
自定义函数及函数头说明如下：
'''函数功能：使用深度优先搜索来寻找路径函数名：dfs_ans(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把列表book和ans当做全局变量，若从当前格子能够到达终点，返回True，否则False。'''def dfs_ans(r, c):if r==r2 and c==c2:return True# (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]==1 and book[i][j]==0: book[i][j] = 1# 递归去走下一个点if dfs_ans(i, j): # 若当前格子与终点连通，将当前格子行列下标加入到ansans.append((i, j))return Truereturn False'''函数功能：根据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)
课后练习
本文展示的成品效果图中，有红、绿两种颜色的路径，其中红色为采用深度优先搜索算法获得的路径，绿色路径较短，它是采用广度优先搜索算法获得的最短路径。
现在请你在原有代码的基础上，增加程序功能，自定义相关函数，使用广度优先搜索算法寻找路径，并用绿色画笔把路径绘制出来。
需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：