背景
我打开手机，发现有人在QQ空间里叫嚣。
看他得意的样子，显然是在家里呆久了，已经忘了天有多高。
预处理
设计一个迷宫自动寻路算法并不难，但是对于当下这个任务而言，第一个棘手的地方在于，如何把这个迷宫变成计算机认识的样子，也就是迷宫图片的矩阵化。
图片的大小是 397×390 。先把四周的白边裁掉，再把这幅图中的每一个像素二值化，再根据颜色赋值，黑色用 0 表示，白色用 1 表示，建立一个 0/1 矩阵。考虑到迷宫的边界都是封闭的，为了防止由于图片质量问题导致某些看上去是 0 的地方其实是 1 ，在之后走迷宫的过程中造成一些可预知的影响，比如列表的越界等，我们再把四条边上的元素全部强制变成 0 。这时，对迷宫的预处理已经基本完成，如果我们把 1 隐藏，把所有的 0 打印出来，经过放缩之后，就得到了这样的结果：
寻路算法
得到了这个迷宫矩阵之后，我们需要找到一条从左上角到右下角的路。
印象中我与有关走迷宫的方法有过一面之缘，那是在一节算法选修课上，老师在台上深情地讲着深度优先搜索与广度优先搜索，我在台下忘我地抄着大物实验报告。至今，提起这两个概念，我唯一的印象只有它俩的英文缩写一个是D开头一个是B开头。
不过没关系。当年陈刀仔他能用20块赢到3700万，我用 for循环 搞定这个小迷宫，没有问题。
一般来说，迷宫的内部是不封闭的，我从任意一个地方倒水，总能把整个迷宫填满。因此，假定我们有一个小老鼠，把它放在起点，如果它能够保证 自动避障、不踩走过的路、遇死胡同回退 ，那么它总能找到终点。
因此，我们定义一个点 (x,y) ，初始位置为 (1,1) ，也就是边界内左上角的第一个点。
定义两个列表，一个是 path ，用来存放它最终确定下来的路径（也就是那个最终走到终点的路径）中的每一个点；另一个是 footprint ，用来存放所有它走过的地方，包括它走的错路。两个列表形如 [(1,1),(1,2),(2,2),......,(m,n)] 。
再定义四种动作，分别是：向下走一步 (y=y+1) ，向右走一步 (x=x+1) ，向左走一步 (x=x-1) 和向上走一步 (y=y-1) 。我们每次让这个点尝试四种动作，如果能走就让它走。判断是否不能走是看下一步的坐标是否是墙或者是足迹。把新的点放进 path 和 footprint 里，成为新的足迹。
确定四个动作的优先级，即 下、右、左、上 ，能下则下，不能下则右，不能右则左，不能左则上。这样它就不会在一个空地上平白无故地乱转，而是具有一定方向性地探索。
接下来，让算法具备自动回退的能力。我们想象一个简单情景：
这个图不准确，不满足本文的优先级设定，但也足以表意
遇到这样的死胡同，假如进来的时候足迹把出去的路给封死了，那么这个点就没办法再出来了。一旦我们发现这个点陷入了绝境，哪里都不能走了，这时候我们就得让它原路返回。实迷途其未远，回到上一个路口也很简单，无非就是删掉这一段路线。方法就是把 path 列表里的最后一个元素逐一弹出列表，由于我们有 footprint 记录，所有它走过的地方都不能再走第二遍，所以只要这条错误的路没有完全退出去，退到哪一步都是四个方向都不能走的，因为附近都被它走过了。这样它就会一直退到我们期望的那个地方，也就是它误入歧途的那个路口。
测试
下面，我们让它开始循环。只要它的坐标不等于终点的坐标，我们就一直让它不断地探索。运行结束后，我们得到了一条迂回的曲线，如图（局部）。
程序成功得到了一条可以通往终点的路径，但这条路径过于冗杂，以上图为例，所有宽度不为 1 的地方都是这个点绕来绕去所导致的。因此，该路径还有待优化。
优化
我们考虑如下一种简单情况：
在这条路线中，显然 4 ~ 9 属于没有意义的兜圈，正确的路线应该是从 3 直接到 10 。
我们的优化方法是：如果 第n步 在 (x,y) ，从 第n+2步 （也就是下一步的下一步），一直到最后一步，这中间只要有一步落在 (x,y) 一步之遥的地方，就把从 第n+1步 到这一步的所有路径点都删掉。拿上面这个例子来说，我们从 第1步 开始检查。检查到 第3步 时，我们从 第5步 开始看，一直看到 第10步 发现 10 落在 3 一步就能到达的地方，这时我们把中间的 4-9 全部删掉，直接把 10 接在 3 的后面。
不过，考虑到后面可能还会有更优的情况，比如说从 12 开始继续绕，绕到 20 发现 20 刚好落在 3 的上面，那我们事实上应该直接把 20 接在 3 后面， 12 也要丢掉，之前的方法有些缺陷。因此，为了避免这种情况，我们逆着循环，对于 第3步 而言，我们从 第20步 往前循环，一直循环到 第5步 ，看是否有3能直接到达的地方。这样我们就能对这条路线进行最大优化了。
绘制路径
最终，我们得到了正确而简洁的路径，也记录了曾经走过的错路和多走的路。
根据矩阵和图片的对应关系，我们把图片里对应的像素改变颜色，其它点不作更改。
绘制路径：
优化之前：
全部足迹：
结语
至此，我们已经把这个问题解决得差不多了。整个程序在我的电脑上运行下来大概需要三五分钟这个样子，毕竟是只用 for循环 的暴力方法。
查看更多关于Python实现迷宫自动寻路实例的详细内容...