A*算法，A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快，它常用于游戏中。通过二维数组构建的一个迷宫，“%”表示墙壁，A为起点，B为终点，“#”代表障碍物，“*”代表算法计算后的路径。

代码结构图如下：

小编整理了一份java学习资料，私信回复【01】，获取源码。

算法的核心公式为：F=G+H

把地图上的节点看成一个网格。

G=从起点A,沿着产生的路径，移动到网格上指定节点的移动消耗，在这个例子里，我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。我们取这些值是因为沿对角线

的距离是沿水平或垂直移动耗费的的根号2，或者约1.414倍。为了简化，我们用10和14近似。

既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它父节点的G值，然后依照它相对父节点是对角线方向或者直角方向(非对角线)，分别增加14和10。例子中这

个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。

H=从当前格移动到终点B的预估移动消耗。为什么叫”预估“呢，因为我们没有办法事先知道路径的长度，这里我们使用曼哈顿方法，它计算从当前格到目的格之间水平和垂直

的方格的数量总和，忽略对角线方向。然后把结果乘以10。

F的值是G和H的和，这是我们用来判断优先路径的标准，F值最小的格，我们认为是优先的路径节点。

实现步骤

算法使用java写的，先看一看节点类的内容

还需要一个地图类，在map的构造方法中，我通过创建节点的二维数组来实现一个迷宫地图，其中包括起点和终点

下面是最重要的AStar类

操作过程

1从起点A开始，并且把它作为待处理点存入一个“开启列表”，这是一个待检查方格的列表。

2寻找起点周围所有可到达或者可通过的方格，跳过无法通过的方格。也把他们加入开启列表。为所有这些方格保存点A作为“父方格”。当我们想描述路径的时候，父方格的资

料是十分重要的。后面会解释它的具体用途。

3从开启列表中删除起点A，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。

经过以上步骤，“开启列表”中包含了起点A周围除了障碍物的所有节点。他们的父节点都是A,通过前面讲的F=G+H的公式，计算每个节点的G，H，F值，并按照F的值大小，从小

到大进行排序。并对F值最小的那个节点做以下操作

4，把它从开启列表中删除，然后添加到关闭列表中。

5，检查所有相邻格子。跳过那些不可通过的(1.在”关闭列表“中，2.障碍物)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。

6，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不

做。（这里，我的代码中并没有判断）

7，我们重复这个过程，直到目标格（终点“B”）被添加进“开启列表”，说明终点B已经在上一个添加进“关闭列表”的节点的周围，只需走一步，即可到达终点B。

8，我们将终点B添加到“关闭列表”

9，最后一步，我们要将从起点A到终点B的路径表示出来。父节点的作用就显示出来了，通过“关闭列表”中的终点节点的父节点，改变其value值，顺藤摸瓜即可以显示出路径。

看看代码

最后写一个Main方法

修改地图再测试一下，看看效果

总结

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到

最优解。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

声明：本文内容来源于网络，如有侵权请联系删除