基于啟發(fā)式搜索算法的地圖尋徑的研究.pdf

1、隨著計(jì)算機(jī)技術(shù)及因特網(wǎng)技術(shù)在中國(guó)的發(fā)展，中國(guó)游戲產(chǎn)業(yè)逐漸形成規(guī)模。尤其是這幾年，國(guó)家提倡電腦游戲軟件的自主研發(fā)，因此各種游戲引擎軟件中的技術(shù)和算法成為了人們研發(fā)的熱點(diǎn)，其中地圖尋徑算法是游戲引擎軟件中最重要的算法之一。最常用的地圖尋徑算法是一種啟發(fā)式搜索算法--A*算法。而傳統(tǒng)的A*算法在數(shù)據(jù)結(jié)構(gòu)優(yōu)化方面沒(méi)有做足夠的研究，因此在這方面還有優(yōu)化的余地。其次，各種對(duì)A*算法的研究過(guò)于理論化，而將A*算法實(shí)際的使用在項(xiàng)目當(dāng)中的研究極少，這也是

2、地圖尋徑算法研究的一個(gè)欠缺。 本文針對(duì)以上所述的兩點(diǎn)不足進(jìn)行了研究和探討。首先，通過(guò)設(shè)計(jì)算法演示程序研究了A*算法在地圖尋徑中的執(zhí)行過(guò)程，對(duì)其整個(gè)過(guò)程中的各種操作進(jìn)行了詳細(xì)分析，針對(duì)分析結(jié)果提出了幾種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，并將新設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)用于算法當(dāng)中，通過(guò)算法的執(zhí)行，對(duì)各種優(yōu)化結(jié)果做比較，得到最優(yōu)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。其次，本文將抽象的A*算法實(shí)例化，對(duì)算法進(jìn)行適應(yīng)實(shí)際應(yīng)用的擴(kuò)展，并對(duì)實(shí)際中出現(xiàn)的各種問(wèn)題進(jìn)行研究和探討，設(shè)計(jì)出相應(yīng)的解決