一類新的網(wǎng)絡(luò)游戲場(chǎng)景3D障礙信息表達(dá)方案

陳疆，郭克華，梁琳

(1. 中南大學(xué) 湘雅醫(yī)院, 湖南 長沙，410008；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

傳統(tǒng)網(wǎng)絡(luò)游戲的體系結(jié)構(gòu)通常分為服務(wù)器和客戶端2部分。在服務(wù)器和客戶端，都需要存儲(chǔ)和使用游戲場(chǎng)景的障礙信息。其中，客戶端不僅需要利用場(chǎng)景障礙信息使游戲表現(xiàn)正確，而且需要利用其隱含的路徑連通信息，實(shí)現(xiàn)游戲角色的 AI 尋路算法；而服務(wù)器端則因網(wǎng)絡(luò)游戲的運(yùn)營通常處于公共網(wǎng)絡(luò)環(huán)境的特殊情況，要隨時(shí)面對(duì)包括偽造數(shù)據(jù)包、外掛加速在內(nèi)的各種風(fēng)險(xiǎn)[1]。因此，網(wǎng)絡(luò)游戲的服務(wù)器端需要進(jìn)行極頻繁和大量的數(shù)據(jù)校驗(yàn)工作，對(duì)數(shù)據(jù)訪問的性能要求極高，這樣，對(duì)數(shù)據(jù)存儲(chǔ)的格式也提出了更高的要求[2-3]。在一般情況下，游戲服務(wù)器需要服務(wù)成千上萬的用戶，同時(shí)處理幾十甚至幾百個(gè)場(chǎng)景信息，因此，游戲場(chǎng)景的障礙信息占據(jù)的存儲(chǔ)空間受到嚴(yán)格的限制[4]。傳統(tǒng)的 2D 網(wǎng)絡(luò)游戲場(chǎng)景中的障礙信息表達(dá)方案很成熟，但網(wǎng)絡(luò)游戲產(chǎn)品的 3D 化是大趨勢(shì)，這對(duì)信息的存儲(chǔ)訪問及相關(guān)算法提出了新的要求[5]。從項(xiàng)目研發(fā)周期成本和產(chǎn)品的繼承性等方面考慮，都傾向于在現(xiàn)有成熟的 2D 方案上進(jìn)行擴(kuò)展，力求尋找既能夠清晰地表達(dá)游戲場(chǎng)景的障礙信息，又能夠支持節(jié)省空間、快速訪問的方法[6-9]。針對(duì)此類問題，本文作者基于傳統(tǒng) 2D 網(wǎng)絡(luò)游戲場(chǎng)景的障礙信息表達(dá)方式，針對(duì)3D游戲場(chǎng)景，提出一種偽 3D 障礙信息表達(dá)方案和一種真 3D 障礙信息表達(dá)方案。通過效率分析和實(shí)際應(yīng)用對(duì)這 2種方法的可行性進(jìn)行分析驗(yàn)證。

1 2D場(chǎng)景的障礙信息表達(dá)方案

傳統(tǒng)2D網(wǎng)絡(luò)游戲場(chǎng)景通常是1個(gè)簡單的柵格平面，使用二維數(shù)組直接存儲(chǔ)。這種方案的優(yōu)勢(shì)在于：數(shù)據(jù)訪問是常數(shù)級(jí)的時(shí)間復(fù)雜度，因此，有較好的數(shù)據(jù)訪問性能。在此數(shù)據(jù)格式的基礎(chǔ)上，客戶端可使用成熟的 Astar 算法實(shí)現(xiàn)尋路功能[10]。實(shí)踐證明，在中等規(guī)模的場(chǎng)景且數(shù)量不大的情況下，該方案能夠滿足需求[11-13]。圖 1所示為 1個(gè)典型的障礙物場(chǎng)景中Astar算法的尋路過程，圖2所示為該障礙信息的存儲(chǔ)矩陣。

在傳統(tǒng) 2D 網(wǎng)絡(luò)游戲場(chǎng)景下，對(duì)于一個(gè) n×n的矩陣，其效率如表1所示。

表1 2D場(chǎng)景方案下的效率Table 1 Efficiencies under 2D approach

圖1 Astar 算法圖示Fig.1 Chart of Astar algorithm

圖2 障礙信息存儲(chǔ)矩陣Fig.2 Barriers information storage matrix

2 多層偽3D場(chǎng)景的障礙信息表達(dá)方案

從功能模塊劃分的角度，游戲的場(chǎng)景渲染呈現(xiàn)與游戲的數(shù)據(jù)邏輯可以完全分離。基于該思路，很多游戲使用 3D 渲染技術(shù)，用于呈現(xiàn)真實(shí)場(chǎng)景，但在數(shù)據(jù)層面上是完全的 2D 邏輯，稱為偽 3D 方案[14]。

偽 3D 方案在本質(zhì)上是 2D 數(shù)據(jù)邏輯，所以，在1個(gè) (x, z) 坐標(biāo)確定的垂直方向上，只能存儲(chǔ)地表障礙信息。游戲角色一旦離地騰空，則服務(wù)器不可識(shí)別。因此，場(chǎng)景中無法布置上、下2層都可以行走的如空中島、橋洞、城門等地形。

但實(shí)際情況是：很多偽 3D場(chǎng)景中，都存在對(duì)如橋洞和城門等地形的需求。真 3D場(chǎng)景所需的計(jì)算代價(jià)較高，為此，本文作者基于現(xiàn)有研究基礎(chǔ)，提出一套偽3D地形的擴(kuò)展方案。

2.1 設(shè)計(jì)思想

該方案在原 2D 的單層障礙信息基礎(chǔ)上，再增加一層障礙信息，用于表達(dá)橋洞和城門等上層障礙。2層障礙信息之間通過特殊指定的連通點(diǎn)連通。

在這種數(shù)據(jù)組織結(jié)構(gòu)基礎(chǔ)上，最關(guān)鍵的問題就是要正確判斷角色當(dāng)前所處的層。在偽 3D 地形的擴(kuò)展方案中，為當(dāng)前地表生成一張高度圖，根據(jù)角色所處的位置高度判斷是在地面層還是在擴(kuò)展層。

這種擴(kuò)展格式對(duì)客戶端的尋路需求具有較好的天然支持。在 2D 數(shù)據(jù)邏輯基礎(chǔ)上，依據(jù)對(duì)障礙信息中隱含的路徑連通性的理解，可分為 4 連通定義和 8連通定義。這2種連通定義對(duì)Astar尋路算法沒有本質(zhì)區(qū)別。實(shí)際上，多數(shù)游戲使用介于兩者之間的、帶權(quán)重的 8 連通定義。對(duì)于擴(kuò)展出來的一層障礙信息，只需要將 8 連通定義理解為 10 連通定義即可。

需要特別考慮的是：跨層的路徑只能在特別指定的跨層點(diǎn)出現(xiàn)，因此，10 連通定義也只對(duì)特別指定的跨層點(diǎn)有效，在其他情況下，仍然將其連通性限制在單層數(shù)據(jù)內(nèi)。在該方案基礎(chǔ)上，對(duì)原 Astar尋路算法略微調(diào)整即可使用。圖3所示為基于多層偽3D場(chǎng)景的障礙信息表達(dá)方案的搜索過程。

2.2 性能分析

多層偽 3D 場(chǎng)景的障礙信息表達(dá)方案的訪問效率仍然保持常數(shù)級(jí)的時(shí)間復(fù)雜度。但因?yàn)闃O少量的雙層地形，需要增加1倍數(shù)據(jù)量，所以，存儲(chǔ)效率有所下降，這也是本方案最大的缺點(diǎn)。而客戶端的 Astar尋路算法也可能在某些極端地形下遇到性能瓶頸(如回旋下降的臺(tái)階)，該問題可以在游戲策劃層面進(jìn)行規(guī)避。本方案的優(yōu)勢(shì)在于：僅需在2D數(shù)據(jù)邏輯基礎(chǔ)上付出極低的修改成本。因此，該方案能夠很好地滿足大型網(wǎng)絡(luò)游戲的需求，且在實(shí)施成本很低。

