python走迷宫,迷宫自动寻路算法
大家好，本文主要讲Python实现迷宫自动寻路的例子。有兴趣的同学过来看看，如果对你有帮助记得收藏。
00-1010后台预处理寻路算法测试优化绘制路径结论
目录
我打开手机，发现有人在QQ空间大喊大叫。
看他洋洋得意的样子，很明显他在家呆久了，已经忘了天有多高了。
背景
设计一个迷宫自动寻路算法并不难，但对于目前的任务来说，第一个棘手的部分在于如何让迷宫看起来像计算机，也就是迷宫图片的矩阵。
这幅画的尺寸是397390。先把周围的白边剪掉，然后把这张图的每个像素二值化，再根据颜色赋值。黑色用0表示，白色用1表示，建立0/1矩阵。考虑到迷宫的边界是封闭的，为了防止一些看起来是0的地方因为画面质量问题实际上是1，进而在走迷宫的过程中造成一些可以预见的效果，比如列表的越级，我们强制四边的元素都是0。此时，迷宫的预处理已经基本完成。如果我们隐藏1并打印出所有的0，缩放后，我们将得到以下结果：
预处理
得到这个迷宫矩阵后，我们需要找到一条从左上角到右下角的路。
我有这样的印象，我曾经遇到过走迷宫的方法。那是在一次算法选修课上，老师在台上深入讲深度优先搜索和广度优先搜索，我无私的抄了大东西实验报告2。到目前为止，我提到这两个概念的时候，唯一的印象就是它们的英文缩写是D开头，b开头。
不过没关系。当年，小刀陈用20元赢了3700万。我用for loop解决这个小迷宫，没问题。
一般来说，迷宫内部是不封闭的。我总能从任何地方倒水来填满整个迷宫。因此，假设我们有一只小老鼠，把它放在起点，如果它能保证自动避障、不踩走过的路、遇死胡同回退,它总能找到终点。
因此，我们定义一个初始位置为(1，1)的点(x，y)，它是边界左上角的第一个点。
定义两个链表，一个是path，用来存储它最终确定的路径(即最终到达终点的路径)中的每个点；另一个是footprint，用来存储它走过的所有地方，包括它走过的错误的路。两个列表像[(1，1)，(1，2)，(2，2)，(m，n)]。
再定义四个动作，分别是：下一步(y=y-1)、右一步(x=x-1)、左一步(x=x-1)和上一步(y=y-1)。我们让这个点一次尝试四个动作，能放就放。走不走，取决于下一步的坐标是墙还是脚印。将新的点放入路径和足迹中，成为新的足迹。
确定四个动作的优先级，即向下、向右、向左和向上。如果可以，可以下去；下不去，右不去；不能往右，就不能往左；如果你不能向左走，你可以向上走。这样，它就不会无缘无故地在一个空旷的地方四处游荡，而是朝着某个方向探索。
接下来，让算法具备自动回滚的能力。让我们想象一个简单的场景：
这张图不准确，不符合本文的优先设置，但也表意。
遇到这样的死胡同，如果进来的时候脚印挡住了出去的路，那么这个点就不能再出来了。一旦发现这个点处于绝境，哪里都去不了，那就要让它原路返回。离迷失不远了。回到上一个路口也很简单。无非就是删了这条路线。方法是将路径列表中的最后一个元素逐个弹出列表。由于我们有足迹记录，它走过的地方都不可能走第二遍，所以只要这条错误的路没有完全退出，就不可能往四个方向退任何一步，因为附近的地方都被它走过。这样，它总会退到我们预想的地方，也就是它误入歧途的那个路口。
aodian">
测试
下面，我们让它开始循环。只要它的坐标不等于终点的坐标，我们就一直让它不断地探索。运行结束后，我们得到了一条迂回的曲线，如图（局部）。
程序成功得到了一条可以通往终点的路径，但这条路径过于冗杂，以上图为例，所有宽度不为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循环的暴力方法。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。