亲宝软件园·资讯

展开

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

加蛋加蛋 人气:0
想了解Java编程实现A*算法完整代码的相关内容吗,加蛋加蛋在本文为您仔细讲解Java编程实现A*算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:java,算法,java编程,a*算法,java,算法,实例,下面大家一起来学习吧。

前言

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

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

本文实例代码结构:

% % % % % % %  
% 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 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值,顺藤摸瓜即可以显示出路径。

看看代码

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方法

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 % 
% % % % % % % 

总结

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

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

最大的感触就是:做事最忌三天打渔,两天晒网。量可以不大,但必须有连续性,贵在坚持。

希望每一个程序员,都能开心的敲着代码,做自己喜欢做的事。

以上就是本文关于Java编程实现A*算法完整代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。

加载全部内容

相关教程
猜你喜欢
用户评论