关于H值
H值是从当前方块到终点的移动量估算值（在本游戏中是指方块的数目）。 移动量估算值离真实值越接近，最终的路径会更加精确。如果估算值停止作用，很可能生成出来的路径不会是最短的（但是它可能是接近的）。这个题目相对复杂，所以我们不会再本教程中讲解，但是我在教程的末尾提供了一个网络链接，对它做了很好的解释。
为了让它更简单，我们将使用“曼哈顿距离方法”（也叫“曼哈顿长”或者“城市街区距离”），它只是计算出距离点B，剩下的水平和垂直的方块数量，略去了障碍物或者不同陆地类型的数量。
例如，下图展示了使用“城市街区距离”，从不同的开始点到终点，去估算H的值（黑色字）：
A星算法
既然你知道如何计算每个方块的和值（我们将它称为F，等于G+H), 我们来看下A星算法的原理。
猫会重复以下步骤来找到最短路径：
? 将方块添加到open列表中，该列表有最小的和值。且将这个方块称为S吧。
? 将S从open列表移除，然后添加S到closed列表中。 ? 对于与S相邻的每一块可通行的方块T： ? 如果T在closed列表中：不管它。
? 如果T不在open列表中：添加它然后计算出它的和值。
? 如果T已经在open列表中：当我们使用当前生成的路径到达那里时，检查F 和值是否更小。如果是，更新它的和值和它的前继。
如果你对它的工作原理还有点疑惑，不用担心 – 我们会用例子一步步介绍它的原理！:]
猫的路径
让我们看下我们的懒猫到达骨头的行程例子。
在下图中，我根据以下内容，列出了公式F = G + H 中的每项值： ? F（方块的和值）：左上角 ? G（从A点到方块的移动量）：左下角 ? H（从方块到B点的估算移动量): 右下角 同时，箭头指示了到达相应方块的移动方向。
最后，在每一步中，红色方块表示closed列表，绿色方块表示open列表。 好的，我们开始吧！ 第一步
第一步，猫会确定相对于开始位置（点A）的相邻方块，计算出他们的F和值，然后把他们添加到open列表中：
你会看到每个方块都列出了H值（有两个是6，一个是4）。我建议根据“城市街区距离”去计算方块的相关值，确保你理解了它的原理。
同时注意F值（在左上角）是G（左下角）值和H（右下脚）值的和。 第二步
在第二步中，猫选择了F和值最小的方块，把它添加到closed列表中，然后检索它的相邻方块的相关数值。
现在你将看到拥有最小增量的是F值为4的方块。猫尝试添加所有相邻的方块到open列表中（然后计算他们的和值），除了猫自身的方块不能添加以外（因为它已经被添加到了closed列表中）或者它是墙壁方块（因为它不能通行）。 注意被添加到open列表的两个新方块，他们的G值都增加了1，因为他们现在离开始点有2个方块远了。你也许需要再计算下“城市街区距离”以确保你理解了每个新方块的H值。 第三步
再次，我们选择了有最小F和值（5）的方块，继续重复之前的步骤：
现在，只有一个可能的方块被添加到open列表中了，因为已经有一个相邻的方块在close列表中，其他两个是墙壁方块。
第四步
现在我们遇到了一个有趣的情况。正如你之前看到的，有4个方块的F和值都为7 – 我们要怎么做呢？！
有几种解决方法可以使用，但是最简单（快速）的方法是一直跟着最近被添加到open列表中的方块。现在继续沿着最近被添加的方块前进。