3D空間自動尋路算法的各功能模塊研究以及優化設計

楊艷　王一名

基金項目：本文是湖北省教育廳科學技術研究計劃指導性項目論文，項目編號：B2017410。

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

關鍵詞：自動尋路算法;各功能模塊;優化設計

中圖分類號：TP317 文獻標識碼：A 文章編號：1672-9129（2020）06-0028-02

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

Keywords：Automaticpathfindingalgorithm;Eachfunctionmodule;Theoptimizationdesign

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

1各功能模塊研究

1.1開啟列表模塊。作用：保存需要搜索的節點的數據結構，整個過程如圖1.1開啟列表流程圖所示：

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

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

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

2算法的優化設計

傳統的A星算法是一個很慢的算法，永遠達不到想要的速度。目前也有很多算法對此進行優化設計。所以對算法的優化是很有必要的。A星算法的搜索受到它所在空間的影響。在一個2000*2000的正方形的區域內進行搜索，那么它的可能性就是2000的平方種可能性，也就是4000000。

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

2.1時間優化設計。這種算法在時間上是非常浪費時間的，所以應該選擇其他的類型的，這種算法的本質，無論怎么樣去優化代碼，計算出正確的路徑總會花費特別長的時間和占據大量的內存。這種巨大的工作量會導致嚴重影響游戲的性能。

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

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

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

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

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

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

3總論

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

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

在不斷進行的測試中發現不足點，對于現在已經足夠好的，可以暫時忽略不計，在最穩定的算法中不斷提高自己的對算法設計的能力，提高自己對于多種數據結構的分析能力。

參考文獻：

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

[2]劉靈均.基于人工智能角色的3D游戲開發平臺的設計與實現[D].西南交通大學，2017.

[3]武文娜.基于視景仿真的槍械作戰效能評估系統[D].中北大學，2017.

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

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