《仙剑奇侠传online》游戏后台优化分析：CPU、内存与启动时间
一、服務(wù)器CPU性能優(yōu)化
1.1尋路算法JPS優(yōu)化
MMORPG游戲中服務(wù)器中需要對(duì)NPC尋路，然而A*算法及其各種優(yōu)化并不讓人滿意，因此尋路算法也成為瓶頸之一。
因此，本文介紹JPS的效率、多線程、內(nèi)存、路徑優(yōu)化算法。為了測試搜索算法的優(yōu)化性能，實(shí)驗(yàn)中設(shè)置游戲場景使得起點(diǎn)和終點(diǎn)差距200個(gè)格子，需要尋路104次。結(jié)果發(fā)現(xiàn)，A*尋路總時(shí)間約2.6074x1011納秒（一秒為109納秒）；基礎(chǔ)版JPS尋路總時(shí)間1.7037x1010納秒；利用位運(yùn)算優(yōu)化的JPS（下文稱JPS-Bit）尋路總時(shí)間3.2364x109納秒；利用位運(yùn)算和剪枝優(yōu)化的JPS（下文稱JPS-BitPrune）尋路總時(shí)間2.3703x109納秒；利用位運(yùn)算和預(yù)處理的JPS（下文稱JPS-BitPre）尋路總時(shí)間2.0043x109納秒；利用位運(yùn)算、剪枝和預(yù)處理三個(gè)優(yōu)化的JPS（下文稱JPS-BitPrunePre）尋路總時(shí)間9.5434x108納秒。
上述結(jié)果表明，尋路200個(gè)格子的路徑，JPS的五個(gè)版本，平均消耗時(shí)間分別為1.7毫秒、0.32毫秒、0.23毫秒、0.02毫秒、0.095毫秒，尋路速度分別為A*算法的15倍、81倍、110倍、130倍、273倍，大幅度超越A*算法，標(biāo)志著尋路已經(jīng)不會(huì)成為性能的瓶頸。
事實(shí)上，在2012到2014年舉辦的三屆（目前為止只有三屆）基于Grid網(wǎng)格尋路的比賽GPPC（The Grid-Based Path Planning Competition）中，JPS已經(jīng)被證明是基于無權(quán)重格子，在沒有預(yù)處理的情況下尋路最快的算法。
1.1.1 JPS算法介紹
JPS又名跳點(diǎn)搜索算法（Jump Point Search），是由澳大利亞兩位教授于2011年提出的基于Grid格子的尋路算法。A*算法整體流程如表1.1.1.1.1所示，JPS算法在保留A*算法的框架的同時(shí)，進(jìn)一步優(yōu)化了A*算法尋找后繼節(jié)點(diǎn)的操作。為了說明JPS在A*基礎(chǔ)上的具體優(yōu)化策略，我們?cè)趫D1.1.1.1.1中給出A*和JPS的算法流程圖對(duì)比。由圖1.1.1.1.1看出，JPS與A*算法主要區(qū)別在后繼節(jié)點(diǎn)拓展策略上，不同于A*算法中直接獲取當(dāng)前節(jié)點(diǎn)所有非關(guān)閉的可達(dá)鄰居節(jié)點(diǎn)來進(jìn)行拓展的策略，JPS根據(jù)當(dāng)前結(jié)點(diǎn)current的方向、并基于跳點(diǎn)的策略來擴(kuò)展后繼節(jié)點(diǎn)，遵循“兩個(gè)定義、三個(gè)規(guī)則”（見表1.1.1.1.2，兩個(gè)定義確定強(qiáng)迫鄰居、跳點(diǎn)，三個(gè)規(guī)則確定節(jié)點(diǎn)的拓展原則），具體流程如下：
一，若current當(dāng)前方向是直線方向：
（1）如果current左后方不可走且左方可走（即左方是強(qiáng)迫鄰居），則沿current左前方和左方尋找不在closedset的跳點(diǎn)；
（2）如果current當(dāng)前方向可走，則沿current當(dāng)前方向?qū)ふ也辉赾losed集合的跳點(diǎn)；
（3）如果current右后方不可走且右方可走（右方是強(qiáng)迫鄰居），則沿current右前方和右方尋找不在closedset的跳點(diǎn)；
二，若current當(dāng)前方向?yàn)閷?duì)角線方向：
（1）如果current當(dāng)前方向的水平分量可走（例如current當(dāng)前為東北方向，則水平分量為東），則沿current當(dāng)前方向的水平分量尋找不在closedset的跳點(diǎn)；
（2）如果current當(dāng)前方向可走，則沿current當(dāng)前方向?qū)ふ也辉赾losedset的跳點(diǎn)；
（3）如果current當(dāng)前方向的垂直分量可走（例如current當(dāng)前為東北方向，則垂直分量為北），則沿current當(dāng)前方向的垂直分量尋找不在closedset的跳點(diǎn)。
JPS尋找跳點(diǎn)的過程有三種優(yōu)化：一，位運(yùn)算；二；預(yù)處理；三；剪枝中間跳點(diǎn)。
?
表1.1.1.1.1 A*算法流程：
?
| ??Step 1.?將起始點(diǎn)start加入開啟集合openset ??Step 2.?重復(fù)以下工作： ??當(dāng)openset為空，則結(jié)束程序，此時(shí)沒有路徑。 ??尋找openset中F值最小的節(jié)點(diǎn)，設(shè)為當(dāng)前點(diǎn)current ??從openset中移出當(dāng)前點(diǎn)current ??關(guān)閉集合closedset中加入當(dāng)前點(diǎn)current ??若current為目標(biāo)點(diǎn)goal，則結(jié)束程序，此時(shí)有路徑生成，此時(shí)由goal節(jié)點(diǎn)開始逐級(jí)追溯路徑上每一個(gè)節(jié)點(diǎn)x的上一級(jí)父節(jié)點(diǎn)parent(x)，直至回溯到開始節(jié)點(diǎn)start，此時(shí)回溯的各節(jié)點(diǎn)即為路徑。 ??對(duì)current的八個(gè)方向的每一個(gè)相鄰點(diǎn)neighbor ??如果neighbor不可通過或者已經(jīng)在closedset中，略過。 ??如果neighbor不在openset中，加入openset中 ??如果neighbor在openset中，G值判定，若此路徑G值比之前路徑小，則neighbor的父節(jié)點(diǎn)為current，同時(shí)更新G與F值。反之，則保持原來的節(jié)點(diǎn)關(guān)系與G、F值。G值表示從起點(diǎn)到當(dāng)前點(diǎn)路徑耗費(fèi)；H值表示不考慮不可通過區(qū)域，當(dāng)前點(diǎn)到終點(diǎn)的理論路徑耗費(fèi)；F=G+H。 ?? ?? | |
| ??術(shù)語參考： ?? | |
| ??current ?? | ??當(dāng)前節(jié)點(diǎn) ?? |
| ??openset ?? | ??開啟節(jié)點(diǎn)集合，集合內(nèi)節(jié)點(diǎn)有待進(jìn)一步探索拓展 ?? |
| ??closedset ?? | ??關(guān)閉節(jié)點(diǎn)結(jié)合，集合內(nèi)節(jié)點(diǎn)后續(xù)不再進(jìn)行拓展 ?? |
| ??neighbor ?? | ??鄰居，與當(dāng)前節(jié)點(diǎn)相鄰的節(jié)點(diǎn) ?? |
| ??parent(x) ?? | ??節(jié)點(diǎn)x的父節(jié)點(diǎn)，即算法尋得的路徑中節(jié)點(diǎn)parent(x)的下一節(jié)點(diǎn)為x ?? |
表1.1.1.1.2 JPS算法的“兩個(gè)定義、三個(gè)規(guī)則”：
?
| ??定義一，強(qiáng)迫鄰居（forced neighbour）：如果點(diǎn)n是x的鄰居，并且點(diǎn)n的鄰居有阻擋（不可行走的格子），并且從parent(x)、x、n的路徑長度比其他任何從parent(x)到n且不經(jīng)過x的路徑短，其中parent(x)為路徑中x的前一個(gè)點(diǎn)，則n為x的強(qiáng)迫鄰居，x為n的跳點(diǎn)），例如圖2中，尋找從S到E的路徑時(shí)，K為I的強(qiáng)迫鄰居（I為K的跳點(diǎn)）。這里不認(rèn)為從H到K能走，因?yàn)閷?duì)角線有阻擋（這點(diǎn)和論文不一致，但和代碼一致，因?yàn)槿绻鸋到K能直接到達(dá)，會(huì)走進(jìn)H右邊的阻擋區(qū)，大部分的JPS開源代碼根據(jù)論文都認(rèn)為H到K能走，所以存在穿越阻擋的情況），如果需要H到K可走，則K為H的強(qiáng)迫鄰居（H為K的跳點(diǎn)）。 ??定義二，跳點(diǎn)（jump point）：（1）如果點(diǎn)y是起點(diǎn)或目標(biāo)點(diǎn)，則y是跳點(diǎn)，例如圖2中，S是起點(diǎn)也是跳點(diǎn)，E是目標(biāo)點(diǎn)也是跳點(diǎn)；（2）如果y有鄰居且是強(qiáng)迫鄰居則y是跳點(diǎn)，??例如I是跳點(diǎn)，請(qǐng)注意此類跳點(diǎn)和強(qiáng)迫鄰居是伴生關(guān)系，從上文強(qiáng)迫鄰居的定義來看n是強(qiáng)迫鄰居，x是跳點(diǎn)，二者的關(guān)系是伴生的，例如圖2中K的鄰居只有I是跳點(diǎn)，M雖然也是K的鄰居，但M不是跳點(diǎn)，因?yàn)镵不是M的強(qiáng)迫鄰居；（3）如果parent(y)到y(tǒng)是對(duì)角線移動(dòng)，并且y經(jīng)過水平或垂直方向移動(dòng)可以到達(dá)跳點(diǎn)，則y是跳點(diǎn)，例如圖2中G是跳點(diǎn)，因?yàn)閜arent(G)為S，S到G為對(duì)角線移動(dòng)，從G到跳點(diǎn)I為垂直方向移動(dòng)，I是跳點(diǎn)，所以G也是跳點(diǎn)。 ??規(guī)則一，JPS搜索跳點(diǎn)的過程中，如果直線方向（為了和對(duì)角線區(qū)分，直線方向代表水平方向、垂直方向，下文所說的直線均為水平方向和垂直方向）、對(duì)角線方向都可以移動(dòng)，則首先在直線方向搜索跳點(diǎn)，再在對(duì)角線方向搜索跳點(diǎn)。 ??規(guī)則二，（1）如果從parent(x)到x是直線移動(dòng)，n是x的鄰居，若有從parent(x)到n的路徑不經(jīng)過x且路徑長度小于或等于從parent(x)經(jīng)過x到n的路徑，則走到x后下一個(gè)點(diǎn)不會(huì)走到n；（2）如果從parent(x)到x是對(duì)角線移動(dòng)，n是x的鄰居，若有從parent(x)到n的路徑不經(jīng)過x且路徑長度小于從parent(x)經(jīng)過x到n的路徑，則走到x后下一個(gè)點(diǎn)不會(huì)走到n（相關(guān)證明見論文）。 ??規(guī)則三，只有跳點(diǎn)才會(huì)加入openset，因?yàn)樘c(diǎn)會(huì)改變行走方向，而非跳點(diǎn)不會(huì)改變行走方向，最后尋找出來的路徑點(diǎn)也只會(huì)是跳點(diǎn)集合的子集。 ?? |
1.1.1.2 JPS算法舉例
?
| ??S ?? | ??F ?? | ?? ?? | ?? ?? | ??E ?? |
| ??A ?? | ??G ?? | ?? ?? | ?? ?? | ??O ?? |
| ??B ?? | ??H ?? | ?? ?? | ?? ?? | ??P ?? |
| ??C ?? | ??I ?? | ??K ?? | ??M ?? | ??Q ?? |
| ??D ?? | ??J ?? | ??L ?? | ??N ?? | ??R ?? |
下面舉例說明JPS具體的尋路流程。問題示例如圖1.1.1.2.1所示，5*5的網(wǎng)格，黑色代表阻擋區(qū)，S為起點(diǎn)，E為終點(diǎn)。JPS要尋找從S到E的最短路徑，首先初始化將S加入openset。從openset取出F值最小的點(diǎn)S，并從openset刪除，加入closedset，S的當(dāng)前方向?yàn)榭?#xff0c;則沿八個(gè)方向?qū)ふ姨c(diǎn)，在該圖中只有下、右、右下三個(gè)方向可走，但向下遇到邊界，向右遇到阻擋，因此都沒有找到跳點(diǎn)，然后沿右下方向?qū)ふ姨c(diǎn)，在G點(diǎn)，根據(jù)上文定義二的第（3）條，parent(G)為S，praent(G)到S為對(duì)角線移動(dòng)，并且G經(jīng)過垂直方向移動(dòng)（向下移動(dòng)）可以到達(dá)跳點(diǎn)I，因此G為跳點(diǎn)，將G加入openset。從openset取出F值最小的點(diǎn)G，并從openset刪除，加入closedset，因?yàn)镚當(dāng)前方向?yàn)閷?duì)角線方向（從S到G的方向），因此在右、下、右下三個(gè)方向?qū)ふ姨c(diǎn)，在該圖中只有向下可走，因此向下尋找跳點(diǎn)，根據(jù)上文定義二的第（2）條找到跳點(diǎn)I，將I加入openset。從openset取出F值最小的點(diǎn)I，并從openset刪除，加入closedset，因?yàn)镮的當(dāng)前方向?yàn)橹本€方向（從G到I的方向），在I點(diǎn)時(shí)I的左后方不可走且左方可走，因此沿下、左、左下尋找跳點(diǎn)，但向下、左下都遇到邊界，只有向左尋找到跳點(diǎn)Q（根據(jù)上文定義二的第（2）條）），因此將Q加入openset。從openset取出F值最小的點(diǎn)Q，并從openset刪除，加入closedset，因?yàn)镼的當(dāng)前方向?yàn)橹本€方向，Q的左后方不可走且左方可走，因此沿右、左、左上尋找跳點(diǎn)，但向右、左上都遇到邊界，只有向左尋找到跳點(diǎn)E（根據(jù)上文定義二的第（1）條）），因此將E加入openset。從openset取出F值最小的點(diǎn)E，因?yàn)镋是目標(biāo)點(diǎn)，因此尋路結(jié)束，路徑是S、G、I、Q、E。
注意，本文不考慮從H能走到K的情況，因?yàn)閷?duì)角線有阻擋（這點(diǎn)和論文不一致，但和代碼一致，因?yàn)槿绻鸋到K能直接到達(dá)，會(huì)走進(jìn)H右邊的阻擋區(qū)，大部分的JPS開源代碼根據(jù)論文都認(rèn)為H到K能直接到達(dá)，所以存在穿越阻擋的情況），如果需要H到K能走，則路徑是S、G、H、K、M、P、E，修改跳點(diǎn)的計(jì)算方法即可。
上述的JPS尋路效率是明顯快于A*的，原因在于：在從S到A沿垂直方向?qū)ぢ窌r(shí)，在A點(diǎn)，如果是A*算法，會(huì)將F、G、B、H都加入openset，但是在JPS中這四個(gè)點(diǎn)都不會(huì)加入openset。對(duì)F、G、H三點(diǎn)而言，因?yàn)閺腟、A、F的路徑長度比S、F長，所以從S到F的最短路徑不是S、A、F路徑，同理S、A、G也不是最短路徑，根據(jù)上文規(guī)則二的第（1）條，走到A后不會(huì)走到F、G，所以F、G不會(huì)加入openset，雖然S、A、H是S到H的最短路徑，但因?yàn)榇嬖赟、G、H的最短路徑且不經(jīng)過A，據(jù)上文規(guī)則二的第（1）條，從S走到A后，下一個(gè)走的點(diǎn)不會(huì)是H，因此H也不會(huì)加入openset；對(duì)B點(diǎn)而言，根據(jù)上文規(guī)則三，B不是跳點(diǎn)，也不會(huì)加入openset，直接走到C即可。
表1.1.1.2.1所示為A*和JPS在尋路消耗中的對(duì)比，D.Age:Origins、D.Age 2、StarCraft為三個(gè)游戲龍騰世紀(jì)：起源、、龍騰世紀(jì)2、星際爭霸的場景圖集合，M.Time表示操作openset和closedset的時(shí)間，G.Time表示搜索后繼節(jié)點(diǎn)的時(shí)間。可見A*大約有58%的時(shí)間在操作openset和closedset，42%時(shí)間在搜索后繼節(jié)點(diǎn)；而JPS大約14%時(shí)間在操作openset和closedset，86%時(shí)間在搜索后繼節(jié)點(diǎn)。避免在openset中加入太多點(diǎn)，從而避免過多的維護(hù)最小堆是JPS比A*快的原因（（最小堆插入新元素時(shí)間復(fù)雜度log(n)，刪除最小元素后調(diào)整堆，時(shí)間復(fù)雜度也為log(n)）），實(shí)際上在從S到E的尋路過程中，進(jìn)入openset的只有S、G、I、Q、E
表1.1.1.2.1 A*和JPS的尋路消耗對(duì)比
?
1.1.2 JPS五個(gè)優(yōu)化算法
1.1.2.1 JPS優(yōu)化之一JPS-Bit：位運(yùn)算優(yōu)化
利用位運(yùn)算優(yōu)化的JPS-Bit的關(guān)鍵優(yōu)化思路在于利用位運(yùn)算來優(yōu)化JPS中節(jié)點(diǎn)拓展的效率。下面以圖1.1.2.1.1中的場景示例說明如何將位運(yùn)算融合于JPS算法中，其中黑色部分為阻擋，假設(shè)當(dāng)前位置為I（標(biāo)藍(lán)位置），當(dāng)前方向?yàn)橛?#xff0c;位運(yùn)算中使用1代表不可走，0代表可走，則I當(dāng)前行B的八位可以用八個(gè)bit：00000100表示，I上一行B-的八位可以用八個(gè)bit：00000000表示，I的下一行B+的八位可以用八個(gè)bit：00110000表示。在當(dāng)前行尋找阻擋的位置可以用CPU的指令__builtin_clz(B)（返回前導(dǎo)0的個(gè)數(shù)），即當(dāng)前阻擋在第5個(gè)位置（從0開始）。尋找當(dāng)前行的跳點(diǎn)可以用__builtin_clz(((B->>1)&&!B-)||((B+>>1)&&!B+))尋找，例如本例中(B+>>1)&&!B+為：(00110000>>1)&&11001111，即00001000，而(B->>1)&&!B為00000000，所以__builtin_clz(((B->>1)&&!B-)||((B+>>1)&&!B+))為__builtin_clz(00001000)為4，所以跳點(diǎn)為第4個(gè)位置M（從0開始）。注意論文中使用_builtin_ffs(((B-<<1)&&!B-)||((B+<<1)&&!B+))，__builtin_ffs(x)返回x的最后一位1是從后向前第幾位，比如7368（1110011001000）返回4，因?yàn)檎撐膶?duì)格子的bit編碼采用小端模式，而這里對(duì)格子的bit編碼采用大端模式。
由于JPS-Bit使用運(yùn)算效率更高的位運(yùn)算和CPU指令運(yùn)算來優(yōu)化原始JPS節(jié)點(diǎn)擴(kuò)展過程中的遍歷操作，JPS-Bit的算法效率高于原始的JPS，實(shí)測中JPS-Bit的尋路時(shí)間比JPS縮短5倍左右。
?
| ??A ?? | ??B ?? | ??C ?? | ??D ?? | ??E ?? | ??F ?? | ??G ?? | ??H ?? |
| ??I ?? | ??J ?? | ??K ?? | ??L ?? | ??M ?? | ?? ?? | ??N ?? | ??O ?? |
| ??P ?? | ??Q ?? | ?? ?? | ?? ?? | ??R ?? | ??S ?? | ??T ?? | ??U ?? |
1.1.2.2 JPS優(yōu)化之二JPS-BitPrune：位運(yùn)算與剪枝優(yōu)化
利用位運(yùn)算和剪枝優(yōu)化的JPS-BitPrune在JPS-Bit的基礎(chǔ)上進(jìn)一步進(jìn)行剪枝優(yōu)化，剪掉不必要的中間跳點(diǎn)（見表1.1.1.1.2，定義二第(3)條定義），根據(jù)定義二，中間跳點(diǎn)在節(jié)點(diǎn)拓展過程中只具有簡單的“承接”作用，不具備拓展價(jià)值，將中間跳點(diǎn)放入openset會(huì)增大擴(kuò)展的次數(shù)，因此JPS-BitPrune將中間跳點(diǎn)全部刪除，將中間跳點(diǎn)后繼跳點(diǎn)中的非中間跳點(diǎn)的父跳點(diǎn)改為中間跳點(diǎn)的父跳點(diǎn)，可以有效避免冗余的節(jié)點(diǎn)拓展運(yùn)算。
拐點(diǎn)獲取：值得一提的是，JPS-BitPrune由于刪除了中間跳點(diǎn)，因此JPS-BitPrune需要在搜索到完整的路徑之后以一定的策略在最后尋得的路徑中加入中間拐點(diǎn)，使得每兩個(gè)相鄰的路徑節(jié)點(diǎn)之間都是垂直、水平、對(duì)角線方向可達(dá)的。對(duì)此，JPS-BitPrune采用的具體方法如下：
假設(shè)目前搜索到的路徑為start(jp1)、jp2、jp3...jpk..end(jpn)，對(duì)每兩個(gè)相鄰的跳點(diǎn)jpi、jpi+1，一，如果jpi、jpi+1的x坐標(biāo)或者y坐標(biāo)相等，說明這兩個(gè)跳點(diǎn)在同一個(gè)水平方向或垂直方向，可以直線到達(dá)，無需在這兩個(gè)跳點(diǎn)之間加入拐點(diǎn)；二，如果jpi、jpi+1的x坐標(biāo)和y坐標(biāo)都不相等，（1）如果x坐標(biāo)的差dx（即jpi的x坐標(biāo)減去jpi+1的x坐標(biāo)）和y坐標(biāo)的差dy的絕對(duì)值相等，說明這兩個(gè)跳點(diǎn)在對(duì)角線方向，也可以直線到達(dá)，無需在這兩個(gè)跳點(diǎn)之間加入拐點(diǎn)；（2）如果x坐標(biāo)的差dx和y坐標(biāo)的差dy的絕對(duì)值不相等，說明這兩個(gè)跳點(diǎn)不在對(duì)角線方向，并且有可能不能直線到達(dá)（因?yàn)樘c(diǎn)附近有阻擋），此時(shí)jpi、jpi+1之間只需要加入一個(gè)從jpi出發(fā)離jpi+1最近的對(duì)角線上的點(diǎn)即可（jpi、jpi+1不能水平、垂直、對(duì)角線到達(dá)，說明jpi、jpi+1之間一定存在被剪枝的中間跳點(diǎn)，只需要補(bǔ)上離jpi+1最近的一個(gè)中間跳點(diǎn)充當(dāng)拐點(diǎn)即可，該拐點(diǎn)即為jpi沿對(duì)角線方向走min(dx,dy)步到達(dá)的點(diǎn)）。
?
圖1.1.2.2.1 JPS-BitPrune的剪枝優(yōu)化示例
下面以圖1.1.2.2.1的問題場景示例JPS-BitPrune如何在剪枝的同時(shí)進(jìn)行尋路。起點(diǎn)為S（坐標(biāo)為(1,1)，即S(1,1)），節(jié)點(diǎn)1、4、6均為中間跳點(diǎn)：因?yàn)楣?jié)點(diǎn)2、3是滿足定義二第(2)條的跳點(diǎn)，所以節(jié)點(diǎn)1是為了到達(dá)節(jié)點(diǎn)2、3的中間跳點(diǎn)，同理節(jié)點(diǎn)4、6也為中間跳點(diǎn)。在剪枝中間跳點(diǎn)之前，要將中間跳點(diǎn)的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)調(diào)整為該中間跳點(diǎn)的父節(jié)點(diǎn)。例如圖1.1.2.2.1中，節(jié)點(diǎn)1的后繼跳點(diǎn)為節(jié)點(diǎn)2、3、4，其中節(jié)點(diǎn)4也為中間跳點(diǎn)，刪掉中間跳點(diǎn)中的節(jié)點(diǎn)1后，節(jié)點(diǎn)2、3的父跳點(diǎn)由節(jié)點(diǎn)1改為節(jié)點(diǎn)S，刪除中間跳點(diǎn)中的節(jié)點(diǎn)4后，節(jié)點(diǎn)4的后繼跳點(diǎn)5的父跳點(diǎn)由節(jié)點(diǎn)4改為節(jié)點(diǎn)S（節(jié)點(diǎn)4的父跳點(diǎn)為節(jié)點(diǎn)1，但節(jié)點(diǎn)1已經(jīng)被刪掉，因此回溯到節(jié)點(diǎn)S），刪除中間跳點(diǎn)中的節(jié)點(diǎn)6后，節(jié)點(diǎn)6的后繼跳點(diǎn)7的父跳點(diǎn)由節(jié)點(diǎn)6改為節(jié)點(diǎn)S（節(jié)點(diǎn)6的父跳點(diǎn)為節(jié)點(diǎn)4，但節(jié)點(diǎn)4被刪，節(jié)點(diǎn)4的父跳點(diǎn)節(jié)點(diǎn)1也被刪，因此回溯到節(jié)點(diǎn)S）。
上述過程是簡化的邏輯描述，實(shí)際運(yùn)行中的做法是從節(jié)點(diǎn)S尋找跳點(diǎn)，首先找到中間跳點(diǎn)節(jié)點(diǎn)1，然后在水平方向和垂直方向?qū)ふ业教c(diǎn)節(jié)點(diǎn)2、3，將節(jié)點(diǎn)2、3的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S；繼續(xù)沿對(duì)角線方向?qū)ふ姨c(diǎn)，走到節(jié)點(diǎn)4后，沿水平方向和垂直方向?qū)ふ业教c(diǎn)節(jié)點(diǎn)5，將節(jié)點(diǎn)5的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S；繼續(xù)沿對(duì)角線方向?qū)ふ姨c(diǎn)，走到節(jié)點(diǎn)6后，沿水平方向和垂直方向?qū)ふ业教c(diǎn)7，將跳點(diǎn)7的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S。因此JPS-BitPrune獲得路徑S(1,1)、節(jié)點(diǎn)7(4,6)。
因?yàn)槁窂街蠸(1,1)無法垂直、水平、對(duì)角線方向走到節(jié)點(diǎn)7(4,6)，需要加入中間拐點(diǎn)，根據(jù)上述的拐點(diǎn)添加策略，有dx為3，dy為5，需要從S沿對(duì)角線走3步，即節(jié)點(diǎn)6(4,4)可作為中間拐點(diǎn)，因此，在圖1.1.2.2.1的示例中，JPS-BitPrune最后構(gòu)建的完整路徑為S(1,1)、節(jié)點(diǎn)6(4,4)、節(jié)點(diǎn)7(4,6)。
1.1.2.2.1剪枝的優(yōu)化效率
下面通過對(duì)比剪枝前后的JPS節(jié)點(diǎn)拓展的情況來說明剪枝操作的優(yōu)化效率：
場景一（無剪枝）如果不對(duì)中間跳點(diǎn)進(jìn)行剪枝，那么從節(jié)點(diǎn)S尋路到節(jié)點(diǎn)7將經(jīng)歷如下過程：
從節(jié)點(diǎn)S搜索跳點(diǎn)，找到跳點(diǎn)節(jié)點(diǎn)1，openset此時(shí)只有節(jié)點(diǎn)1；
從openset取出F值最小跳點(diǎn)節(jié)點(diǎn)1，并搜索節(jié)點(diǎn)1的后繼跳點(diǎn)，水平方向和垂直方向找到跳點(diǎn)節(jié)點(diǎn)2、3，對(duì)角線方向找到跳點(diǎn)節(jié)點(diǎn)4，此時(shí)openset有節(jié)點(diǎn)2、3、4；
從openset取出F值最小跳點(diǎn)節(jié)點(diǎn)4，并搜索節(jié)點(diǎn)4的后繼跳點(diǎn)，水平和垂直方向找到跳點(diǎn)節(jié)點(diǎn)5，對(duì)角線方向找到跳點(diǎn)6，此時(shí)openset有節(jié)點(diǎn)2、3、5、6；
從openset取出F值最小跳點(diǎn)節(jié)點(diǎn)6，垂直方向找到跳點(diǎn)7，此時(shí)openset有節(jié)點(diǎn)2、3、5、7；
從openset取出F值最小的跳點(diǎn)節(jié)點(diǎn)7，為目的點(diǎn)，搜索結(jié)束，因此完整路徑為節(jié)點(diǎn)S(1,1)、節(jié)點(diǎn)1(2,2)、節(jié)點(diǎn)4(3,3)、節(jié)點(diǎn)6(4,4)、節(jié)點(diǎn)7(4,6)。JPS在到達(dá)目的節(jié)點(diǎn)7之前，需要接連拓展中間跳點(diǎn)1，4，6。
場景二（剪枝中間跳點(diǎn)）在剪枝中間跳點(diǎn)之后，從節(jié)點(diǎn)S尋路到節(jié)點(diǎn)7的流程得到了明顯簡化：
從節(jié)點(diǎn)S尋找跳點(diǎn)，首先找到中間跳點(diǎn)節(jié)點(diǎn)1，然后在水平方向和垂直方向?qū)ふ业教c(diǎn)節(jié)點(diǎn)2、3，將節(jié)點(diǎn)2、3的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S；繼續(xù)沿對(duì)角線方向?qū)ふ姨c(diǎn)，走到節(jié)點(diǎn)4后，沿水平方向和垂直方向?qū)ふ业教c(diǎn)節(jié)點(diǎn)5，將節(jié)點(diǎn)5的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S；繼續(xù)沿對(duì)角線方向?qū)ふ姨c(diǎn)，走到節(jié)點(diǎn)6后，沿水平方向和垂直方向?qū)ふ业教c(diǎn)7，將跳點(diǎn)7的父跳點(diǎn)設(shè)為節(jié)點(diǎn)S；繼續(xù)沿對(duì)角線方向?qū)ふ姨c(diǎn)，遇到阻擋，搜索終止，此時(shí)openset有節(jié)點(diǎn)2、3、5、7；
從openset取出F值最小的跳點(diǎn)節(jié)點(diǎn)7，為目的點(diǎn)，搜索結(jié)束，此時(shí)獲得的路徑為S(1,1)、節(jié)點(diǎn)7(4,6)。不同于無剪枝的JPS需要拓展中間跳點(diǎn)1、4、6，在JPS-BitPrune中，節(jié)點(diǎn)1、4、6作為中間跳點(diǎn)均被剪枝，有效避免了冗余的節(jié)點(diǎn)拓展，尋路效率得到大大提升。
1.1.2.3 JPS優(yōu)化之三JPS-BitPre：位運(yùn)算與預(yù)處理
本優(yōu)化中的預(yù)處理在一些文章被稱為JPS+。JPS-BitPre和JPS-BitPrunePre都不支持動(dòng)態(tài)阻擋，因?yàn)閯?dòng)態(tài)阻擋的出現(xiàn)會(huì)導(dǎo)致八個(gè)方向最多能走的步數(shù)發(fā)生變化，從而導(dǎo)致預(yù)處理的結(jié)果不再準(zhǔn)確。利用位運(yùn)算和預(yù)處理的JPS-BitPre依舊采用JPS-Bit中的位運(yùn)算，而其中的預(yù)處理則是對(duì)每個(gè)點(diǎn)存儲(chǔ)八個(gè)方向最多能走的步數(shù)step，這個(gè)step值將影響JPS中節(jié)點(diǎn)的拓展順序和拓展“跨度”，加快尋路效率。由于預(yù)處理版本的JPS需要存儲(chǔ)八個(gè)方向最多能走多少步，如果地圖大小是N*N，每個(gè)方向最多能走的步數(shù)用16位數(shù)表示，則需要存儲(chǔ)空間N*N*8*16bit，如果N為1024，則大概需要存儲(chǔ)空間為16M，存儲(chǔ)空間占用較大，使用該版本JPS時(shí)需要權(quán)衡是否以空間換時(shí)間，另外預(yù)處理的時(shí)間對(duì)小于1024*1024個(gè)格子的圖可以在1秒內(nèi)處理完，但對(duì)于2048*2048個(gè)格子的圖需要一小時(shí)左右處理完。
其中，step值由跳點(diǎn)、阻擋、邊界等決定，如果遇到跳點(diǎn)，則step為走到跳點(diǎn)的步數(shù)；否則step為走到阻擋或邊界的步數(shù)。
例如對(duì)圖1.1.2.3.1中的N點(diǎn)，向北最多走到節(jié)點(diǎn)8，即2步；
向南最多走到節(jié)點(diǎn)4，即4步；
向西最多走到節(jié)點(diǎn)6，即3步；
向東最多走到節(jié)點(diǎn)2（節(jié)點(diǎn)2是滿足定義二第（2）條的跳點(diǎn)），即5步；
西北最多走到節(jié)點(diǎn)7，即2步；
東北最多走到節(jié)點(diǎn)1（節(jié)點(diǎn)為1是上文定義二第（3）條定義的跳點(diǎn)），即1步；
西南最多走到節(jié)點(diǎn)5，即3步；
東南最多走到節(jié)點(diǎn)3（節(jié)點(diǎn)3是上文定義二第（3）條定義的跳點(diǎn)），即3步。
?
| ??7 ?? | ?? ?? | ??7 ?? | ?? ?? | ??8 ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? |
| ??6 ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ??1 ?? | ?? ?? | ?? ?? | ??9 ?? | ?? ?? |
| ??5 ?? | ??6 ?? | ?? ?? | ?? ?? | ??N ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ??2 ?? |
| ??4 ?? | ?? ?? | ?? ?? | ??11 ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? |
| ??3 ?? | ?? ?? | ?? ?? | ??T ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? |
| ??2 ?? | ??5 ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ?? ?? | ??3 ?? | ?? ?? | ??10 ?? |
以圖1.1.2.3.1中的場景為例，要尋找從節(jié)點(diǎn)N到節(jié)點(diǎn)T的路徑，JPS-BitPre的尋路流程如下：
從openset取出節(jié)點(diǎn)N，從N沿八個(gè)方向?qū)ふ姨c(diǎn)，根據(jù)預(yù)處理得到的各方向最遠(yuǎn)可走的step值，可以快速確定八個(gè)方向最遠(yuǎn)能到達(dá)的節(jié)點(diǎn){1，2，3，4，5，6，7，8}，如圖1.1.2.3.1所示，其中，節(jié)點(diǎn)1、2、3均為滿足定義二的跳點(diǎn)，直接加入openset，對(duì)于節(jié)點(diǎn)4、5、6、7、8，首先判斷終點(diǎn)T位于以N為中心的南、西南、西、西北、北的哪部分，因?yàn)門位于西南方向，只有節(jié)點(diǎn)5位于西南方向，因此節(jié)點(diǎn)4、6、7、8直接略過，在從N到5的方向上，N可走3步，而N和T的x坐標(biāo)差絕對(duì)值dx為1，y坐標(biāo)差絕對(duì)值dy為2，因此將從節(jié)點(diǎn)N到節(jié)點(diǎn)5方向上走min(dx,dy)步即節(jié)點(diǎn)11，加入openset；
從openset取出F值最小節(jié)點(diǎn)11，垂直方向找到跳點(diǎn)T，加入openset；三，從openset取出F值最小節(jié)點(diǎn)T，為目的點(diǎn)，搜索結(jié)束，此時(shí)獲得的路徑為N(4,5)、節(jié)點(diǎn)11(3,4)、節(jié)點(diǎn)T(3,3)。
為了說明JPS-BitPre尋路的準(zhǔn)確性與高效率，這里給出原始JPS-Bit從N到T的尋路流程作為對(duì)比：
從openset取出節(jié)點(diǎn)N后，需要沿八個(gè)方向?qū)ふ姨c(diǎn)，節(jié)點(diǎn)1、3、11為上文定義二第（3）條定義的跳點(diǎn)，加入openset，節(jié)點(diǎn)2為上文定義二的第（2）條定義的跳點(diǎn)，加入openset；
從openset取出F值最小節(jié)點(diǎn)11，垂直方向找到跳點(diǎn)T，加入openset；
從openset取出F值最小跳點(diǎn)T，為目的點(diǎn)，搜索結(jié)束，此時(shí)獲得的路徑也為N(4,5)、節(jié)點(diǎn)11(3,4)、節(jié)點(diǎn)T(3,3)。
對(duì)比發(fā)現(xiàn)，經(jīng)過預(yù)處理的JPS-BitPre和只使用位運(yùn)算的JPS-Bit最后尋得的路徑是一樣的，然而，由于JPS-BitPre無需在每一步節(jié)點(diǎn)拓展過程中沿各方向?qū)ふ姨c(diǎn)，其可以根據(jù)預(yù)處理得到的step值快速確定openset的備選節(jié)點(diǎn)，從而大大提升尋路效率。
1.1.2.4 JPS優(yōu)化之四：不可達(dá)兩點(diǎn)提前判斷
如圖1.1.2.4.1所示，起點(diǎn)S不可到達(dá)終點(diǎn)E，然而尋路算法仍然會(huì)花費(fèi)時(shí)間去尋找S、E之間的路徑，而且失敗情況下尋路花費(fèi)的時(shí)間遠(yuǎn)大于成功情況下尋路花費(fèi)的時(shí)間，因?yàn)槭∏闆r下需要遍歷所有的路徑，才能確定兩點(diǎn)不可達(dá)。因此為了避免這種情況，在每次尋路之前，判斷起點(diǎn)和終點(diǎn)是否可達(dá)：如果起點(diǎn)和終點(diǎn)在同一連通區(qū)域，則起點(diǎn)和終點(diǎn)可達(dá)，否則不可達(dá)。只有起點(diǎn)和終點(diǎn)可達(dá)，才需要去尋路。
首先計(jì)算Grid網(wǎng)格的連通區(qū)域，算法如表1.1.2.4.1所示，算法只能采用寬度優(yōu)先搜索，深度優(yōu)先搜索的遞歸層次太深，會(huì)導(dǎo)致棧溢出。按照表1.1.2.4.1的算法，圖1.1.2.4.1的點(diǎn)S、1、2的連通區(qū)域編號(hào)均為1，點(diǎn)3、4、E的連通區(qū)域編號(hào)均為2，S、E連通區(qū)域編號(hào)不同，因此S、E不在同一連通區(qū)域，不需要尋找路徑。表1.1.2.4.1的算法在程序啟動(dòng)時(shí)計(jì)算一次即可，算法復(fù)雜度為O(N)，N為Grid網(wǎng)格數(shù)目，運(yùn)行時(shí)只需要查詢兩點(diǎn)是否在同一連通區(qū)域，算法復(fù)雜度為O(1)。
?
表1.1.2.4.1計(jì)算連通區(qū)域
?
| ??Step1.?當(dāng)前連通區(qū)域編號(hào)num初始化為0?? ??Step2.?對(duì)Grid網(wǎng)格每個(gè)點(diǎn)current重復(fù)以下工作： ??? ??一、 num++。 ??二、 如果current是阻擋點(diǎn)，跳過。 ??三、 如果current被訪問過，跳過。 ??四、 current的連通區(qū)域編號(hào)記為num，標(biāo)記已訪問過。 ??五、 寬度優(yōu)先搜索和current四連通的所有Grid網(wǎng)格點(diǎn)，連通區(qū)域編號(hào)均記為num， ??? ???并標(biāo)記已訪問過。 ?? |
1.1.2.5 JPS優(yōu)化之五：空間換時(shí)間
openset采用最小堆實(shí)現(xiàn)，最小堆的底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組，從最小堆中插入、刪除時(shí)間復(fù)雜度為O(logn)。除了刪除還需要查找操作，每次找到一個(gè)跳點(diǎn)，都需要判斷在最小堆中是否有，如果有，則判斷是否更新G值、F值、父跳點(diǎn)等，如果沒有，則加入openset。在最小堆的中查找操作時(shí)間復(fù)雜度O(n)，因此需要優(yōu)化。closedset存的是已經(jīng)從openset中彈出的跳點(diǎn)，實(shí)際只需要對(duì)每個(gè)跳點(diǎn)加個(gè)標(biāo)記即可，如果跳點(diǎn)打上標(biāo)記，則表示是closedset中跳點(diǎn)，否則不是。
綜合上述需求，針對(duì)1km*1km的地圖，構(gòu)建2k*2k的二維數(shù)組matrix，數(shù)組每個(gè)元素pnode均為一個(gè)指針，指針的對(duì)象類型包括節(jié)點(diǎn)id、是否擴(kuò)展過expanded(即是否在closedset中)、G值、F值、父跳點(diǎn)指針parent、在最小堆中的索引index等12個(gè)byte。如果地圖(x,y)處是搜索到的跳點(diǎn)，首先檢查在二維數(shù)組matrix對(duì)應(yīng)的(x,y)處指針pnode是否為空，如果為空，表示該跳點(diǎn)之前未搜索過，從內(nèi)存池new出一個(gè)跳點(diǎn)，將指針加到最小堆openset中，并在執(zhí)行shift up、shift down操作之后，記錄在最小堆中的索引index；如果不為空，則表示該跳點(diǎn)之前搜索過，首先檢查expand標(biāo)記，如果為真，則表示在closedset中，直接跳過該跳點(diǎn)；否則表示在openset中，通過matrix(x,y)記錄的在openset中的索引index找到對(duì)應(yīng)的指針，檢查matrix(x,y)和openset(index)的指針是否相等進(jìn)行二次確認(rèn)，然后檢查判斷是否需要更新G值、F值、父跳點(diǎn)等，采用空間換時(shí)間的方法可以將openset和closedset中查找操作降為O(1)。游戲中有很多場景，無需為每個(gè)場景構(gòu)建一個(gè)matrix，以最大的場景的大小構(gòu)建一個(gè)matrix即可。
1.1.3多線程支持
游戲服務(wù)器普遍采用單進(jìn)程多線程架構(gòu)，多線程下，不能對(duì)JPS尋路加鎖，否則尋路串行化，失去了多線程的優(yōu)勢(shì)，為了支持多線程JPS尋路，需要將一些變量聲明為線程獨(dú)有thread_local，例如上文提到的為了優(yōu)化openset和closedset的查找速度，構(gòu)建的二維跳點(diǎn)指針數(shù)組matrix。該數(shù)組必須為線程獨(dú)有，否則，不同線程在尋路時(shí)，都修改matrix元素指向的跳點(diǎn)數(shù)據(jù)，例如A線程在擴(kuò)展完跳點(diǎn)后，將expanded標(biāo)記為真，B線程再試圖擴(kuò)展該跳點(diǎn)時(shí)，發(fā)現(xiàn)已經(jīng)擴(kuò)展過，就直接跳過，導(dǎo)致尋路錯(cuò)誤。
1.1.4 JPS內(nèi)存優(yōu)化算法
1.1.4.1分層
JPS的地圖格子粒度如果采用0.5m*0.5m，每個(gè)格子占1bit，則1km*1km的地圖占用內(nèi)存2k*2k/8個(gè)byte，即0.5M；為了向上、向下也能通過取32位數(shù)獲得向上、向下的32個(gè)格子阻擋信息，需要存將地圖旋轉(zhuǎn)90度后的阻擋信息；
上文JPS優(yōu)化之四：不可達(dá)兩點(diǎn)提前判斷，需要存連通信息，假設(shè)連通區(qū)數(shù)目最多15個(gè)，則需內(nèi)存2k*2k/2個(gè)byte，即2m，則內(nèi)存為：原地圖阻擋信息0.5m、旋轉(zhuǎn)地圖阻擋信息0.5m、連通區(qū)信息2m，即3m。另外，上文提到用空間換時(shí)間的方法，為了優(yōu)化openset和closedset的查找速度，構(gòu)建二維跳點(diǎn)指針數(shù)組matrix。1km*1km的地圖，格子粒度為0.5m*0.5m，構(gòu)建出的matrix指針數(shù)組大小為2k*2k*4byte即為8m，為了支持多線程，該matrix數(shù)組必須為thread_local，即線程獨(dú)有，16個(gè)線程共需內(nèi)存16*8m即為128m，內(nèi)存空間太大，因此需要優(yōu)化這部分內(nèi)存。
首先將2k*2k分成100*100的塊，即20*20個(gè)塊，20*20個(gè)塊為第一層數(shù)組firLayerMatrix，100*100為第二層數(shù)組secLayerMatrix，firLayerMatrix的400個(gè)元素為400個(gè)指針，每個(gè)指針初始化為空，當(dāng)遍歷到的跳點(diǎn)屬于firLayerMatrix中(x,y)的塊時(shí)，則從內(nèi)存池new出100*100*4byte的secLayerMatrix，secLayerMatrix每個(gè)元素也是一個(gè)指針，指向一個(gè)從內(nèi)存池new出來的跳點(diǎn)。
例如，搜索2k*2k的地圖時(shí)，在(231,671)位置找到一個(gè)跳點(diǎn)，首先檢查firLayerMatrix的(2,6)位置指針是否為空，如果為空，則new出100*100*4byte的secLayerMatrix，繼續(xù)在secLayerMatrix查找(31,71)位置檢查跳點(diǎn)的指針是否為空，如果為空，則從內(nèi)存池new出來跳點(diǎn)，加入openset，否則檢查跳點(diǎn)的expanded標(biāo)記，如果標(biāo)記為真，表示在closedset中，直接跳過該點(diǎn)，否則表示在openset中，判斷是否更新G值、F值、父節(jié)點(diǎn)等。因?yàn)橛螒蛑蠳PC尋路均為短距離尋路，JPS尋路區(qū)域最大為80*80，一個(gè)secLayerMatrix是100*100，因此只需要一個(gè)secLayerMatrix，則兩層matrix大小為：20*20*4byte+100*100*4byte即為0.04m。
所以16個(gè)線程下，總內(nèi)存為：原地圖阻擋信息0.5m、旋轉(zhuǎn)地圖阻擋信息0.5m、連通區(qū)信息2m、兩層matrix0.04m*16，共3.64M，游戲中場景最多不到20個(gè)，所有場景JPS總內(nèi)存為72.8M。
1.1.4.2內(nèi)存池
在JPS搜索過程中，每次將一個(gè)跳點(diǎn)加入openset，都需要new出對(duì)應(yīng)的節(jié)點(diǎn)對(duì)象，節(jié)點(diǎn)對(duì)象中存節(jié)點(diǎn)id、父節(jié)點(diǎn)、尋路消耗等共12個(gè)byte，為了減少內(nèi)存碎片，以及頻繁new的時(shí)間消耗，需要自行管理內(nèi)存池，每次new節(jié)點(diǎn)對(duì)象時(shí)，均從內(nèi)存池中申請(qǐng)，內(nèi)存池詳解請(qǐng)見下文服務(wù)器內(nèi)存優(yōu)化，為了防止內(nèi)存池增長過大，需要限制搜索步數(shù)。
本文的內(nèi)存池共有兩個(gè)：
一，跳點(diǎn)的內(nèi)存池，初始大小為800個(gè)跳點(diǎn)，當(dāng)new的跳點(diǎn)數(shù)目超出800個(gè)，即停止尋路，因?yàn)榉?wù)器用JPS進(jìn)行NPC的尋路，NPC不會(huì)進(jìn)行長距離尋路，假設(shè)NPC尋路上限距離是20m，則尋路區(qū)域面積是40m*40m，格子數(shù)80*80即6400，經(jīng)統(tǒng)計(jì)跳點(diǎn)數(shù)目占所有格子數(shù)目的比例不到1/10，即跳點(diǎn)數(shù)目少于640，因此800個(gè)跳點(diǎn)足夠使用，800個(gè)跳點(diǎn)共占內(nèi)存800byte*12，即為9.6k，忽略不計(jì)；
二，secLayerMatrix指向的100*100*4byte的內(nèi)存池，因?yàn)槊看螌ぢ范夹枰辽僖粋€(gè)secLayerMatrix，如果每次尋路都重新申請(qǐng)，尋路完后再釋放，會(huì)造成開銷，因此secLayerMatrix指向的100*100*4byte的空間也在內(nèi)存池中，申請(qǐng)時(shí)，從內(nèi)存池拿出，釋放時(shí)，放回內(nèi)存池即可，secLayerMatrix內(nèi)存池占內(nèi)存0.04m。
1.1.5路徑優(yōu)化
如圖1.1.4.1所示，綠色格子為起點(diǎn)，紅色格子為終點(diǎn)，灰色格子為跳點(diǎn)，藍(lán)線為JPS搜出來的路徑，灰色虛線為搜索過程。可以看出，從綠色格子到紅色格子可以直線到達(dá)，而JPS搜索出來的路徑卻需要轉(zhuǎn)折一次，在游戲表現(xiàn)上，會(huì)顯得比較奇怪。因此在JPS搜索出來路徑后，需要對(duì)路徑進(jìn)行后處理。
比如JPS搜出來的路徑有A、B、C、D、E、F、G、H八個(gè)點(diǎn)，走到A時(shí)，需要采樣檢查A、C是否直線可達(dá)，如果A、C直線可達(dá)，再檢查A、D是否直線可達(dá)，如果A、D直線可達(dá)，繼續(xù)檢查A、E，如果A、E直線不可達(dá)，則路徑優(yōu)化為A、D、E、F、G、H，走到D時(shí)，再檢查D、F是否直線可達(dá)，如果D、F直線可達(dá)，繼續(xù)檢查D、G，如果D、G直線不可達(dá)，則路徑優(yōu)化為A、D、F、G、H。依此類推，直到走到H。因?yàn)椴蓸訖z查的速度很快，大約占JPS尋路時(shí)間的1/5，而且只有當(dāng)走到一個(gè)路點(diǎn)后，才采樣檢查該路點(diǎn)之后的路點(diǎn)是否可以合并，將采樣的消耗平攤在行走的過程中，因此采樣的消耗可以忽略。
?
1.2視野管理算法的優(yōu)化
1.2.1視野管理算法的背景
1.2.1.1九宮格
游戲中地圖用來承載阻擋、靜態(tài)建筑、NPC（非玩家控制角色：Non-Player-Controlled Character）、WRAP點(diǎn)等。玩家在地圖上移動(dòng)，其可見的其他玩家即發(fā)生變化，如果玩家的每次移動(dòng)，都更新視野列表，時(shí)間成本太高，因此只有當(dāng)玩家離開某個(gè)區(qū)域時(shí)，才更新視野列表，而在這個(gè)區(qū)域內(nèi)的移動(dòng)，并不更新視野列表。為了劃分這個(gè)區(qū)域，引入九宮格概念，如圖1所示，九個(gè)格子的總面積大于一個(gè)手機(jī)屏幕，小于兩個(gè)手機(jī)屏幕。大于一個(gè)手機(jī)屏幕的原因是，可以預(yù)先計(jì)算當(dāng)前屏幕外的一些玩家，但又沒有必要預(yù)先計(jì)算太多的屏幕外玩家，因此小于兩個(gè)手機(jī)屏幕，玩家可見的范圍為以玩家為中心周圍九個(gè)格子內(nèi)的其他玩家。
如果玩家Me在格子5內(nèi)移動(dòng)，則不主動(dòng)更新視野列表，玩家可見范圍為紅色和綠色格子內(nèi)的玩家（如果玩家Me視野列表內(nèi)的玩家He從一個(gè)格子移動(dòng)到另一個(gè)格子，導(dǎo)致Me和He不可見，也會(huì)導(dǎo)致玩家Me的視野列表發(fā)生更新，稱為被動(dòng)更新），如果玩家Me從格子5移動(dòng)到格子8則主動(dòng)更新視野列表，玩家可見范圍為紫色和綠色格子內(nèi)的玩家。
?
1.2.1.2視野管理的必要性
在大型多人在線游戲MMO（Massively Multiplayer Online）中，多個(gè)玩家在同一場景，此時(shí)玩家需要能看到其附近的玩家，同時(shí)不需要看到與其距離遠(yuǎn)的玩家。這就是視野管理需要做的事情：為每個(gè)玩家維護(hù)一個(gè)視野列表，管理每個(gè)玩家可見視野內(nèi)的其他玩家。
MMO游戲中，視野對(duì)服務(wù)器造成的壓力主要來源于兩點(diǎn)：一，玩家頻繁移動(dòng)造成視野列表的頻繁更新的壓力；二，廣播視野列表的帶寬壓力。因?yàn)橐曇傲斜碇械耐婕翌l繁變化，有的玩家離開當(dāng)前玩家的視野，有的玩家新進(jìn)入當(dāng)前玩家的視野，因此當(dāng)前玩家的視野列表需要進(jìn)行頻繁的增、刪、查操作，因此增、刪、查操作的時(shí)間復(fù)雜度要盡可能的低，從而緩解視野列表頻繁更新的壓力。
如果當(dāng)前視野列表中有100個(gè)玩家，每個(gè)玩家都移動(dòng)了一段距離，為了讓其他玩家看到自己的移動(dòng)，每個(gè)玩家都需要被通知其他99個(gè)玩家的移動(dòng)，這就需要廣播100*99個(gè)數(shù)據(jù)包，隨著地圖中玩家數(shù)目增加，造成廣播量急劇增加，對(duì)帶寬造成極大壓力，因此玩家的視野列表需要有規(guī)模限制，從而緩解帶寬壓力。
本文提出一種利用全局內(nèi)存池、雙向鏈表、位標(biāo)記進(jìn)行視野管理的算法，可以將每次增、刪、查視野列表的復(fù)雜度降為O(1)。
1.2.2全局內(nèi)存池
全局內(nèi)存池中存放的元素如圖1.2.1.1所示。ViewLinkNodePair中有兩個(gè)ViewLinkNode類型元素，ViewLinkNode定義如圖1.2.1.2所示，記錄ViewLinkNodePair指針類型的m_Parents，以及Obj_User指針類型的m_pUser，m_pUser即為指向玩家的指針。ViewLinkNodePair兩個(gè)ViewLinkNode元素各自包含一個(gè)m_pUser指針，這兩個(gè)m_pUser指針存放相互可見的兩個(gè)玩家。采用內(nèi)存池好處是避免內(nèi)存碎片、以及頻繁分配的消耗。
?
1.2.3雙向鏈表
每個(gè)玩家的視野列表是一個(gè)雙向鏈表，雙向鏈表中每個(gè)元素包含ViewLinkNodePair中的兩個(gè)ViewLinkNode之一，ViewLinkNode中記錄ViewLinkNodePair和可見的玩家。當(dāng)玩家A和B相互可見時(shí)，申請(qǐng)ViewLinkNodePair，A的ViewLinkNodeA記錄ViewLinkNodePair和B，B的ViewLinkNodeB記錄ViewLinkNodePair和A。當(dāng)玩家A和B不相互可見時(shí)，在A的雙向鏈表中找到記錄B的ViewLinkNodeA，然后從A的雙向鏈表中刪除，并在記錄B的ViewLinkNodeA中找到ViewLinkNodePair，在ViewLinkNodePair中找到記錄A的ViewLinkNodeB，在B的雙向鏈表中刪除。
雙向鏈表每個(gè)元素是CChainItem<ViewLinkNode>的指針，類模板CChainItem定義如圖1.2.2.1所示，data存的是ViewLinkNode的指針。如圖1.2.2.2所示，當(dāng)兩個(gè)玩家rObjA、rObjB相互可見時(shí)，首先從全局內(nèi)存池g_ViewLinkPool新建一個(gè)對(duì)象，對(duì)象的指針為pPair，將pPair的m_LinkNodeA的m_pUser指向rObjB的地址，m_LinkNodeB的m_pUser指向rObjA的地址，m_Parents指向pPair。當(dāng)兩個(gè)玩家rObjA、rObjB相互不可見時(shí)，只需要在rObjA的雙向鏈表中找到對(duì)應(yīng)的CChainItem<ViewLinkNode>的指針，該指針的m_LinkNodeA中的m_pUser指向rObjB的地址，并將對(duì)應(yīng)的雙向鏈表的元素從rObjA的雙向鏈表中刪除，然后根據(jù)m_LinkNodeA的m_Parents找到對(duì)應(yīng)的pPair，再從pPair中找到m_LinkNodeB，m_LinkNodeB的m_pUser指向rObjA的地址，將m_LinkNodeB從rObjB的雙向鏈表中刪除。
?
1.2.4位標(biāo)記
游戲中需要頻繁的判斷兩個(gè)玩家是否相互可見，然而采用全局內(nèi)存池+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，最快只能采用遍歷雙向鏈表的方法，該時(shí)間復(fù)雜度為O(n)，因此采用第三個(gè)數(shù)據(jù)結(jié)構(gòu)：位標(biāo)記輔助完成這項(xiàng)工作。每個(gè)場景中的Obj數(shù)量是有限的，我們游戲每個(gè)場景的Obj數(shù)目最大為2048，ObjID編號(hào)從0到2047，每個(gè)玩家是否可見用一個(gè)bit表示。所以每個(gè)玩家共需要2047個(gè)bit表示是否與其他2047個(gè)Obj可見，即0.25K，3000個(gè)玩家同時(shí)在線，位標(biāo)記占0.75M。假設(shè)He的ObjID為10，判斷Me是否可見He，只需要查看Me的第10個(gè)位標(biāo)記是否為1即可。
1.2.5視野管理流程
如圖1.2.1.1.1所示，玩家Me從格子5移動(dòng)到格子8，老視野可見的玩家為紅色和綠色格子內(nèi)的玩家，新視野可見的玩家為紫色和綠色格子內(nèi)的玩家。首先遍歷Me的雙向鏈表，對(duì)所有老視野列表的玩家打上標(biāo)簽1，然后遍歷紫色和綠色格子內(nèi)的玩家，如果玩家He已打標(biāo)簽1，則將玩家He打上標(biāo)簽2，說明玩家He在新視野和老視野都可見；如果玩家He沒打標(biāo)簽1，則說明玩家He是新進(jìn)視野的玩家，加入EnterList；重新遍歷Me的雙向鏈表，如果玩家He仍然是標(biāo)簽1，說明玩家He只在老視野，沒在新視野中，加入LeaveList，同時(shí)記錄玩家He在玩家Me視野數(shù)組中的索引。
例如Me在格子5時(shí)老視野列表里的玩家為：User1、User2、User3、User4、User5、User6；Me移動(dòng)到格子8時(shí)，紫色和綠色格子內(nèi)的玩家有User3、User4、User5、User6、User7、User8。首先對(duì)雙向鏈表User1到User6六個(gè)玩家打標(biāo)簽1；然后對(duì)User3到User8打標(biāo)簽，因?yàn)閁ser3到User6已打標(biāo)簽1，所以對(duì)這4個(gè)玩家打標(biāo)簽2，而User7、User8沒打標(biāo)簽1，所以這兩個(gè)玩家加入EnterList；再遍歷雙向鏈表User1、User2因?yàn)槿匀皇菢?biāo)簽1，所以將這兩個(gè)玩家加入LeaveList，同時(shí)記錄這兩個(gè)玩家的pPair。
對(duì)LeaveList的兩個(gè)玩家User1、User2，因?yàn)橐阎猵Pair，所以已知Me和User1、User2三個(gè)玩家的雙向鏈表中CChainItem<ViewLinkNode>的指針位置，刪除即可。
對(duì)EnterList中的玩家，需要按照優(yōu)先級(jí)高低放到不同的桶里，比如隊(duì)友的優(yōu)先級(jí)比其他玩家優(yōu)先級(jí)高。然后按照優(yōu)先級(jí)高低的順序加入視野列表，二手QQ轉(zhuǎn)讓如果視野列表已滿，優(yōu)先級(jí)高的玩家仍然沒進(jìn)入視野列表，需要從視野列表中刪除優(yōu)先級(jí)低的玩家，以便騰出空間將優(yōu)先級(jí)高的玩家加入。對(duì)EnterList的兩個(gè)玩家User7、User8，新建ViewLinkNodePair，并將ViewLinkNode插入對(duì)應(yīng)的雙向鏈表即可。
1.3玩家屬性同步的優(yōu)化
1.3.1背景介紹
本文適用于所有臟標(biāo)記遍歷功能，提升性能幾十倍，本文以游戲中玩家的屬性同步作為例子進(jìn)行介紹。
MMORPG游戲中玩家有大量屬性需要從服務(wù)器同步給客戶端，例如名字、血量、戰(zhàn)力、等級(jí)、速度等等。每當(dāng)某個(gè)玩家的某個(gè)屬性發(fā)生變化時(shí)，需要將玩家該屬性的標(biāo)志位置臟，在心跳或者其他需要發(fā)送的時(shí)機(jī)，調(diào)用同步屬性函數(shù)，判斷置臟的屬性并同步給所有客戶端。需要注意，不能每次在某個(gè)玩家的某個(gè)屬性發(fā)生變化時(shí)，均同步給所有客戶端，因?yàn)殚_銷太大，一般在心跳里（固定時(shí)間間隔）同步。為了保證玩家屬性在所有客戶端及時(shí)更新，心跳間隔一般在500ms左右，如此頻繁的調(diào)用以及同步屬性函數(shù)內(nèi)大量的臟標(biāo)記判斷導(dǎo)致同步屬性函數(shù)成為性能瓶頸之一，大約占后臺(tái)性能消耗的10%。
假設(shè)玩家有n個(gè)屬性，k個(gè)屬性置臟，最直觀的做法是遍歷所有n個(gè)屬性，逐個(gè)判斷是否置臟，置臟的屬性同步給客戶端，需要判斷n次；本文作者之前提過一種優(yōu)化算法，根據(jù)屬性置臟的頻率，優(yōu)先判斷置臟頻率高的屬性，當(dāng)判斷出的臟屬性數(shù)目等于k，則停止，該優(yōu)化效率顯著優(yōu)于遍歷n個(gè)屬性，但也不是最優(yōu)的算法。
還有一種優(yōu)化思路是用set記錄置臟的屬性，set插入時(shí)間復(fù)雜度為O(logn)，置臟m個(gè)屬性，set插入操作總時(shí)間復(fù)雜度為O(log(1*2*..*m))，再考慮某個(gè)屬性頻繁置臟的情況，比如第m個(gè)屬性在同步之前置臟p次，則set操作時(shí)間復(fù)雜度為O(log(1*2..*m*p)，雖然一般情況下m比較小，但不排除某些情況m很大，就會(huì)導(dǎo)致出現(xiàn)性能瓶頸，實(shí)測中發(fā)現(xiàn)采用set，o2編譯，如圖1.3.1.1所示插入50個(gè)臟屬性耗時(shí)165639微秒，如圖1.3.1.2所示置臟50個(gè)標(biāo)記位耗時(shí)1522微秒，set效率低108倍，雖然同步的時(shí)間間隔內(nèi)更新的屬性數(shù)目很少，但某個(gè)屬性更新的可能非常頻繁，所以同步時(shí)間間隔內(nèi)假設(shè)插入50個(gè)臟屬性模擬很合理。
顯然，如果算法無論屬性更新是否頻繁，無論屬性數(shù)目是多是少，都能在k的時(shí)間判斷出哪些屬性置臟，則該算法為最優(yōu)算法。因?yàn)橹门K的屬性非常稀疏，k往往是個(gè)位數(shù)，所以最優(yōu)算法可以將效率提升幾十倍。
1.3.2優(yōu)化算法
為引出本文的優(yōu)化算法，本文首先介紹一個(gè)問題：計(jì)算一個(gè)整數(shù)的二進(jìn)制表示中有多少個(gè)1。基本做法如圖1.3.2.1所示。假設(shè)該整數(shù)n為10001100，則需要右移7次。但計(jì)算機(jī)里的數(shù)字本來就是用二進(jìn)制存的，所以計(jì)算過程也都是二進(jìn)制計(jì)算。利用一些位運(yùn)算的特性，可以很容易計(jì)算1的個(gè)數(shù)。該例子中n-1為10001011，n&(n-1)為10001000，可以看到低3位都變成了0。多驗(yàn)證幾個(gè)例子，可以看出結(jié)論，要消除整數(shù)n最低位的1，可以使用n=n&(n-1)。從而計(jì)算n的二進(jìn)制表示有多少個(gè)1的算法如圖1.3.2.2所示。
?
本文介紹一個(gè)gcc的內(nèi)置函數(shù)，__builtin_ffs(uint32 n)，返回n最后一個(gè)為1的位是從后向前的第幾位，例如若n為10001100，則__builtin_ffs(n)為3，該函數(shù)對(duì)應(yīng)的x86匯編代碼，O0編譯結(jié)果如圖1.3.2.3所示，僅有四條匯編指令。該內(nèi)置函數(shù)64位的版本為__builtin_ffsll(uint64 n)。
?
接下來正式介紹本文的優(yōu)化算法，假設(shè)有64個(gè)屬性，該64個(gè)屬性用bit位表示是否置臟，共需64bit，將64bit轉(zhuǎn)成uint64的n，每次用__builtin_ffsll找出最低位的1的位置，即可找出一個(gè)置臟的屬性，然后用n&(n-1)消除最低位的1，當(dāng)n為0時(shí)算法終止。假設(shè)64個(gè)屬性第2個(gè)屬性和第9個(gè)屬性置臟，則該64bit編碼為0...0100000010，首先用__builtin_ffsll找出低第2位的置臟屬性，然后n=n&(n-1)，即0...0100000000，再用__builtin_ffsll找出低第9位的置臟屬性，然后n=n&(n-1)即為0，算法終止，可看出從64個(gè)屬性里找出置臟的兩個(gè)屬性，只需要兩次操作。
找出置臟屬性后，使用switch語句而不是if語句處理需要同步的屬性。因?yàn)殡S著if語句數(shù)目增多，效率會(huì)線性降低。而switch語句在case多的情況下（gcc在O0編譯，case大于等于5個(gè)），翻譯的匯編代碼會(huì)使用查找表，在O(1)時(shí)間內(nèi)找到對(duì)應(yīng)的case，所以switch語句不會(huì)在case規(guī)模很大的情況下降低效率；在case很少的情況下（gcc在O0編譯，case小于5個(gè)），仍然會(huì)逐個(gè)比較。需要注意，為盡可能提升性能，臟標(biāo)記數(shù)目最好為64位整數(shù)倍，否則假如臟標(biāo)記數(shù)目為120位，取出64位后，需要將剩下的63位拆分成32位、16位、8位，分三次取出，再計(jì)算臟標(biāo)記位置，性能會(huì)降低。
1.3.3性能對(duì)比
num類型為uint64，記錄所有臟標(biāo)記，num低第2位、低第64位置臟，即num為100...010。圖1.3.3.1所示為遍歷所有屬性，并逐個(gè)判斷是否置臟，num&1不為0時(shí)，表示第j個(gè)屬性被置臟，圖1.3.3.2所示為采用本文的優(yōu)化算法，index為最低位的臟標(biāo)記的位置。實(shí)測中圖1.3.3.1耗時(shí)2011微秒，圖1.3.3.2耗時(shí)26微秒，性能提升77倍。本文的優(yōu)化算法不僅適用于屬性同步，所有臟標(biāo)記相關(guān)的功能均可采用，例如數(shù)據(jù)的判斷置臟并落地存儲(chǔ)。
?
1.4跨服戰(zhàn)團(tuán)匹配算法的優(yōu)化
游戲中存在跨服戰(zhàn)等需求，將一些隊(duì)伍組成固定規(guī)模戰(zhàn)團(tuán)，然后戰(zhàn)團(tuán)之間戰(zhàn)斗，戰(zhàn)團(tuán)匹配過程應(yīng)當(dāng)盡量高效、快速，同時(shí)實(shí)現(xiàn)戰(zhàn)力均衡。為了實(shí)現(xiàn)盡可能公平均衡的戰(zhàn)團(tuán)匹配，直觀的做法當(dāng)然是搜索所有隊(duì)伍組成固定規(guī)模的戰(zhàn)團(tuán)，然而其時(shí)間復(fù)雜度為指數(shù)級(jí)，以極高的計(jì)算代價(jià)換取最優(yōu)匹配顯然是不現(xiàn)實(shí)的，因此，戰(zhàn)團(tuán)匹配問題也成為制約服務(wù)器性能瓶頸問題。
為此，本文利用壓桶法實(shí)現(xiàn)了快速組成固定規(guī)模為K的戰(zhàn)團(tuán)，在盡量保證匹配戰(zhàn)團(tuán)的戰(zhàn)力均衡前提下，將戰(zhàn)團(tuán)匹配的時(shí)間復(fù)雜度降為O(n)。具體上，當(dāng)有玩家或隊(duì)伍（實(shí)際中，隊(duì)伍人數(shù)為1到5）申請(qǐng)組成戰(zhàn)團(tuán)時(shí)，將其加入隊(duì)列尾部。然后在游戲的心跳中遍歷隊(duì)列，如果當(dāng)前遍歷的玩家或隊(duì)伍的人數(shù)加上桶里的人數(shù)小于等于K，則將當(dāng)前玩家或隊(duì)伍加入桶，并從隊(duì)列中刪除；否則新建一個(gè)桶，將玩家或隊(duì)伍加入新桶中。在戰(zhàn)團(tuán)匹配時(shí)，找出所有人數(shù)為K的桶，將桶里所有玩家的戰(zhàn)力值的和設(shè)為對(duì)應(yīng)桶的權(quán)重值，并以此對(duì)所有的滿的桶進(jìn)行排序，每次選擇戰(zhàn)力值最接近的兩個(gè)戰(zhàn)團(tuán)進(jìn)行戰(zhàn)力均衡的調(diào)整，然后傳送到戰(zhàn)斗服務(wù)器進(jìn)行戰(zhàn)斗。
然而，由于壓桶法是為了節(jié)省時(shí)間而選擇的貪心算法，可能會(huì)遺漏能組成戰(zhàn)團(tuán)的玩家或隊(duì)伍，因此在壓桶法后，本文采用查表法對(duì)剩余的玩家和隊(duì)伍再次嘗試組成固定規(guī)模的戰(zhàn)團(tuán)。首先在服務(wù)器啟動(dòng)時(shí)做些預(yù)處理，群舉所有能組成兩個(gè)固定規(guī)模戰(zhàn)團(tuán)的組合（隊(duì)伍人數(shù)為一的隊(duì)伍數(shù)目，隊(duì)伍人數(shù)為二的隊(duì)伍數(shù)目，...，隊(duì)伍人數(shù)為五的隊(duì)伍數(shù)目），并存在set里，該步驟是全局唯一的，并且只需要做一次。然后統(tǒng)計(jì)剩下的玩家和隊(duì)伍，計(jì)算人數(shù)為一、二、...、五的隊(duì)伍數(shù)目。如果剩下的玩家或隊(duì)伍隊(duì)伍人數(shù)為一到五的隊(duì)伍數(shù)目均大于set中某個(gè)元素，則set中該元素表示能組成兩個(gè)固定規(guī)模戰(zhàn)團(tuán)的組合，并從剩下的玩家或隊(duì)伍中刪除。此步驟重復(fù)進(jìn)行，直到剩下的玩家或隊(duì)伍無法組成兩個(gè)固定規(guī)模的戰(zhàn)團(tuán)。
通過上述方法，本文實(shí)現(xiàn)盡可能合理的戰(zhàn)團(tuán)組成，在此之后，為了盡可能實(shí)現(xiàn)兩個(gè)戰(zhàn)團(tuán)戰(zhàn)力均衡，本文進(jìn)一步設(shè)計(jì)戰(zhàn)團(tuán)玩家調(diào)整方法。當(dāng)兩個(gè)固定規(guī)模的戰(zhàn)團(tuán)組成后，通過查詢預(yù)先生成的表，調(diào)整兩個(gè)戰(zhàn)團(tuán)里的玩家，使得兩個(gè)戰(zhàn)團(tuán)的戰(zhàn)力盡可能相等，增強(qiáng)戰(zhàn)斗刺激性。具體上，首先群舉所有的能組成兩個(gè)固定規(guī)模戰(zhàn)團(tuán)的可能，并存在map里，map的key為字符串，key唯一標(biāo)識(shí)戰(zhàn)團(tuán)的構(gòu)成（隊(duì)伍人數(shù)為一的隊(duì)伍數(shù)目，隊(duì)伍人數(shù)為二的隊(duì)伍數(shù)目，...，隊(duì)伍人數(shù)為五的隊(duì)伍數(shù)目），map的value為一個(gè)vector容器，vector中存儲(chǔ)當(dāng)前key拆分成兩個(gè)固定規(guī)模戰(zhàn)團(tuán)的所有可能。當(dāng)調(diào)整兩個(gè)戰(zhàn)團(tuán)的戰(zhàn)力時(shí)，通過map查詢當(dāng)前兩個(gè)戰(zhàn)團(tuán)能重組成的所有兩個(gè)戰(zhàn)團(tuán)的可能，然后遍歷所有的可能，找出兩個(gè)戰(zhàn)團(tuán)戰(zhàn)力最接近的組合。
1.5發(fā)包邏輯拆分
在服務(wù)器給客戶端發(fā)包時(shí)，需要將數(shù)據(jù)包打包成流，在Encode操作中存在大量memcpy操作，而每個(gè)memcpy時(shí)間復(fù)雜度為O(n)，因此打包過程也成為性能瓶頸之一。因此，本文認(rèn)為有必要將數(shù)據(jù)包打包并發(fā)包的過程從游戲主線程中拆分，另開一個(gè)線程處理。在具體的多線程實(shí)現(xiàn)過程中，在主線程和發(fā)包線程之間需要有通信的數(shù)據(jù)結(jié)構(gòu)，主線程負(fù)責(zé)將數(shù)據(jù)包寫進(jìn)該數(shù)據(jù)結(jié)構(gòu)，發(fā)包線程負(fù)責(zé)將包從該數(shù)據(jù)結(jié)構(gòu)中讀取、打包、發(fā)送，合理的通信數(shù)據(jù)結(jié)構(gòu)的使用將對(duì)多線程效率影響很大。
簡單的實(shí)現(xiàn)可以采用c++的queue作為兩個(gè)線程通信的數(shù)據(jù)結(jié)構(gòu)，然而需要對(duì)queue加鎖，才能保證兩個(gè)線程讀寫安全，但鎖的開銷會(huì)降低性能。因此，本文采用基于字節(jié)流的無鎖循環(huán)隊(duì)列。因?yàn)槊總€(gè)數(shù)據(jù)包大小不一樣，小的幾個(gè)Byte，大的幾百K，因此不能采用基于對(duì)象的無鎖循環(huán)隊(duì)列，否則幾個(gè)Byte的數(shù)據(jù)包也會(huì)占據(jù)幾百K的空間。
另外本文采用Tconnd作為網(wǎng)絡(luò)通信組件，Tconnd發(fā)包需要攜帶TFRAMEHEAD，該結(jié)構(gòu)體大小為12K，除了TFRAMEHEAD_CMD_START等管理包的該TFRAMEHEAD是從Tconnd接收然后再自己填充一些字段外，其他數(shù)據(jù)包的TFRAMEHEAD完全是自己拼的，因此知道需要填充哪些字段。所以除了TFRAMEHEAD_CMD_START等管理包的TFRAMEHEAD是在主線程收到并拼完，然后12K完整的寫進(jìn)無鎖循環(huán)隊(duì)列，其他的TFRAMEHEAD均是主線程將需要的參數(shù)寫進(jìn)無鎖循環(huán)隊(duì)列，發(fā)包線程再根據(jù)這些參數(shù)拼TFRAMEHEAD。這種優(yōu)化可以大大降低無鎖循環(huán)隊(duì)列所占內(nèi)存。
1.6玩家Cache
在當(dāng)前多進(jìn)程的服務(wù)器的架構(gòu)下，查看玩家信息亟需優(yōu)化。當(dāng)一臺(tái)服務(wù)器（GameServer1）的玩家要查看另一臺(tái)服務(wù)器（GameServer2）的玩家信息時(shí)，需要經(jīng)過多個(gè)服務(wù)器的多次查詢中轉(zhuǎn)。譬如，上述請(qǐng)求的流程可能為GameServer1->WorldServer->GameServer2->WorldServer->GameServer1，請(qǐng)求消息共需要轉(zhuǎn)發(fā)四次。同時(shí)，查看離線玩家信息時(shí)，通常需要對(duì)數(shù)據(jù)庫進(jìn)行操作，這都導(dǎo)致查看玩家信息需要被優(yōu)化。
為此，本文通過對(duì)玩家信息進(jìn)行緩存（玩家cache）實(shí)現(xiàn)玩家信息查看優(yōu)化。具體上，1）同一游戲服務(wù)器下的用戶不需緩存，譬如，GameServer1玩家A查看GameServer1的玩家B不通過緩存就可以很容易地獲取玩家B信息；2）不同游戲服務(wù)器下需進(jìn)行玩家緩存，且緩存按需更新。譬如，GameServer1玩家A查看GameServer2的玩家C，在GameServer1的玩家cache中查看玩家C，如果玩家C進(jìn)入緩存時(shí)間超過10秒，更新緩存中玩家C信息，如果玩家C不在緩存中，則從數(shù)據(jù)庫加載；3）查看離線玩家同樣利用玩家cache，每逢玩家離線，通知所有GameServer更新玩家cache中該玩家信息。
因?yàn)楸徊榭吹耐婕彝际堑燃?jí)、戰(zhàn)力等特別高的玩家，這些玩家會(huì)被大量玩家查看，所以本文提出的玩家緩存機(jī)制往往命中率極高，實(shí)測中緩存命中率達(dá)到80%-90%左右。
二、服務(wù)器內(nèi)存優(yōu)化
2.1內(nèi)存統(tǒng)計(jì)
在對(duì)內(nèi)存優(yōu)化之前，需要先確定程序每個(gè)模塊的內(nèi)存分配。程序的性能有perf、gprof等分析工具，但內(nèi)存沒有較好的分析工具，因此需要自行統(tǒng)計(jì)。在linux下/proc/self/statm有當(dāng)前進(jìn)程的內(nèi)存占用情況，共有七項(xiàng)：指標(biāo)vsize虛擬內(nèi)存頁數(shù)、resident物理內(nèi)存頁數(shù)、share共享內(nèi)存頁數(shù)、text代碼段內(nèi)存頁數(shù)，lib引用庫內(nèi)存頁數(shù)、data_stack數(shù)據(jù)/堆棧段內(nèi)存頁數(shù)、dt臟頁數(shù)，七項(xiàng)指標(biāo)的數(shù)字是內(nèi)存的頁數(shù)，因此需要乘以getpagesize()轉(zhuǎn)換為byte。在每個(gè)模塊結(jié)束后統(tǒng)計(jì)vsize的增加，即可知該模塊占用的內(nèi)存大小。
在面向?qū)ο箝_發(fā)中，內(nèi)存的消耗由對(duì)象的消耗組成，因此需要統(tǒng)計(jì)每個(gè)類的成員變量的占用內(nèi)存大小。使用CLion或者visual studio都可以導(dǎo)出類中定義的所有成員變量，然后在gdb使用命令：
p((unsigned long)(&((ClassName*)0)->MemberName))，即可打印出類ClassName的成員變量MemberName相對(duì)類基地址的偏移，根據(jù)偏移從小到大排序后，變量的順序即為定義的順序，根據(jù)偏移相減即可得出每個(gè)成員變量大小，然后優(yōu)化占用內(nèi)存大的成員變量。
2.2內(nèi)存泄露
內(nèi)存泄露是指程序中已動(dòng)態(tài)分配的堆內(nèi)存由于某種原因程序未釋放或無法釋放，導(dǎo)致內(nèi)存一直增長。雖然有valgrind等工具可以檢查內(nèi)存泄露，但valgrind虛擬出一個(gè)CPU環(huán)境，在該環(huán)境上運(yùn)行，會(huì)導(dǎo)致內(nèi)存增大、效率降低，對(duì)于大規(guī)模程序，基本無法在valgrind上運(yùn)行。因此需要自行檢查內(nèi)存泄露，glibc提供的內(nèi)存管理器的鉤子函數(shù)可以監(jiān)控內(nèi)存的分配、釋放。如圖2.2.2、2.2.3所示，分別為鉤子函數(shù)的分配內(nèi)存和釋放內(nèi)存。因?yàn)榉?wù)器啟動(dòng)時(shí)需要預(yù)先分配很多內(nèi)存，比如內(nèi)存池，這些內(nèi)存是在服務(wù)器停止時(shí)才釋放，因此為了避免這些內(nèi)存的干擾，在服務(wù)器啟動(dòng)之后才能開始內(nèi)存泄露的統(tǒng)計(jì)。
首先申請(qǐng)固定大小的vec_stack，記錄所有分配的內(nèi)存，如果有釋放，則從vec_stack中刪除，最后vec_stack中的元素即為泄露的內(nèi)存，vec_stack必須為固定大小，否則vector擴(kuò)容中會(huì)有內(nèi)存分配，也不可以用map，map的紅黑樹旋轉(zhuǎn)也會(huì)有內(nèi)存分配，會(huì)造成干擾；然后通過圖2.2.1所示的my_back_hook記錄原有的malloc、free；并通過圖2.2.2所示的my_init_hook將malloc、free換成自定義的鉤子函數(shù)。
每次分配內(nèi)存時(shí)，都會(huì)進(jìn)入自定義鉤子函數(shù)my_malloc_hook中，如圖2.2.2所示。在my_malloc_hook中首先通過my_recover_hook將malloc恢復(fù)成默認(rèn)的，否則會(huì)造成死遞歸，然后通過默認(rèn)的malloc分配大小為size的空間，為了分線程統(tǒng)計(jì)內(nèi)存泄露，還需要對(duì)線程號(hào)做判斷，在stTrace.m_pAttr記錄內(nèi)存分配的地址，m_nSize記錄大小，m_szCallTrace記錄調(diào)用棧，如果vec_stack已滿，需要根據(jù)m_nSize從大到小排序，如果當(dāng)前分配內(nèi)存大于vec_stack記錄的最小的分配內(nèi)存，則替換；如果未滿，則直接加入vec_stack，在my_malloc_hook結(jié)束時(shí)，將malloc替換成自定義的malloc。
每次釋放內(nèi)存時(shí)，都會(huì)進(jìn)入自定義鉤子函數(shù)my_malloc_free中，如圖2.2.3所示。在my_malloc_free中首先通過my_recover_hook將free恢復(fù)成默認(rèn)的，否則會(huì)造成死遞歸，對(duì)線程號(hào)判斷，然后在vec_stack中刪除對(duì)應(yīng)的分配，并將free替換成自定義free。
?
2.3內(nèi)存池
在游戲服務(wù)器內(nèi)存分配過程中，glibc中的malloc采用的是ptmalloc，ptmalloc在對(duì)小對(duì)象進(jìn)行分配時(shí)會(huì)產(chǎn)生大量內(nèi)部碎片，同時(shí)也會(huì)有外部碎片的產(chǎn)生。因此往往需要自行設(shè)計(jì)并實(shí)現(xiàn)模板化的內(nèi)存池，采用內(nèi)存池的好處是，避免內(nèi)部、外部碎片，對(duì)象New/Delete均為O(1)復(fù)雜度，同時(shí)有利于監(jiān)控。例如當(dāng)模板參數(shù)為寵物時(shí)，首先new出60個(gè)寵物的空間，對(duì)這60個(gè)寵物空間，當(dāng)60個(gè)空間被全部使用時(shí)，再分配60個(gè)空間。本文在內(nèi)存池設(shè)計(jì)中實(shí)現(xiàn)兩個(gè)數(shù)據(jù)管理器，分別是空閑數(shù)據(jù)管理器freeList和使用空間管理器usedList，freeList采用queue實(shí)現(xiàn)即可，usedList采用vector。
由于這部分較復(fù)雜，因此用代碼輔以說明。如圖2.3.1，在Init函數(shù)中傳入要?jiǎng)?chuàng)建的對(duì)象數(shù)目capacity，pointer根據(jù)capacity預(yù)先分配空間，用于建立所有對(duì)象索引，pointer主要用來校驗(yàn)。本文按塊Chunk創(chuàng)建對(duì)象，每塊Chunk有objectperchunk個(gè)T類型對(duì)象。chunksize記錄當(dāng)前總共創(chuàng)建了多少對(duì)象。雖然Init函數(shù)設(shè)定了capacity，但是初始并沒有創(chuàng)建capacity個(gè)T對(duì)象，而是先創(chuàng)建objectperchunk個(gè)T對(duì)象供使用，并記錄到freelist中。
如圖2.3.2所示，每次新創(chuàng)建對(duì)象時(shí)調(diào)用NewObj函數(shù)，如果freelist為空，說明所有已創(chuàng)建的對(duì)象均被使用，則再調(diào)用NewChunk創(chuàng)建objectperchunk個(gè)T對(duì)象；如果不為空，直接返回freeList頭部的指針。
如圖2.3.3所示，每次刪除對(duì)象時(shí)調(diào)用DeleteObj函數(shù)，參數(shù)為待刪除對(duì)象指針，除了必要的校驗(yàn)以外，將對(duì)象指針從usedList刪除，并將usedList最后一個(gè)對(duì)象指針移動(dòng)到刪除位置，記錄刪除位置deleteusedlistindex。同時(shí)將對(duì)象指針?biāo)傅膶?duì)象清空加入freeList，以便再次使用，好處時(shí)內(nèi)存不回收可以重復(fù)使用。
如圖2.3.4所示，對(duì)象的遍歷在usedList上進(jìn)行，但在遍歷中可能會(huì)刪除對(duì)象，此時(shí)deleteusedlistindex==iterateindex，因?yàn)閯h除對(duì)象后，會(huì)將usedList最后一個(gè)對(duì)象指針移動(dòng)到deleteusedlistindex位置，因此iterateindex不能增加。
?
2.4內(nèi)存分配（ptmalloc vs tcmalloc）
即使使用內(nèi)存池，程序中仍然需要大量使用malloc分配空間。但主流使用的ptmalloc存在如下缺點(diǎn)：一，ptmalloc采用多個(gè)線程輪詢加鎖主分配區(qū)和非主分配的方式，造成鎖的開銷；二，多線程間的空閑內(nèi)存無法復(fù)用，利用線程A釋放一塊內(nèi)存，由于并不一定會(huì)釋放給操作系統(tǒng)，線程B申請(qǐng)同樣大小的內(nèi)存時(shí)，不能復(fù)用A釋放的內(nèi)存，導(dǎo)致使用內(nèi)存增加；三，ptmalloc分配的每塊chunk需要8個(gè)字節(jié)記錄前一個(gè)空閑塊大小和當(dāng)前塊大小以及一些標(biāo)記位。
為此，本文提倡使用tcmalloc進(jìn)行內(nèi)存分配。tcmalloc對(duì)每個(gè)線程單獨(dú)維護(hù)ThreadCache分配小內(nèi)存；針對(duì)ptmalloc多線程內(nèi)存無法復(fù)用的問題，tcmalloc為進(jìn)程內(nèi)的所有線程維護(hù)公共的CentralCache，ThreadCache會(huì)階段性的回收內(nèi)存到CentralCache；針對(duì)ptmalloc每塊chunk使用8個(gè)字節(jié)表示其他信息，tcmalloc對(duì)每塊chunk使用大概百分之一的空間表示其他信息，對(duì)小對(duì)象分配，空間利用率遠(yuǎn)高于ptmalloc。
三、服務(wù)器啟動(dòng)時(shí)間優(yōu)化
3.1讀取阻擋文件優(yōu)化
服務(wù)器啟動(dòng)時(shí)，需要讀大量文件，其中最大的文件就是阻擋文件，每個(gè)阻擋文件大約有幾M，采用c++的ifstream可以一次讀取一個(gè)字節(jié)，也可以一次讀取整個(gè)文件，后者的速度比前者快幾十倍以上。如圖3.1.1所示，MATRIX_LEN為4096，阻擋文件為4096*4096byte，共16M，圖3.1.1按byte讀取阻擋文件需要2564ms，圖3.1.2一次性讀取阻擋文件需要50ms。
?
總結(jié)
以上是生活随笔為你收集整理的《仙剑奇侠传online》游戏后台优化分析：CPU、内存与启动时间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 从《王者荣耀》来聊聊游戏的帧同步
- 下一篇： 游戏中的整容术！ 《Honey Sele