它有啥用晌杰？

沒錯跷睦！這就是那個傳說中的算法，AStar算法肋演。
直白的描述就是抑诸，它能告訴你從源點繞過障礙物到達終點的最短路徑。
以魔獸爭霸為例爹殊，你控制一個游戲單位從上次鼠標右鍵點擊的位置到本次鼠標右鍵點擊的位置走的路線蜕乡，中間可能有商店、水泉梗夸、樹木层玲、高坡等障礙物。
再舉個例子反症，不過這個例子是我估計的辛块，我估計刀塔里面英雄的走位操作也是用這個算法實現(xiàn)的。

它的原理是什么铅碍？

很簡單润绵，廣度優(yōu)先搜索+迪杰斯特拉算法。

性能如何胞谈？

很快尘盼，不過在我看來還不夠快憨愉，因為廣度優(yōu)先嘛，像震蕩波一樣向周圍輻射卿捎，所以那些本來不是路徑的地方也會被遍歷一遍配紫，不完美，不過相對來說還是很快的娇澎”恳希空間嘛，太浪費空間了趟庄，而且路線精度要求越高越消耗空間括细。

路徑形成的關(guān)鍵是什么？

鏈表和指針戚啥。
它把每個涉及到的頂點都用結(jié)構(gòu)體或者對象封裝成了鏈表結(jié)點来累。
每出隊一個頂點就讓它周圍的頂點指向它，以此類推玻募，最終終點變成了鏈表頭次和，起點變成了鏈表尾。
我是感覺這個設(shè)計挺好值得借鑒拖云。
至于其他的要義可以百度出來贷笛。

具體是什么效果？

請看下圖宙项。

A星算法

代碼的用法

尋找路徑的范圍往往被抽象為一個二維數(shù)組乏苦，或者說地圖被抽象為一個二維數(shù)組也行。拿地圖來說事吧尤筐，都玩過《紅色警戒》吧汇荐，那里面地圖的組成小單位是小方塊，這個很典型盆繁，其他形狀的也有掀淘，比如說正六邊形等。在A*算法中這些小形狀都被抽象成為它的中心點油昂，所以無論是普通點革娄、終點、起點還是障礙點都是點冕碟。
在本算法中
0代表可走點稠腊。
-1代表障礙點。
1代表起點鸣哀。
2代表終點架忌。
3代表已經(jīng)找到的路徑點。

public class Main {

    public static void main(String[] args) {
    // write your code here
        //這里規(guī)定障礙結(jié)點為-1.
        // 起點值為1我衬，
        // 終點值為2叹放，
        // 其他點為0.
        int[][] testMatrix = {
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,-1,0,0,0,0,0,0,0,0,0},
                {1,0,0,0,-1,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,-1,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,-1,0,0,-1,0,0,0,0,0,0},
                {0,0,0,0,-1,0,0,-1,0,0,0,0,0,0},
                {0,0,0,0,-1,0,0,-1,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,-1,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,-1,2,0,0,0,0},
                {0,0,0,0,0,0,0,0,-1,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        };
        int[][] testMatrix0 = {
                {0,0,0,0,0,0,0},
                {0,0,0,-1,0,0,0},
                {0,1,0,-1,0,2,0},
                {0,0,0,-1,0,0,0},
                {0,0,0,0,0,0,0}
        };
        AStar.aStar0(testMatrix,2,0,8,9);
        for (int counter = 0;counter < testMatrix.length;counter++) {
            for (int counter0 = 0;counter0 < testMatrix[0].length;counter0++) {
                System.out.print(testMatrix[counter][counter0] + " ");
            }
            System.out.println();
        }
    }
}

輸出

0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 -1 0 0 0 0 0 0 0 0 0 
1 0 0 0 -1 0 0 0 0 0 0 0 0 0 
0 3 0 0 -1 0 0 0 0 0 0 0 0 0 
0 0 3 0 -1 0 0 -1 0 0 0 0 0 0 
0 0 0 3 -1 0 0 -1 0 0 0 0 0 0 
0 0 0 3 -1 0 0 -1 0 0 0 0 0 0 
0 0 0 0 3 0 0 0 -1 0 0 0 0 0 
0 0 0 0 0 3 3 0 -1 2 0 0 0 0 
0 0 0 0 0 0 0 3 -1 3 0 0 0 0 
0 0 0 0 0 0 0 0 3 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 

