A star A星路径搜寻法在机器人智能车避障上的应用

两个网页版的a星算法演示 

http://qiao.github.io/PathFinding.js/visual/

http://xiexuefeng.cc/lab/369.html

算法的原理已经有好多网友解释过了。可以认为就是行动消耗和距离消耗的总和，其越小就可以认为是最佳路径。

行动消耗就是转弯的幅度大小，当然就是相对于中心点到周围八个点的行动消耗，八个点中上下左右的消耗成本要优于四个角上的。

距离成本就是所对应八个点到终点的距离，距离越短越优。

判断路径点的时候，要考虑是否有障碍物在路径上。

总结与思考

1.A*的消耗是一个及其不稳定的过程，消耗的最小值不低于直线路径上的消耗，消耗的最大值不高于遍历整张地图的消耗。

2.A*的消耗主要在搜索的搜索格子，以及对其FGH的操作上。

3.由1，2可以得出，在对运行速率和效率有要求的场景下，A*可能不是一个比较好选择。

4 A星在地图较小的时候可以使用。

5 opencv可以利用Mat 来生成栅格地图。

算法步骤

横向纵向的格子的单位消耗为10，对角单位消耗为14。

定义一个OpenList，用于存储和搜索当前最小值的格子。

定义一个CloseList，用于标记已经处理过的格子，以防止重复搜索。

开始搜索寻路

1.将起点加入OpenList

2.从OpenList中弹出F值最小的点作为当前点

3.获取当前点九空格（除去自己）内所有的非障碍且不在CloseList内的邻居点

4.遍历上一步骤得到的邻居点的集合，每个邻居点执行以下逻辑

 如果邻居点在OpenList中
    计算当前值的G与该邻居点的G值
    如果G值比该邻居点的G值小
        将当前点设置为该邻居点的父节点
        更新该邻居点的GF值
若不在
    计算并设置当前点与该邻居点的G值
    计算并设置当前点与该邻居点的H值
    计算并设置该邻居点的F值
    将当前点设置为该邻居点的父节点 

5.判断终点是否在OpenList中，如果已在OpenList中，则返回该点，其父节点连起来的路径就是A*搜索的路径。如果不在，则重复执行2，3，4，5。直到找到终点，或者OpenList中节点数量为0。

Tip：判定结束的有两种

第一种是以OpenList中有终点节点或者OpenList中没有节点

第二种是CLoseList中有终点节点或者......

第一种要比第二种运算次数要少许多，但在最短路径的的处理上，第二种要比第一种要精准，是相对精准。

源码工程

[lv]https://github.com/horo2016/Astar_ocv [/lv]