多人在線角色扮演游戲中智能尋路的設(shè)計與實現(xiàn).pdf

1、近年來，隨著游戲產(chǎn)業(yè)的不斷發(fā)展，人工智能在游戲中的作用也越來越大，并且成為了一項熱門技術(shù)。智能尋路系統(tǒng)作為人工智能的一個分支在現(xiàn)代網(wǎng)絡(luò)游戲中占據(jù)著重要的地位。當前大部分游戲中的智能尋路系統(tǒng)都放在客戶端完成，這樣在處理上簡單易實現(xiàn)。但當玩家惡意修改時，服務(wù)器不能準確的做出判斷，從而導(dǎo)致了游戲的不公平性。為了避免這個問題，需要實現(xiàn)服務(wù)器端的智能尋路系統(tǒng)，這就要求智能尋路系統(tǒng)既不能影響游戲服務(wù)器的正常邏輯處理，還要能支持盡可能多的用戶同時請求

2、，而現(xiàn)在比較流行的尋路方法A*在平均尋路時間上無法達到這一要求，需要尋找一種快速尋路方法。
　　為此，本文首先改進了基于A*的尋路策略，提出了懶惰初始化，棧數(shù)組策略。探討了利用A*中的啟發(fā)式估價函數(shù)的特性對路徑節(jié)點進行分類管理。對比優(yōu)化后的算法和傳統(tǒng)的優(yōu)先隊列算法的實驗數(shù)據(jù)，在不同障礙率下，優(yōu)化算法的運行時間變化趨勢與改進前方法基本一致。在平均尋路時間上，改進后的算法雖然有一定優(yōu)勢，但還是不能達到支持大量用戶并發(fā)尋路的要求。

3、>　　因此，本文討論了基于深度優(yōu)先搜索的尋路策略，提出了優(yōu)化方法，實現(xiàn)了快速尋路。經(jīng)過實驗測試，應(yīng)用快速尋路方法之后，平均尋路時間由原來的0.13毫秒降低到0.067毫秒，尋路效率顯著提升；其不足是，障礙率越大，尋路準確率越小，在高障礙率的情況下，尋路準確率低于50％。
　　為了彌補這一缺點，本文提出了一種基于預(yù)判障礙的混合尋路的新方法。此方法先利用一種稱為邊緣搜索的搜索算法對地圖進行掃描，然后對地圖中的障礙率進行評估，從而選擇最