A*(A-star)是遊戲界中極出名的演算法 有研究這個領域的都知道
A*是用來搜尋路徑的演算法,它保證每次都能找到成本最低的路徑
有幾個術語:
節點: 在地圖上佈滿了節點,角色可由一個節點經過另一個而達到目標結點
地形成本: 由某一節點走向另一個所花費的成本(也許是錢,也許是時間......)
啟發成本: 用來評估一個節點是否接近終點(可能是到終點的距離),一個有點抽象的概念...用來決定節點搜尋的優先順序
總成本: 由起點累積到當前結點的地形成本和 + 當前結點的啟發成本
擴展: 拜訪相鄰節點
概觀:
在一個地圖中,我們要搜尋從A點到B點的最低成本路徑,所得的最短路徑為一個節點陣列,為路徑通過的結點
在連續的空間環境中,可能較難建立節點,因為鄰近結點之間要能相通;在方塊世界比較容易
演算法:
宣告陣列 open,closed
建立起始節點
open.push(起始結點)
while open不為空
{
set 當前節點 = open中總成本小的節點
if 當前節點 == 終點
{
搜尋結束,回傳當前節點
}
else
{
//擴展當前節點
for each 相鄰節點
{
if 此相鄰節點未被拜訪過 or 此相鄰節點總成本 > 當前節點的總成本 + 地形成本
{
set 此相鄰節點.parent = 當前節點
set 此相鄰節點的總成本 + 地形成本
set 此相鄰節點.parent = 當前節點
set 此相鄰節點的總成本 + 地形成本
open.push(此相鄰節點)
if 此相鄰節點在closed中
{
把此相鄰節點從closed中移除
}
}
}
//擴展結束
把當前節點從open中移除
closed.push(當前節點)
}
}
open裡面放的是尚未拓展,而已經到訪的結點,裡面總成本(包含起發成本)最小的作為下次拓展對象
closed裡面放的是已經拓展過的結點
每一次while迴圈時, 從open中選出最小成本的結點進行拓展,直到終點
每一個節點,除了起始結點外都記錄一個parent,也就是前一步是哪個節點
如果將要到訪的節點之前已經被到訪過了,就檢查舊的成本是否大於此路線的成本,如果是,便設此節點的parent為當前節點,改變路徑
最後,到訪至終點後,回傳"終點"這個節點,我們的路徑可以藉由parent這項追溯到起點
至於啟發成本,比較不確定,可以簡略地設為到終點的直線距離
總地形成本才算是真正的成本,啟發成本只是用來決定拓展順序而已
在此簡介A*結束 的相關文章可以在許多遊戲書籍中找到
創作內容
人工智慧演算法~A*
雜記 (18)