A*算法结合区域分割搜索路径
用于weNavi的一个内置寻路算法,由于需要保证实时性,由于节点较多单纯的A*算法不能保证效率,所以做了如下优化
优化:在其中我把地图的像素点进行聚类,将同一区域内的点看做是一个chunk,来进行更大粒度的搜索
A算法核心回顾: A是一种启发式算法,BFS和Dijkstra都可以看做是A*算法的简化形式,这俩个算法在我其他的目录里也有实现。
A关键在于f(n) = g(n) + h(n)这公式中的启发函数h(n). 启发函数可以看做是一个指导老师,每次在搜寻下一个节点时来指导哪些 节点该被搜寻。典型的启发函数算法有曼哈顿距离(这份实现就是用的这个),切比雪夫距离等等。总体来说A算法应该是最好的寻路 思路了