Java編程如何實(shí)現(xiàn)A*算法

這篇文章主要介紹了Java編程如何實(shí)現(xiàn)A*算法，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

本文實(shí)例代碼結(jié)構(gòu)：

% % % % % % %  
% o o o o o %  
% o o # o o %  
% A o # o B %  
% o o # o o %  
% o o o o o %  
% % % % % % %  
============================= 
經(jīng)過A*算法計(jì)算后 
============================= 
% % % % % % %  
% o o * o o %  
% o * # * o %  
% A o # o B %  
% o o # o o %  
% o o o o o %  
% % % % % % % <

算法理論

算法的核心公式為：F=G+H

把地圖上的節(jié)點(diǎn)看成一個(gè)網(wǎng)格。

G=從起點(diǎn)A,沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定節(jié)點(diǎn)的移動消耗，在這個(gè)例子里，我們令水平或者垂直移動的耗費(fèi)為10，對角線方向耗費(fèi)為14。我們?nèi)∵@些值是因?yàn)檠貙蔷€

的距離是沿水平或垂直移動耗費(fèi)的的根號2，或者約1.414倍。為了簡化，我們用10和14近似。

既然我們在計(jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它父節(jié)點(diǎn)的G值，然后依照它相對父節(jié)點(diǎn)是對角線方向或者直角方向(非對角線)，分別增加14和10。例子中這

個(gè)方法的需求會變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。

H=從當(dāng)前格移動到終點(diǎn)B的預(yù)估移動消耗。為什么叫”預(yù)估“呢，因?yàn)槲覀儧]有辦法事先知道路徑的長度，這里我們使用曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直

的方格的數(shù)量總和，忽略對角線方向。然后把結(jié)果乘以10。

F的值是G和H的和，這是我們用來判斷優(yōu)先路徑的標(biāo)準(zhǔn)，F(xiàn)值最小的格，我們認(rèn)為是優(yōu)先的路徑節(jié)點(diǎn)。

實(shí)現(xiàn)步驟

算法使用java寫的，先看一看節(jié)點(diǎn)類的內(nèi)容

package a_star_search; 
/** 
 * 節(jié)點(diǎn)類 
 * @author zx 
 * 
 */ 
public class Node { 
  private int x; //x坐標(biāo) 
  private int y; //y坐標(biāo) 
  private String value;  //表示節(jié)點(diǎn)的值 
  private double FValue = 0; //F值 
  private double GValue = 0; //G值 
  private double HValue = 0; //H值 
  private boolean Reachable; //是否可到達(dá)（是否為障礙物） 
  private Node PNode;   //父節(jié)點(diǎn) 
   
  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; 
  }   
}

還需要一個(gè)地圖類，在map的構(gòu)造方法中，我通過創(chuàng)建節(jié)點(diǎn)的二維數(shù)組來實(shí)現(xiàn)一個(gè)迷宮地圖，其中包括起點(diǎn)和終點(diǎn)

