Heath's Blog

Hierarchical Path-Finding

     《Near Optimal Hierarchical Path-Finding》中提出了一種層次A*算法，正好能夠用于解決項(xiàng)目大地圖尋路的問(wèn)題。大致思路是：1）預(yù)處理。將地圖劃分為nxn大小的區(qū)塊，找出每個(gè)區(qū)塊與周圍四個(gè)區(qū)塊在邊界上的互通點(diǎn)，在區(qū)塊中使用局部A*對(duì)找出的點(diǎn)做連通性測(cè)試并將其保存下來(lái)；2）尋路時(shí)，使用預(yù)處理得到的數(shù)據(jù)（邊界上的可通點(diǎn)與區(qū)塊內(nèi)部的互通點(diǎn)），先在區(qū)塊層級(jí)上做一次A*，根據(jù)結(jié)果再在每個(gè)區(qū)塊中使用局部A*找到區(qū)塊與區(qū)塊之間的路徑，最終得到完整路徑。

一、A* Path-Finding

     A*算法就不多講了，可參考：

• http://theory.stanford.edu/~amitp/GameProgramming/
• http://www.policyalmanac.org/games/aStarTutorial.htm

二、預(yù)處理

     每個(gè)相鄰區(qū)塊（C1和C2）都有一條由公共邊，該邊兩側(cè)小格組成L1和L2，則連通點(diǎn)集E滿足下列條件：

• E ? L1 ∪ L2
• ?t ∈ L1 ∪ L2 : t ∈ E ? symm(t) ∈ E ，其中symm(t)為對(duì)稱關(guān)系
• E不含不可行走格子

    對(duì)上面得到的位于同一區(qū)塊的點(diǎn)集合使用local A*做連通性測(cè)試，下圖用直線連接來(lái)表示兩點(diǎn)互通：

三、尋路

     使用區(qū)塊連通信息，進(jìn)行區(qū)塊級(jí)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ù)存路徑的情況下，中長(zhǎng)距離尋路使用層次A*后的平均效率是普通A*的5倍以上，距離越長(zhǎng)效率對(duì)比越明顯。

     A* 93ms

HPA* 15ms

     從上圖中可以看出，HPA*得到的路徑并不是最優(yōu)的，它是在最優(yōu)和效率上的折中，適合作為長(zhǎng)距離尋路的一種優(yōu)化方案。

四、優(yōu)化點(diǎn)

• 可擴(kuò)展為多層而不僅限于一層
• 預(yù)存區(qū)塊內(nèi)連通點(diǎn)路徑
• 區(qū)塊邊界可通面積較大時(shí)，產(chǎn)生不自然路徑，如下圖所示：

          一個(gè)改進(jìn)的方法是對(duì)過(guò)長(zhǎng)的邊界再做劃分：

posted on 2011-11-12 12:50 Heath 閱讀(4223) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Game Development