/**
 * A*算法是用來干嘛的饰恕？
 * 它是用來尋找從源點到終點的最小的可能路徑。
 * 什么叫可能路徑井仰？
 * 形象一點埋嵌，比方說你要去目的地，沿途有一道峽谷俱恶，又寬又深雹嗦，
 * 又沒有橋有沒有飛機，也沒有阿凡達，你又不會飛泊藕。
 * 那咋辦？那你只能繞過去了难礼，所以這個峽谷就是不
 * 可能路徑的范疇了讼呢。
 * 再比如，在你的路徑上面有一堵墻散劫，這墻又高又厚沒有門窗赖条。
 * 你咋過裸卫？你會穿墻術(shù)蜓氨？你當然不會嗜侮，于是這也在不可能路徑的范疇內(nèi)。
 * 那咋辦？那你只能在沒有障礙物的路徑上才能到達目的地了。
 * 那么怎么在沒有障礙物的路徑上怎么走路程最小呢？
 * 那就是本算法要解決的問題了革屠。
 * 一般把這個所有的路徑党瓮，包括可行不可行的在跳，以及起點和終點
 * 都抽象在一個二維平面上。
 */
public class AStar {
    /**
     * 從源點到終點的可行路徑有很多，但是最短路徑一般只有一條。
     * 在試探的過程中，每個頂點的相鄰頂點有8個，我想這一點很明確。
     * 如果不明白可以去玩玩掃雷洛巢。
     * 于是每個頂點有8個方向可以移動，此時這個頂點被稱為父結(jié)點稿茉。
     * 而你所需要做的就是在這8個方向中锹锰，排除不能走的方向恃慧，找到最佳的頂點良瞧。
     * 然后再以這個最佳的頂點為父結(jié)點開始找它自身的8個方向中的最佳頂點澳骤。
     * 那么什么是最佳頂點呢为肮？
     * 其實本算法的精髓就在這里摊册，這個最佳點是在父結(jié)點的8個結(jié)點中選出父結(jié)點
     * 到該結(jié)點的路程+該結(jié)點到終點的路程之和最小的那個結(jié)點，這個結(jié)點
     * 就是所謂的最佳結(jié)點棋枕。
     * 網(wǎng)上通常把這個比較稱為f(n)=g(n)+h(n)白修。
     * n就是當前父結(jié)點。
     * f就是和
     * g就是從當前結(jié)點到起點的路程重斑。
     * h就是該結(jié)點到終點的路程兵睛，其實這代表的是該結(jié)點與終點的距離，或者說接近程度窥浪。
     * 不過有的時候最小的f(n)有好幾個相等的祖很，這個不用管，算法會自動找一個漾脂。
     * 那么如何獲取最佳路徑呢突琳？
     * 只需要把每個父結(jié)點存儲起來就行。
     * 我搞錯了符相，原來這個g值是結(jié)點當前的g值加上它父結(jié)點的g值得到的拆融。
     * 如何高效地確定某結(jié)點的周圍結(jié)點已經(jīng)在開放列表中？
     * 用數(shù)組的話效率會非常低啊终，因為你肯定要遍歷镜豹，但是如
     * 果你用哈希表的話需要的空間開銷特大，尤其是如果地
     * 圖被劃分得比較細的話蓝牲。
     * 我認為把周圍的頂點變成結(jié)點趟脂，并用標志位把是否在開
     * 放列表中指示出來。
     * 沒辦法例衍，看來只能需要一個輔助空間來換取時間上的高效了昔期。
     * 本算法其實用不著open表，因為已經(jīng)使用二維數(shù)組作為索引
     * 佛玄，所以沒有必要再判斷該結(jié)點在不在open表中了硼一，因為但凡
     * 被加入到open表中的結(jié)點肯定是新結(jié)點，與此相同新結(jié)點在
     * 使用之前也一定先被加入到索引數(shù)組中梦抢。
     * 這個結(jié)點包含的信息是一個比較復雜的結(jié)構(gòu)般贼，所以每個結(jié)點
     * 適合用對象進行封裝。
     * A*算法的關(guān)鍵在于當前結(jié)點的周圍結(jié)點可能和別的已經(jīng)被淘
     * 汰的結(jié)點尤其是前一個結(jié)點的周圍結(jié)點重合。在算法中表現(xiàn)
     * 為新結(jié)點周圍的結(jié)點有一部分已經(jīng)在open表中了哼蛆。對于重疊
     * 的結(jié)點以當前結(jié)點作為中間結(jié)點可能存在更優(yōu)的路徑蕊梧，具體
     * 就是指g值更小。比較的方法是假設(shè)現(xiàn)在比較的是當前結(jié)點的
     * 周圍結(jié)點A腮介，經(jīng)由當前結(jié)點到達A的時候肥矢，A的g值比原來的g
     * 值更小。這就代表更優(yōu)解出現(xiàn)了于是需要改變當前結(jié)點的父指
     * 針到當前結(jié)點的父指針的父指針叠洗。這種情況常見于當前結(jié)點和
     * 它的父結(jié)點以及父父結(jié)點都鄰接橄抹。
     * 排序最好使用小根堆排序，首先是因為它不需要額外空間惕味，其
     * 次它的復雜度是O(nlogn)比較快楼誓。但是它對下標有要求，如
     * 果不想調(diào)整下標的話可以使用快排來調(diào)整名挥。
     * @param sourceArray
     * @param sourcePointX
     * @param sourcePointY
     * @param targetPointX
     * @param targetPointY
     */
    static public void aStar0(int[][] sourceArray,
                              int sourcePointX,
                              int sourcePointY,
                              int targetPointX,
                              int targetPointY) {
        //首先檢查輸入是否合法疟羹。
        // 起點和終點不能越界
        //獲取xy維度。
        int xLength = sourceArray.length;
        int yLength = sourceArray[0].length;
        if (sourcePointX < 0 || sourcePointX >= xLength || targetPointY < 0 || targetPointY >= yLength) {
            System.out.println("起點或終點輸入越界");
            return;
        }
        //其次不能和障礙物重疊
        if (sourceArray[sourcePointX][sourcePointY] == -1 || sourceArray[targetPointX][targetPointY] == -1) {
            System.out.println("與障礙點沖突");
            return;
        }
        //起點和終點不能相等
        if (sourcePointX == targetPointX && sourcePointY == targetPointY) {
            System.out.println("起點和終點相同");
            return;
        }
        //為了把索引的結(jié)點的時間加快到常數(shù)級別禀倔，在這里需要一個和源數(shù)組同等維度的二維數(shù)組榄融。
        VertexObject[][] vertexIndexTable = new VertexObject[xLength][yLength];
        //正向行走是10
        final int obstacle = 10;
        //斜向行走是14
        final int obliqueObstacle = 14;
        //首先把起點和終點放到索引數(shù)組里面去。
        vertexIndexTable[sourcePointX][sourcePointY] = new VertexObject(sourcePointX,sourcePointY);
        vertexIndexTable[sourcePointX][sourcePointY].setPointType(VertexObject.PointType.startPoint);
        vertexIndexTable[sourcePointX][sourcePointY].setG(0);
        vertexIndexTable[sourcePointX][sourcePointY].setH((Math.abs(targetPointX - sourcePointX) + Math.abs(targetPointY - sourcePointY)) * obstacle);
        vertexIndexTable[targetPointX][targetPointY] = new VertexObject(targetPointX,targetPointY);
        vertexIndexTable[targetPointX][targetPointY].setPointType(VertexObject.PointType.endPoint);
        vertexIndexTable[targetPointX][targetPointY].setH(0);
        //現(xiàn)在需要一個數(shù)組救湖，其實它就是open表愧杯。
        // 我也不知道多長合適，于是來個最長的吧鞋既，反正現(xiàn)在電腦內(nèi)存夠用力九。
        int openTableLength = xLength * yLength;
        VertexObject[] openTable = new VertexObject[openTableLength];
        //其實這就是個隊列，但是這個隊列用不著循環(huán)隊列邑闺。
        int front = 0;
        int rear = 0;
        //先把起始點放到open隊列中跌前。
        openTable[rear++] = vertexIndexTable[sourcePointX][sourcePointY];
        //方向數(shù)組，從西北順時針旋轉(zhuǎn)陡舅。
        final int[][] vectorArray = {
                {-1,-1},{0,-1},{1,-1},{1,0},
                {1,1},{0,1},{-1,1},{-1,0}
        };
        //循環(huán)終止的條件是要么open表為空或者終點進入到open表中抵乓。
        while (front < rear && openTable[rear - 1].getPointType() != VertexObject.PointType.endPoint) {
            AStar.sortByHeap(openTable,front,rear - front);
            VertexObject currentObject = openTable[front++];
            currentObject.setPointState(VertexObject.StateType.closedPoint);
            //把它的8個鄰接點一個一個地送入隊列。
            for (int counter = 0;counter < 8;counter++) {
                int adjacentPointX = currentObject.getCoordinateX() + vectorArray[counter][1];
                int adjacentPointY = currentObject.getCoordinateY() + vectorArray[counter][0];
                //如果越界就跳過
                if (adjacentPointX < 0
                        || adjacentPointX >= xLength
                        || adjacentPointY <0
                        || adjacentPointY >= yLength)
                    continue;
                //如果是障礙物就跳過
                if (sourceArray[adjacentPointX][adjacentPointY] == -1)
                    continue;
                //如果該結(jié)點已經(jīng)在close表中了
                if (vertexIndexTable[adjacentPointX][adjacentPointY] != null
                        && vertexIndexTable[adjacentPointX][adjacentPointY].getPointState()
                        == VertexObject.StateType.closedPoint)
                    continue;
                //如果是終點那就結(jié)束循環(huán)因為此時已經(jīng)找到了路徑靶衍，因為此時是終點灾炭。
                if (adjacentPointX == targetPointX
                        && adjacentPointY == targetPointY) {
                    vertexIndexTable[targetPointX][targetPointY].setPrePointer(currentObject);
                    openTable[rear++] = vertexIndexTable[targetPointX][targetPointY];
                    break;
                }
                if (vertexIndexTable[adjacentPointX][adjacentPointY] == null) {
                    VertexObject newNode = new VertexObject(adjacentPointX,adjacentPointY);
                    vertexIndexTable[adjacentPointX][adjacentPointY] = newNode;
                    int orginalG = currentObject.getG();
                    int newG = (vectorArray[counter][0] * vectorArray[counter][1] == 0)?
                            (orginalG + obstacle):(orginalG + obliqueObstacle);
                    newNode.setG(newG);
                    int hLength = (Math.abs(targetPointX - adjacentPointX) +
                            Math.abs(targetPointY - adjacentPointY)) * obstacle;
                    newNode.setH(hLength);
                    newNode.setPrePointer(currentObject);
                    openTable[rear++] = newNode;
                } else {
                    //剩下的就是正常的情況了。如果這個點已經(jīng)在open表中的話
                    int orginalG = vertexIndexTable[adjacentPointX][adjacentPointY].getG();
                    int newG = (vectorArray[counter][0] * vectorArray[counter][1] == 0)?
                            (orginalG + obstacle):(orginalG + obliqueObstacle);
                    if (newG < orginalG) {
                        vertexIndexTable[currentObject.getCoordinateX()]
                                [currentObject.getCoordinateY()].setPrePointer(currentObject.getPrePointer());
                        vertexIndexTable[currentObject.getCoordinateX()]
                                [currentObject.getCoordinateY()].setG(newG);
                        AStar.sortByHeap(openTable,front,rear - front);
                    }
                }
            }
        }
        //對原數(shù)組進行賦值
        if (front < rear) {
            VertexObject currentPointer = vertexIndexTable[targetPointX][targetPointY];
            while (currentPointer != null) {
                if (currentPointer.getPointType() == VertexObject.PointType.startPoint)
                    sourceArray[currentPointer.getCoordinateX()][currentPointer.getCoordinateY()] = 1;
                else if (currentPointer.getPointType() == VertexObject.PointType.endPoint)
                    sourceArray[currentPointer.getCoordinateX()][currentPointer.getCoordinateY()] = 2;
                else sourceArray[currentPointer.getCoordinateX()][currentPointer.getCoordinateY()] = 3;
                currentPointer = currentPointer.getPrePointer();
            }
        }
    }

