多人在線角色扮演游戲中智能尋路的設計與實現.pdf

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

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

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