Algorithm ：

?????? A* 在地圖中兩點間找出一條路徑，如果存在至少一條路徑，在各種不同的算法中 A* 將找到最短路徑，而且相比之下算法速度快。 A* 是一種可控的算法，是一種啟發式搜索算法，也就是說算法本身不會盲目的搜索路徑，而是估計一個最佳的考察方向，進行搜索。

? ???? 在 A* 尋路算法中，我們從起點開始，檢查相鄰方格的方式，向外擴展直到找到目標。

我們做如下操作開始搜索：

1. 從起點開始，并且把它作為待處理的第一個點存入一個 “ 開啟列表 ” 。開啟列表就像一張購物清單。盡管現在列表里只有一個元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個待檢查方格的列表。

2. 從開啟列表中取出一個代價最小的點

關于代價值的計算

F = G + H

這里：
??? * G = 從起點，沿著產生的路徑，移動到當前節點的移動耗費。
??? * H = 從網格上那個方格移動到終點的預估移動耗費。這經常被稱為啟發值

?

如果開啟列表為空則說明路徑沒有找到，結束搜索。如果取到這個節點，則將這個結點加入到 ” 關閉列表 ” ，如果這個點是終點，則結束搜索。如果不是終點就把這個點作為當前點。

3. 按照八個方向查找與當前點相鄰的節點，如果是可以移動的點（尋找起點周圍所有可到達或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格）

a. 如果新考核的點在 ” 關閉列表 ” 中，并且從當前點到達這個點的 G 值更小則

將這個點作為當前點的孩子節點

更新這個點的 G 值

更新這個點所有孩子節點的父節點指針、 G 值、 F 值

b. 如果新考核的點在 ” 開啟列表中 ” ，并且從當前點到達這個點的 G 值更小則

將這個點作為當前點的孩子節點

更新這個點的 G 值

?c. 將這個點作為當前點的孩子節點，計算這個點的 G 、 H 、 F 值，將這個節點加入到 ” 開啟列表 ” 中。

?

4 ．跳回第二步周而復始，直到 ” 開啟列表 ” 為空，或者將終點加入到 ” 關閉列表 ”

? 流程圖:

算法優化：

? ? ?? 算法中消耗分析

1.???? 節點的內存分配與釋放

?

節點的內存分配與釋放非常頻繁，大規模搜索的時候通常需要數千個節點乃至上萬個節點。所以很有必要做內存管理。考慮用 placement new 來分配內存減少分配與釋放的開銷，但是需要在程序運行開始就事先分配好內存。每個節點大約 20 字節左右，正常的情況下一張稍大的地圖有 1500x1500 大小 2,250,000 格，那么最壞情況下，需要內存約 40,000k ，所以如果一開始就分配這么多內存是不現實的，所以只能限制一個內存分配極值，比如一次分配一兆，如果用完就結束搜索。但如果游戲一開始就分配 1 兆內存用于尋路，實際上有可能一直都不需要大規模搜索，所以最好有增長方式的內存管理。

另一個方案是每次分配一批節點所需內存，用完了再增長，分配粒度越大命中效果也會更好些。

?

2.???? 從開啟列表中取出一個代價最小的點

從開啟列表中取出一個代價最小的點需要比較并遍歷所有在開啟表中節點。優化的做法是在每次插入開啟表的時候都將節點插入在表的最前端，這樣每次從前端取就可以避免遍歷的開銷，但是分析證明，每次節點的值改變都需要重新排序，一次大循環中可能需要多次排序，而每次大循環只會取一次代價最小節點，所以這一次的遍歷相比開銷要比排序小的多。

3.???? 查找考核點是否在關閉列表

查找考察點是否在關閉或者開啟列表中都需要遍歷整張表，優化的辦法是選擇合適的數據結構。

相比使用 vector 插入和刪除的速度會很慢，但是訪問和遍歷的速度很快，但如果 vector 預先分配內存，內存命中會很高，訪問和遍歷也會更快，插入和刪除如果用 swap 也會相對較快。

使用 list 插入和刪除速度會很快，但是遍歷會很慢，內存命中也會比較差。如果算法中對表的插入比遍歷頻繁，可以考慮使用 list 。

經過測試發現，瓶頸在表的遍歷與搜索上， vector 無論有多快搜索速度都是線性的而且隨著節點的增加，遍歷時間也隨之線性增長，而 map 的查找速度是常數級的， Hash map 查找的時間復雜度為 O(1) ，即使用 STL 的 map 也會有 O(log (n)) 比線性查找 O(n) 快很多， map 永遠是穩定的。

?

4.???? 如果已經存在在列表中并且當前 G 值最小則更新其 G 值和這個考核點所有的孩子節點的 G 值和父節點指針。

遍歷孩子節點需要遞規來完成搜索整棵樹，開銷在于函數調用，所以采用棧的方式來模擬遞規。

5.???? 查找考核點是否在開啟列表，如果在開啟列表則更新這個節點。

6.???? 函數調用帶來的開銷，所有檢測函數都做成內聯函數，封裝后的 A* 需要對外開放一個檢測函數指針，可以實現函數對象來做檢測函數，函數對象的可以內聯 operator 操作符。

?

A* 帶來的其他問題

A* 在最壞的情況下會廣度搜索地圖，花費很多時間才能找到終點，尤其是目標點為掩碼（即無論如何到達不了的終點），所以通常情況下要對尋路時間加以限制，但是限制時間短了可能找不到目標點，限制時間長了又可能影響游戲幀率，比如在在游戲 Mouse Hold 的情況下，尋路是頻繁進行的。一個經驗值是 20 毫秒，對有效的目標點搜索超過 20 毫秒都沒有找到有效的路徑就放棄搜索，找一個離目標最近的終點即可。

但是時間限制可能存在硬件不同而效果不同的問題，對于不同的 cpu 來說，相同的時間搜索的范圍會不一樣，另一個選擇是利用循環次數來限制。

對于目標點為掩碼的處理，與其讓 A* 進行超時搜索不如在開始設置目標點的時候就計算一個離目標點最近的可以到達的點。可以從目標點為中心一圈一圈向外搜索，直到搜索到一個可以到達的點（非掩碼 … ）為止，這比起直接用 A* 消耗要小的多。

?

算法的進一步改進

1.?????? 需要更快的速度

a.???? 改進數據結構

?????? 當前使用的是 STL 的 map ，是使用紅黑樹來管理內存的而不是真正的 Hash Map ，如果改為 HashMap ，效率可能會再有一些改進。 ???

b. ?? 分時計算

如果需要更快速的得到路徑，需要分時計算。一開始就計算出一條快速路徑，可能只有幾步，只是一個大概的方向，然后讓角色開始按照這條路徑開始行進，與此同時繼續計算完整路徑。

2. ?? 需要更優的路徑

?????? 如果需要更優的路徑，可以做進一步對路徑進行修正，也就是在搜索好的路徑上面選取一個點為目標再次進行搜索，找到更短路徑。這也意味著運算時間更長，這時候就需要在性能和更好的效果上取一個平衡點。