学更好的别人,
做更好的自己。
——《微卡智享》
本文长度为1809字,预计阅读5分钟
前言
上一篇《实战|OpenCV结合A*算法实现简单的运动路径规划》我们实现了运动路径的规划功能,在上次的图片中效果还不错,因为本身就是想做通用的寻路,所以就又换了几张图片看了看,结果在比较复杂的路径上看,计算的时间就有点太长了,所以这篇专门研究下自己实现的代码里面有没有可优化的地方。
耗时问题
微卡智享
上图中可以看出来,我们换了一个商场的平面图,从起点到终点计算用时要2分多钟,为了看看不是一直这样,我做了五次测试,上图中后框里面的时间都是155秒,145秒,142秒,146秒,177秒,五次平均下来也要2分多,简直是不能忍,所以我们就研究下写A*算法时看看有没有可优化的地方了。
在A*算法中,有两个列表,一个OpenList(开启列表),一个CloseList(关闭列表),在计算的过程中,我们统计一下处理这两个列表的次数:
在代码中我们用了isInList函数来查找点是否存在
上面的耗时步骤中,步骤2(用了1次),步骤3(用了8次),步骤4(用了最多8次,因为返回的点不一定在计算内了),按最大次数算的话就是
1+8+8=17次
01
初步优化
从上面的遍历代码中我们可以看到,当遇到相同的点后,就会跳出,因为for(auto p:list)的方式都是从第一条开始的,整个流程上看,我们在OpenList和CloseList列表中越新插入的点都是离终点越近的点,所以如果通过for语句从后往前去的话,应该跳出过程的时间要少很多,所以可以有两个思路优化一下:
从上面两个方式来看,不用说还是第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的跳点寻路算法。
完