首页 > 未分类 > 【转贴】A-寻路算法(简明教程)
2019
11-29

【转贴】A-寻路算法(简明教程)

由于非计算机专业毕业,对于一些经典有用的算法不是很了解,最近在网上看了些关于寻路算法的,虽然没有立刻拿来所具体的项目,对于平时的一些思维还是很有用.高级的用法还需继续探索.

用A*算法寻路有个比较郁闷的问题,虽然每一步都可以选择到最优路径,但是并不是起点到终点的最优路径,特别是在有障碍物的时候,可以饶开障碍物,但也会走“冤枉路”。

我个人认为的解决方法:

1、确定障碍范围。障碍物所围成的凸多边形内的可走路径会成为“冤枉路”的陷阱。

2、障碍物所围成的凸多边形的众横向延伸范围应为低可走优先级。

下图中,橘红色的线是用A*算法做的,很明显,不是最优路径,绿色和紫色是两条最优路径,但是黑色如果都到当前的位置它应该怎么选择下一步呢?

【转贴】A-寻路算法(简明教程) - 第1张  | 逗分享开发经验

或则通过计算,如果在某路径下遇到不合理情况(代价+目标距离大于了前一步的代价+目标距离),那么退回到前一个岔口选择另一个路径,但是这样的计算会比较复杂,而且在路径长并且障碍多的时候效率会很低。

以下是在网上找到的一篇比较简要明了的文章

如果通过图像模拟搜索点,可以发现:非启发式的寻路算法实际上是一种穷举法,通过固定顺序依次搜索人物周围的路点,直到找到目的地,搜索点在图像上的表现为一个不断扩大的矩形。如下:

 【转贴】A-寻路算法(简明教程) - 第2张  | 逗分享开发经验  

 

很快人们发现如此穷举导致搜索速度过慢,而且不是很符合逻辑,试想:如果要从(0,0)点到达(100,0)点,如果每次向东搜索时能够走通,那么干吗还要搜索其他方向呢?所以,出现了启发式的A*寻路算法,一般通过 已经走过的路程 + 到达目的地的直线距离 代价值作为搜索时的启发条件,每个点建立一个代价值,每次搜索时就从代价低的最先搜索,如下:

【转贴】A-寻路算法(简明教程) - 第3张  | 逗分享开发经验

   

综上所述,以上的搜索是一种矩阵式的不断逼近终点的搜索做法。优点是比较直观,缺点在于距离越远、搜索时间越长。

最后编辑:
作者:搬运工
这个作者貌似有点懒,什么都没有留下。