A星算法Java实现，星算法java,import java.
分享于 点击 20018 次 点评：251
A星算法Java实现，星算法java,import 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+h public 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(); } }
用户点评