凸多边形障碍物寻路算法
根据两点之间直线最短。可以知道最短路径的拐点(拐弯的地方)一定是凸多边形障碍物的顶点。
1.那么我把所有障碍物的顶点,起点,终点 互相连接 得到的线段。就是可走路径。这里排除穿过障碍物的线段。
如上图,红色点为起点,蓝色点为终点,黑色凸多边形为障碍物。那么所有可以走的路径为 12,13,14,7,8,9,10,1,0,4,15,16… 等等 这些有限线段是所有的可走路径。
- 找到可走路径之后, 剩下的事跟A*算法一致. 开放列表中存放将要遍历的顶点,关闭列表中存放计算过的顶点,F值 = 起点到当前点的线段总长 + 该点到终点的直线距离。
如果不懂A* 算法可以看我的上一篇文章步骤都很清楚。
https://blog.csdn.net/qq_27461747/article/details/106690890
附上很久之前写的寻路。
https://tt1253.oss-cn-shenzhen.aliyuncs.com/Code/FindWay.rar
由于以前未完全理解透彻A* 导致这份源码A* 有些差异。
比如我并未计算H值(点到终点的直线距离) 我直接用G值进行排序。
这样与A* 不同的是,A*只要下一个计算的是终点,那么就意味着已经找到最短路径。
而直接用G值进行排序,就还要往下继续寻找。直到找到终点总长度G值最短的那个路径。