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

這種看似尋常的尋路在程序?qū)崿F(xiàn)起來就需要一定的尋路算法來解決，如何在最短時間內(nèi)找到一條路徑最短的路線，這是尋路算法首先要考慮的問題。

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

本篇主要包含以下內(nèi)容:

1、圖

2、寬度***搜索,

3、Dijkstra 算法，

4、貪心算法，

****搜索算法,

6、B*搜索算法,

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

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

開發(fā)人員實際所看到的方式: 

或者是這種: 

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

 2、圖

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

圖的基本定義:

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

3、搜索算法

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

深度優(yōu)先搜索

深度優(yōu)先算法和最小路徑關(guān)系不大，我們只簡單介紹。

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

 

廣度優(yōu)先搜索

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

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

- 首先將根節(jié)點放入隊列中。

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

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

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

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

網(wǎng)格:

我們看下代碼(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;

          }

       }
}

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

缺陷:

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

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

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

4、Dijkstra 算法

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

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

 

解決痛點:

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

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

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

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

3、循環(huán)A的直接子頂點，獲取子頂點當前cost值命名為current_cost，并計算新路徑new_cost，new_cost=父節(jié)點A的cost+v(父節(jié)點到當前節(jié)點的邊權(quán)值),如果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

       //查找周圍節(jié)點

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

缺點:

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

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

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

5、貪婪***優(yōu)先搜索

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

解決痛點:

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

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

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

我們看下算法(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 ) {

            //離目標的距離 ，距離越近優(yōu)先級越高

             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.路徑不是最短路徑，只能是較優(yōu)

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

 6、A*算法

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

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

解決痛點:

A*算法的優(yōu)先隊列排序方式基于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

              //隊列優(yōu)先級= 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*算法的尋路雷達圖，其中格子有數(shù)字標識已經(jīng)被搜索了，可以對比下三種效率:

 7、B*算法

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

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