在多層偽 3D 場(chǎng)景方案下，對(duì)于1個(gè)n×n的矩陣，3D場(chǎng)景高度為m，其效率分析如表2所示。

但是，多層偽 3D 場(chǎng)景的障礙信息表達(dá)方案通常只能表達(dá)2層至多3層障礙地形。其原因是：隨著層數(shù)增加，其存儲(chǔ)效率會(huì)急速下降至不可接受的程度，大量數(shù)據(jù)不被用到。超過2層的障礙信息也會(huì)給基于高度圖的層定位造成困難。而大量的無用數(shù)據(jù)也會(huì)快速增加客戶端 Astar 尋路算法的時(shí)間。從服務(wù)器到客戶端所遇到的各種限制都決定了其只能表達(dá)有限的障礙信息層。多層偽3D場(chǎng)景方案下的效率見表2。

圖3 多層偽3D場(chǎng)景下的搜索過程圖示Fig.3 Search process under multi-layer pseudo-3D scene

表2 多層偽 3D 場(chǎng)景方案下的效率Table 2 Efficiencies under multi-layer pseudo-3D approach

該方案已成功應(yīng)用于1款名為《問鼎》的大型在線網(wǎng)絡(luò)游戲，其3D城戰(zhàn)場(chǎng)景部分依托上述方案實(shí)現(xiàn)。該游戲的最高同時(shí)在線數(shù)于2009年達(dá)到峰值3萬人。