package a_star_search;
public class Map {
	private Node[][] map;
	//節(jié)點(diǎn)數(shù)組 
	private Node startNode;
	//起點(diǎn) 
	private Node endNode;
	//終點(diǎn) 
	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從起點(diǎn)A開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”，這是一個(gè)待檢查方格的列表。

2尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過無法通過的方格。也把他們加入開啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資

料是十分重要的。后面會解釋它的具體用途。

3從開啟列表中刪除起點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。

經(jīng)過以上步驟，“開啟列表”中包含了起點(diǎn)A周圍除了障礙物的所有節(jié)點(diǎn)。他們的父節(jié)點(diǎn)都是A,通過前面講的F=G+H的公式，計(jì)算每個(gè)節(jié)點(diǎn)的G，H，F(xiàn)值，并按照F的值大小，從小

到大進(jìn)行排序。并對F值最小的那個(gè)節(jié)點(diǎn)做以下操作

4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。

5，檢查所有相鄰格子。跳過那些不可通過的(1.在”關(guān)閉列表“中，2.障礙物)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。

6，如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達(dá)它的話，G值是否會更低一些。如果不是，那就什么都不

做。（這里，我的代碼中并沒有判斷）

7，我們重復(fù)這個(gè)過程，直到目標(biāo)格（終點(diǎn)“B”）被添加進(jìn)“開啟列表”，說明終點(diǎn)B已經(jīng)在上一個(gè)添加進(jìn)“關(guān)閉列表”的節(jié)點(diǎn)的周圍，只需走一步，即可到達(dá)終點(diǎn)B。

8，我們將終點(diǎn)B添加到“關(guān)閉列表”

9，最后一步，我們要將從起點(diǎn)A到終點(diǎn)B的路徑表示出來。父節(jié)點(diǎn)的作用就顯示出來了，通過“關(guān)閉列表”中的終點(diǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，改變其value值，順藤摸瓜即可以顯示出路徑。

看看代碼

package a_star_search;
import java.util.ArrayList;
public class AStar {
	/** 
   * 使用ArrayList數(shù)組作為“開啟列表”和“關(guān)閉列表” 
   */
	ArrayList<Node> open = new ArrayList<Node>();
	ArrayList<Node> close = new ArrayList<Node>();
	/** 
   * 獲取H值 
   * @param currentNode：當(dāng)前節(jié)點(diǎn) 
   * @param endNode：終點(diǎn) 
   * @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：當(dāng)前節(jié)點(diǎn) 
   * @return 
   */
	public double getGValue(Node currentNode){
		if(currentNode.getPNode()!=null){
			if(currentNode.getX()==currentNode.getPNode().getX()||currentNode.getY()==currentNode.getPNode().getY()){
				//判斷當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)之間的位置關(guān)系（水平？對角線） 
				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();
	}
	/** 
   * 將選中節(jié)點(diǎn)周圍的節(jié)點(diǎn)添加進(jìn)“開啟列表” 
   * @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++){
				//判斷條件為：節(jié)點(diǎn)為可到達(dá)的（即不是障礙物，不在關(guān)閉列表中），開啟列表中不包含，不是選中節(jié)點(diǎn) 
				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]);
					//將選中節(jié)點(diǎn)作為父節(jié)點(diǎn) 
					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]);
				}
			}
		}
	}
	/** 
   * 使用冒泡排序?qū)㈤_啟列表中的節(jié)點(diǎn)按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);
				}
			}
		}
	}
	/** 
   * 將節(jié)點(diǎn)添加進(jìn)”關(guān)閉列表“ 
   * @param node 
   * @param open 
   */
	public void inClose(Node node,ArrayList<Node> open){
		if(open.contains(node)){
			node.setReachable(false);
			//設(shè)置為不可達(dá) 
			open.remove(node);
			close.add(node);
		}
	}
	public void search(Map map){
		//對起點(diǎn)即起點(diǎn)周圍的節(jié)點(diǎn)進(jìn)行操作 
		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);
		//重復(fù)步驟 
		do{
			inOpen(open.get(0), map);
			inClose(open.get(0), open);
			sort(open);
		}
		while(!open.contains(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()]));
		//知道開啟列表中包含終點(diǎn)時(shí)，循環(huán)退出 
		inClose(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()], open);
		showPath(close,map);
	}
	/** 
   * 將路徑標(biāo)記出來 
   * @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");
	}
}

最后寫一個(gè)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("經(jīng)過A*算法計(jì)算后"); 
    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 % 
% % % % % % % 
=============================
經(jīng)過A*算法計(jì)算后
=============================
% % % % % % % 
% o o o o o % 
% o o # o o % 
% A o # o B % 
% o o # o o % 
% o o o o o % 
% % % % % % %

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java編程如何實(shí)現(xiàn)A*算法”這篇文章對大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!