尋路演算法有哪些

A. 星際爭霸2的尋路演算法思路是怎樣的

首先地圖整體開始前，會用多層可達矩陣演算法，算出路徑關鍵點
2，創建關鍵節點可達矩陣
3，再每個兵當前位置對關鍵節點進行路徑計算
這樣可以最小化資源佔用就可以完成路徑計算了，高數的離散數學，挺容易解的

B. 即時戰略游戲中實用的尋路演算法都有哪些

Potential Field，它是將地圖用一個矩陣來表示，矩陣儲存著大小不同的電勢（整數）。例如，正電勢表示吸引，負電勢表示排斥。而游戲中的單位本身是一個負電勢，游戲以一個數組儲存所有單位的電勢和位置。這樣，在計算一個單位需要怎麼從A點到B點時，我們可以用一個新的矩陣將目的地B點設成正電勢，並以不同方式（如圓形、四邊形等）輻射開來，離B點越遠電勢越低，直到0。然後將地圖矩陣，目的地矩陣，和所有單位數組的電勢相加，得出一個新的、反映當前游戲世界的電勢矩陣，然後單位再選擇周圍所有電勢點中的最高電勢點去走。不過這里坑很多，因為它本質上是Greedy Algorithm，所以它未必能找出解。然而在某些設定中，例如在沒有過於復雜地形，並且需要單位自動不相互覆蓋的情況下，Potential Field還是可以完成任務。

Flocking Behavior，在對於一大群單位的尋路，計算量是很大的，而且往往會有很多的重復，這些都是可以避免的。如果單位的移動是利用Steering Behavior來實現的話，那麼就可以為其中一個單位，稱之為Leader，計算路徑（例如用導航網格），然後其他單位按照以下Flocking原則來移動：1. 分離，避開相鄰單位2. 一致，和整體的移動方向一致，這里應該是Leader的移動方向3. 聚合，向整體的平均位置靠攏這樣的話，就可以降低尋路的計算量，並且得到更加真實的群體單位行進效果。

C. A星尋路演算法和Unity自帶的尋路相比有什麼優勢

在理解Navigation的時候，首先要明確兩個知識點：

AStar：AStar是路點尋路演算法中的一種，同時AStar不屬於貪婪演算法，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。AStar是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。

性能和內存佔用率都還行，和啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。

A Star一般使用場景：

• 策略游戲的策略搜索

• 方塊格子游戲中的格子尋路

Navigation：網格尋路演算法，嚴格意義上它屬於」拐角點演算法」，效率是比較高的，但是不保證最優解演算法。Navigation相對來說消耗內存更大，性能的話還不錯。

Navigation一般使用場景：

• 游戲場景的怪物尋路

• 動態規避障礙

它們二者事件的實現方式和原理都不同。

AStar的話，

D. 夢幻西遊自動尋路的尋路演算法怎麼算

A*尋路演算法 A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}

E. 有哪些應用於移動機器人路徑規劃的演算法

機器人家上了解到，在二維二值地圖（FREE or OCCUPIED）場景下進行路徑規劃的方法。我看之前有同學在回答的時候配上了這幅圖：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

兩大類：
1. 完備的（complete)
2. 基於采樣的（sampling-based）又稱為概率完備的

一 完備的規劃演算法

A*演算法

所謂完備就是要達到一個systematic的標准，即：如果在起始點和目標點間有路徑解存在那麼一定可以得到解，如果得不到解那麼一定說明沒有解存在。
這一大類演算法在移動機器人領域通常直接在occupancy grid網格地圖上進行規劃（可以簡單理解成二值地圖的像素矩陣）以深度優先尋路演算法、廣度優先尋路演算法、Dijkstra(迪傑斯特拉)演算法為始祖，以A*演算法(Dijstra演算法上以減少計算量為目的加上了一個啟發式代價)最為常用，近期的Theta*演算法是在A*演算法的基礎上增加了line-of-sight優化使得規劃出來的路徑不完全依賴於單步的柵格形狀（答主以為這個演算法意義不大，不就是規劃了一條路徑再簡單平滑了一下么）。
完備的演算法的優勢在與它對於解的捕獲能力是完全的，但是由此產生的缺點就是演算法復雜度較大。這種缺點在二維小尺度柵格地圖上並不明顯，但是在大尺度，尤其是多維度規劃問題上，比如機械臂、蛇形機器人的規劃問題將帶來巨大的計算代價。這樣也直接促使了第二大類演算法的產生。

二 基於采樣的規劃演算法

RRT-connect演算法
這種演算法一般是不直接在grid地圖進行最小柵格解析度的規劃，它們採用在地圖上隨機撒一定密度的粒子來抽象實際地圖輔助規劃。如PRM演算法及其變種就是在原始地圖上進行撒點，抽取roadmap在這樣一個拓撲地圖上進行規劃；RRT以及其優秀的變種RRT-connect則是在地圖上每步隨機撒一個點，迭代生長樹的方式，連接起止點為目的，最後在連接的圖上進行規劃。這些基於采樣的演算法速度較快，但是生成的路徑代價（可理解為長度）較完備的演算法高，而且會產生「有解求不出」的情況（PRM的逢Narrow space卒的情況）。這樣的演算法一般在高維度的規劃問題中廣泛運用。

三 其他規劃演算法
除了這兩類之外還有間接的規劃演算法：Experience-based（Experience Graph經驗圖演算法）演算法：基於經驗的規劃演算法，這是一種存儲之前規劃路徑，建立知識庫，依賴之進行規劃的方法，題主有興趣可以閱讀相關文獻。這種方法犧牲了一定的空間代價達到了速度與完備兼得的優勢。此外還有基於廣義Voronoi圖的方法進行的Fast-marching規劃，類似dijkstra規劃和勢場的融合，該方法能夠完備地規劃出位於道路中央，遠離障礙物的路徑。答主最近也在研究此類演算法相關的工作。

