制作迷宫地图和行走路线（1）

说在前面

前几天，在微信群看到“编程玩家俱乐部胡老师”发的一篇文章《迷宫是怎么生成的？》，点进去看了一下，发现挺有趣，能够生成漂亮的迷宫图案，代码也简明易懂，算得上“小而美”的精品。

美中不足的是，程序只完成了构造随机迷宫图案的功能，却没有记录通道的行进路线。这样只能通过肉眼观察迷宫，手动绘制从起点到终点的路线，而不能让电脑自动绘制行走路线。

认真分析了胡老师的代码以后，我对程序做了一些改进，增加了记录迷宫路线功能，可以给定起点和终点坐标，让电脑自动绘制行走路线。胡老师的程序是按照深度优先搜索算法来构造迷宫的，从起点到终点只有一条路径（没有环）。我在此基础上增加了部分环，这样行走路线就不是唯一的了，可以采用深度优先搜索算法随机寻找不同的路径，也可以使用广度优先搜索算法来寻找最短路径。

另外，胡老师的程序是直接绘制随机迷宫图案，没有存储迷宫中各坐标点是空地还是墙壁的信息，这与通常的迷宫地图不一样。我又编写了利用二维数组存储迷宫各坐标点信息，根据二维数组绘制迷宫地图的程序，该程序先生成随机地图，然后通过手动修改坐标点信息对地图进行修改，以便绘制想要的地图。之后可以输入起点和终点坐标，分别根据深度优先搜索和广度优先搜索算法寻找行走路线。

我把上述内容整理成一个迷宫系列专题，逐一和大家分享。请大家批评指正，希望能对您有所启发，开发出更多更有趣的程序。

第1节      使用深度优先搜索算法生成不含环迷宫

不含环迷宫是最简单的迷宫。其基本思路是直接用画笔在黑色背景中绘制白色通道。先设置好迷宫的宽w、高h和格子大小size。因为画笔粗细就等于迷宫通道宽度，故可以设置画笔粗细略小于格子宽度，这样未被遮盖的黑色背景就表示迷宫的墙壁。

绘制二维迷宫，需要先做一点坐标变换的工作。因为点在屏幕上的坐标是用(x,y)表示的，而格子是否被访问的信息存储在二维数组maze中，maze[r][c]=1表示行列下标为(r,c)的格子已经来过了。所以需要把行列坐标为(r,c)的格子与屏幕上的实际坐标(x,y)建立联系。

以迷宫左上角作为行列下标起始点(0, 0)，它在屏幕上的实际坐标为(start_x,start_y)，则行列下标为(r,c)的格子在屏幕上的实际坐标为(start_x+c*size, start_y-r*size)。

先让画笔走到迷宫左上角位置，然后调用dfs()函数生成迷宫。

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)]
start_x = -w / 2 * sizestart_y = h / 2 * size# 让画笔到左上角位置tt.penup()tt.goto(start_x, start_y)tt.pendown()# 从左上角(0, 0)开始走dfs(0, 0) # 使用深度优先搜索来生成不含环迷宫
tt.done()  # 结束绘图，这将不会关闭窗口

'''函数功能：使用深度优先搜索来生成不含环迷宫函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组maze当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。''' 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:            # 递归去走下一个点            dfs(i, j)            # 回溯到(r, c)            tt.goto(start_x+c*size, start_y-r*size)

代码说明：

函数把二维数组maze当做全局变量使用，直接修改maze[r][c]= 1，表示(r, c)处的格子已经来过了。列表d存储(r, c)的上下左右位置，我们把d的元素随机打乱，这样就可以随机生成迷宫通道了。接下来遍历与(r, c)相邻的格子(i, j)，若格子(i, j)没有去过，则递归处理该格子，直到无路可走为止。然后回溯到(r, c)，即将画笔移动到(r, c)格子处，以便递归处理下一个相邻格子。

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

现在请你仔细思考，在现有代码的基础上，增加记录迷宫路线的功能；并实现给定任意起点和终点坐标，让电脑自动绘制行走路线的功能。

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

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

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类