A星算法步驟：

1.起點(diǎn)先添加到開啟列表中。

2.開啟列表中有節(jié)點(diǎn)的話，取出***個(gè)節(jié)點(diǎn)，即最小F值的節(jié)點(diǎn)，

判斷此節(jié)點(diǎn)是否是目標(biāo)點(diǎn)，是則找到了，跳出，

根據(jù)此節(jié)點(diǎn)取得八個(gè)方向的節(jié)點(diǎn)，求出G，H，F(xiàn)值，

判斷每個(gè)節(jié)點(diǎn)在地圖中是否能通過，不能通過則加入關(guān)閉列表中，跳出判斷每個(gè)節(jié)點(diǎn)是否在關(guān)閉列表中，在則跳出，

判斷每個(gè)節(jié)點(diǎn)是否在開啟列表中，在則更新G值，F(xiàn)值，還更新其父節(jié)點(diǎn)；不在則將其添加到開啟列表中，計(jì)算G值，H值，F(xiàn)值，添加其節(jié)點(diǎn)。

3.把此節(jié)點(diǎn)從開啟列表中刪除，再添加到關(guān)閉列表中。

4.把開啟列表中按照F值最小的節(jié)點(diǎn)進(jìn)行排序，最小的F值在***個(gè)。

5.重復(fù)2，3，4步驟，

直到目標(biāo)點(diǎn)在開啟列表中，即找到了；目標(biāo)點(diǎn)不在開啟列表中，開啟列表為空，即沒找到。

//A*算法public class AStar {  
    private int[][] map;//地圖(1可通過 0不可通過)  
    private List<Node> openList;//開啟列表  
    private List<Node> closeList;//關(guān)閉列表  
    private final int COST_STRAIGHT = 10;//垂直方向或水平方向移動(dòng)的路徑評分  
    private final int COST_DIAGONAL = 14;//斜方向移動(dòng)的路徑評分  
    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>();  
    }  
        //查找坐標(biāo)（-1：錯(cuò)誤，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值，即***個(gè)存儲的值的F為***的  
            node=openList.get(0);  
            //判斷是否找到目標(biāo)點(diǎn)  
            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);  
            }  
            //從開啟列表中刪除  
            //添加到關(guān)閉列表中  
            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;  
        }  
        //查找關(guān)閉列表中是否存在  
        if(isListContains(closeList, x, y)!=-1){  
            return false;  
        }  
        //查找開啟列表中是否存在  
        int index=-1;  
        if((index=isListContains(openList, x, y))!=-1){  
            //G值是否更小，即是否更新G，F(xiàn)值  
            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;  
    }  
        //集合中是否包含某個(gè)元素(-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;  
    }  
        //從終點(diǎn)往返回到起點(diǎn)  
    private void getPath(List<Node> resultList,Node node){  
        if(node.getParentNode()!=null){            getPath(resultList, node.getParentNode());  
        }  
        resultList.add(node);  
    }  
        //計(jì)算G,H,F值  
    private void count(Node node,Node eNode,int cost){  
        countG(node, eNode, cost);  
        countH(node, eNode);  
        countF(eNode);  
    }  
    //計(jì)算G值  
    private void countG(Node node,Node eNode,int cost){  
        if(node.getParentNode()==null){  
            node.setG(cost);  
        }else{  
            node.setG(node.getParentNode().getG()+cost);  
        }  
    }  
    //計(jì)算H值  
    private void countH(Node node,Node eNode){  
        node.setF(Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()));  
    }  
    //計(jì)算F值  
    private void countF(Node node){  
        node.setF(node.getG()+node.getF());  
    }  
    }//節(jié)點(diǎn)類class Node {  
    private int x;//X坐標(biāo)  
    private int y;//Y坐標(biāo)  
    private Node parentNode;//父類節(jié)點(diǎn)  
    private int g;//當(dāng)前點(diǎn)到起點(diǎn)的移動(dòng)耗費(fèi)  
    private int h;//當(dāng)前點(diǎn)到終點(diǎn)的移動(dòng)耗費(fèi)，即曼哈頓距離|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;  
    }}//節(jié)點(diǎn)比較類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[][]{
// 地圖數(shù)組
                {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("傳輸數(shù)據(jù)有誤！");  
        }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();  
            }  
        }  
    }} 

原文鏈接：http://www.cnblogs.com/xmmdream/archive/2011/12/12/2284627.html

【編輯推薦】

1. Tomcat運(yùn)行Java Web內(nèi)存溢出總結(jié)
2. Java NIO如何處理慢速的連接
3. Java數(shù)據(jù)緩存實(shí)現(xiàn)的核心機(jī)制
4. Java與Cobol對決：Cobol軟件質(zhì)量最過硬
5. Java NIO類庫關(guān)系圖解