A星算法

算法分析

Node的属性 gCost 利用currentNode来来计算从起点到currentNode再到neighbourNode的距离=gCost hCost 网格到targetNode的距离 fCost fCost = gCost + hCost parent neighbourNode的parent就是使其gCost最短的NodeneighbourNode不在openlist中，则parent = currentNode

---

openList 可查找的序列，用来遍历最小的fCost的序列数组每次查找neighbourNode时，都会把不在openList中的neighbourNode添加进去

---

closeList

选择最大的fCost的Node作为currentNode，并把currentNode从openList从openlist移除，并放入closeList中

findPath过程

1.startTarget加入openlist,遍历openlist中fCost最小的Node作为currentNode（此时只有startNode） 2.将currentNode从openList中移除,并加入closeList 3.遍历出currentNode的neighbourNode,并计算neighbourNode的gCost和hCost，若gCost变小，则parent为currentNode，如果neighbourNode不在openList中，则将neighbourNode加入到openlist中，并且parent为currentNode。 4.查找openlist中fCost最小的Node，循环到步骤1重新开始 直到将targetNode添加入openList中，遍历结束。

路径:

targetNode targetNode.parent targetNode.parent.parent ... startNode

距离计算

dis = 14y + 10( x - y )其中x,y为Node的下标

总结

每个Node的parent都是从startNode到parent再到Node的距离最短每个current都是fCost最小，有同样的parent的Node到targetNode的距离也最短可以理解为每个Node到起点的距离最短，到终点的距离也最短，故总的距离最短