網(wǎng)游服務(wù)器端尋路學(xué)習(xí)教案

1、網(wǎng)游服務(wù)器端尋路網(wǎng)游服務(wù)器端尋路第一頁，共30頁。尋路在游戲中是一個(gè)相對(duì)底層的模塊(m kui)NPC的AI系統(tǒng)依賴于一個(gè)可靠的尋路算法尋路模塊(m kui)依賴于游戲?qū)Φ貓D的描述尋路模塊(m kui)基本上是一種服務(wù)模塊(m kui)，總是被調(diào)用，但是自己不需要主動(dòng)去做什么事情第1頁/共30頁第二頁，共30頁。在游戲邏輯服務(wù)器內(nèi)實(shí)現(xiàn)一個(gè)A star算法，在邏輯地圖描述數(shù)據(jù)上(CELL)搜索。效率很低可能會(huì)阻塞主循環(huán)(xnhun)增加服務(wù)器復(fù)雜度第2頁/共30頁第三頁，共30頁。Need for Speed！將性能提升100倍！在單位時(shí)間內(nèi)出更多的結(jié)果不能影響游戲邏輯的主循環(huán)更好的利用多核，甚

2、至多臺(tái)計(jì)算機(jī)的運(yùn)算能力如何在邏輯很復(fù)雜，數(shù)據(jù)結(jié)構(gòu)很復(fù)雜，為了提高效率而指針滿天飛的情況下，讓服務(wù)器跑穩(wěn)定？如何更方便的在游戲運(yùn)營過程中逐步改進(jìn)巡邏(xnlu)模塊？第3頁/共30頁第四頁，共30頁。 Cell結(jié)構(gòu)適合描述(mio sh)邏輯數(shù)據(jù):Trap, Obstacle 但是Cell的數(shù)量太大，直接用來A Star效率很低 在NPC大多數(shù)時(shí)候不需要跳躍、游泳、空中飛行的時(shí)候，可以是用NavMesh來描述(mio sh)尋路所需要的地圖障礙信息 NavMesh使用凸多邊形來描述(mio sh)可以移動(dòng)的區(qū)域，數(shù)量通常只有CELL的幾十分之一到數(shù)百分之一第4頁/共30頁第五頁，共30頁。第5頁

3、/共30頁第六頁，共30頁。第6頁/共30頁第七頁，共30頁。為什么要獨(dú)立出去？不必?fù)?dān)心阻塞游戲服務(wù)器的主循環(huán)。不論是主服務(wù)器還是尋路模塊，都變得更簡單一些。為什么是進(jìn)程而不是線程？尋路模塊使用自己的地圖描述數(shù)據(jù)，和其他邏輯(lu j)模塊沒有太多需要共享的資源。更健壯。尋路模塊本身沒有狀態(tài)，也沒有不能丟失的動(dòng)態(tài)數(shù)據(jù)。即使尋路模塊掛了，也不會(huì)影響游戲的主服務(wù)器。直接重啟就可以了。第7頁/共30頁第八頁，共30頁。第8頁/共30頁第九頁，共30頁。AI的行為會(huì)經(jīng)常周期性的調(diào)用尋路。附近有很多NPC，他們的坐標(biāo)很接近，尋路的計(jì)算是很相似(xin s)，或者完全相同的。如果將尋路的計(jì)算結(jié)果緩存起來，

4、就可以減少重復(fù)運(yùn)算。第9頁/共30頁第十頁，共30頁。第10頁/共30頁第十一頁，共30頁。一份地圖的NavMesh數(shù)據(jù)需要加載到多個(gè)尋路服務(wù)進(jìn)程中，浪費(fèi)寶貴的內(nèi)存。每個(gè)尋路進(jìn)程單獨(dú)Cache尋路結(jié)果，使得尋路Cache中的數(shù)據(jù)重復(fù)，命中次數(shù)下降。對(duì)于硬件需求過高。一般不可能(knng)做到每臺(tái)尋路服務(wù)器都在獨(dú)立的物理服務(wù)器上。第11頁/共30頁第十二頁，共30頁。第12頁/共30頁第十三頁，共30頁。在不考慮地形(dxng)(障礙)動(dòng)態(tài)變化的情況下，NavMesh的數(shù)據(jù)是靜態(tài)的。所有尋路進(jìn)程可以同時(shí)讀取共享數(shù)據(jù)。但是Cache是動(dòng)態(tài)刷新的。必須考慮進(jìn)程間的同步問題。第13頁/共30頁第十四頁

