寻路A*算法

先描述A*算法的大致过程：

  1. 将初始节点放入到open列表中。
  2. 判断open列表。如果为空，则搜索失败。如果open列表中存在目标节点，则搜索成功。
  3. 从open列表中取出F值最小的节点作为当前节点，并将其加入到close列表中。
  4. 计算当前节点的相邻的所有可到达节点，生成一组子节点。对于每一个子节点：
    • 如果该节点在close列表中，则丢弃它
    • 如果该节点在open列表中，则检查其通过当前节点计算得到的F值是否更小，如果更小则更新其F值，并将其父节点设置为当前节点。
    • 如果该节点不在open列表中，则将其加入到open列表，并计算F值，设置其父节点为当前节点。
  5. 转到2步骤

初始节点，目标节点，分别表示路径的起点和终点，相当于上图的绿色节点和红色节点
F值，就是前面提到的启发式，每个节点都会被绑定一个F值
F值是一个估计值，用F(n) = G(n) + H(n) 表示，其中G(n)表示由起点到节点n的预估消耗，H(n)表示节点n到终点的估计消耗。H(n)的计算方式有很多种，比如曼哈顿H(n) = x + y，或者欧几里得式H(n) = sqrt(x^2 + y^2)。本例中采用曼哈顿式。
F(n)就表示由起点经过n节点到达终点的总消耗
为了便于描述，本文在每个方格的左下角标注数字表示G(n)，右下角数字表示H(n)，左上方数字表示F(n)。具体如何计算请看下面的一个例子

接下来，我们严格按照A*算法找出从绿色节点到红色节点的最佳路径
首先将绿色节点加入到open列表中
接着判断open列表不为空（有起始节点），红色节点不在open列表中
然后从open列表中取出F值最小的节点，此时，open列表中只有绿色节点，所以将绿色节点取出，作为当前节点，并将其加入到close列表中
计算绿色节点的相邻节点（暂不考虑斜方向移动），如下图所示的所有灰色节点，并计算它们的F值。这些子节点既没有在open列表中，也没有在close列表中，所以都加入到open列表中，并设置它们的父节点为绿色节点

寻路算法关键点：1.两个队列，openList和closeList，openlist用于存放接下来可能会去的点的位置，closeList用于存放已经去过的点。
2.三个值，H值 ,当前点到起点消耗值，G值，当前点到重点的消耗值，F值，H值和G值之和。
3.在所有的openlist中找到F值最小的点，然后以该点为下一步行进点，在继续查找该行进点的上下左右符合要求的点。重复操 作。结束条件，当openlist为空，没有找到终点，则不存在可以到达的路线，当行进点为终点时，则找到了最小路径。