    /**
     * 小頂堆排序颅眶，堆排序只能從0開始蜈出，要不然不正確。
     * @param openTable
     * @param startIndex
     * @param sortLength
     */
    static private void sortByHeap(VertexObject[] openTable,int startIndex,int sortLength) {
        VertexObject[] tempArray = new VertexObject[sortLength];
        for (int counter = 0,counter0 = startIndex;counter < sortLength;counter++,counter0++)
            tempArray[counter] = openTable[counter0];
        for (int counter = sortLength / 2 - 1;counter > -1;counter--)
            adjustToSmallHeap(tempArray,counter,sortLength);
        for (int counter = 0,counter0 = startIndex;counter < sortLength;counter++,counter0++)
            openTable[counter0] = tempArray[counter];
    }

    /**
     * 堆調(diào)整
     * @param sourceArray
     * @param rootIndex
     * @param adjustLength
     */
    static private void adjustToSmallHeap(VertexObject[] sourceArray,int rootIndex,int adjustLength) {
        for (int counter = rootIndex;counter < adjustLength / 2;) {
            int leftChildIndex = 2 * counter + 1;
            int rightChildIndex = leftChildIndex + 1;
            int smallerPointer = leftChildIndex;
            if (rightChildIndex < adjustLength &&
                    sourceArray[leftChildIndex].getF() >
                            sourceArray[rightChildIndex].getF())
                smallerPointer = rightChildIndex;
            if (sourceArray[counter].getF() > sourceArray[smallerPointer].getF()) {
                VertexObject tempElement = sourceArray[counter];
                sourceArray[counter] = sourceArray[smallerPointer];
                sourceArray[smallerPointer] = tempElement;
                counter = smallerPointer;
            } else break;
        }
    }
}

