A星算法Java實現
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;public class AStar {
private int[][] map;// 地圖(1可通過 0不可通過) private List<Node> openList;// 開啟列表 private List<Node> closeList;// 關閉列表 private final int COST_STRAIGHT = 10;// 垂直方向或水平方向移動的路徑評分 private final int COST_DIAGONAL = 14;// 斜方向移動的路徑評分 private int row;// 行 private int column;// 列 public AStar(int[][] map, int row, int column) { this.map = map; this.row = row; this.column = column; openList = new ArrayList<Node>(); closeList = new ArrayList<Node>(); } // 查找坐標（-1：錯誤，0：沒找到，1：找到了） public int search(int x1, int y1, int x2, int y2) { if (x1 < 0 || x1 >= row || x2 < 0 || x2 >= row || y1 < 0 || y1 >= column || y2 < 0 || y2 >= column) { return -1; } if (map[x1][y1] == 0 || map[x2][y2] == 0) { return -1; } Node sNode = new Node(x1, y1, null); Node eNode = new Node(x2, y2, null); openList.add(sNode); List<Node> resultList = search(sNode, eNode); if (resultList.size() == 0) { return 0; } for (Node node : resultList) { map[node.getX()][node.getY()] = -1; } return 1; } // 查找核心算法 private List<Node> search(Node sNode, Node eNode) { List<Node> resultList = new ArrayList<Node>(); boolean isFind = false; Node node = null; while (openList.size() > 0) { // 取出開啟列表中最低F值，即第一個存儲的值的F為最低的 node = openList.get(0); // 判斷是否找到目標點 if (node.getX() == eNode.getX() && node.getY() == eNode.getY()) { isFind = true; break; } // 上 if ((node.getY() - 1) >= 0) { checkPath(node.getX(), node.getY() - 1, node, eNode, COST_STRAIGHT); } // 下 if ((node.getY() + 1) < column) { checkPath(node.getX(), node.getY() + 1, node, eNode, COST_STRAIGHT); } // 左 if ((node.getX() - 1) >= 0) { checkPath(node.getX() - 1, node.getY(), node, eNode, COST_STRAIGHT); } // 右 if ((node.getX() + 1) < row) { checkPath(node.getX() + 1, node.getY(), node, eNode, COST_STRAIGHT); } // 左上 if ((node.getX() - 1) >= 0 && (node.getY() - 1) >= 0) { checkPath(node.getX() - 1, node.getY() - 1, node, eNode, COST_DIAGONAL); } // 左下 if ((node.getX() - 1) >= 0 && (node.getY() + 1) < column) { checkPath(node.getX() - 1, node.getY() + 1, node, eNode, COST_DIAGONAL); } // 右上 if ((node.getX() + 1) < row && (node.getY() - 1) >= 0) { checkPath(node.getX() + 1, node.getY() - 1, node, eNode, COST_DIAGONAL); } // 右下 if ((node.getX() + 1) < row && (node.getY() + 1) < column) { checkPath(node.getX() + 1, node.getY() + 1, node, eNode, COST_DIAGONAL); } // 從開啟列表中刪除 // 添加到關閉列表中 closeList.add(openList.remove(0)); // 開啟列表中排序，把F值最低的放到最底端 Collections.sort(openList, new NodeFComparator()); } if (isFind) { getPath(resultList, node); } return resultList; } // 查詢此路是否能走通 private boolean checkPath(int x, int y, Node parentNode, Node eNode, int cost) { Node node = new Node(x, y, parentNode); // 查找地圖中是否能通過 if (map[x][y] == 0) { closeList.add(node); return false; } // 查找關閉列表中是否存在 if (isListContains(closeList, x, y) != -1) { return false; } // 查找開啟列表中是否存在 int index = -1; if ((index = isListContains(openList, x, y)) != -1) { // G值是否更小，即是否更新G，F值 if ((parentNode.getG() + cost) < openList.get(index).getG()) { node.setParentNode(parentNode); countG(node, eNode, cost); countF(node); openList.set(index, node); } } else { // 添加到開啟列表中 node.setParentNode(parentNode); count(node, eNode, cost); openList.add(node); } return true; } // 集合中是否包含某個元素(-1：沒有找到，否則返回所在的索引) private int isListContains(List<Node> list, int x, int y) { for (int i = 0; i < list.size(); i++) { Node node = list.get(i); if (node.getX() == x && node.getY() == y) { return i; } } return -1; } // 從終點往返回到起點 private void getPath(List<Node> resultList, Node node) { if (node.getParentNode() != null) { getPath(resultList, node.getParentNode()); } resultList.add(node); } // 計算G,H,F值 private void count(Node node, Node eNode, int cost) { countG(node, eNode, cost); countH(node, eNode); countF(eNode); } // 計算G值 private void countG(Node node, Node eNode, int cost) { if (node.getParentNode() == null) { node.setG(cost); } else { node.setG(node.getParentNode().getG() + cost); } } // 計算H值 private void countH(Node node, Node eNode){ int x = Math.abs(node.getX() - eNode.getX()); int y = Math.abs(node.getY() - eNode.getY()); if(x<y){ node.setH(x * COST_DIAGONAL + (y-x) * COST_STRAIGHT); }else{ node.setH(y * COST_DIAGONAL + (x-y) * COST_STRAIGHT); } } // 計算F值 private void countF(Node node) { node.setF(node.getG() + node.getH()); } public static void main(String[] args) { int[][] map=new int[][]{// 地圖數組 {1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,0,1,1,1,1,1}, {1,1,1,1,0,1,1,1,1,1}, {1,1,1,1,0,1,1,1,1,1}, {1,1,1,1,0,1,1,1,1,1}, {1,1,1,1,0,1,1,1,1,1} }; AStar aStar=new AStar(map, 6, 10); int flag=aStar.search(4, 0, 3, 8); if(flag==-1){ System.out.println("傳輸數據有誤！"); }else if(flag==0){ System.out.println("沒找到！"); }else{ for(int x=0;x<6;x++){ for(int y=0;y<10;y++){ if(map[x][y]==1){ System.out.print(" "); }else if(map[x][y]==0){ System.out.print("〓"); }else if(map[x][y]==-1){ System.out.print("※"); } } System.out.println(); } } }}
// 節點類
class Node {
private int x;// X坐標
private int y;// Y坐標
private Node parentNode;// 父類節點
private int g;// 當前點到起點的移動耗費
private int h;// 當前點到終點的移動耗費，即曼哈頓距離|x1-x2|+|y1-y2|(忽略障礙物)
private int f;// f=g+hpublic Node(int x, int y, Node parentNode) { this.x = x; this.y = y; this.parentNode = parentNode; } 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 Node getParentNode() { return parentNode; } public void setParentNode(Node parentNode) { this.parentNode = parentNode; } public int getG() { return g; } public void setG(int g) { this.g = g; } public int getH() { return h; } public void setH(int h) { this.h = h; } public int getF() { return f; } public void setF(int f) { this.f = f; }}
// 節點比較類
class NodeFComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.getF() - o2.getF();
}
} </pre>
本文由用戶 m2yy 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！