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();        }    }