A星寻路算法
这几天实现了一个A*寻路算法，其实在刚毕业的时候就写了一个，算法不复杂，就是效率有点儿低，这些天趁着空闲时间，重新实现了一遍。
算法其实也不复杂，首先有以下几个概念：
开启的节点表(OpenTable)
存放着所有的待检测的节点（坐标），每次都会从其中寻找出符合某个条件的坐标。
关闭的节点表(ClosedTable)
存放着所有不会被检测的节点（坐标），每次检测都会忽略它们。
首先，我们定义了两个坐标(sx,sy) (dx,dy) ，分别是起点和终点。
整个算法的核心就是启发式的权值比较，分为G和H值。
G值
是从起点到某一点积累的移动值。一般我们将从起点按非斜向方向移动的G值定为10，斜向为14，走一步必须将此节点的值增加，也就是说移动到的节点的G值等于移动前节点的G值加上按方向走到该店的G值的增加量。
打个比方，移动前(0,0)的G值为0，则(0,1)的G值就是10，(1,2)的G值就是24
H值
该值和终点坐标相关，一般常用的曼哈顿算法为: abs(dx-x)+abs(dy-y)，也就是横坐标的差值加上纵坐标的差值。
F值
F值为G值和H值之和
上述的基本概念理清的话，下面的算法就简单了。
算法的基本逻辑基本按下述步骤走：
1.将起点放入OpenTable中
2.将OpenTable中最小F值的节点(MinFNode)取出，并放入ClosedTable中
3.遍历MinFNode周围的节点，忽略障碍节点和已在ClosedTable中的节点，这里会有3种情况
不在OpenTable中的，简单的计算好H值和G值（MinFNode的G值加上移动所产生的G值），并且把该节点的父节点设置为MinFNode (后期找到终点后，需要用父节点进行路径回溯)
已在OpenTable中的，则判断从MinFNode节点的G值加上移动所产生的G值之和，是否小于原先该节点的G值，假设小于了，则更新该节点的G值为较小的那个，然后重新设置该节点的父节点为MinFNode
假设遍历到的节点是终点，则按MinFNode的父节点进行回溯，获取到起点的路径，进行一次reverse，就是最终路径，然后路径就找到了
4.没有找到终点，继续回到第二部，继续执行
其实整个逻辑很简单，但是效率也很重要。以前我用了链表的排序，每次排序出最小F值的节点，效率太差。后来这次改用最小堆来实现，效率高了不少。
我的A*寻路算法模块：github
作者
