Python实现迷宫自动寻路实例
作者:程序媛小本 发布时间:2021-12-22 10:00:44
背景
我打开手机,发现有人在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能直接到达的地方。这样我们就能对这条路线进行最大优化了。
绘制路径
最终,我们得到了正确而简洁的路径,也记录了曾经走过的错路和多走的路。
根据矩阵和图片的对应关系,我们把图片里对应的像素改变颜色,其它点不作更改。
绘制路径:
优化之前:
全部足迹:
来源:https://blog.csdn.net/m0_59236127/article/details/122804899
猜你喜欢
- 一般网站发布信息会在具体实现范围内发布,我们在进行网络爬虫的过程中,可以通过设置定时爬虫,定时的爬取网站的内容。使用python爬虫框架Sc
- 在Python中,任何类型的对象都可以做真值测试,并且保证返回True或者False。以下几种值(不论类型)在真值测试中返回False:1.
- 很多时候,希望能够在 HTML 中使用空格排版。但浏览器在解析 HTML 时,会把连续的空格解析成一个,所以我们会使用
- 今天有个学生问我:页面中使用GIF格式,失真太大,怎么办呢?这个问题比较简单啊,只要用JPG就可以了。我们常用的页面的图片格式有三种,GIF
- 今天在群里,熊猫君提议整理一个帖子,一方面为初学者提供一个入门指南,另一方面也象借此和已经在从事这个行业进行一点交流。下面是我从事这个行当多
- 本文文章主要介绍了Python内置函数—vars的具体使用方法,分享给大家,具体如下:英文文档:vars([object])Return t
- 如何在服务器端调用winzip命令行对上传的多个文件打包压缩?要解决这个问题,首先要了解一下Windows Scripting Host,简
- OpenCV的全称是:Open Source Computer Vision Library。OpenCV是一个基于(开源)发行的跨平台计算
- 一、Pandas Series对象Pandas 是基于 NumPy 设计实现的 Python 数据分析库,Pandas 提供了大量的能让我们
- Pygame是跨平台Python模块,专为电子游戏设计,包含图像、声音。建立在SDL基础上,允许实时电子游戏研发而无需被低级语言(如机器语言
- Python socket网络编程初学 python,前段时间买了两本书《python 编程从入门到实践》《Python 核心编程第三版》,
- 前言:内容提要:本文比较了 Python 中用于列表排序的两种函数 sort() 和 sorted(),帮助您选择合适的排序函数。对列表排序
- 本文实例讲述了Python快速排序算法。分享给大家供大家参考,具体如下:快速排序的时间复杂度是O(NlogN)算法描述:① 先从序列中取出一
- python随机数种子seed()栗子1import numpy as npimport randomrandom.seed(0)np.ra
- 目前绝大多数手机都支持WAP 2.0。WAP 2.0的页面设计具有更好的视觉效果,更接近网页。不过由于手机千差万别,手机浏览器的能力也各不相
- <script language="javascript"> functio
- SQL Server数据库的六个实用技巧:(一)挂起操作在安装Sql或sp补丁的时候系统提示之前有挂起的安装操作,要求重启,这里往往重启无用
- 索引是提高数据查询最有效的方法,也是最难全面掌握的技术,因为正确的索引可能使效率提高10000倍,而无效的索引可能是浪费了数据库空间,甚至大
- 相关文章推荐:各种loading加载图标下载 gif格式loadinfo和ajaxload一样,也是一个在线Ajax载入动画生成工
- 今天开始学习Python时发现Pycharm竟然过期了需要重新注册,穷苦学生没钱只能再找找百度了浪费了半天时间终于找到一个可以使用的了,支持