A 算法*是一種解決圖遍歷問題的計(jì)算機(jī)算法，在電子游戲中最主要的應(yīng)用是尋找地圖上兩點(diǎn)間的最佳路線。
為了便于理解，本文將以正方形網(wǎng)格地圖為例進(jìn)行講解。
如圖，藍(lán)色格子是障礙物，灰色格子是可通過區(qū)域，綠色格子是起點(diǎn)（S），紅色格子是終點(diǎn)（D）。我們要做的是找到一條從起點(diǎn)到終點(diǎn)的最佳路線。
為了順利地解決問題，我們先要設(shè)定一些約束條件：
從一個(gè)格子可以朝周圍 8 個(gè)方向移動(dòng)。其中朝上、下、左、右移動(dòng)的成本為 1，朝左上、右上、左下、右下移動(dòng)的成本為 1.4（√2 近似值）；
不能朝障礙物所在格子移動(dòng)（顯然啦?。?/p>
如果右邊和上邊兩個(gè)格子都是障礙物，則不能朝右上方的格子移動(dòng)（如圖：不能朝右上和右下兩個(gè)格子移動(dòng)，太窄擠不過去呀～）。
好，下面開始找路！
首先，我們把起點(diǎn) S 加入一個(gè)待檢查節(jié)點(diǎn)的列表（Open List）。
接下來，找出 S 周圍所有可移動(dòng)的格子（鄰居），算出從 S 移動(dòng)到該格子的總成本（記為 G），并將 S 設(shè)為其父節(jié)點(diǎn)。
好，這樣我們已經(jīng)完成了對(duì) S 的檢查。把上一步找到的鄰居都加入 Open List。從 Open List 中移除 S，并將其加入另一個(gè)已檢查節(jié)點(diǎn)的列表（Closed List）。如圖，橙色邊框代表待檢查節(jié)點(diǎn)，黑色邊框代表已檢查節(jié)點(diǎn)。
這下問題來了，Open List 一下有了 8 個(gè)待檢查節(jié)點(diǎn)，先檢查哪一個(gè)呢？每一個(gè)待檢查節(jié)點(diǎn)都有一個(gè) G 值，代表從起點(diǎn) S 移動(dòng)到這個(gè)節(jié)點(diǎn)的成本。我們?cè)儆?jì)算出每一個(gè)待檢查節(jié)點(diǎn)與終點(diǎn) D 之間的曼哈頓距離（只通過朝上、下、左、右四個(gè)方向的移動(dòng)，抵達(dá)終點(diǎn) D 的最短距離），作為從該節(jié)點(diǎn)移動(dòng)到終點(diǎn) D 的估算成本（記為 H）。注意！這里計(jì)算曼哈頓距離時(shí)要忽略所有障礙物。最后把 G 和 H 相加（記為 F）。
現(xiàn)在，從 Open List 中選出 F 值最小的節(jié)點(diǎn)（上圖中應(yīng)該是 S 右邊 F 值為 4 的格子），對(duì)它執(zhí)行前面的檢查。不過這一次搜索鄰居時(shí)需要注意以下幾點(diǎn)：
如果鄰居已經(jīng)在 Closed List 中，直接忽略；
如果鄰居不在 Open List 中，計(jì)算 G、H、F，設(shè)置父節(jié)點(diǎn)，并將其加入 Open List；
這一點(diǎn)非常重要！如果鄰居已經(jīng)在 Open List 中（即該鄰居已有父節(jié)點(diǎn)），計(jì)算從當(dāng)前節(jié)點(diǎn)移動(dòng)到該鄰居是否能使其得到更小的 G 值。如果能，則把該鄰居的父節(jié)點(diǎn)重設(shè)為當(dāng)前節(jié)點(diǎn)，并更新其 G 和 F 值。
完成檢查后，把當(dāng)前節(jié)點(diǎn)從 Open List 中移除，放入 Closed List。
繼續(xù)處理其他待檢查節(jié)點(diǎn)。
注意！在下面這一次檢查中，S 下方兩格的節(jié)點(diǎn)（星標(biāo)）更新了 G 值和父節(jié)點(diǎn)。
在下面這一步中，我們注意到終點(diǎn) D 已經(jīng)進(jìn)入了 Open List，并且是其中 F 值最小的。
我們從 Open List 取出的 F 值最小的節(jié)點(diǎn)后，發(fā)現(xiàn)它的 H 值為 0，這意味著我們已經(jīng)找到了終點(diǎn) D，搜索到此就可以告一段落。
從終點(diǎn) D 開始，依次向父節(jié)點(diǎn)移動(dòng)，直到回到起點(diǎn) S，途經(jīng)即最佳路線，總長(zhǎng) 5.6。
算法講解完畢，請(qǐng)各位自己動(dòng)手嘗試實(shí)現(xiàn)吧。
查看在線演示
補(bǔ)充幾點(diǎn)
最佳路線可能有多條，比如本文的示例，下圖也是一條總長(zhǎng)為 5.6 的路線。這取決于當(dāng) Open List 存在多個(gè) F 值最小的節(jié)點(diǎn)時(shí)，先選取哪一個(gè)進(jìn)行搜索；
曼哈頓距離只是估算 H 值最簡(jiǎn)單的一種方法，常用的方法還有歐幾里德距離、切比雪夫距離等。估算方法的優(yōu)劣是影響算法效率的重要因素；
Open List 的數(shù)據(jù)結(jié)構(gòu)也是算法實(shí)現(xiàn)的改良點(diǎn)。通常為了從中取出 F 值最小的節(jié)點(diǎn)，我們需要遍歷整個(gè) Open List，對(duì)其排序。因此，維護(hù)一個(gè)好的 Open List 結(jié)構(gòu)，減少遍歷，也能夠提高算法的效率；
實(shí)際應(yīng)用中，為提高效率，還可以進(jìn)行雙向搜索。從起點(diǎn)和終點(diǎn)分別發(fā)起搜索，一方搜索到另一方的已檢查節(jié)點(diǎn)時(shí)，即找到最佳路線。地圖較復(fù)雜時(shí)，雙向搜索可以顯著減少尋路過程中檢查的節(jié)點(diǎn)數(shù)量。
除了正方形網(wǎng)格地圖，A* 算法也能處理其他正多邊形鑲嵌和復(fù)雜甚至不規(guī)則多邊形鑲嵌的地圖。其區(qū)別在于對(duì)鄰居的處理和計(jì)算；
A* 算法并不保證得到的路線是平滑的。為了解決這個(gè)問題，我們可以對(duì)轉(zhuǎn)向進(jìn)行懲罰。即當(dāng)移動(dòng)方向發(fā)生變化時(shí)，增加額外的 G 值，以此提高轉(zhuǎn)向的成本，從而得到更平滑（轉(zhuǎn)向少、轉(zhuǎn)角?。┑淖罴崖肪€；
A* 算法的在游戲中的實(shí)際應(yīng)用可能會(huì)復(fù)雜得多。比如不同種族或技能的單位在同一地形上的移動(dòng)成本各有差異，同一單位在草地、泥地、砂石、沼澤等各種地形上移動(dòng)的成本也不盡相同（對(duì)應(yīng)不同的 G 值增量），甚至允許以較高的成本翻越障礙（翻墻、過河等）；
在游戲中你可能還需要處理與障礙物和其他移動(dòng)單位的碰撞；
歡迎繼續(xù)補(bǔ)充……
– 完 –
本站專欄文章皆為原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處（帶有 前端亂燉 字樣）和本文的顯式鏈接(http://www.html-js.com/article/2434)，本站和作者保留隨時(shí)要求刪除文章的權(quán)利！