public class VertexObject {
    public enum PointType{startPoint,endPoint,reachablePoint};
    public enum StateType{availablePoint,closedPoint};
    //這個就是A*算法中說的父結(jié)點
    private VertexObject prePointer = null;
    private int coordinateX = -1;
    private int coordinateY = -1;
    private StateType pointState = StateType.availablePoint;
    private PointType pointType = PointType.reachablePoint;
    private int g = 0;
    private int h = 0;
    private int f = 0;

    public VertexObject(int coordinateX, int coordinateY) {
        this.coordinateX = coordinateX;
        this.coordinateY = coordinateY;
    }

    public StateType getPointState() {
        return pointState;
    }

    public void setPointState(StateType pointState) {
        this.pointState = pointState;
    }

    public int getCoordinateX() {
        return coordinateX;
    }

    public int getCoordinateY() {
        return coordinateY;
    }

    public int getG() {
        return g;
    }

    public void setG(int g) {
        this.g = g;
        f = g + h;
    }

    public void setH(int h) {
        this.h = h;
        f = g + h;
    }

    public int getF() {
        f = g + h;
        return f;
    }

    public void setPointType(PointType pointType) {
        this.pointType = pointType;
    }

    public PointType getPointType() {
        return pointType;
    }

    public VertexObject getPrePointer() {
        return prePointer;
    }

    public void setPrePointer(VertexObject prePointer) {
        this.prePointer = prePointer;
    }
}