一类新的网络游戏场景3D障碍信息表达方案

陈疆¹，郭克华²，梁琳¹

(1. 中南大学 湘雅医院, 湖南 长沙，410008；

2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

摘要：针对传统网络游戏的2D场景向3D场景演化过程中游戏服务器所面临的障碍信息存储和访问的技术难题，提出伪3D和真3D 2种解决方案。伪3D方案通过对原2D方案的数据结构和寻路算法进行扩展，在2D数据逻辑基础上实现3D游戏场景。真3D方案将原2D场景的数据存储方案在纵向维度上完全扩展，再应用RLE压缩算法，解决纵向扩展带来的数据膨胀问题，同时兼顾访问效率。研究结果表明：伪3D方案适用于非完全自由、有限层可表达的3D场景，完全兼容原2D数据存储格式、寻路算法及功能模块接口，具有开发周期短、实施成本低的优势；真3D方案适用于完全自由、无限层可表达的3D场景，能够满足复杂的3D场景需求，并在空间效率和时间效率方面取得了较好平衡，可实现大型3D网络游戏场景障碍信息高效表达及访问的需要。

关键词：障碍信息表达；Astar算法；RLE算法；网络游戏场景

中图分类号：TP391         文献标志码：A         文章编号：1672-7207(2012)07-2636-06

A novel approach for 3D barriers information expression in network game scene

CHEN Jiang¹, GUO Ke-hua², LIANG Lin¹

(1. Xiangya Hospital, Central South University, Changsha 410008, China;

2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: In order to solve technical problems such as obstacle information storage and access to game servers in the evolution process from the traditional network 2D game scene to 3D game scene, both the pseudo 3D and real 3D solutions were proposed. Through the extension of original 2D method data structure and routing algorithm, pseudo 3D method realized 3D game scene at 2D data. Real 3D method completed extended original 2D scene data base storage in the vertical dimension, and then it applied the RLE compressive algorithm to the solution of the data distention issue caused by the vertical expansion and ameliorate accessing efficiency. The results show that pseudo 3D method can be applied by non-completed free and limited layer expression of 3D scene, totally being compatible to original 2D data storage format and routing algorithm and function module interface, which has short development cycle and low implement cost advantage. Real 3D method can be used in completed free and unlimited layer expressed 3D scene, which can satisfy the complicated need in 3D scene. Also, it gains a fit balance between the space efficiency and time efficiency, realizing large 3D network game scene obstacle information efficiently expression and access requirements.

Key words: barriers information expression; Astar algorithm; RLE algorithm; network game scene

传统网络游戏的体系结构通常分为服务器和客户端2部分。在服务器和客户端，都需要存储和使用游戏场景的障碍信息。其中，客户端不仅需要利用场景障碍信息使游戏表现正确，而且需要利用其隐含的路径连通信息，实现游戏角色的 AI 寻路算法；而服务器端则因网络游戏的运营通常处于公共网络环境的特殊情况，要随时面对包括伪造数据包、外挂加速在内的各种风险^[1]。因此，网络游戏的服务器端需要进行极频繁和大量的数据校验工作，对数据访问的性能要求极高，这样，对数据存储的格式也提出了更高的要求^[2-3]。在一般情况下，游戏服务器需要服务成千上万的用户，同时处理几十甚至几百个场景信息，因此，游戏场景的障碍信息占据的存储空间受到严格的限 制^[4]。传统的 2D 网络游戏场景中的障碍信息表达方案很成熟，但网络游戏产品的 3D 化是大趋势，这对信息的存储访问及相关算法提出了新的要求^[5]。从项目研发周期成本和产品的继承性等方面考虑，都倾向于在现有成熟的 2D 方案上进行扩展，力求寻找既能够清晰地表达游戏场景的障碍信息，又能够支持节省空间、快速访问的方法^[6-9]。针对此类问题，本文作者基于传统 2D 网络游戏场景的障碍信息表达方式，针对3D游戏场景，提出一种伪 3D 障碍信息表达方案和一种真 3D 障碍信息表达方案。通过效率分析和实际应用对这2种方法的可行性进行分析   验证。

1  2D场景的障碍信息表达方案

传统2D网络游戏场景通常是1个简单的栅格平面，使用二维数组直接存储。这种方案的优势在于：数据访问是常数级的时间复杂度，因此，有较好的数据访问性能。在此数据格式的基础上，客户端可使用成熟的 Astar 算法实现寻路功能^[10]。实践证明，在中等规模的场景且数量不大的情况下，该方案能够满足需求^[11-13]。图1所示为1个典型的障碍物场景中Astar算法的寻路过程，图2所示为该障碍信息的存储矩阵。

在传统 2D 网络游戏场景下，对于一个n×n的矩阵，其效率如表1所示。

表1  2D场景方案下的效率

Table 1  Efficiencies under 2D approach

图1  Astar 算法图示

Fig.1  Chart of Astar algorithm

图2  障碍信息存储矩阵

Fig.2  Barriers information storage matrix

2  多层伪3D场景的障碍信息表达方案

从功能模块划分的角度，游戏的场景渲染呈现与游戏的数据逻辑可以完全分离。基于该思路，很多游戏使用 3D 渲染技术，用于呈现真实场景，但在数据层面上是完全的 2D 逻辑，称为伪 3D 方案^[14]。

伪 3D 方案在本质上是 2D 数据逻辑，所以，在1个 (x, z) 坐标确定的垂直方向上，只能存储地表障碍信息。游戏角色一旦离地腾空，则服务器不可识别。因此，场景中无法布置上、下2层都可以行走的如空中岛、桥洞、城门等地形。

但实际情况是：很多伪3D场景中，都存在对如桥洞和城门等地形的需求。真3D场景所需的计算代价较高，为此，本文作者基于现有研究基础，提出一

套伪3D地形的扩展方案。

2.1  设计思想

该方案在原 2D 的单层障碍信息基础上，再增加一层障碍信息，用于表达桥洞和城门等上层障碍。2层障碍信息之间通过特殊指定的连通点连通。

在这种数据组织结构基础上，最关键的问题就是要正确判断角色当前所处的层。在伪 3D 地形的扩展方案中，为当前地表生成一张高度图，根据角色所处的位置高度判断是在地面层还是在扩展层。

这种扩展格式对客户端的寻路需求具有较好的天然支持。在 2D 数据逻辑基础上，依据对障碍信息中隐含的路径连通性的理解，可分为 4 连通定义和 8 连通定义。这2种连通定义对Astar寻路算法没有本质区别。实际上，多数游戏使用介于两者之间的、带权重的 8 连通定义。对于扩展出来的一层障碍信息，只需要将 8 连通定义理解为 10 连通定义即可。

需要特别考虑的是：跨层的路径只能在特别指定的跨层点出现，因此，10 连通定义也只对特别指定的跨层点有效，在其他情况下，仍然将其连通性限制在单层数据内。在该方案基础上，对原Astar寻路算法略微调整即可使用。图3所示为基于多层伪3D场景的障碍信息表达方案的搜索过程。

2.2  性能分析

多层伪 3D 场景的障碍信息表达方案的访问效率仍然保持常数级的时间复杂度。但因为极少量的双层地形，需要增加1倍数据量，所以，存储效率有所下降，这也是本方案最大的缺点。而客户端的Astar 寻路算法也可能在某些极端地形下遇到性能瓶颈(如回旋下降的台阶)，该问题可以在游戏策划层面进行规避。本方案的优势在于：仅需在2D数据逻辑基础上付出极低的修改成本。因此，该方案能够很好地满足大型网络游戏的需求，且在实施成本很低。

在多层伪 3D 场景方案下，对于1个n×n的矩阵，3D场景高度为m，其效率分析如表2所示。

但是，多层伪 3D 场景的障碍信息表达方案通常只能表达2层至多3层障碍地形。其原因是：随着层数增加，其存储效率会急速下降至不可接受的程度，大量数据不被用到。超过2层的障碍信息也会给基于高度图的层定位造成困难。而大量的无用数据也会快速增加客户端 Astar 寻路算法的时间。从服务器到客户端所遇到的各种限制都决定了其只能表达有限的障碍信息层。多层伪3D场景方案下的效率见表2。

图3  多层伪3D场景下的搜索过程图示

Fig.3  Search process under multi-layer pseudo-3D scene

表2  多层伪 3D 场景方案下的效率

Table 2  Efficiencies under multi-layer pseudo-3D approach

该方案已成功应用于1款名为《问鼎》的大型在线网络游戏，其3D城战场景部分依托上述方案实现。该游戏的最高同时在线数于2009年达到峰值3万人。

3  真3D场景障碍信息表达方案

若不考虑实现上的困难，尝试将伪 3D 场景的障碍信息表达方案进行无限扩展，则障碍信息将从几个有限的 2D 矩阵的层叠转化为1个 3D 矩阵。障碍信息的存储单元也从单元格变成单位立方体。这种结构能够从逻辑上满足真3D 场景所有关于障碍信息的功能性需求。但是，其带来的巨大存储和寻路算法开销是无法承受的，所以，要在该思路下实施真 3D 场景障碍信息表达方案，实际上就是要解决存储和寻路2个问题。图4所示为3D场景障碍信息存储矩阵。

图4  3D场景障碍信息存储矩阵图示

Fig.4  3D barriers information storage matrix

针对寻路算法方面的问题，在该方案下，只能抛弃Astar算法，使用矢量寻路方案。常见的基于NavMesh导航网格的寻路方案都可以取得较好的效果。

针对存储效率的问题，1个表达真 3D 场景障碍信息的 3D 矩阵中大量的数据实际上是冗余的。直观的理解是：在1个 3D 场景中，除去贴近地表的部分和极少量的空中岛、城墙、桥洞等地形，离开地面一定高度后，几乎全是非障碍点。换句话说，其真实的信息量其实并不大，这需要对数据进行压缩来大幅度提高存储效率。但是，数据压缩带来的问题是访问效率下降，所需数据无法直接索引。最坏的情况是需要解压缩访问。所以，寻找一种合适的压缩算法能够在存储效率和访问效率间取得平衡，这是该方案的关键点。

3.1  设计思想

本方案的基本思想是：将一种常被用于图像无损压缩的 RLE 算法^[15]解决真 3D 场景障碍信息表达所遇到的问题。RLE(Run-length encoding，即游程长编码)算法的基本思路是将多个连续的数据记录为 value-length 的格式。例如，数据流中连续出现 10 个 0，则记录为 (0,10)，数据量从 10 个整数减少到 2 个整数，从而达到压缩存储的目的。其优势在于无需解压缩即可直接访问。被压缩数据流中连续出现的数据越多，存储和访问效率就越高。

将1个真 3D 场景的障碍信息矩阵看成是1个 2D 矩阵在纵向上的流式扩展。相应地，将其存储为1个平面上的 2D 矩阵，而矩阵中的每个元素是该点在纵向上障碍信息的数据流。考虑到空间中绝大部分位置都是非障碍点，对应的数据流基本上都是单一数据的连续重复。因此，该数据流是绝好的 RLE 压缩对象。实际上，若仅用 0 和 1 表达障碍和非障碍2种情况，则RLE中value-length的value部分都可以被省略，存储效率能够再提高1倍。图5所示为用颜色区分标记处 RLE 的压缩段，能更清楚地显示该方案效果。

其中：v11~v99都是表达在各自垂直方向上障碍信息的一组向量，对应图5，有

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

图5  3D障碍信息存储矩阵

Fig.5  3D barriers information storage matrix

表3  多层真3D场景方案下的效率

Table 3  Efficiencies under multi-layer real-3D approach

表4  3类方案的性能比较

Table 4  Performance comparison of three kinds of approach

经RLE压缩后为：

v16=(1,5,0,5)

若进一步省略value，将value的变换隐含在length中，默认初始value为0，则可表示为：v16=(0,5,5)。

3.2  性能分析

在多层真 3D 场景方案下，其效率分析如表3所示。该方案已应用于1款目前正在开发当中的名为《斗仙》的大型全3D多人在线网络游戏中。该款游戏为即时战斗类型，其所有场景均为真3D场景。依托真3D方案，其数据量仅仅是相同平面尺寸的 2D障碍信息的 2~3 倍，在纵向上所能表达的空间高度和层数不受限制。实验室模拟测试结果显示数据访问的时间和空间效率与理论值非常接近，预计能够达到单CPU承载1 000~1 500人的性能设计目标。

4  2D方案、伪3D方案和真3D方案的性能比较

伪3D方案拥有对2D方案的最佳兼容性和最低的开发成本，在场景高度能够使用有限层表达时，优势较明显。真3D方案在3D支持方面要大大优于伪3D方案，但放弃了对原2D方案的兼容支持，从而增加了开发方面的投入。这3类方案的性能比较结果如表4所示。

5  结论

(1) 提出了基于2D场景方案扩展的伪3D和基于RLE压缩的真3D 2种解决方案，以适应传统2D网络游戏向3D网络游戏演化进程中不同阶段的需求。

(2) 伪3D方案通过对原2D方案的数据结构和寻路算法进行扩展，在2D数据逻辑的基础上实现3D游戏场景。访问效率仍然保持常数级的时间复杂度；但受空间效率的制约，表达的层次不能超过3层。该方案适用于非完全自由的、有限层可表达的3D场景，在开发周期和实施成本上优势明显。

(3) 真3D方案适用于完全自由、无限层可表达的复杂3D场景表达需求。3D游戏场景带使数据存储和寻路算法开销巨大，通过引入了RLE压缩算法，在大大提高存储效率的同时，实现了与访问效率之间的平衡。空间复杂度和时间复杂度分别从2D情况下的O(n²)和O(1)，仅增长到O(k*n²)和O(k)，且通常情况下k较小。实验结果也验证了该方案的可行性。

参考文献：

[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 frequency- directed run-length (FDR) codes[J]. IEEE Transactions on Computers, 2003, 52(8): 1076-1088.

[4] 杨玲. 一种高性能网络游戏服务器架构设计[J]. 网络安全技术与应用, 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游戏图形渲染引擎的设计[J]. 软件导刊, 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] 梁华国, 蒋翠云. 基于交替与连续长度码的有效测试数据压缩和解压[J]. 计算机学报, 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游戏场景绘制和管理的特殊技术[J]. 贵州师范大学学报: 自然科学版, 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] 刘娟, 欧阳一鸣, 梁华国. 基于连续和交替序列编码的测试数据压缩[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*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件, 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相结合的网络游戏寻路算法设计与实现[J]. 成都理工大学学报: 自然科学版, 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游戏引擎渲染内核架构及其技术[J]. 计算机应用研究, 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] 陈文萍, 邓俊辉, 唐泽圣. 基于图像的虚拟场景实时漫游[J]. 计算机辅助设计与图形学学报, 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. 大型多人在线游戏开发[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]. 庄越挺, 吴飞, 译. 北京: 清华大学出版社, 2005: 90-133.
Rabin S. AI game programming wisdom[M]. ZHUANG Yue-ting, WU Fei, transl. Beijing: Tsinghua University Press, 2005: 90-133.

[15] 姚敏. 数字图像处理[M]. 北京: 机械工业出版社, 2006: 18-22.
YAO Min. Digital image processing[M]. Beijing: China Machine Press, 2006: 18-22.

(编辑 陈灿华)

收稿日期：2012-01-10；修回日期：2012-03-10

基金项目：教育部博士点基金资助项目(20090162120069)；湖南省科技计划项目(2009FJ3016)

通信作者：陈疆(1976-)，男，湖南郴州人，工程师，从事计算机网络及应用等研究；电话：0731-84327569；E-mail: cjxyz@126.com