3D空間自動尋路算法的各功能模塊研究以及優(yōu)化設(shè)計

楊艷　王一名

基金項目：本文是湖北省教育廳科學(xué)技術(shù)研究計劃指導(dǎo)性項目論文，項目編號：B2017410。

摘要：隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)游戲的發(fā)展也到達(dá)到了一個前所未有新的高度。目前虛擬3D游戲開發(fā)尤其火熱。在3D游戲世界中，如何控制NPC角色自動尋路，是影響游戲體驗最為核心的一個算法，同時也是最設(shè)備消耗性能的計算之一。A星尋路算法是目前普遍使用的路徑搜索算法之一，它不僅僅用于游戲開發(fā)設(shè)計，同時在機(jī)器人自動行走算法中，也起著重大的影響。本文通過分析算法的不同模塊之間的聯(lián)系與區(qū)別，對于每一個功能性的組件進(jìn)行的描。

關(guān)鍵詞：自動尋路算法;各功能模塊;優(yōu)化設(shè)計

中圖分類號：TP317 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-9129（2020）06-0028-02

Abstract：WiththecontinuousdevelopmentofInternettechnology，thedevelopmentofonlinegameshasreachedanunprecedentednewheight.Virtual3Dgamedevelopmentisparticularlyhotrightnow.Inthe3Dgameworld，howtocontroltheNPCcharacter'sautomaticpathfindingisthemostcorealgorithmaffectingthegameexperience，andalsooneofthemostdeviceperformanceconsumingcalculations.Astarpathfindingalgorithmisoneofthecommonlyusedpathsearchalgorithms.Itisnotonlyusedingamedevelopmentanddesign，butalsoplaysAsignificantroleinautomaticrobotwalkingalgorithm.Thispaperdescribeseachfunctionalcomponentbyanalyzingtheconnectionsanddifferencesbetweendifferentmodulesofthealgorithm.

Keywords：Automaticpathfindingalgorithm;Eachfunctionmodule;Theoptimizationdesign

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)游戲的發(fā)展也到達(dá)到了一個前所未有新的高度。目前虛擬3D游戲開發(fā)尤其火熱。在3D游戲世界中，如何控制NPC角色自動尋路，是影響游戲體驗最為核心的一個算法，同時也是最設(shè)備消耗性能的計算之一。A星尋路算法是目前普遍使用的路徑搜索算法之一，它不僅僅用于游戲開發(fā)設(shè)計，同時在機(jī)器人自動行走算法中，也起著重大的影響。

1各功能模塊研究

1.1開啟列表模塊。作用：保存需要搜索的節(jié)點的數(shù)據(jù)結(jié)構(gòu)，整個過程如圖1.1開啟列表流程圖所示：

最開始的時候，把開始點加入到開啟列表中，從這個點出發(fā)不斷向周圍進(jìn)行檢測。

1.2最佳路徑生成點。在獲取周圍可以行走的節(jié)點的過程中，我們可以使用幾種不同的方式，提高運(yùn)行的效率和節(jié)省空間的占用。如圖1.2最佳路徑選擇計算所示：

跳點尋路算法最核心的部分就是在A星尋路的基礎(chǔ)上，優(yōu)化對于周圍可能要搜尋的節(jié)點的查找方式，沿著一個方向一直向前去尋找。

2算法的優(yōu)化設(shè)計

傳統(tǒng)的A星算法是一個很慢的算法，永遠(yuǎn)達(dá)不到想要的速度。目前也有很多算法對此進(jìn)行優(yōu)化設(shè)計。所以對算法的優(yōu)化是很有必要的。A星算法的搜索受到它所在空間的影響。在一個2000*2000的正方形的區(qū)域內(nèi)進(jìn)行搜索，那么它的可能性就是2000的平方種可能性，也就是4000000。

所以這種算法的本質(zhì)，無論怎么樣去優(yōu)化代碼，計算出正確的路徑總會花費(fèi)特別長的時間和占據(jù)大量的內(nèi)存。這種巨大的工作量會導(dǎo)致嚴(yán)重影響游戲的性能。所以我們可以解決的方式就是在路徑搜索時，首先將其的存在的空間信息進(jìn)行優(yōu)化。

2.1時間優(yōu)化設(shè)計。這種算法在時間上是非常浪費(fèi)時間的，所以應(yīng)該選擇其他的類型的，這種算法的本質(zhì)，無論怎么樣去優(yōu)化代碼，計算出正確的路徑總會花費(fèi)特別長的時間和占據(jù)大量的內(nèi)存。這種巨大的工作量會導(dǎo)致嚴(yán)重影響游戲的性能。

