Java编程实现A*算法完整代码

时间:2022-11-24 09:26:47

前言

a*搜寻算法俗称a星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中

通过二维数组构建的一个迷宫,“%”表示墙壁,a为起点,b为终点,“#”代表障碍物,“*”代表算法计算后的路径

本文实例代码结构:

Java编程实现A*算法完整代码

?
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