A*算法的思想:注意,以下标为粗体的字表示A*算法中的变量或者不变量.

① 在一张大网格上面,也可以是一张画布上面,这个比较抽象,以下以网格为主,有2个点,称为最初起始点,最终目标点.有一些障碍物阻隔.(具体复杂的A*算法涉及到各种3D世界的2点之间的最短距离,最短距离是否可达等等判断,非常复杂,以下讲解比较简单的A*算法.)

②制作网格地图,A*寻路主要是在地图上面寻找2个点之间的最短距离.将最初起始点,最终目标点,障碍物拟化成为一个个网格上的小点,这样,就屏蔽了细节,计算就变得简单内敛许多.障碍物数据(数组记录),整个网格的数据(二维数组记录),将每一个点作为节点记录数据.需要在网格类里面写一个当前节点上下左右的相邻节点的计算方法,将相邻节点返回出来,供以后计算.

③计算最初起始点,和最终目标点的位置,当前起始点的初始成本为0,估算总成本为从最初起始点到最终目标点的直线距离(ps:非常复杂的情况下,不能将最短直线距离作为判断依据,但是大多数场景下是可以的,可以多加判断依据,分段判断依据等).

此时既可以做一个节点类,将最初起始点和最终目标点都作为一个节点使用.这个类包含初始成本(ps:表示从一个节点到相邻的节点必须消耗的成本),估算总成本(ps:表示这个节点到最终目标点需要消耗的成本),这个节点是否为障碍物,这个节点的父节点是谁(ps:链表的数据结构逻辑,最初起始点没有父节点,没一个节点的子节点有很多,子节点也就是相邻节点,但是父节点只有一个),当前节点的位置.

最重要的思想即是:当前节点位置估算成本加上中间的一个节点位置估算成本,再加上中间的一个节点位置到最终目标点位置的估算成本,相比于另外几条路径的估算成本是最低的.

④当节点类完成之后,需要 优先级队列 存储节点.这个优先级队列最主要的是做2个节点之间的估算总成本计算.每当这个优先级队列添加,移除时做节点的估算成本比较,将最小估算成本的节点放在优先级队列的第一个位置.如果节点是障碍物,则不加入优先级队列计算.这个类使用任何数据结构都可以达到效果.

⑤A*算法实现:

A方法,一个2点之间最短距离的计算方法.

B方法:计算一个最终节点循环指向父节点的链表数据,返回一个数组,包含了最短路径的节点

C方法:寻找2点之间的算法逻辑

    第一步:初始化2个优先级队列用来记录计算过成本的节点TQ, 记录没有计算过成本的节点YQ.将最初起始点加入没有计算过成本的队列中.

    第二步:从没有计算过成本的节点中弹出第一元素,记住这个元素在所有的节点中是估算成本最低的那一个节点,前面有讲过.

                 这个第一元素记录为 current 节点.

    第三步: current节点和最终目标点的位置相同,则返回计算路径(B方法).

    第四步:得到 current节点的上下左右节点 Adjacent数组,如果是障碍物,则不会出现在数组中,此时调用的是网格的方法.

    第五步:进入循环遍历Adjacent数组中的节点,如果TQ队列和YQ队列里面包含了数组中的节点,则使用continue 继续下一次循环,

                   将数组中的节点的父节点指向为当前current节点,计算数组中的节点的成本,

                    节点的估算成本 = 父节点的初始成本+从父节点到此节点的绝对成本 + 计算此节点距离最终目标点的估算成本 ,

                    将这些节点加入YQ队列中.直到结束循环.

    第六步:将current节点加入TQ队列中,将current节点从YQ队列中移除.

    第七步:当YQ队列的count大于0时,则返回第二步进行循环,直到第三步返回计算的最短路径.

    第八步:如果障碍物包裹住了最终目标点,则node永远达不到,返回null;

    ps:在第五步中  计算此节点距离最终目标点的估算成本 此步表示出了最短路径思想,我是按照2点之间最短来计算,

            如果此规则不适应于你当前的寻路规则,需要自己修改规则.

最后的最后,如果不给代码,只给思路,纯属耍流氓行为.以下为代码地址:

https://pan.baidu.com/s/10qvXFKE7rnnqdEjlvQpDCQ 密码：0n9s

https://github.com/BingJin-Zheng/A-pathfinding-algorithm