本文最后编辑于 前，其中的内容可能需要更新。
A*寻路算法
关于A算法网上优秀的文章有很多，本篇只是参考了那些文章，我自己实现了A算法后，对A的个人理解，在此记录下A的实现过程，同时防止时间久了自己忘了，随时可以回来看。如有不对的地方，欢迎评论指正。
A启发式搜索，什么是启发式？就是给搜索的时候有一个参考，大致的方向，让搜索的时候有一定的方向性的去寻找，这样相比广度遍历要少一些搜索范围。那么A是如何做到启发式搜索，在我看来就是那个公式F = G + H。 G：当前点到起始点路径上的消耗，H：当前点到终点的距离。通过公式可以看出F是受到G和H的影响的，可以说F越小所得到的路径就越小，所以按照F的大小顺序来进行遍历，即可获得达到终点的最短路径。下面先上代码，具体详细实现步骤和思路在代码后面。
MapItem.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
| public class MapItem{
private int Pre_x;
private int Pre_y;
private int G;
private int H;
private int F;
public MapItem() {
Pre_x = 0;
Pre_y = 0;
G = 0;
H = 0;
F = 0;
}
public int getPre_x() {
return Pre_x;
}
public void setPre_x(int pre_x) {
Pre_x = pre_x;
}
public int getPre_y() {
return Pre_y;
}
public void setPre_y(int pre_y) {
Pre_y = pre_y;
}
public int getG() {
return G;
}
public void setG(int g) {
G = g;
}
public int getH() {
return H;
}
public void setH(int h) {
H = h;
}
public int getF() {
return F;
}
public void setF(int f) {
F = f;
}
}
|
这个只是记录每个格子的F值，G值，H值，前一个格子坐标用的，至于为什么记录前一个格子坐标，原因很简单，就是为了找到路径后，按照坐标回溯从而将路线展现出来。
Main.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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
| import java.awt.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
public class Main {
private static final int STARTPOINT= 1;
private static final int ENDPOINT = 2;
private static final int WALLPOINT = 3;
private static final int WAY_POINT = 4;
private static final int WIDTH = 10;
private static final int HEIGHT = 10;
private static List<Point> openlist = new ArrayList<>();
private static List<Point> closelist = new ArrayList<>();
private static int map[][] = new int[HEIGHT][WIDTH];
private static MapItem[][] items = new MapItem[HEIGHT][WIDTH];
private static int tempx[] = {0,1,1,1,0,-1,-1,-1};
private static int tempy[] = {1,1,0,-1,-1,-1,0,1};
private static Point startPoint = new Point(2,3);
private static Point endPoint = new Point(8,3);
public static void main(String[] args){
init();
Astar();
printmap(map);
}
private static void printmap(int map[][]){
for(int i = 0;i < HEIGHT;i++){
for (int j = 0;j < WIDTH;j++){
switch (map[i][j]){
case STARTPOINT:
System.out.print(" S ");
break;
case ENDPOINT:
System.out.print(" E ");
break;
case WALLPOINT:
System.out.print(" # ");
break;
case WAY_POINT:
System.out.print(" * ");
break;
default:
System.out.print(" ");
break;
}
}
System.out.println();
}
}
private static void init(){
for(int i = 0;i < HEIGHT;i++){
for(int j = 0;j < WIDTH;j++){
items[i][j] = new MapItem();
}
}
map[startPoint.y][startPoint.x] = STARTPOINT;
items[startPoint.y][startPoint.x].setH(0);
items[startPoint.y][startPoint.x].setF(0);
items[startPoint.y][startPoint.x].setG(0);
openlist.add(startPoint);
map[endPoint.y][endPoint.x] = ENDPOINT;
items[endPoint.y][endPoint.x].setH(0);
items[endPoint.y][endPoint.x].setF(0);
items[endPoint.y][endPoint.x].setG(0);
map[1][6] = WALLPOINT;
map[2][6] = WALLPOINT;
map[3][6] = WALLPOINT;
map[4][6] = WALLPOINT;
map[5][6] = WALLPOINT;
map[1][5] = WALLPOINT;
map[1][4] = WALLPOINT;
map[5][5] = WALLPOINT;
map[5][4] = WALLPOINT;
map[5][3] = WALLPOINT;
}
private static void Astar(){
boolean find = false;
while(openlist.size() != 0){
if(havePointInOpenList(endPoint.x,endPoint.y)){
find = true;
break;
}
Point tempPoint = openlist.get(0);
List<Point> minList = new ArrayList<>();
for(int i = 0;i < openlist.size();i++){
Point p = openlist.get(i);
if(items[p.y][p.x].getF() <= items[tempPoint.y][tempPoint.x].getF())
tempPoint = p;
}
closelist.add(tempPoint);
openlist.remove(tempPoint);
for(int i = 0;i < 8;i++){
int x = tempPoint.x + tempx[i];
int y = tempPoint.y + tempy[i];
if(x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT || map[y][x] == WALLPOINT || havePointInCloseList(x,y))
continue;
int gLeng = items[tempPoint.y][tempPoint.x].getG();
if(i % 2 == 0){
gLeng = gLeng + 10;
}else{
gLeng = gLeng + 14;
}
if(havePointInOpenList(x,y)){
if(gLeng < items[y][x].getG()){
items[y][x].setPre_x(tempPoint.x);
items[y][x].setPre_y(tempPoint.y);
items[y][x].setG(gLeng);
items[y][x].setF(items[y][x].getH() + items[y][x].getG());
}
}else{
int hLeng = Math.abs(endPoint.x - x) + Math.abs(endPoint.y - y);
hLeng = hLeng * 10;
items[y][x].setPre_x(tempPoint.x);
items[y][x].setPre_y(tempPoint.y);
items[y][x].setG(gLeng);
items[y][x].setH(hLeng);
items[y][x].setF(items[y][x].getH() + items[y][x].getG());
Point p = new Point(x,y);
openlist.add(p);
}
}
}
int currentx = items[endPoint.y][endPoint.x].getPre_x();
int currenty = items[endPoint.y][endPoint.x].getPre_y();
if(find){
while(currentx != startPoint.x || currenty != startPoint.y){
map[currenty][currentx] = WAY_POINT;
MapItem item = items[currenty][currentx];
currentx = item.getPre_x();
currenty = item.getPre_y();
}
}else{
System.out.println("抱歉没有找到路径");
}
}
private static boolean havePointInCloseList(int x,int y){
for(Point p : closelist){
if(p.x == x && p.y == y)
return true;
}
return false;
}
private static boolean havePointInOpenList(int x,int y){
for(Point p : openlist){
if(p.x == x && p.y == y)
return true;
}
return false;
}
}
|
Ok,全部代码就在这里了。
Openlist :开放列表，存放预选节点，也就是预选列表，选择下一个被遍历节点就是从这里面选的。
Closelist:关闭列表，存放已经遍历过的节点，也就是说已经确定了，被检查过周围节点的节点，确定了周围节点都是最优路线的，这个节点不能被重复遍历的。
关于F,G,H计算：F = G + H，G的话就是从开始到当前点的消耗，上下左右四个方向走一步距离为1，斜对角那么就是约为1.4，为了方便计算就都扩大10倍，10和14。其实不用那么严格，只要保证两边之和大于第三边即可，朝正方向的步长小于斜对角长度。 H的距离的话，愿意用勾股定理计算也可以，不过为了方便我还是用的x向的距离加上y向的距离。也可表示距离长度。没什么影响的。
大体思路：
将起始节点加入openlist当中，然后就进入循环查找路线。一个循环过程：
从openlist当中找F值为最小的节点作为父节点然后遍历周围的节点，若有F相同选择G最小的
将父节点从openlist中移除，加入到closelist当中
遍历父节点周围的节点，如果是墙壁或边界，跳过该节点。如果在closelist当中，跳过该节点。
如果该节点（父节点周围的节点）不在openlist当中，计算F,G,H,并记录父节点坐标，G值为父节点的G值加上到达当前点的步长消耗。（因为这种节点，第一次遍历到，那么到达它目前的最优路径就是通过父亲节点到达）。
如果该节点在openlist当中，说明他也是待选节点，他已经被遍历过了，那么他就有了选择，选择原先的父节点，还是当前的父节点，这取决于G值，因为此时H值是不会变的，G值越小消耗越小，F就会越小，路径会越短。那么F的大小决定了优先级，决定了该节点被当做父节点的优先级。F越小优先级越高，优先级越高被先遍历到的可能性越大。（这块就是启发式搜索，我个人感觉这个F起到优先级作用，改变了搜索的优先顺序，从而使得寻路更加的高效。）
- 重复以上步骤，直到openlist为空（为什么会空呢，当开始节点在一个被障碍物组成的封闭空间内，边界被跳过，closelist被跳过，每次循环都有节点放入close当中，那么封闭空间内节点终将会被遍历完，全部放入closelist中，自然就为空了），或者目标节点放入了openlist（找到路径）。
我写的时候一些担心和小问题：
- F值相同的情况
不用担心F值相同的节点，因为都相同的话，位置不同，每次遍历都是优先选择F最小的，终会遍历完所有的相同F的坐标，那么它如果离终点较远的话，要知道H的值是不会改变的，他的G值会变得很大，导致F也会变得很大，那么它周围的节点很大可能是不会被下一次循环选中作为父节点的。
- 遍历周围节点太麻烦
当初最早的时候还傻乎乎的用一堆if去判断方向，利用偏移量，这个思路我也忘了是从哪里学过来的。自己先定好一个遍历顺序，顺时针啊逆时针啊随你，然后按照顺序将x,y的偏移写到两个数组中去，反正就装起。遍历的时候，循环这个数组，只用写一个当前节点坐标加上偏移量即可，计算G值也很简单，由于遍历是有顺序的，那么就可以通过循环次数的奇偶性判断是对角线还是正方向，对应加上值即可。
以上就是思路，至于代码详细解释，emmm…代码里的注释应该写的比较清楚吧，havePointInCloseList(),havePointInOpenList(),就是判断节点是否在关闭列表和开启列表内用的。