對于每一節(jié)點搜搜索的時間，需要不斷就進(jìn)行檢測，在不等同的路徑選擇的計算過程中，不斷進(jìn)行的計算，會消耗大量的時間。所以需要在時間上進(jìn)行細(xì)致的檢測和設(shè)計，這是非常重要的一點。

只有在最大限度減少時間的消耗才能提供用戶最好的體驗，算法看起來就會更加的快速靈敏。這是算法在設(shè)計的時候需要重要的考慮的一點。

2.2空間優(yōu)化設(shè)計。空間消耗是一個非常重要的方面，只有在最開始的階段不斷優(yōu)化設(shè)計不斷加強(qiáng)對于性能在內(nèi)存方面的管理，那么項目在運(yùn)用過程中，以后的開發(fā)就不會像很多其他的產(chǎn)品一樣會造成數(shù)據(jù)過于龐大。如圖2.1程序內(nèi)存消耗圖所示：

內(nèi)存是一個非常重要的方面只有在不斷的對內(nèi)存的控制提出高標(biāo)標(biāo)準(zhǔn)的限制，整個算法才不會再最后的階段，變得不可控，變得巨大消耗內(nèi)存，卻無法控制。慢慢一步步將整個算法，都拖累了。優(yōu)化空間的消耗，也同樣是一個巨大而困難的任務(wù)。

所以這種算法的本質(zhì)，無論怎么樣去優(yōu)化代碼，計算出正確的路徑總會花費(fèi)特別長的時間和占據(jù)大量的內(nèi)存。這種巨大的工作量會導(dǎo)致嚴(yán)重影響游戲的性能。所以我們可以解決的方式就是在路徑搜索時，首先將其的存在的空間信息進(jìn)行優(yōu)化。

內(nèi)存是計算機(jī)中重要的部件之一，它是與CPU進(jìn)行溝通的作用。計算機(jī)中所有程序的運(yùn)行都是在內(nèi)存中進(jìn)行的，因此內(nèi)存的性能對計算機(jī)的影響非常大。內(nèi)存Memory也被稱為內(nèi)存儲器，其作用是用于暫時存放CPU中的運(yùn)算數(shù)據(jù)，以及與硬盤等外部存儲器交換的數(shù)據(jù)。只要計算機(jī)在運(yùn)行中，CPU就會把需要運(yùn)算的數(shù)據(jù)調(diào)到內(nèi)存中進(jìn)行運(yùn)算，當(dāng)運(yùn)算完成后CPU再將結(jié)果傳送出來，內(nèi)存的運(yùn)行也決定了計算機(jī)的穩(wěn)定運(yùn)行。內(nèi)存是由內(nèi)存芯片、電路板、金手指等部分組成的。

3總論

我們對游戲的簡單的尋路算法做了最為基本的了解介紹，并且把它一步步把這個算法逐步實現(xiàn)。講解每一部分的后來分析了算法的性能，從幾個不同的方面做出了歸納。為了在以后的算法中提高性能，我們就能在這幾個方面中去針對性加強(qiáng)改善。

算法的重點在于運(yùn)算的速度以及這些計算對于內(nèi)存的消耗，一個最好的算法不是在某一方面取得好成績，而是在平衡了時間以及占用的空間而綜合得出來的一個雙方都滿意的結(jié)果。算法的實現(xiàn)需要。

在不斷進(jìn)行的測試中發(fā)現(xiàn)不足點，對于現(xiàn)在已經(jīng)足夠好的，可以暫時忽略不計，在最穩(wěn)定的算法中不斷提高自己的對算法設(shè)計的能力，提高自己對于多種數(shù)據(jù)結(jié)構(gòu)的分析能力。

參考文獻(xiàn)：

[1]李橋.基于NavMesh自動尋路算法在動態(tài)尋路問題上的研究[D].華中科技大學(xué)，2019.

[2]劉靈均.基于人工智能角色的3D游戲開發(fā)平臺的設(shè)計與實現(xiàn)[D].西南交通大學(xué)，2017.

[3]武文娜.基于視景仿真的槍械作戰(zhàn)效能評估系統(tǒng)[D].中北大學(xué)，2017.

[4]蔣愷.淺談游戲中自動尋路算法的實現(xiàn)與應(yīng)用[J].中國新通信.2018，（2）.91-92.

[5]李樊.基于虛擬現(xiàn)實技術(shù)的3D游戲場景設(shè)計研究[J].科學(xué)大眾（科學(xué)教育）.2019，（2）.91-92.