这篇文章主要介绍了Java编程如何实现A*算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
本文实例代码结构:
% % % % % % % % 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写的,先看一看节点类的内容
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的构造方法中,我通过创建节点的二维数组来实现一个迷宫地图,其中包括起点和终点
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 > </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值,顺藤摸瓜即可以显示出路径。
看看代码
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 > </span>node = map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()]; //<span > </span>while(!(node.getX() ==map.getStartNode().getX()&&node.getY() ==map.getStartNode().getY())){ //<span > </span>node.getPNode().setValue("*"); //<span > </span>node = node.getPNode(); //<span > </span>} } //<span > </span>map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setValue("A"); } }
最后写一个Main方法
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(); } }
修改地图再测试一下,看看效果
% % % % % % % % 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 % % % % % % % %
感谢你能够认真阅读完这篇文章,希望小编分享的“Java编程如何实现A*算法”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。