A*算法Java簡單實現

jopen 10年前發布 | 1K 次閱讀 Java 算法
package astar;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
/**

A*搜索算法，A星算法。
這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。
常用于游戲中的NPC的移動計算，或在線游戲的BOT的移動計算上。
該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
在此算法中，如果以 g(n)表示從起點到任意頂點n的實際距離，
h(n)表示任意頂點n到目標頂點的估算距離，
那么 A*算法的公式為：f(n)=g(n)+h(n)。 這個公式遵循以下特性：
如果h(n)為0，只需求出g(n)，即求出起點到任意頂點n的最短路徑，則轉化為單源最短路徑問題，即Dijkstra算法
如果h(n)<=“n到目標的實際距離”，則一定可以求出最優解。而且h(n)越小，需要計算的節點越多，算法效率越低。
*
@author DBJ(dubenju@126.com)
/
public class AStar {
 /** 搜索區域 0:不能走 1:能走 /
 private int[][] searchArea;
 /* 記錄節點狀態 /
 private int[][] searchAreaStatus;
 private int width;
 private int height;
/ 開啟列表 */
 private PriorityQueue<AStarNode> openList;
 / FComparator */
 public static Comparator<AStarNode> fComparator = new Comparator<AStarNode>() {

 @Override
 public int compare(AStarNode c1, AStarNode c2) {
     return (int) (c1.getF() - c2.getF());
 }

};
/**

AStart
@param searchArea 搜索區域
@param width      搜索區域的寬
@param height     搜索區域的高
*/
public AStar(int[][] searchArea, int width, int height) {
 this.width = width;
 this.height = height;
 this.searchArea = searchArea;
 this.searchAreaStatus = new int[this.height][this.width];
 this.openList = new PriorityQueue<>(10, fComparator);
}
/**

查找路徑
*
@param x1 起點A的x坐標
@param y1 起點A的y坐標
@param x2 終點B的x坐標
@param y2 終點B的y坐標
@return   起點A到終點B的路徑
*/
public List<AStarNode> find(int x1, int y1, int x2, int y2) {
 AStarNode startNode = new AStarNode(x1, y1);
 AStarNode endNode = new AStarNode(x2, y2);
return this.find(startNode, endNode);
}
/**

find 搜索
@param startNode 起點
@param endNode   終點
@return          路徑
/
private List<AStarNode> find(AStarNode startNode, AStarNode endNode) {
 List<AStarNode> resultList = new ArrayList<AStarNode>();
 / 是否找到 */
 boolean findFalg = false;
/ 1.從起點A開始，并將它添加到 “開啟列表”。 /
 this.openList.add(startNode);
 searchAreaStatus[startNode.getX()][startNode.getY()] = AStarConstants.NOTE_STATUS_OPEN;
