实战|A*寻路算法遇到的问题及解决方法
学更好的别人,
做更好的自己。
——《微卡智享》
本文长度为1809字,预计阅读5分钟
前言
上一篇《实战|OpenCV结合A*算法实现简单的运动路径规划》我们实现了运动路径的规划功能,在上次的图片中效果还不错,因为本身就是想做通用的寻路,所以就又换了几张图片看了看,结果在比较复杂的路径上看,计算的时间就有点太长了,所以这篇专门研究下自己实现的代码里面有没有可优化的地方。
耗时问题
微卡智享
上图中可以看出来,我们换了一个商场的平面图,从起点到终点计算用时要2分多钟,为了看看不是一直这样,我做了五次测试,上图中后框里面的时间都是155秒,145秒,142秒,146秒,177秒,五次平均下来也要2分多,简直是不能忍,所以我们就研究下写A*算法时看看有没有可优化的地方了。
耗时分析
在A*算法中,有两个列表,一个OpenList(开启列表),一个CloseList(关闭列表),在计算的过程中,我们统计一下处理这两个列表的次数:
- 从OpenList列表中找到离终点F值最小的点
- 找到后查看是否在关闭列表中,如果在直接跳出程序了
- 通过当前点找到邻近的8个点,然后每个点要判断是否在CloseList列表中存在,如果存在就不列入计算中
- 取出的点要进行判断是否在OpenList列表中存在,如果存在也跳过
在代码中我们用了isInList函数来查找点是否存在
上面的耗时步骤中,步骤2(用了1次),步骤3(用了8次),步骤4(用了最多8次,因为返回的点不一定在计算内了),按最大次数算的话就是
1+8+8=17次
01
初步优化
从上面的遍历代码中我们可以看到,当遇到相同的点后,就会跳出,因为for(auto p:list)的方式都是从第一条开始的,整个流程上看,我们在OpenList和CloseList列表中越新插入的点都是离终点越近的点,所以如果通过for语句从后往前去的话,应该跳出过程的时间要少很多,所以可以有两个思路优化一下:
- 查询前将传入的List重新从后往前排序
- 不改变LIst排序,每次插入的时候都是从第一条插入
从上面两个方式来看,不用说还是第2条比较好,因为第一条重新排序还是要花费时间的,如果在起初把插入的地方改一下,这里就不用做变化了,不费话,我们直接找插入两个List的代码
找到相关的List,把原来的push_back(),全部改为push_front();
运行效果
还是运行了5次,明显可以看到平均时长80几秒,比原来的速度要快了一分多钟了,我们再研究下看看怎么优化。
02
检测跳出优化
上面的步骤2中,我们取出的离终点最近的F点中要检测在关闭列表中是否存在,因为在循环中,每次都检测,我觉得这一步可以直接不用检测了,取出的点直接在OpenList中删除,加入到CloseLIst中即可。
修改为
优化效果
再运行了5次我们看到,平均60几秒,比上次又减少了10几秒钟。
03
获取F最小的点
本来想从最小F点那个函数中研究研究,看看怎么简化,原来考虑到设置一个F的阈值,距离近了后就更新这个阈值后不再检测了,不过像我们刚才这个路线,因为有些地方是过不去的,肯定需要绕路,这样的话这个方法就不合适,简单测试了一下确实也是如此,所以这块暂时先不动了,不过在测试的过程中正好也发现了一个小BUG,就是判断地图点是不是有问题时没加入超出的判断,会报错,这里也修改一下
//判断是否是障碍点bool AStarCalc::isInSites(const Point* point) const{ if (point->x < 0 || point->y < 0 || point->x >= sites.size() || point->y >= sites[0].size()) return true; return sites[point->x][point->y] == 1;}
总结
从上面的代码中我们做的优化可以看出,整体上已经减少了接近1分半的时间,所以说在做开发的过程中,首先去实现,然后需要不断地去打磨,细节的找到问题去解决问题是很关键的。
啰嗦了这么多其实就是说明了一个事,就是A*算法在这个复杂点的地图中做路径规划是无法在生产环境中使用的,即使我们去做了些细节的优化,但还是需要一分钟才出来,这个的用户体验我觉得就是0,不过做为学习路径规划上还是不错的,通过A*的算法也算是入了个门,后面会延伸出JPS的跳点寻路算法。
完
推荐阅读
-
了解YUV和RGB的不同之处及其对YUV444、YUV422、YUV411和YUV420的介绍
-
踞觑yuv422、yuv420和yuv444间的差异
-
每周总结20130814——Android NDK环境的搭建和使用,YUV420SP格式图像的处理
-
二、代码实现YUV420图像的水平拼接
-
重新表达该标题:编码格式YUV420的解释
-
转换NV12为YUV420格式的百转工具
-
研究针对 YUV420 颜色空间的深度图像压缩
-
解密Android Bitmap转I420的难题,附图文详解YUV420数据格式
-
互相转换的BGRA、RGBA和YUV420
-
如何实现neon优化的yuv420转rgb24汇编代码,iOS/Android可用的具体操作步骤