A*的总结

   一直就很想把A*看一下，虽然所早的项目一直没用上A*，但是对它还是情有独钟，

可能是打心底的对寻路比较有好奇感把。原本网上关于A*的解释说明的文章数不胜数，

但是我还是想把自己所理解的写在自己的博客上，方便日后的回顾，

当然还是从各位大牛那一点点的积累下来的。

一、A*算法总结：

1.
将开始节点放入开放列表(开始节点的F和G值都视为0);
2.
重复一下步骤:
    i.
    在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;
    ii.
    把当前节点从开放列表删除, 加入到封闭列表;
    iii.
    对当前节点相邻的每一个节点依次执行以下步骤:
      (a.
      如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
      (b.
      如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节       点,同时保存该相邻节点的G和F值;
      (c.
      如果该相邻节点在开放列表中, 则判断若经由当前节点到达该相邻节点的G值是否小于原来保存             的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
    iv.
    循环结束条件:
    当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环;
    或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找     到,此时也结束循环;
3.
从终点节点开始沿父节点遍历, 并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;

 二、路径排序

 

决定哪些方格会形成路径的关键是下面这个等式：
F = G + H
这里

·G＝从起点A沿着已生成的路径到一个给定方格的移动开销。

·H＝从给定方格到目的方格的估计移动开销。这种方式常叫做试探，有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离，因为任何东西都有可能出现在半路上（墙啊，水啊什么的）。本文中给出了一种计算H值的方法，网上还有很多其他文章介绍的不同方法。

我们要的路径是通过反复遍历开放列表并选择具有最小F值的方格来生成的。

 

 

   三、功能拓广

   1.

    使用二叉堆优化开放列表，缩短检索的时间，因为它是最耗时的；

   2.

    A*的最小路径问题；

   3.

    对于不同大小的人物角色的寻路技巧；

   4.

    与Djikstra算法的对比；

（这部分下次有空的时候好好的补上.）

  四、优缺点

   网上有很多。

先去睡觉了，下次再分享一个大牛的代码，我先整理下。