前言
a*搜寻算法俗称a星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中
通过二维数组构建的一个迷宫，“%”表示墙壁，a为起点，b为终点，“#”代表障碍物，“*”代表算法计算后的路径
本文实例代码结构：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % ============================= 经过a*算法计算后 ============================= % % % % % % % % o o * o o % % o * # * o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % < |
算法理论
算法的核心公式为：f=g+h
把地图上的节点看成一个网格。
g=从起点a,沿着产生的路径，移动到网格上指定节点的移动消耗，在这个例子里，我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。我们取这些值是因为沿对角线
的距离是沿水平或垂直移动耗费的的根号2，或者约1.414倍。为了简化，我们用10和14近似。
既然我们在计算沿特定路径通往某个方格的g值，求值的方法就是取它父节点的g值，然后依照它相对父节点是对角线方向或者直角方向(非对角线)，分别增加14和10。例子中这
个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。
h=从当前格移动到终点b的预估移动消耗。为什么叫”预估“呢，因为我们没有办法事先知道路径的长度，这里我们使用曼哈顿方法，它计算从当前格到目的格之间水平和垂直
的方格的数量总和，忽略对角线方向。然后把结果乘以10。
f的值是g和h的和，这是我们用来判断优先路径的标准，f值最小的格，我们认为是优先的路径节点。
实现步骤
算法使用java写的，先看一看节点类的内容
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
package a_star_search; /** * 节点类 * @author zx * */public class node { private int x; //x坐标 private int y; //y坐标 private string value; //表示节点的值 private double fvalue = 0; //f值 private double gvalue = 0; //g值 private double hvalue = 0; //h值 private boolean reachable; //是否可到达（是否为障碍物） private node pnode; //父节点 public node(int x, int y, string value, boolean reachable) { super(); this.x = x; this.y = y; this.value = value; reachable = reachable; } public node() { super(); } public int getx() { return x; } public void setx(int x) { this.x = x; } public int gety() { return y; } public void sety(int y) { this.y = y; } public string getvalue() { return value; } public void setvalue(string value) { this.value = value; } public double getfvalue() { return fvalue; } public void setfvalue(double fvalue) { fvalue = fvalue; } public double getgvalue() { return gvalue; } public void setgvalue(double gvalue) { gvalue = gvalue; } public double gethvalue() { return hvalue; } public void sethvalue(double hvalue) { hvalue = hvalue; } public boolean isreachable() { return reachable; } public void setreachable(boolean reachable) { reachable = reachable; } public node getpnode() { return pnode; } public void setpnode(node pnode) { pnode = pnode; } } |
还需要一个地图类，在map的构造方法中，我通过创建节点的二维数组来实现一个迷宫地图，其中包括起点和终点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
package a_star_search;public class map { private node[][] map; //节点数组 private node startnode; //起点 private node endnode; //终点 public map() { map = new node[7][7]; for (int i = 0;i<7;i++){ for (int j = 0;j<7;j++){ map[i][j] = new node(i,j,"o",true); } } for (int d = 0;d<7;d++){ map[0][d].setvalue("%"); map[0][d].setreachable(false); map[d][0].setvalue("%"); map[d][0].setreachable(false); map[6][d].setvalue("%"); map[6][d].setreachable(false); map[d][6].setvalue("%"); map[d][6].setreachable(false); } map[3][1].setvalue("a"); startnode = map[3][1]; map[3][5].setvalue("b"); endnode = map[3][5]; for (int k = 1;k<=3;k++){ map[k+1][3].setvalue("#"); map[k+1][3].setreachable(false); } } <span style="white-space:pre"> </span>//展示地图 public void showmap(){ for (int i = 0;i<7;i++){ for (int j = 0;j<7;j++){ system.out.print(map[i][j].getvalue()+" "); } system.out.println(""); } } public node[][] getmap() { return map; } public void setmap(node[][] map) { this.map = map; } public node getstartnode() { return startnode; } public void setstartnode(node startnode) { this.startnode = startnode; } public node getendnode() { return endnode; } public void setendnode(node endnode) { this.endnode = endnode; }} |
下面是最重要的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值，顺藤摸瓜即可以显示出路径。
看看代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
package a_star_search;import java.util.arraylist;public class astar { /** * 使用arraylist数组作为“开启列表”和“关闭列表” */ arraylist<node> open = new arraylist<node>(); arraylist<node> close = new arraylist<node>(); /** * 获取h值 * @param currentnode：当前节点 * @param endnode：终点 * @return */ public double gethvalue(node currentnode,node endnode){ return (math.abs(currentnode.getx() - endnode.getx()) + math.abs(currentnode.gety() - endnode.gety()))*10; } /** * 获取g值 * @param currentnode：当前节点 * @return */ public double getgvalue(node currentnode){ if(currentnode.getpnode()!=null){ if(currentnode.getx()==currentnode.getpnode().getx()||currentnode.gety()==currentnode.getpnode().gety()){ //判断当前节点与其父节点之间的位置关系（水平？对角线） return currentnode.getgvalue()+10; } return currentnode.getgvalue()+14; } return currentnode.getgvalue(); } /** * 获取f值 ： g + h * @param currentnode * @return */ public double getfvalue(node currentnode){ return currentnode.getgvalue()+currentnode.gethvalue(); } /** * 将选中节点周围的节点添加进“开启列表” * @param node * @param map */ public void inopen(node node,map map){ int x = node.getx(); int y = node.gety(); for (int i = 0;i<3;i++){ for (int j = 0;j<3;j++){ //判断条件为：节点为可到达的（即不是障碍物，不在关闭列表中），开启列表中不包含，不是选中节点 if(map.getmap()[x-1+i][y-1+j].isreachable()&&!open.contains(map.getmap()[x-1+i][y-1+j])&&!(x==(x-1+i)&&y==(y-1+j))){ map.getmap()[x-1+i][y-1+j].setpnode(map.getmap()[x][y]); //将选中节点作为父节点 map.getmap()[x-1+i][y-1+j].setgvalue(getgvalue(map.getmap()[x-1+i][y-1+j])); map.getmap()[x-1+i][y-1+j].sethvalue(gethvalue(map.getmap()[x-1+i][y-1+j],map.getendnode())); map.getmap()[x-1+i][y-1+j].setfvalue(getfvalue(map.getmap()[x-1+i][y-1+j])); open.add(map.getmap()[x-1+i][y-1+j]); } } } } /** * 使用冒泡排序将开启列表中的节点按f值从小到大排序 * @param arr */ public void sort(arraylist<node> arr){ for (int i = 0;i<arr.size()-1;i++){ for (int j = i+1;j<arr.size();j++){ if(arr.get(i).getfvalue() > arr.get(j).getfvalue()){ node tmp = new node(); tmp = arr.get(i); arr.set(i, arr.get(j)); arr.set(j, tmp); } } } } /** * 将节点添加进”关闭列表“ * @param node * @param open */ public void inclose(node node,arraylist<node> open){ if(open.contains(node)){ node.setreachable(false); //设置为不可达 open.remove(node); close.add(node); } } public void search(map map){ //对起点即起点周围的节点进行操作 inopen(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()],map); close.add(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()]); map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setreachable(false); map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setpnode(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()]); sort(open); //重复步骤 do{ inopen(open.get(0), map); inclose(open.get(0), open); sort(open); } while(!open.contains(map.getmap()[map.getendnode().getx()][map.getendnode().gety()])); //知道开启列表中包含终点时，循环退出 inclose(map.getmap()[map.getendnode().getx()][map.getendnode().gety()], open); showpath(close,map); } /** * 将路径标记出来 * @param arr * @param map */ public void showpath(arraylist<node> arr,map map) { if(arr.size()>0){ node node = new node(); //<span style="white-space:pre"> </span>node = map.getmap()[map.getendnode().getx()][map.getendnode().gety()]; //<span style="white-space:pre"> </span>while(!(node.getx() ==map.getstartnode().getx()&&node.gety() ==map.getstartnode().gety())){ //<span style="white-space:pre"> </span>node.getpnode().setvalue("*"); //<span style="white-space:pre"> </span>node = node.getpnode(); //<span style="white-space:pre"> </span>} } //<span style="white-space:pre"> </span>map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setvalue("a"); }} |
最后写一个main方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package a_star_search; public class maintest { public static void main(string[] args) { map map = new map(); astar astar = new astar(); map.showmap(); astar.search(map); system.out.println("============================="); system.out.println("经过a*算法计算后"); system.out.println("============================="); map.showmap(); } } |
修改地图再测试一下，看看效果
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % =============================经过a*算法计算后=============================% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % |
总结
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到
最优解。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
最大的感触就是：做事最忌三天打渔，两天晒网。量可以不大，但必须有连续性，贵在坚持。
希望每一个程序员，都能开心的敲着代码，做自己喜欢做的事。
以上就是本文关于java编程实现a*算法完整代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。
原文链接：http://blog.csdn.net/u014735301/article/details/40039595
