Java版A星算法實現步驟

A星算法步驟：

1.起點先添加到開啟列表中。

2.開啟列表中有節點的話，取出第一個節點，即最小F值的節點，

判斷此節點是否是目標點，是則找到了，跳出，

根據此節點取得八個方向的節點，求出G，H，F值，

判斷每個節點在地圖中是否能通過，不能通過則加入關閉列表中，跳出判斷每個節點是否在關閉列表中，在則跳出，

判斷每個節點是否在開啟列表中，在則更新G值，F值，還更新其父節點；不在則將其添加到開啟列表中，計算G值，H值，F值，添加其節點。

3.把此節點從開啟列表中刪除，再添加到關閉列表中。

4.把開啟列表中按照F值最小的節點進行排序，最小的F值在第一個。

5.重復2，3，4步驟，

直到目標點在開啟列表中，即找到了；目標點不在開啟列表中，開啟列表為空，即沒找到。

//A*算法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){  
        node.setF(Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()));  
    }  
    //計算F值  
    private void countF(Node node){  
        node.setF(node.getG()+node.getF());  
    }  
    }//節點類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();  
    }  
    }  

測試類：

public class Test {  
        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();  
            }  
        }  
    }}