如果你玩過MMOARPG游戲，比如魔獸，你會發現人物行走會很有趣，為了模仿人物行走的真實體驗，他們會選擇最近路線達到目的地，期間會避開高山或者湖水，繞過箱子或者樹林，直到走到你所選定的目的地。

這種看似尋常的尋路在程序實現起來就需要一定的尋路算法來解決，如何在最短時間內找到一條路徑最短的路線，這是尋路算法首先要考慮的問題。

在這篇文章中我們會循序漸進來講解尋路算法是如何演進的，你會看到一種算法從簡單到高效所遇到的問題，以及精進的過程，帶著問題來閱讀，理解更快。

本篇主要包含以下內容:

1、圖

2、寬度***搜索,

3、Dijkstra 算法，

4、貪心算法，

****搜索算法,

6、B*搜索算法,

1、游戲中的人物是如何尋路的

你所看到的人物行走方式: 

開發人員實際所看到的方式: 

或者是這種: 

對于一張地圖，開發人員需要通過一定的方案將其轉換為數據對象，常見的就是以上這種把地圖切個成網格，當然了地圖的劃分方式不一定非要用網格這種方式，采用多邊形方式也可以，這取決于你的游戲，一般情況下，同等面積的地圖采用更少的頂點，尋路算法會更快。尋路中常用的數據結構就是圖，以下我們先來了解一下。

 2、圖

在講尋路算法之前我們先了解一種數據結構—圖，數據結構是我們進行算法運算的基礎，好的數據結構除了方便我們理解算法，還會提升算法的效率。網格某種意義上也是圖的演變，只是圖形變了而已,理解了圖的概念可以幫助我們更好理解尋路算法。

圖的基本定義:

圖的正式表達式是G=(V,E),V是代表頂點的集合，E和V是一種二元關系，可以理解為邊，比如有條邊從頂點U到頂點V結束,那么E可以用(u,v)來表示這條邊。具體的有向圖和無向圖，也是邊是否有方向來區分。為了方便理解，我們文中所有的數據演示都是基于網格地圖來進行講解，以下是幾種關系梳理，以A為頂點，BCDE為子頂點,我們可以把每個格子也看是一個頂點。

3、搜索算法

對一個圖進行搜索意味著按照某種特定的順序依次訪問其頂點。對于多圖算法來說，廣度優先算法和深度優先搜索算法都十分重要，因為它們提供了一套系統地訪問圖數據結構的方法。我們著重講解廣度優先搜索算法。

深度優先搜索

深度優先算法和最小路徑關系不大，我們只簡單介紹。

深度優先搜索算法（簡稱DFS）是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。

 

廣度優先搜索

廣度優先搜索算法（簡稱BFS）又稱為寬度優先搜索，是一種圖形搜索算法，很適合用來探討最短路徑的***個模型，我們會順著這個思路往下講。

BFS是一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以找尋結果。換句話說，它并不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止它的步驟如下:

- 首先將根節點放入隊列中。

- 從隊列中取出***個節點，并檢驗它是否為目標。

- 如果找到目標，則結束搜尋并回傳結果。

- 否則將它所有尚未檢驗過的直接子節點（鄰節點）加入隊列中。

- 若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋并回傳“找不到目標”。

網格:

我們看下代碼(js)：

var frontier = new Array();

frontier.put(start);

var visited = new Array();

visited[start] = true;



while(frontier.length>0){

    current = frontier.get();

     //查找周圍頂點

    for(next in graph.neighbors(current)){

        var notInVisited = visited.indexOf(next)==-1;

        //沒有訪問過

        if(notInVisited) {

            frontier.put(next);

            visited[next] = true;

          }

       }
}

從上可以發現，寬度搜索就是以開始頂點為起點，訪問其子節點（在網格中是訪問周圍節點），然后不斷的循環這個過程，直到找到目標，這種算法比較符合常規邏輯，把所有的的頂點全部枚舉一遍。不過這種方式也有很明顯的缺點。

缺陷:

1、效率底下， 時間復雜度是:T(n) = O(n^2)

2、每個頂點之間沒有權值，無法定義優先級，不能找到***路線。比如遇到水域需要繞過行走，在寬度算法里面無法涉及。

如何解決這個問題？我們來看Dijkstra 算法。

4、Dijkstra 算法

寬度優先搜索算法，解決了起始頂點到目標頂點路徑規劃問題，但不是***以及合適的，因為它的邊沒有權值（比如距離），路徑無法進行估算比較***解。為何權值這么重要，因為真實環境中，2個頂點之間的路線并非一直都是直線，需要繞過障礙物才能達到目的地，比如森林，湖水，高山，都需要繞過而行，并非直接穿過。

比如我采用寬度優先算法，遇到如下情況，他會直接穿過障礙物（綠色部分 ），明顯這個不是我們想要的結果:

 

解決痛點:

尋找圖中一個頂點到另一個頂點的最短以及最小帶權路徑是非常重要的提煉過程。為每個頂點之間的邊增加一個權值，用來跟蹤所選路徑的消耗成本，如果位置的新路徑比先前的***路徑更好，我們將添加它，規劃到新的路線中。

Dijkstra 算法基于寬度優先算法進行改進，把當前看起來最短的邊加入最短路徑樹中 ，利用貪心算法計算并最終能夠產生***結果的算法。具體步驟如下:

1、每個頂點都包含一個預估值cost(起點到當前頂點的距離)，每條邊都有權值v ，初始時，只有起始頂點的預估值cost為0，其他頂點的預估值d都為無窮大 ∞。

2、查找cost值最小的頂點A，放入path隊列

