相信大家都玩过迷宫的游戏,对于简单的迷宫,我们可以一眼就看出通路,但是对于复杂的迷宫,可能要仔细寻找好久,甚至耗费数天,然后可能还要分别从入口和出口两头寻找才能找的到通路,甚至也可能找不到通路。
虽然走迷宫问题对于我们人类来讲比较复杂,但对于计算机来说却是很简单的问题。为什么这样说呢,因为看似复杂实则是有规可循的。
我们可以这么做,携带一根很长的绳子,从入口出发一直走,如果有岔路口就走最左边的岔口,直到走到死胡同或者找到出路。如果是死胡同则退回上一个岔路口,我们称之为岔口 A,
这时进入左边第二个岔口,进入第二个岔口后重复第一个岔口的步骤,直到找到出路或者死胡同退回来。当把该岔路口所有的岔口都走了一遍,还未找到出路就沿着绳子往回走,走到岔口 A 的前一个路口 B,重复上面的步骤。
不知道你有没有发现,这其实就是一个不断递归的过程,而这正是计算机所擅长的。
上面这种走迷宫的算法就是我们常说的深度优先遍历算法,与之相对的是广度优先遍历算法。有了理论基础,下面我们就来试着用 程序来实现一个走迷宫的小程序。
先来看看最终的效果视频。
生成迷宫
生成迷宫有很多种算法,常用的有递归回溯法、递归分割法和随机 Prim 算法,我们今天是用的最后一种算法。
该算法的主要步骤如下:
1 |
|
我们定义一个 Maze 类,用二维数组表示迷宫地图,其中 1 表示墙壁,0 表示路,然后初始化左上角为入口,右下角为出口,最后定义下方向向量。
1 |
|
接下来就是生成迷宫的主函数了。
1 |
|
该函数里面有两个主要函数 get_neighbor_road(point)
和 deal_with_not_visited()
,前者会获得传入坐标点 point 的邻路节点,返回值是一个二维数组,后者 deal_with_not_visited()
函数处理步骤 4.1 的逻辑。
由于 Prim 随机算法是随机的从列表中的所有的单元格进行随机选择,新加入的单元格和旧加入的单元格被选中的概率是一样的,因此其分支较多,生成的迷宫较复杂,难度较大,当然看起来也更自然些。来看看我们生成的迷宫。
1 |
|
走出迷宫
得到了迷宫的地图,接下来就按照我们文首的思路来走迷宫即可。主要函数逻辑如下:
1 |
|
很明显,这就是一个典型的递归程序。当该节点坐标越界、该节点被访问过或者该节点是墙壁的时候,直接返回,因为该节点肯定不是我们要找的路径的一部分,否则就将该节点加入被访问过的节点和路径的集合中。
然后如果该节点是出口则表示程序执行结束,找到了通路。不然就遍历四个方向向量,将节点的邻路传入函数 dfs 继续以上步骤,直到找到出路或者程序所有节点都遍历完成。
来看看我们 dfs 得出的路径结果:
1 |
|
可视化
有了迷宫地图和通路路径,剩下的工作就是将这些坐标点渲染出来。今天我们用的可视化库是 pyxel
,这是一个用来写像素级游戏的 Python 库,
当然是用前需要先安装下这个库。
Win 用户直接用 pip install -U pyxel
命令安装即可。
Mac 用户使用以下命令安装:
1 |
|
先来看个简单的 Demo。
1 |
|
类 App 的执行逻辑就是不断的调用 update 函数和 draw 函数,因此可以在 update 函数中更新物体的坐标,然后在 draw 函数中将图像画到屏幕即可。
如此我们就先把迷宫画出来,然后在渲染 dfs 遍历动画。
1 |
|
看起来还可以,这里的宽和高我分别用了 37 和 21 个像素格来生成,所以生成的迷宫不是很复杂,如果像素点很多的话就会错综复杂了。
接下里来我们就需要修改 update 函数和 draw 函数来渲染路径了。为了方便操作,我们在 init 函数中新增几个属性。
1 |
|
其中 index 和 step 是用来控制渲染速度的,在 draw 函数中 index 每次自增 1,然后再对 step 求余得到当前的真实下标 real_index,简言之就是 index 每增加 step,real_index 才会加一,渲染路径向前走一步。
1 |
|
1 |
|
至此,我们完整的从迷宫生成,到寻找路径,再到路径可视化已全部实现。直接调用主函数 App()
然后按 S
键盘开启游戏,就可以看到文首的效果了。
总结
今天我们用深度优先算法实现了迷宫的遍历,对于新手来说,递归这思路可能比较难理解,但这才是符合计算机思维的,随着经验的加深会理解越来越深刻的。
其次我们用 pyxel 库来实现路径可视化,难点在于坐标的计算更新,细节比较多且繁琐,当然读者也可以用其他库或者直接用网页来实现也可以。
快去后台获取源码链接一试身手吧。
代码地址
示例代码:https://github.com/JustDoPython/python-examples/tree/master/doudou/2020-06-12-maze