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

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

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

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