5、，共30頁。對(duì)Cache進(jìn)行加鎖尋路算法每搜索一塊區(qū)域時(shí)都要獲取鎖，然后判斷(pndun)Cache里是否有可以利用的數(shù)據(jù)。當(dāng)尋路出新的路徑時(shí)也要獲取鎖，并將計(jì)算結(jié)果寫入Cache中。尋路過程中總是在獲取鎖，等于單進(jìn)程跑。第14頁/共30頁第十五頁，共30頁。尋路過程中可以明確區(qū)分讀寫兩個(gè)階段尋路過程中，獲取讀鎖來獲取Cache數(shù)據(jù)。尋路結(jié)束(jish)后，獲取寫鎖來更新Cache數(shù)據(jù)。多個(gè)進(jìn)程可以同時(shí)讀Cache，但是如果有進(jìn)程要寫Cache的話，所有進(jìn)程都要等。第15頁/共30頁第十六頁，共30頁。為每個(gè)進(jìn)程增加一個(gè)本地的私有Cache。尋路進(jìn)程算出結(jié)果后只將尋路結(jié)果更新到本地的Cache

6、。而不是立刻去寫共享的Cache。等一段時(shí)間之后，進(jìn)程再一次性講本地Cache的內(nèi)容(nirng)提交到共享Cache。降低了進(jìn)程獲取共享Cache寫鎖的頻率，從而提高并發(fā)能力。第16頁/共30頁第十七頁，共30頁。第17頁/共30頁第十八頁，共30頁。 鎖的目的就是讓程序變得不并行。 鎖本身的代價(jià)很高，特別是進(jìn)程之間的鎖，往往需要(xyo)使用操作系統(tǒng)內(nèi)核對(duì)象來實(shí)現(xiàn)，獲取和釋放的開銷通常在1000 CPU Tick左右。 鎖很不安全，只有有一初代碼沒有按規(guī)矩來獲取或者釋放鎖，整個(gè)系統(tǒng)都會(huì)出問題。第18頁/共30頁第十九頁，共30頁。引入一個(gè)調(diào)度(diod)進(jìn)程。所有尋路進(jìn)程的任務(wù)由調(diào)度(di

7、od)進(jìn)程分配。所有尋路進(jìn)程完成尋路任務(wù)的時(shí)候向調(diào)度(diod)進(jìn)程匯報(bào)。調(diào)度(diod)進(jìn)程沒有分配任務(wù)的時(shí)候，尋路進(jìn)程不能訪問共享Cache（讀/寫都不行）。調(diào)度(diod)進(jìn)程可以在沒有進(jìn)程訪問共享Cache的時(shí)候向一個(gè)進(jìn)程分配更新共享Cache的任務(wù)。第19頁/共30頁第二十頁，共30頁。第20頁/共30頁第二十一頁，共30頁。 調(diào)度進(jìn)程會(huì)周期性的控制尋路進(jìn)程向共享Cache中更新數(shù)據(jù)。 再此之前，調(diào)度程序會(huì)保證(bozhng)所有的尋路進(jìn)程都是等待狀態(tài)。 再此期間，調(diào)度程序不會(huì)向任何尋路進(jìn)程發(fā)出新的尋路任務(wù)。第21頁/共30頁第二十二頁，共30頁。調(diào)度本身做的事情很簡單，開銷相對(duì)于尋

8、路算法而言可以忽略不計(jì)。由于每個(gè)尋路進(jìn)程有本地Cache，所以調(diào)度算法應(yīng)該將同一個(gè)地圖并且坐標(biāo)(zubio)相近的尋路任務(wù)盡量分配給同一個(gè)尋路進(jìn)程。調(diào)度控制尋路進(jìn)程將本地Cache提交到共享Cache的頻率會(huì)影響整個(gè)系統(tǒng)的效率。頻率太低的話，共享Cache中有效數(shù)據(jù)就少。頻率太高的話，不管用不用鎖寫操作是互斥的。第22頁/共30頁第二十三頁，共30頁。如果調(diào)度器分配一個(gè)任務(wù)給尋路進(jìn)程，但是尋路進(jìn)程出錯(cuò)，而一直(yzh)沒有給調(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)程獲取了鎖，而一直(yzh)沒有釋放這個(gè)鎖，是一樣的道理。第23頁/共30頁第二十四頁，共30頁。第24頁/共30頁第二十五頁，共30頁。第25頁/共30頁第二十六頁，共30頁。允許一個(gè)模塊(m kui)可以有多份實(shí)例（進(jìn)程）。多個(gè)實(shí)例要求接口（協(xié)議）兼容，不需要二進(jìn)制匹配。調(diào)度器可識(shí)別不同模塊(m kui)和版本。一旦發(fā)現(xiàn)新版本就停止向舊模塊(m kui)分配任務(wù)。當(dāng)舊模塊(m kui)執(zhí)行完當(dāng)前的任務(wù)時(shí)可以卸載。第26頁/共30頁第二十七