自動尋路算法（A*算法）分享

一、為什麼地圖網格化？

位置描述：

滑鼠位置使用像素坐标描述。

地圖位置使用經度緯度描述。

為了友善描述地圖上元素的位置，将地圖網格化。

二、什麼是曼哈頓距離？

曼哈頓距離（Manhattan distance）：兩點在南北方向上的距離加上在東西方向上的距離，即D（I，J）=|XI-XJ|+|YI-YJ|。

計算曼哈頓距離時，忽略兩點之間的障礙物。

若有兩點(1,2)和(3,4)，則曼哈頓距離 = |3 -1| + |4 - 2| = 4

三、A*算法涉及的名詞

開啟清單：存放即将進行分析的可達位置。

關閉清單：存放已經分析完畢的可達位置。

估價函數：f(n) = g(n) + h(n)

f(n) 是從初始點經由節點n到目标點的估價函數。

g(n) 是在地圖中從初始節點到n節點的實際代價h(n) 是從n到目标節點最佳路徑的估計代價。

h(n)是估計代價，可以使用曼哈頓距離作為估計代價。

四、A*算法步驟

1、将起始位置放入開啟清單。

2、擷取開啟清單中F(n) 值（經由點n的估價值）最小的位置，且曼哈頓距離最小，作為目前位置。

3、判斷目前位置是否為終點，若為終點，将終點放入關閉清單并執行第八步。

4、将目前位置從開啟清單中移除，并放入關閉清單。

5、擷取目前位置可達的位置。注意：關閉清單中的位置不可達。

6、将目前位置可達的位置放入開啟清單。

7、若開啟清單不為空，則從第二步繼續循環。

8、若終點存在關閉清單，則傳回路徑，否則未找到路徑。

五、A*算法優化

1、地圖粒度沒必要劃分到像素點。像素點的劃分粒度對于搜尋來說代價太高。

建議劃分的粒度在不影響使用的情況下取最大值。

2、每次新位置放入開啟清單時，給清單排序（建議選擇快速排序算法），

這樣每次從開啟清單取位置時，隻取第一個位置即可。

這種方式适用于超大地圖，分支節點多的地圖。

3、可以前進到相鄰的對角線上的位置（8個方向）。建議使用8方向而非4方向。

相鄰對角線上位置的代價建議為1.4。

4、不同位置的損耗。在地圖中，位置有兩種狀态，可通過和不可通過。

但有的可通過位置可能移動代價更高，比如，堵車道路上的位置。

5、對于超級大的地圖尋路，可以把大地圖劃分為N個小區域。先使用A*算法

在N個小區域裡找到路徑，在路徑上的每個小區域裡再次使用A*算法找到

最終的路徑。

6、Dijkstra（狄克斯特拉）算法：該算法與A*算法差別在于估價函數， Dijkstra 算法

沒有h(n)。Dijkstra 算法每次疊代時選擇的下一個頂點是标記點之外距離源點最

近的頂點。但由于dijkstra算法主要計算從源點到其他所有點的最短路徑，是以

算法的效率較低。

對于多個目标位置，建議采用Dijkstra算法。比如停車場有多個出口，需要找到離

目前位置最近的出口。

-=各種=-尋路算法示範：

[url]http://qiao.github.io/PathFinding.js/visual/[/url]