摘要: 五邑隐俠，本名關健昌，10年遊戲生涯，現隐居五邑。本系列文章以TypeScript為介紹語言。
這一篇介紹A*尋路算法。在RPG、SLG、模拟經營類遊戲，有需要給角色尋路的需求，一般尋路我們采用A*尋路算法，A*尋路算法是一種廣度優先啟發性算法。
先說說什麼叫廣度優先。搜尋分為廣度優先和深度優先，主要展現在對節點的展開上。深度優先一直往一個方向查找，如果沒辦法查找下去，在目前節點改變方向繼續查找，直到找到終點。如果無法繼續查找，就回退上一格重複操作。廣度優先把目前節點放入待探索清單，循環從待探索清單裡取出節點進行展開，直到找到終點。如果待探索清單為空，說明沒有路可走。
啟發性指算法在待探索清單裡取節點時，先預測哪個節點的路徑可能會最短，優先對該節點展開，A*算法基于對未探索路徑的假設和預測，假設所有路都能通行前提下總路徑最短值。在圖論裡，介紹過有一種尋找最短路徑的算法叫Dijkstra算法，該算法基于貪心算法，即目前選擇探索的節點，為尚未确定最短路徑，目前源點能到達且路徑最短的節點。Dijkstra算法基于已知距離源點最短。為了便于了解這兩種算法的差別，先介紹下Dijkstra算法。
Dijkstra算法知道所有可能的節點，如下圖，知道總共有ABCDE5個節點，尋找從A點出發到各點的最短路徑。
1）算法有兩個數組，一個維護目前已知最終最短路徑的節點數組S，找到為路徑字元串和長度，否則為空字元串，初始隻有起點A點标記為“A”。另一個數組V，維護各個節點“目前所知”從源點出發最短的路徑長度（不一定是最終的最短路徑，初始B标記為6，D為7），已經找到最終最短路徑的标記為0（初始時起點A标記為0），目前無法到達的标記為無窮大。
2）循環從數組V中擷取标記非0，非無窮大，路徑最短的節點，在數組S中标記為1，修正V中其他節點的最短路徑。直到數組S中所有節點都标記為1
如上圖，尋路的過程為：
V：（A，0），（B：6），（C：無窮大），（D：7），（E：無窮大），S：（A，“A”），（B：“”），（C：“”），（D：“”），（E：“”）
V：（A，0），（B：0），（C：11），（D：7），（E：18），S：（A，“A”），（B：“AB”），（C：“”），（D：“”），（E：“”）
V：（A，0），（B：0），（C：10），（D：0），（E：18），S：（A，“A”），（B：“AB”），（C：“”），（D：“AD”），（E：“”）
V：（A，0），（B：0），（C：0），（D：0），（E：18），S：（A，“A”），（B：“AB”），（C：“ADC”），（D：“AD”），（E：“”）
V：（A，0），（B：0），（C：0），（D：0），（E：0），S：（A，“A”），（B：“AB”），（C：“ADC”），（D：“AD”），（E：“ABE”）
這裡，Dijkstra算法基于知道所有可能的節點，目标節點也有多個，每個節點可以直接到達的節點數沒有限制。
遊戲裡的尋路是目标節點隻有一個，中間節點可能有多個，每個節點可以直接到達的節點數最多4個（如果是8個方向是8）
将數組改成清單會更靈活，現在将數組V改成open隊列，将數組S改成close隊列。如上圖，要找到A到E的路徑，仍然按照Dijkstra算法思路，
1）先将A放入open隊列，路徑長度為0
2）循環從open清單裡拿出路徑長度最短的節點，将其放入close隊列并記錄上一節點，對其4個方向進行展開，如果已經在open、close隊列，修正其最短路徑長度；如果不可走，忽略；否則放入open隊列并計算其路徑長度。
3）如果找到E點，通過E點的上一節點，上一節點的上一節點...一直反推到A點，形成反推路徑，進而找到A到E的最短路徑。
4）如果還沒找到E點，open 隊列為空，A到E路不通。
如上圖，從Dijkstra算法修改過來的尋路算法，按照紅色、綠色、藍色、黃色節點，逐漸展開尋找才找到A到E的最短路徑，很多沒用的分支，效率低。
A*的優化思路主要在挑選節點展開時，假設找到一個中間節點B後，中間節點B到E的路都是可走的。這時候最短路徑長度是計算經過B點A到E的最短路徑（AB）+（BE）。在RPG遊戲中，最簡單的情況是，A到B的路徑長度等于從A走到B經過的格子數，B到E的路徑長度等于假設B到E的路都相通情況下B走到E經過的格子數。A*算法每次展開節點時都盡可能的往可能最短的路徑去展開尋找，減少沒必要的分支，提高尋路效率。
下面是A*尋路算法過程
1）先将A放入open隊列，記錄其上一節點為空
2）循環從open清單裡拿出節點N，N為經過該點N，A到E路徑預測長度最短的節點，将其放入close隊列；對其4個方向進行展開，如果已經在open、close隊列，修正其上一節點；如果不可走，忽略；否則放入open隊列并記錄其上一節點為N。
A*尋路算法先說到這裡，下一篇我們将介紹有限狀态機和行為樹。