《Near Optimal Hierarchical Path-Finding》中提出了一種層次A*算法，正好能夠用于解決項(xiàng)目大地圖尋路的問題。大致思路是：1）預(yù)處理。將地圖劃分為nxn大小的區(qū)塊，找出每個區(qū)塊與周圍四個區(qū)塊在邊界上的互通點(diǎn)，在區(qū)塊中使用局部A*對找出的點(diǎn)做連通性測試并將其保存下來；2）尋路時(shí)，使用預(yù)處理得到的數(shù)據(jù)（邊界上的可通點(diǎn)與區(qū)塊內(nèi)部的互通點(diǎn)），先在區(qū)塊層級上做一次A*，根據(jù)結(jié)果再在每個區(qū)塊中使用局部A*找到區(qū)塊與區(qū)塊之間的路徑，最終得到完整路徑。
一、A* Path-Finding
A*算法就不多講了，可參考：
A*算法的優(yōu)化可從搜索節(jié)點(diǎn)儲存和OpenList排序兩方面入手。
二、預(yù)處理
每個相鄰區(qū)塊（C1和C2）都有一條由公共邊，該邊兩側(cè)小格組成L1和L2，則連通點(diǎn)集E滿足下列條件：
- E ? L1 ∪ L2
- ?t ∈ L1 ∪ L2 : t ∈ E ? symm(t) ∈ E ，其中symm(t)為對稱關(guān)系
- E不含不可行走格子
對在E中且同邊的連續(xù)格子取其中點(diǎn)，如下圖所示：
_thumb.png "Image(6)")
對上面得到的位于同一區(qū)塊的點(diǎn)集合使用local A*做連通性測試，下圖用直線連接來表示兩點(diǎn)互通：
_thumb.png "Image(7)")
三、尋路
使用區(qū)塊連通信息，進(jìn)行區(qū)塊級A*，得到區(qū)塊之間的連接點(diǎn)，如果在預(yù)處理時(shí)保存了區(qū)塊內(nèi)互通點(diǎn)的路徑，就不必再進(jìn)行區(qū)塊內(nèi)的local A*了。
實(shí)驗(yàn)結(jié)果表明，在未采用區(qū)塊內(nèi)預(yù)存路徑的情況下，中長距離尋路使用層次A*后的平均效率是普通A*的5倍以上，距離越長效率對比越明顯。
A* 93ms
HPA* 15ms
從上圖中可以看出，HPA*得到的路徑并不是最優(yōu)的，它是在最優(yōu)和效率上的折中，適合作為長距離尋路的一種優(yōu)化方案。
四、優(yōu)化點(diǎn)
- 可擴(kuò)展為多層而不僅限于一層
- 預(yù)存區(qū)塊內(nèi)連通點(diǎn)路徑
- 區(qū)塊邊界可通面積較大時(shí)，產(chǎn)生不自然路徑，如下圖所示：
一個改進(jìn)的方法是對過長的邊界再做劃分：
_thumb.png "Image(5)")