3 真3D場(chǎng)景障礙信息表達(dá)方案

若不考慮實(shí)現(xiàn)上的困難，嘗試將偽 3D 場(chǎng)景的障礙信息表達(dá)方案進(jìn)行無限擴(kuò)展，則障礙信息將從幾個(gè)有限的 2D 矩陣的層疊轉(zhuǎn)化為 1個(gè) 3D 矩陣。障礙信息的存儲(chǔ)單元也從單元格變成單位立方體。這種結(jié)構(gòu)能夠從邏輯上滿足真3D 場(chǎng)景所有關(guān)于障礙信息的功能性需求。但是，其帶來的巨大存儲(chǔ)和尋路算法開銷是無法承受的，所以，要在該思路下實(shí)施真 3D場(chǎng)景障礙信息表達(dá)方案，實(shí)際上就是要解決存儲(chǔ)和尋路2個(gè)問題。圖4所示為3D場(chǎng)景障礙信息存儲(chǔ)矩陣。

圖4 3D場(chǎng)景障礙信息存儲(chǔ)矩陣圖示Fig.4 3D barriers information storage matrix

針對(duì)尋路算法方面的問題，在該方案下，只能拋棄 Astar算法，使用矢量尋路方案。常見的基于NavMesh導(dǎo)航網(wǎng)格的尋路方案都可以取得較好的效果。

針對(duì)存儲(chǔ)效率的問題，1個(gè)表達(dá)真 3D 場(chǎng)景障礙信息的 3D 矩陣中大量的數(shù)據(jù)實(shí)際上是冗余的。直觀的理解是：在1個(gè) 3D 場(chǎng)景中，除去貼近地表的部分和極少量的空中島、城墻、橋洞等地形，離開地面一定高度后，幾乎全是非障礙點(diǎn)。換句話說，其真實(shí)的信息量其實(shí)并不大，這需要對(duì)數(shù)據(jù)進(jìn)行壓縮來大幅度提高存儲(chǔ)效率。但是，數(shù)據(jù)壓縮帶來的問題是訪問效率下降，所需數(shù)據(jù)無法直接索引。最壞的情況是需要解壓縮訪問。所以，尋找一種合適的壓縮算法能夠在存儲(chǔ)效率和訪問效率間取得平衡，這是該方案的關(guān)鍵點(diǎn)。

3.1 設(shè)計(jì)思想

本方案的基本思想是：將一種常被用于圖像無損壓縮的 RLE 算法[15]解決真 3D 場(chǎng)景障礙信息表達(dá)所遇到的問題。RLE(Run-length encoding，即游程長編碼)算法的基本思路是將多個(gè)連續(xù)的數(shù)據(jù)記錄為value-length 的格式。例如，數(shù)據(jù)流中連續(xù)出現(xiàn) 10個(gè) 0，則記錄為 (0,10)，數(shù)據(jù)量從 10 個(gè)整數(shù)減少到2 個(gè)整數(shù)，從而達(dá)到壓縮存儲(chǔ)的目的。其優(yōu)勢(shì)在于無需解壓縮即可直接訪問。被壓縮數(shù)據(jù)流中連續(xù)出現(xiàn)的數(shù)據(jù)越多，存儲(chǔ)和訪問效率就越高。

將 1個(gè)真 3D 場(chǎng)景的障礙信息矩陣看成是 1個(gè)2D 矩陣在縱向上的流式擴(kuò)展。相應(yīng)地，將其存儲(chǔ)為1個(gè)平面上的 2D 矩陣，而矩陣中的每個(gè)元素是該點(diǎn)在縱向上障礙信息的數(shù)據(jù)流。考慮到空間中絕大部分位置都是非障礙點(diǎn)，對(duì)應(yīng)的數(shù)據(jù)流基本上都是單一數(shù)據(jù)的連續(xù)重復(fù)。因此，該數(shù)據(jù)流是絕好的 RLE 壓縮對(duì)象。實(shí)際上，若僅用 0 和 1 表達(dá)障礙和非障礙 2種情況，則RLE中value-length的value部分都可以被省略，存儲(chǔ)效率能夠再提高1倍。圖5所示為用顏色區(qū)分標(biāo)記處 RLE 的壓縮段，能更清楚地顯示該方案效果。