AStarNode curNode = this.openList.poll();
 while (curNode != null) {

 /* c）對于當前方格臨近的8個方格的每一個....（For Each） */
 // System.out.println("find@AStar curNode=" + curNode);
 for (int i = 0; i < 8; i++) {
     switch (i) {
     case 0:// 右
         check(curNode.getX(),     curNode.getY() + 1, endNode, curNode, AStarConstants.COST_ORTHOGONAL); // 10
         break;
     case 1:// 下
         check(curNode.getX() + 1, curNode.getY(),     endNode, curNode, AStarConstants.COST_ORTHOGONAL); // 10
         break;
     case 2:// 左
         check(curNode.getX(),     curNode.getY() - 1, endNode, curNode, AStarConstants.COST_ORTHOGONAL); // 10
         break;
     case 3:// 上
         check(curNode.getX() - 1, curNode.getY(),     endNode, curNode, AStarConstants.COST_ORTHOGONAL); // 10
         break;
     case 4:// 右上
         check(curNode.getX() - 1, curNode.getY() + 1, endNode, curNode, AStarConstants.COST_DIAGONAL); // 14
         break;
     case 5:// 右下
         check(curNode.getX() + 1, curNode.getY() + 1, endNode, curNode, AStarConstants.COST_DIAGONAL); // 14
         break;
     case 6:// 左上
         check(curNode.getX() - 1, curNode.getY() - 1, endNode, curNode, AStarConstants.COST_DIAGONAL); // 14
         break;
     case 7:// 左下
         check(curNode.getX() + 1, curNode.getY() - 1, endNode, curNode, AStarConstants.COST_DIAGONAL); // 14
         break;
     } // end switch
 } // end for

 // 加入關閉列表
 findFalg = this.addClosedList(curNode, endNode);
 if (findFalg) {
     break;
 }

 /* a）尋找開啟列表上最小F值的方格。將它作為當前方格。 */
 curNode = this.openList.poll();

} // while
if (findFalg) {

 // 有
 read(resultList, curNode);
 return resultList;

} else {

 /* 無法找到目標方格并且開啟列表是空的時候，不存在路徑。 */
 return resultList;

}
}
/**

讀取所有節點，從起點開始返
*
@param resultList
@param node
*/
private void read(List<AStarNode> resultList, AStarNode node) {
 if (node.getParent() != null) {

 read(resultList, node.getParent());

}
 resultList.add(node);
}
/**

hasNearbyUnwalkable
@param x x坐標
@param y y坐標
@param parent 父
@return
*/
private boolean hasNearbyUnwalkable(int x, int y, AStarNode parent) {
 boolean bRes = false;
 if (x != parent.getX() && y != parent.getY()) {

 if (this.searchArea[parent.getX()][y] == AStarConstants.NOTE_UNWALKABLE) {
     bRes = true;
 }
 if (this.searchArea[x][parent.getY()] == AStarConstants.NOTE_UNWALKABLE) {
     bRes = true;
 }

}
 return bRes;
}
/**

檢查 當前節點周圍的節點，是否能行，是否在開啟列表中，是否在關閉列表中 如果不在關閉與開啟列表中則加入開啟列表，如果在開啟中則更新節點G值信息
*
@param x       x坐標
@param y       y坐標
@param endNode 終點
@param parent 父
@param step 步長
@return
*/
private boolean check(int x, int y, AStarNode endNode, AStarNode parent, int step) {
 // System.out.println("  check@AStar (" + x + "," + y + ")" + parentNode);
 try {

 if (this.searchArea[x][y] == AStarConstants.NOTE_UNWALKABLE) {
     /* 如果不能走，忽略它。*/
     return false;
 }

 if (this.searchAreaStatus[x][y] == AStarConstants.NOTE_STATUS_CLOSED) {
     /* 如果它在關閉列表上，忽略它。 */
     return false;
 }

 /* 否則，執行以下操作。 */
 if (this.searchAreaStatus[x][y] == AStarConstants.NOTE_STATUS_NONE) {
     if (hasNearbyUnwalkable(x, y, parent)) {
         return false;
     }

     /* 如果不在開啟列表中，把它添加到開啟列表。使當前方格成為這個方格的父。記錄的方格F值，G值和H值。*/
     this.addOpenList(x, y, endNode, parent, step);
     this.searchAreaStatus[x][y] = AStarConstants.NOTE_STATUS_OPEN;
     return true;
 } else if (this.searchAreaStatus[x][y] == AStarConstants.NOTE_STATUS_OPEN) {
     /* 如果在開啟列表了，檢查看看采用G值來衡量這個路徑到那個方格是否是更好的。*/
     this.updateOpenList(x, y, endNode, parent, step);
     return true;
 }

} catch (ArrayIndexOutOfBoundsException e) {

 return false;// 下標越界

}
 return false;
}
/**

添加到關閉列表
*
@param node    節點
@param endNode 終點
@return true:路徑被發現
*/
private boolean addClosedList(AStarNode node, AStarNode endNode) {
 if (node.getX() == endNode.getX() && node.getY() == endNode.getY()) {

 /* 在目標方格添加到關閉列表的情況下，路徑已經被發現 */
 return true;

}
this.searchAreaStatus[node.getX()][node.getY()] = AStarConstants.NOTE_STATUS_CLOSED;
 return false;
}
/**

添加到開啟列表
使當前方格成為這個方格的父。記錄的方格F值，G值和H值。
*
@param x x坐標
@param y y坐標
@param endNode 終點
@param parent  父
@param step    步長
@return
/
private boolean addOpenList(int x, int y, AStarNode endNode, AStarNode parent, int step) {
 / 使當前方格成為這個方格的父。 /
 AStarNode node = new AStarNode(x, y, parent);
 / 記錄的方格F值，G值和H值。 */
 this.count(node, endNode, step);
this.openList.add(node);
 // System.out.println("    putOpenTable@AStar " + node + parentNode);
return true;
}
/**

已經在開啟列表了更新節點F值
更低的G值意味著這是一個更好的路徑。如果是這樣，把方格的父改為當前方格，并重新計算方格的G值和F值。如果你保持開啟列表排序F值，由于這個變化你可能需重存列表。
*
@param x x坐標
@param y y坐標
@param endNode 終點
@param parent 父
@param step 步長
@return
*/
private boolean updateOpenList(int x, int y, AStarNode endNode, AStarNode parent, int step) {
 AStarNode node = new AStarNode(x, y);
 for (AStarNode nd : this.openList) {

 if (node.equals(nd)) {
     node = nd;
     break ;
 }

}
 int g = parent.getG() + step;
 if (g < node.getG()) {

 /* 如果是更低的G值意味著這是一個更好的路徑。把方格的父改為當前方格 */
 node.setParent(parent);
 /* 并重新計算方格的G值和F值。*/
 this.count(node, endNode, step);

 /* 如果你保持開啟列表按F值排序，由于這個變化你可能需重存列表。 */
 this.openList.remove(node);
 this.openList.add(node);

 return true;

}
 return false;
}
/**

計算GHF
*
@param node 節點
@param endNode 終點
@param step 步長
*/
private void count(AStarNode node, AStarNode endNode, int step) {
 this.countG(node, node.getParent(), step);
 this.countH(node, endNode);
 this.countF(node);
}
/**

計算G值
將指定每個移動水平或垂直方成本為10，對角線移動成本為14
找出那個方塊的父親的G值，然后加10或14取決于它從父方格是正交（非對角線）還是對角線。
*
@param node 節點
@param parent 父
@param step 步長
*/
private void countG(AStarNode node, AStarNode parent, int step) {
 if (parent == null) {

 node.setG(step);

} else {

 node.setG(parent.getG() + step);

}
}
/**

計算H值
曼哈頓方法
計算從當前方塊到目標方水平和垂直方向移動方塊的總數
將總數乘以10
*
@param node 節點
@param endNode 終點
/
private void countH(AStarNode node, AStarNode endNode) {
 node.setH((Math.abs(endNode.getX() - node.getX()) + Math.abs(endNode.getY() - node.getY()))  10);
}
/**

計算F值
F = G + H
*
@param node 節點
*/
private void countF(AStarNode node) {
 node.setF(node.getG() + node.getH());
}
}</pre>
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
本文地址：http://www.baiduhome.net/code/view/1434591006895
Java 算法
A*算法Java簡單實現

相關代碼

相關文檔

相關經驗

目錄
