a星算法一般指A*搜尋算法，A*算法是比較流行的啟發(fā)式搜索算法之一，被廣泛應(yīng)用于路徑優(yōu)化領(lǐng)域。它的獨特之處是檢查最短路徑中每個可能的節(jié)點時引入了全局信息，對當前節(jié)點距終點的距離做出估計，并作為評價該節(jié)點處于最短路線上的可能性的量度。
一、A*搜尋算法描述
A*改變它自己行為的能力基于啟發(fā)式代價函數(shù)，啟發(fā)式函數(shù)在游戲中非常有用。在速度和精確度之間取得折衷將會讓你的游戲運行得更快。在很多游戲中，你并不真正需要得到最好的路徑，僅需要近似的就足夠了。而你需要什么則取決于游戲中發(fā)生著什么，或者運行游戲的機器有多快。
二、A*搜尋算法缺陷
A*算法進行下一步將要走的節(jié)點的搜索的時候，每次都是選擇F值最小的節(jié)點，因此找到的是最優(yōu)路徑。但是正因為如此A*算法每次都要擴展當前節(jié)點的全部后繼節(jié)點，運用啟發(fā)函數(shù)計算它們的F值，然后選擇F值最小的節(jié)點作為下一步走的節(jié)點。在這個過程中，OPEN表需要保存大量的節(jié)點信息，不僅存儲量大是一個問題，而且在查找F值最小的節(jié)點時，需要查詢的節(jié)點也非常多，當然就非常耗時，這個問題就非常嚴重了。再加上如果游戲地圖龐大，路徑比較復(fù)雜，路徑搜索過程則可能要計算成千上萬的節(jié)點，計算量非常巨大。因此，搜索一條路徑需要一定的時間，這就意味著游戲運行速度降低。
