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

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

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

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

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

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

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

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

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