A星算法

算法分析

• Node的属性
  • gCost

  • 利用currentNode来来计算
  • 从起点到currentNode再到neighbourNode的距离=gCost

  • hCost

  • 网格到targetNode的距离

  • fCost

  • fCost = gCost + hCost

  • parent

  • neighbourNode的parent就是使其gCost最短的Node
  • neighbourNode不在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中，遍历结束。

  路径:

• 距离计算
  

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

• 总结

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