3、循環A的直接子頂點，獲取子頂點當前cost值命名為current_cost，并計算新路徑new_cost，new_cost=父節點A的cost+v(父節點到當前節點的邊權值),如果new_cost<current_cost,當前頂點的cost=new_cost

4、重復2，3直至沒有頂點可以訪問.

我們看下圖例:

我們看下代碼(js)：

var frontier = new PriorityQueue();

frontier.put(start);

path = new Array();

//每個頂點路徑消耗

cost_so_far = new Array();



path[start] = 0;

cost_so_far[start] = 0



while(frontier.length>0){

   current = frontier.get();


   if current == goal:

      break

       //查找周圍節點

    for(next in graph.neighbors(current)){

        var notInVisited = visited.indexOf(next)==-1;

        var new_cost = cost_so_far[current] + graph.cost(current, next);

           //沒有訪問過或者路徑更近

        if(notInVisited ||  new_cost < cost_so_far[next]) {

            cost_so_far[next] = new_cost;

            priority = new_cost;

            frontier.put(next, priority);

            path[next] = current;

          }

       }

}

 

我們看到雖然Dijkstra 算法 雖然相對于寬度優先搜索更加智能，基于cost_so_far ，可以規避路線比較長或者無法行走的區域，但依然會存在盲目搜索的傾向，我們在地圖中常見的情況是查找目標和起始點的路徑，具有一定的方向性，而Dijkstra 算法從上述的圖中可以看到，也是基于起點向子節點全方位擴散。

缺點:

1、運行時間復雜度是:T(n) = O(V^2)，其中V為頂點個數。效率上并不高

2、目標查找不具有方向性

如何解決讓搜索不是全盤盲目瞎找？我們來看Greedy Best First Search算法（貪婪***優先搜索）。  

5、貪婪***優先搜索

在Dijkstra算法中，我已經發現了其最終要的缺陷，搜索存在盲目性。在這里，我們只針對這個痛點，采用貪婪***優先搜索來解決。如何解決？我們只需稍微改變下觀念即可，在Dijkstra算法中，優先隊列采用的是，每個頂點到起始頂點的預估值來進行排序。在貪婪***優先搜索中 ，

解決痛點:

我們采用每個頂點到目標頂點的距離進行排序。一個采用離起始頂點的距離來排序，一個采用離目標頂點距離排序（離目標的遠近排序）

哪個更快？我們看下圖(左邊寬度優先，右邊貪婪優先):

從上圖中我們可以明顯看到右邊的算法（貪婪***優先搜索 ）尋找速度要快于左側，雖然它的路徑不是***和最短的，但障礙物最少的時候，他的速度卻足夠的快。這就是貪心算法的優勢，基于目標去搜索，而不是完全搜索。

我們看下算法(js)：

frontier = new PriorityQueue();

frontier.put(start, 0)

came_from = new Array();

came_from[start] = 0;



while(frontier.length>0){

    current = frontier.get()



   if current == goal:

      break



       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

           //沒有訪問過

        if(notInVisited ) {

            //離目標的距離 ，距離越近優先級越高

             priority = heuristic(goal, next);

             frontier.put(next, priority);

             came_from[next] = current;

          }

       }

}



function heuristic(a, b){

    //離目標的距離

   return abs(a.x - b.x) + abs(a.y - b.y)

}

缺點:

1.路徑不是最短路徑，只能是較優

如何在搜索盡量少的頂點同時保證最短路徑？我們來看A*算法。

 6、A*算法

從上面算法的演進，我們逐漸找到了最短路徑和搜索頂點最少數量的兩種方案，Dijkstra 算法和 貪婪***優先搜索。那么我們有沒有可能汲取兩種算法的優勢，令尋路搜索算法即便快速又高效？

答案是可以的，A*算法正是這么做了，它吸取了Dijkstra 算法中的cost_so_far，為每個邊長設置權值，不停的計算每個頂點到起始頂點的距離，以獲得最短路線，同時也汲取貪婪***優先搜索算法中不斷向目標前進優勢，并持續計算每個頂點到目標頂點的距離，以引導搜索隊列不斷想目標逼近，從而搜索更少的頂點，保持尋路的高效。

解決痛點:

A*算法的優先隊列排序方式基于F值:

F=cost(頂點到起始頂點的距離 )+heuristic(頂點到目標頂點的距離 )

我們看下算法(js)：

var frontier = new PriorityQueue();

frontier.put(start);

path = new Array();

cost_so_far = new Array();

path[start] = 0;

cost_so_far[start] = 0

while(frontier.length>0){

    current = frontier.get()

   if current == goal:

      break

       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

           var new_cost = cost_so_far[current] + graph.cost(current, next);

           //沒有訪問過而且路徑更近

        if(notInVisited ||  new_cost < cost_so_far[next]) {

              cost_so_far[next] = new_cost

              //隊列優先級= new_cost(頂點到起始頂點的距離 )+heuristic(頂點到目標頂點的距離 )

            priority = new_cost + heuristic(goal, next)

            frontier.put(next, priority)

            path[next] = current

          }

       }

}

function heuristic(a, b){

    //離目標的距離

   return abs(a.x - b.x) + abs(a.y - b.y)

}

以下分別是Dijkstra算法，貪心算法，以及A*算法的尋路雷達圖，其中格子有數字標識已經被搜索了，可以對比下三種效率:

 7、B*算法

B*算法是一種比A*算法更高效的算法， 適用于游戲中怪物的自動尋路，其效率遠遠超過A*算法，經過測試，效率是普通A*算法的幾十上百倍。B*算法不想介紹了，自己去google下吧，

通過以上算法不斷的演進，我們可以看出每一種算法的局限，以及延伸出的新算法中出現的解決方式，希望方便你的理解。