Java編程實現A*算法完整代碼

前言

A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中

通過二維數組構建的一個迷宮，“%”表示牆壁，A為起點，B為終點，“#”代表障礙物，“*”代表算法計算後的路徑

本文實例代碼結構：

 % % % % % % % % ooooo % % oo # oo % % A o # o B % % oo # oo % % ooooo % % % % % % % % ============================= 經過A*算法計算後============================= % % % % % % % % oo * oo % % o * # * o % % A o # o B % % oo # oo % % ooooo % % % % % % % % <

算法理論

算法的核心公式為：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(); } }

修改地圖再測試一下，看看效果

% % % % % % % % ooooo % % oo # oo % % A o # o B % % oo # oo % % ooooo % % % % % % % % =============================經過A*算法計算後=============================% % % % % % % % ooooo % % oo # oo % % A o # o B % % oo # oo % % ooooo % % % % % % % %

總結

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：估價值h(n)<=n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索範圍大，效率低。但能得到

最優解。如果估價值>實際值,搜索的點數少，搜索範圍小，效率高，但不能保證得到最優解。

最大的感觸就是：做事最忌三天打漁，兩天曬網。量可以不大，但必須有連續性，貴在堅持。

希望每一個程序員，都能開心的敲著代碼，做自己喜歡做的事。

以上就是本文關於Java編程實現A*算法完整代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。