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