簡介：搜索區(qū)域
綠色是起點A，紅色是終點B，藍(lán)色的是障礙物強(qiáng)。假設(shè)我們要從A點走到B點。
假設(shè)整張地圖是搜索區(qū)域，那么把整張地圖劃分為方塊狀的網(wǎng)格，這樣便簡化了搜索區(qū)域，如此便能用二維數(shù)組來表示整張地圖。而每一個網(wǎng)格分有可行走和不可行走兩個狀態(tài)。通過從A到B走那些網(wǎng)格來確定路徑。
開始搜索
上一步我們將地圖簡化為可管理的二維數(shù)組，下一步就是搜索最短路徑。搜索方法有點類似與八連通種子填充算法。做法是從A點開始，檢查八連通的網(wǎng)格，以此遞歸向外搜索直到找到目標(biāo)。
搜索的步驟如下：
- 創(chuàng)建兩個列表，一個是“打開列表”用于存放將要進(jìn)行搜索，但還沒搜索過的網(wǎng)格。另一個是“關(guān)閉列表”用于存放已經(jīng)搜索過的網(wǎng)格。
- 從起點A開始，將其添加到要進(jìn)行搜索的“打開列表中”。
- 查看起點附近八連通的所有可行走的網(wǎng)格，這里要忽略掉添加到“關(guān)閉列表”中的網(wǎng)格，已經(jīng)搜索過的網(wǎng)格不必再次搜索，并且將這些網(wǎng)格的父網(wǎng)格設(shè)置A，然后將這些網(wǎng)格添加到“打開列表”中。
- 從“打開列表”中刪除起始網(wǎng)格A，并將其添加到“關(guān)閉列表中”。
這時得到如下圖所示的內(nèi)容，其中綠色的方塊是起始網(wǎng)格，帶有淺藍(lán)色輪廓的是已經(jīng)添加到關(guān)閉列表中的網(wǎng)格，帶有淺綠色輪廓的是已經(jīng)添加到打開列表中的網(wǎng)格并且這些網(wǎng)格都有一個灰色的指針指向其父網(wǎng)格。
接下來，只要選擇打開列表中的一個網(wǎng)格，重復(fù)執(zhí)行A點執(zhí)行過的步驟就可以了。那么我們該選擇哪一個方塊作為下一個進(jìn)行八連通搜索的網(wǎng)格呢？看下一步
路徑評分
在進(jìn)行下一步選擇時，確定使用哪個方塊，需要計算一個路徑評分或說時代價。公式如下：
F = G + H
其中
- G是從起點到當(dāng)前網(wǎng)格的移動代價，或者說是距離。
- H是從當(dāng)前網(wǎng)格到終點的移動代價或距離。
- F為G和H的和，表示當(dāng)前網(wǎng)格的總代價。
為了方便計算，我們將兩個水平或垂直相鄰網(wǎng)格的移動代價設(shè)為10，而對角線相鄰的網(wǎng)格的移動代價設(shè)為14。因為如果以1為水平或垂直移動代價，那么對角線的移動代價為√2，顯然這是不利于計算機(jī)計算的。
繼續(xù)搜索
接下來要從“打開列表”中選擇一個F最低的網(wǎng)格進(jìn)行下一步的搜索。
在經(jīng)歷過第一輪的搜索后，我們在“打開列表”中存放了8個網(wǎng)格，其中F最低的為右邊的網(wǎng)格，所以我們選擇這個網(wǎng)格進(jìn)行下一步的搜索。
- 將這個網(wǎng)格從“打開列表”中刪除并添加到“關(guān)閉列表中”
- 其右邊的網(wǎng)格是障礙物，所以忽略其右邊的網(wǎng)格。其左邊的網(wǎng)格是開始點，已經(jīng)在刪除列表中了，所以也忽略。此時只剩上、下、斜左上和斜左下四個網(wǎng)格。
- 計算這四個網(wǎng)格的G值，發(fā)現(xiàn)從起點到當(dāng)前網(wǎng)格再走向這四個網(wǎng)格中的任何一個點，其G值都比從起點直接走向這些點大。所以我們對這四個網(wǎng)格不做任何操作。而且這四個網(wǎng)格已經(jīng)在“打開列表”中，所以我們也不必再次添加。（而當(dāng)經(jīng)過此網(wǎng)格的G值比之前的G值低時，要更新其G值，并將其父網(wǎng)格設(shè)置為此網(wǎng)格）
- 此時“打開列表”中只剩下7個網(wǎng)格。
下一步，我們從這7個網(wǎng)格中再找一個F值最小的網(wǎng)格進(jìn)行下一步的搜索。這時我們發(fā)現(xiàn)斜右上和斜右下的F值一樣，那么我們選擇哪個進(jìn)行下一步呢？這要取決于你的排序算法，當(dāng)然這不重要，但是出于速度考慮，可以選擇最后一個添加到“打開列表”的網(wǎng)格。。
所以，我們選擇再起點右下方的網(wǎng)格。
這一次，當(dāng)進(jìn)行八連通搜索時，右邊是墻，上邊的兩個網(wǎng)格已經(jīng)在“關(guān)閉列表”中了，因此忽略這四個網(wǎng)格。這里我們也忽略了墻下方的網(wǎng)格（這是可選的，也可以視為墻下方的網(wǎng)格可以通過，這取決于你要不要選擇從墻的切角過去）。
剩下的五個網(wǎng)格中，當(dāng)前網(wǎng)格下方的兩個網(wǎng)格沒有在“打開列表”中，因此將其添加進(jìn)去并且將當(dāng)前網(wǎng)格設(shè)置為這兩個網(wǎng)格的父網(wǎng)格。然后計算剩下四個網(wǎng)格的G值。接下來一直重復(fù)這個過程就可以了。
步驟摘要
- 將起始網(wǎng)格添加到“開始列表”中。
- 將網(wǎng)格從“打開列表”中刪除并將其添加到“關(guān)閉列表中”。
- 檢查所有相鄰的網(wǎng)格，忽略障礙、已經(jīng)在“關(guān)閉列表”和其他不可行走的網(wǎng)格。如果他們不在“打開列表”中，則將其添加到列表中設(shè)置其父網(wǎng)格為此網(wǎng)格，計算經(jīng)歷此網(wǎng)格到其的G值。如果在“打開列表中”，則計算經(jīng)歷此網(wǎng)格到其的G值，若G值更小，則更新父網(wǎng)格和G值及F值。
- 重復(fù)以下步驟：
- 在“打開列表”中查找F值最低的網(wǎng)格，設(shè)置為當(dāng)前網(wǎng)格。
- 將其從“打開列表”刪除，添加到“關(guān)閉列表”
- 搜索其八連通網(wǎng)格，忽略障礙、已添加到“關(guān)閉列表”的和其他不可行的網(wǎng)格。
- 對于這些網(wǎng)格，將其添加到“打開列表”中并計算其G值，然后根據(jù)G值設(shè)置父網(wǎng)格和F值。
- 選擇F值最低的進(jìn)行下一次搜索。
廣度優(yōu)先算法
廣度優(yōu)先算法是最簡單的尋路算法，算法執(zhí)行的結(jié)果是獲得從地圖上任意一點S到其他所有可達(dá)點的最短路徑，這里只考慮上下左右四方向行走的情況，算法流程非常容易理解：
- 設(shè)定搜索起點S，放入openList中；
- 判斷openList是否為空，若為空，搜索結(jié)束；若不為空，拿出openList中的第一個節(jié)點G；
- 遍歷G的上下左右四個相鄰節(jié)點N1-N4，對每個節(jié)點N，如果N不在openList或closeList中，那么令N的父節(jié)點為G，將N放入openList中；如果N已經(jīng)在openList或closeList中，跳過不處理；
-
將G放入closeList中，重復(fù)步驟2.
Dijkstra算法
可以視為在A*算法中，只考慮G值而不考慮H。
在地圖內(nèi)的每個區(qū)塊移動消耗不同時，Dijkstra算法可以非常方便的找出從地圖上某個起始區(qū)塊到其他所有可達(dá)區(qū)塊的最短路徑，這里仍然只考慮上下左右四個方向移動的情況，算法流程如下：
說明：起始區(qū)塊記作S，從S到當(dāng)前區(qū)塊G的總移動消耗記作CG，優(yōu)先隊列openList中數(shù)據(jù)為(G,CG)（區(qū)塊，S到當(dāng)前區(qū)塊總移動消耗）,區(qū)塊G自身移動消耗記作ZG。
- 設(shè)定起始區(qū)塊S，將區(qū)塊S和總移動消耗C=0（記作(S,0)）放入openList，其中openList是一個優(yōu)先隊列(PriorityQueue)，總移動消耗C越低優(yōu)先級越高；
- 判斷openList是否為空，如果是空，算法結(jié)束；否則，從openList中拿出優(yōu)先級最高的區(qū)塊G；
- 遍歷G的上下左右四個相鄰區(qū)塊N1-N4，對每個區(qū)塊N，如果N已經(jīng)在closeList中，忽略該區(qū)塊；如果N不可達(dá)，忽略該區(qū)塊；否則會有兩種情況:
- 如果N不在openList中，那么將(N,CN)放入openList中，其中CN=CG+ZN,既S到N的移動總消耗等于S到G的移動總消耗加上N本身的移動消耗，令N的父節(jié)點為G;
- 如果N已經(jīng)在openList中，取出(N,CN)，仍然計算CN1=CG+ZN，如果CN1小于CN，用(N,CN1)替換openList中的(N,CN)，令N的父節(jié)點為G；如果CN1大于或等于CN，不做處理。
-
重復(fù)步驟2直至算法結(jié)束。
Greed-Best-First-Search
可以視為在A*算法中，只考慮H值而不考慮G值
網(wǎng)上沒有找到比較官方的翻譯，有人譯作“最好優(yōu)先貪婪算法”，我們暫時這么稱呼它。
最好優(yōu)先貪婪算法與上面兩種算法的不同之處在于，它總是嘗試向離目標(biāo)節(jié)點更近的方向探索，怎樣才算離目標(biāo)節(jié)點更近呢？在只能上下左右四方向移動的前提下，我們通過計算當(dāng)前節(jié)點到目標(biāo)節(jié)點的曼哈頓距離來進(jìn)行判斷。
假設(shè)當(dāng)前節(jié)點坐標(biāo)為(x,y)，目標(biāo)節(jié)點的坐標(biāo)為(x1,y1)，曼哈頓距離計算公式如下：
Manhattan_distance = abs(x1-x)+abs(y1-y)
由于曼哈頓距離只在兩點之間沒有障礙物的情況下才與實際距離相等，一般情況下曼哈頓距離總是小于實際距離。因此，當(dāng)節(jié)點間不存在障礙物時，算法可以保證找出最短路徑，但是一旦障礙物出現(xiàn)，最短路徑就無法保證了。
算法流程如下：
說明：起始節(jié)點記作S，目標(biāo)節(jié)點記作E，對于任意節(jié)點G，從當(dāng)前節(jié)點G到目標(biāo)節(jié)點E的曼哈頓距離記作MG，優(yōu)先隊列openList中數(shù)據(jù)為(G,MG)（節(jié)點，當(dāng)前節(jié)點到目標(biāo)節(jié)點E的曼哈頓距離）。
- 將起始節(jié)點S放入openList，openList是一個優(yōu)先隊列，曼哈頓距離越小的節(jié)點，優(yōu)先級越高。
- 判斷openList是否為空，如果為空，搜索失敗，目標(biāo)節(jié)點E不可達(dá)；如果不為空，從openList中拿出優(yōu)先級最高的節(jié)點G;
- 遍歷節(jié)點G的上下左右四個相鄰節(jié)點N1-N4，如果N在openList或closeList中，忽略節(jié)點N；否則，令N的父節(jié)點為G，計算N到E的曼哈頓距離MN，將(N,MN)放入openList。
-
判斷節(jié)點G是不是目標(biāo)節(jié)點E，如果是，搜索成功，獲取節(jié)點G的父節(jié)點，并遞歸這一過程（繼續(xù)獲得父節(jié)點的父節(jié)點），直至找到初始節(jié)點S，從而獲得從G到S的一條路徑；否則，重復(fù)步驟2。
總結(jié)
A算法中的G就是根據(jù)Djkstra算法計算的，而H就是根據(jù)最好優(yōu)先貪婪算法計算的。因此可以將A視為Djkstra算法和最好優(yōu)先貪婪算法的結(jié)合。
四種算法的選擇
- 雖然最優(yōu)選擇貪婪算法只在特定情況下才可以找到最短路徑（沒有障礙物、沒有地形移動消耗差異），但是它的運(yùn)行速度是最快的。如果情況允許，優(yōu)先使用本算法。
- 當(dāng)需要知道地圖上某個點到所有其他點的最短路徑，或者反過來，地圖上所有點到某個點的最短路徑時，選擇廣度優(yōu)先算法（各區(qū)塊移動消耗相同）或Dijkstra算法（各區(qū)塊移動消耗不同）。
- 在一般情況下，使用A*算法總是正確的。