APF（人工勢場）演算法

至於D* 、勢場法、DWA(動態窗口法)、SR-PRM屬於在動態環境下為躲避動態障礙物、考慮機器人動力學模型設計的規劃演算法。

F. 從頭理解JPS尋路演算法

本文的思路受到博客： http://blog.sina.com.cn/s/blog_4a5c75d40102wo5l.html
和論文： http://www.doc88.com/p-6099778647749.html 的啟發和借鑒。
JPS(jump point search)演算法實際上是對A 尋路算李祥桐法的一個改進，即在擴展搜索節點時，提出了更優化的策略，A 在擴展節點時會把節點所有鄰居都考慮進去，這樣openlist中點的數量會很多，搜索效率較慢。JPS演算法通過尋找跳點的方式，排除了大量不感興趣的點，減少了openlist中搜索的點的數量，速度大大提高。

水平(垂直)搜索：如圖右邊部分描述，點1和4如果經過x到達，還不如從點p(x)到達，所以不用考慮點1,4，同理繼續向右搜索時，點2,5和點3,6，都是類似的情況，直到遇到黑色的障礙，沒有發現感興趣的點，x處水平方向搜索完成，垂直方向搜索類似。如圖左邊部分描述，在點x處向右搜索至點y時，點y有一個強迫鄰居(點7)，因此y是從點x處沿水平方向搜索的一個跳點，需要將y加入到openlist中。水平搜索結束。

對角搜索：斜向搜索時，需要先在當前點的水平和垂直方向搜索一下，看能否找到感興趣的點，如果找到，則將當前點加到openlist，結束斜向搜索，如果找不到，則繼續宴卜斜向多走一步，繼續，直到找到感興趣的點或者斜向方向遇到障礙。

一條完整路線的搜索過程：

搜索演算法：

下面兩張對比圖，摘自上面的論文，可以看出，JPS演算法實在優秀。

github鏈接

上圖中紅色塊為節點x，基於前節點為P(x)的情況下的自然鄰居節點。而被迫鄰居則是圖中綠色的方塊（其對稱情況未畫出）。x被迫鄰居包含三層隱藏含義：首先被迫鄰居的位置是基於P(x)、x、阻擋塊的相對關系定的，如第三個圖所示，如果第三個圖中，P(x)的位置在節點6的位置，那麼綠色方塊就不是x的被迫鄰居了。其次，被迫鄰居一點是考察非自然鄰居的節點。最後被迫鄰居一定是P(x)經過x到達才能取得最短路徑的點。

起點S，終點T，黑色塊為阻擋黃色塊為跳點，紅色箭頭是搜索方向，但是沒有找到跳點，綠色箭頭表示找到跳點。橫坐標A-N，縱坐標1-10。

起始位置S，將A10加入openlist里，開始演算法流程。
從openlist里取出代價最小的節點(現在為S)，當前節點沒有方向，所以需要搜索8個方向，只有右上方B9點是跳點。因為根據跳點定義iii，斜向搜索時，需要在兩個分量方向查找跳點，右方是牆壁，略過，上方B8點有強迫鄰居點C7，所以B8是跳點（根據跳點定義ii），所以B9是跳點。將B9加入openlist里。A10處理完後，將其從openlist中移除，加入closelist里。

從openlist中取出B9點，該點的父親是S，所以搜索方向為右斜上，需要在右斜上，右方，上方搜索跳點，只有B8滿足要求，將B8加入openlist。處理完B9點將其移到closelist。

從openlist取出B8點，該點搜索哪坦方向為上，B8有被鄰居C7點，在斜上方搜索跳點，可以看出D8是C7的被迫鄰居，所以C7是跳點，B8處繼續向上搜索結束。

從openlist中取出C7點。需要搜索右上，右，上三個方向。水平搜索時發現被迫鄰居D8，加入openlist。右上搜索時發現跳點G3（因其在上方搜索時發現具有被迫鄰居節點的G2），將G3加入openlist。C7點處理結束。

取出G3點（為啥是G3，而不是D8點呢，因為從總代價來說G3比D8更小，總代價=已經走過的距離 + 估值，估值可採用曼哈頓距離或者高斯距離），需要搜索右上，右，上三個方向。向上搜索到跳點G2。

其餘點路徑在圖上標注，就不再重復了。

(1) 若current方向是直線
i. 如果current左後方不可走且左方可走，則沿current左前方和左方尋找跳點。
ii. 如果current當前方向可走，則沿current方向尋找跳點。
iii. 如果current右後方不可走且右方可走，則沿current右前方和右方尋找跳點。
(2) 若current方向是斜線
i. 如果當前方向的水平分量可走，則沿current方向的水平分量方向尋找跳點。
ii. 如果當前方向可走，沿current方向尋找跳點。
iii. 如果當前方向的垂直分量可走，則沿current方向的垂直分量方向尋找跳點。

上述演算法流程是建立在斜向不可穿過阻擋基礎上。

G. 尋路演算法和邏輯演算法之間異同點有哪些

尋路演算法和邏輯演算法之間異同點：
尋路演算法也可以通過深度優先遍歷 dfs 實現，尋找圖 graph 從起始 s 點到其他點的路徑稿頃，在上一小節的實現類中添加全局變數 from數組記錄路徑，from[i] 表示查找的路徑上i的上一個節點。
邏輯演算法又稱布爾運算，通常用來鍵旦陸測試真假值，由於布遲祥爾在符號邏輯運算中的特殊貢獻，很多計算機語言中將邏輯運算稱為布爾運算，用來判斷是否該離開循環或繼續執行循環內的指令，並由二維邏輯運算發展到三維圖形的邏輯運算。