網(wǎng)游服務(wù)器端尋路課件

網(wǎng)游服務(wù)器端尋路面向多核、分布式2008-12軟件

NPC尋路問(wèn)題很重要（雖然也可以不要）游戲玩法與NPC的尋路能力直接相關(guān)計(jì)算量很大數(shù)據(jù)結(jié)構(gòu)和算法的相對(duì)復(fù)雜一臺(tái)服務(wù)器上數(shù)萬(wàn)個(gè)NPC一起尋路有挑戰(zhàn)尋路與其它模塊的關(guān)系尋路在游戲中是一個(gè)相對(duì)底層的模塊NPC的AI系統(tǒng)依賴于一個(gè)可靠的尋路算法尋路模塊依賴于游戲?qū)Φ貓D的描述尋路模塊基本上是一種服務(wù)模塊，總是被調(diào)用，但是自己不需要主動(dòng)去做什么事情目標(biāo)NeedforSpeed！將性能提升100倍！在單位時(shí)間內(nèi)出更多的結(jié)果不能影響游戲邏輯的主循環(huán)更好的利用多核，甚至多臺(tái)計(jì)算機(jī)的運(yùn)算能力如何在邏輯很復(fù)雜，數(shù)據(jù)結(jié)構(gòu)很復(fù)雜，為了提高效率而指針滿天飛的情況下，讓服務(wù)器跑穩(wěn)定？如何更方便的在游戲運(yùn)營(yíng)過(guò)程中逐步改進(jìn)巡邏模塊？改進(jìn)地圖描述數(shù)據(jù)Cell結(jié)構(gòu)適合描述邏輯數(shù)據(jù):Trap,Obstacle…但是Cell的數(shù)量太大，直接用來(lái)AStar效率很低在NPC大多數(shù)時(shí)候不需要跳躍、游泳、空中飛行的時(shí)候，可以是用NavMesh來(lái)描述尋路所需要的地圖障礙信息NavMesh使用凸多邊形來(lái)描述可以移動(dòng)的區(qū)域，數(shù)量通常只有CELL的幾十分之一到數(shù)百分之一將尋路模塊獨(dú)立為進(jìn)程為什么要獨(dú)立出去？不必?fù)?dān)心阻塞游戲服務(wù)器的主循環(huán)。不論是主服務(wù)器還是尋路模塊，都變得更簡(jiǎn)單一些。為什么是進(jìn)程而不是線程？尋路模塊使用自己的地圖描述數(shù)據(jù)，和其他邏輯模塊沒(méi)有太多需要共享的資源。更健壯。尋路模塊本身沒(méi)有狀態(tài)，也沒(méi)有不能丟失的動(dòng)態(tài)數(shù)據(jù)。即使尋路模塊掛了，也不會(huì)影響游戲的主服務(wù)器。直接重啟就可以了。尋路服務(wù)器減少重復(fù)計(jì)算AI的行為會(huì)經(jīng)常周期性的調(diào)用尋路。附近有很多NPC，他們的坐標(biāo)很接近，尋路的計(jì)算是很相似，或者完全相同的。如果將尋路的計(jì)算結(jié)果緩存起來(lái)，就可以減少重復(fù)運(yùn)算。每個(gè)邏輯服務(wù)器獨(dú)享尋路服務(wù)器一份地圖的NavMesh數(shù)據(jù)需要加載到多個(gè)尋路服務(wù)進(jìn)程中，浪費(fèi)寶貴的內(nèi)存。每個(gè)尋路進(jìn)程單獨(dú)Cache尋路結(jié)果，使得尋路Cache中的數(shù)據(jù)重復(fù)，命中次數(shù)下降。對(duì)于硬件需求過(guò)高。一般不可能做到每臺(tái)尋路服務(wù)器都在獨(dú)立的物理服務(wù)器上。共享尋路服務(wù)器的游戲服務(wù)器組一臺(tái)物理服務(wù)器上共享數(shù)據(jù)在不考慮地形(障礙)動(dòng)態(tài)變化的情況下，NavMesh的數(shù)據(jù)是靜態(tài)的。所有尋路進(jìn)程可以同時(shí)讀取共享數(shù)據(jù)。但是Cache是動(dòng)態(tài)刷新的。必須考慮進(jìn)程間的同步問(wèn)題。讀寫鎖尋路過(guò)程中可以明確區(qū)分讀寫兩個(gè)階段尋路過(guò)程中，獲取讀鎖來(lái)獲取Cache數(shù)據(jù)。尋路結(jié)束后，獲取寫鎖來(lái)更新Cache數(shù)據(jù)。多個(gè)進(jìn)程可以同時(shí)讀Cache，但是如果有進(jìn)程要寫Cache的話，所有進(jìn)程都要等。利用本地Cache提高并發(fā)能力為每個(gè)進(jìn)程增加一個(gè)本地的私有Cache。尋路進(jìn)程算出結(jié)果后只將尋路結(jié)果更新到本地的Cache。而不是立刻去寫共享的Cache。等一段時(shí)間之后，進(jìn)程再一次性講本地Cache的內(nèi)容提交到共享Cache。降低了進(jìn)程獲取共享Cache寫鎖的頻率，從而提高并發(fā)能力。帶本地Cache的尋路進(jìn)程利用調(diào)度算法避免鎖引入一個(gè)調(diào)度進(jìn)程。所有尋路進(jìn)程的任務(wù)由調(diào)度進(jìn)程分配。所有尋路進(jìn)程完成尋路任務(wù)的時(shí)候向調(diào)度進(jìn)程匯報(bào)。調(diào)度進(jìn)程沒(méi)有分配任務(wù)的時(shí)候，尋路進(jìn)程不能訪問(wèn)共享Cache（讀/寫都不行）。調(diào)度進(jìn)程可以在沒(méi)有進(jìn)程訪問(wèn)共享Cache的時(shí)候向一個(gè)進(jìn)程分配更新共享Cache的任務(wù)。調(diào)度進(jìn)程通過(guò)調(diào)度來(lái)實(shí)現(xiàn)互斥調(diào)度進(jìn)程會(huì)周期性的控制尋路進(jìn)程向共享Cache中更新數(shù)據(jù)。再此之前，調(diào)度程序會(huì)保證所有的尋路進(jìn)程都是等待狀態(tài)。再此期間，調(diào)度程序不會(huì)向任何尋路進(jìn)程發(fā)出新的尋路任務(wù)。需要避免的問(wèn)題如果調(diào)度器分配一個(gè)任務(wù)給尋路進(jìn)程，但是尋路進(jìn)程出錯(cuò)，而一直沒(méi)有給調(diào)度進(jìn)程發(fā)任務(wù)完成的消息。那么實(shí)際上，調(diào)度器內(nèi)部的狀態(tài)會(huì)“卡”住，而導(dǎo)致調(diào)度器不能發(fā)出更新共享Cache的指令。這個(gè)其實(shí)就和一個(gè)進(jìn)程獲取了鎖，而一直沒(méi)有釋放這個(gè)鎖，是一樣的道理。網(wǎng)絡(luò)游戲服務(wù)器架構(gòu)發(fā)展趨勢(shì)服務(wù)器崩潰恢復(fù)引入備