圖5 3D障礙信息存儲(chǔ)矩陣Fig.5 3D barriers information storage matrix

表3 多層真3D場(chǎng)景方案下的效率Table 3 Efficiencies under multi-layer real-3D approach

表4 3類方案的性能比較Table 4 Performance comparison of three kinds of approach

其中：v11～v99都是表達(dá)在各自垂直方向上障礙信息的一組向量，對(duì)應(yīng)圖5，有

v16=(1,1,1,1,1,0,0,0,0,0)

經(jīng)RLE壓縮后為：

v16=(1,5,0,5)

若進(jìn)一步省略 value，將 value的變換隱含在length中，默認(rèn)初始 value為 0，則可表示為：v16=(0,5,5)。

3.2 性能分析

在多層真 3D 場(chǎng)景方案下，其效率分析如表3所示。該方案已應(yīng)用于1款目前正在開發(fā)當(dāng)中的名為《斗仙》的大型全 3D多人在線網(wǎng)絡(luò)游戲中。該款游戲?yàn)榧磿r(shí)戰(zhàn)斗類型，其所有場(chǎng)景均為真 3D場(chǎng)景。依托真3D方案，其數(shù)據(jù)量僅僅是相同平面尺寸的 2D障礙信息的 2～3 倍，在縱向上所能表達(dá)的空間高度和層數(shù)不受限制。實(shí)驗(yàn)室模擬測(cè)試結(jié)果顯示數(shù)據(jù)訪問的時(shí)間和空間效率與理論值非常接近，預(yù)計(jì)能夠達(dá)到單CPU承載1 000～1 500人的性能設(shè)計(jì)目標(biāo)。

4 2D方案、偽3D方案和真3D方案的性能比較

偽3D方案擁有對(duì)2D方案的最佳兼容性和最低的開發(fā)成本，在場(chǎng)景高度能夠使用有限層表達(dá)時(shí)，優(yōu)勢(shì)較明顯。真3D方案在3D支持方面要大大優(yōu)于偽3D方案，但放棄了對(duì)原 2D方案的兼容支持，從而增加了開發(fā)方面的投入。這3類方案的性能比較結(jié)果如表4所示。

5 結(jié)論

(1) 提出了基于2D場(chǎng)景方案擴(kuò)展的偽3D和基于RLE壓縮的真3D 2種解決方案，以適應(yīng)傳統(tǒng)2D網(wǎng)絡(luò)游戲向3D網(wǎng)絡(luò)游戲演化進(jìn)程中不同階段的需求。

(2) 偽3D方案通過對(duì)原2D方案的數(shù)據(jù)結(jié)構(gòu)和尋路算法進(jìn)行擴(kuò)展，在2D數(shù)據(jù)邏輯的基礎(chǔ)上實(shí)現(xiàn)3D游戲場(chǎng)景。訪問效率仍然保持常數(shù)級(jí)的時(shí)間復(fù)雜度；但受空間效率的制約，表達(dá)的層次不能超過3層。該方案適用于非完全自由的、有限層可表達(dá)的 3D場(chǎng)景，在開發(fā)周期和實(shí)施成本上優(yōu)勢(shì)明顯。

(3) 真 3D方案適用于完全自由、無限層可表達(dá)的復(fù)雜3D場(chǎng)景表達(dá)需求。3D游戲場(chǎng)景帶使數(shù)據(jù)存儲(chǔ)和尋路算法開銷巨大，通過引入了RLE壓縮算法，在大大提高存儲(chǔ)效率的同時(shí)，實(shí)現(xiàn)了與訪問效率之間的平衡。空間復(fù)雜度和時(shí)間復(fù)雜度分別從 2D情況下的O(n2)和O(1)，僅增長到O(k*n2)和O(k)，且通常情況下k較小。實(shí)驗(yàn)結(jié)果也驗(yàn)證了該方案的可行性。

[1] Aliaga D G, Carlbom I. Plenoptic stitching: A scalable method for reconstructing interactive walkthroughs[C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH. Los Angeles, 2001: 443-450.

[2] Gonciari P T, AL-Hashimi B M. Variable-length input Huffmancoding for system-on-a-chip test[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003, 22 (6): 783-796.

[3] Anshuman C, Krishnendu C. Test data compression and test resource partitioning for system-on-a-chip using frequencydirected run-length (FDR) codes[J]. IEEE Transactions on Computers, 2003, 52(8): 1076-1088.

[4] 楊玲. 一種高性能網(wǎng)絡(luò)游戲服務(wù)器架構(gòu)設(shè)計(jì)[J]. 網(wǎng)絡(luò)安全技術(shù)與應(yīng)用, 2010, 4: 59-61.YANG Ling. A high-performance architecture design of network game server[J]. Network Security Technology & Application,2010, 4: 59-61.

[5] 張曉偉. 基于嵌入式的3D游戲圖形渲染引擎的設(shè)計(jì)[J]. 軟件導(dǎo)刊, 2009, 8(8): 185-186.ZHANG Xiao-wei. Based on embedded 3D graphics rendering engine of the gamedesign[J]. Software Guide, 2009, 8(8):185-186.

[6] 梁華國, 蔣翠云. 基于交替與連續(xù)長度碼的有效測(cè)試數(shù)據(jù)壓縮和解壓[J]. 計(jì)算機(jī)學(xué)報(bào), 2004, 27(4): 548-554.LIANG Hua-guo, JIANG Cui-yun. Efficient test data compression and decompression based on alternation and run length codes[J]. Chinese Journal of Computers, 2004, 27(4):548-554.

[7] 張仁津, 劉彬. 3D游戲場(chǎng)景繪制和管理的特殊技術(shù)[J]. 貴州師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2011, 29(1): 74-77, 87.ZHANG Ren-jin, LIU Bin. The specific technology of 3D game scene drawing and management[J]. Journal of Guizhou Normal University: Natural Sciences, 2011, 29(1): 74-77, 87.

[8] 劉娟, 歐陽一鳴, 梁華國. 基于連續(xù)和交替序列編碼的測(cè)試數(shù)據(jù)壓縮[J]. 計(jì)算機(jī)工程, 2010, 36(1): 274-276.LIU Juan, OUYANG Yi-ming, LIANG Hua-guo. Test data compression based on encoding series and alternation sequences[J]. Computer Engineering, 2010, 36(1): 274-276.

[9] 陳和平, 張前哨. A*算法在游戲地圖尋徑中的應(yīng)用與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件, 2005, 22(12): 118-120.CHEN He-ping, ZHANG Qian-shao. Application and implementation of A* algorithms in the game map path-finding[J]. Computer Applications and Software, 2005,22(12): 118-120.

[10] 王同喜, 孫淑霞. 基于A*和Bresenham相結(jié)合的網(wǎng)絡(luò)游戲?qū)ぢ匪惴ㄔO(shè)計(jì)與實(shí)現(xiàn)[J]. 成都理工大學(xué)學(xué)報(bào): 自然科學(xué)版, 2007,34(7): 456-459.WANG Tong-xi, SUN Shu-xia. Design and realization of a net game path-seeking algorithm based on A* and Bresenham[J].Journal of Chengdu University of Technology: Science &Technology Edition, 2007, 34(7): 456-459.

[11] 劉祎瑋, 張引, 葉修梓. 3D游戲引擎渲染內(nèi)核架構(gòu)及其技術(shù)[J]. 計(jì)算機(jī)應(yīng)用研究, 2006, 23(8): 45-51.LIU Yi-wei, ZHANG Yin, YE Xiu-zi. Architecture of 3D game renderer and its technologies[J]. Application Research of Computers, 2006, 23(8): 45-51.

[12] 陳文萍, 鄧俊輝, 唐澤圣. 基于圖像的虛擬場(chǎng)景實(shí)時(shí)漫游[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(9): 1191-1195.CHEN Wen-ping, DENG Jun-hui, TANG Ze-sheng. Image based real-time walkthrough in virtual environment[J]. Journal of Computer Aided Design & Computer Graphics, 2004, 16(9):1191-1195.

[13] Alexander T. 大型多人在線游戲開發(fā)[M]. 史曉明, 譯. 北京:人民郵電出版社, 2006: 1-15.Alexander T. Massively multiplayer game development[M].SHI Xiao-ming, trans. Beijing: The People's Posts and Telecommunications Press: 2006: 1-15.

[14] Rabin S. 人工智能游戲編程真言[M]. 莊越挺, 吳飛, 譯. 北京: 清華大學(xué)出版社, 2005: 90-133.Rabin S. AI game programming wisdom[M]. ZHUANG Yue-ting,WU Fei, transl. Beijing: Tsinghua University Press, 2005:90-133.

[15] 姚敏. 數(shù)字圖像處理[M]. 北京: 機(jī)械工業(yè)出版社, 2006:18-22.YAO Min. Digital image processing[M]. Beijing: China Machine Press, 2006: 18-22.