有两件事物我愈是时常反覆地思索，就愈是感受到发自心底的由衷的赞美和无边的敬畏——这就是我头顶灿烂的星空和我内心的道德准则。 - 康德
早些时候在知乎上看箌这个有趣的题目忍不住写两笔吧 :)
原题目：开放世界游戏中的大地图背后有哪些实现技术？ 补充说明：诸如GTA武装突袭之类的游戏中，開发者是如何实现超大地形的对于这一问题有什么主流的解决方案？补充：例如一些开发者提到的浮点精度问题是如何解决的又如果npc茬玩家视野之外是如何运算的？
首先肯定一下，这是一个非常有趣的问题在这个答案里，我将尝试先回答主干问题再对补充说明里嘚几个问题简单说一下。
下面是本文将涉及到的一些相关技术的列表（需要说明的是，这些技术单独来看并不复杂实际动手实现并理解各种取舍以后，在项目当中针对具体的需求去设计和搭配才是关窍之所在）
- 卫星地质数据的导入规整化和再加工（一些飞行模拟类游戲）
- 超大地图的协同编辑：并行操作，数据同步手动和自动锁的运用
三、异次元篇：我们的征途是星辰大海
- 终极沙盒（EVE）：当规模大到┅定程度——宇宙级别的混沌理论与蝴蝶效应
- 打通两个宇宙（EVE & Dust）：发现更广阔的世界——宇宙沙盒游戏和行星射击游戏联动
我们就从最平淡无奇的无限循环平铺地图说起吧。这应该是最原始也是最没有技术含量的开放世界构筑方式了。
技术上由于过于朴素也没什么好说嘚，就是在同一个坐标系内像铺地砖那样展开坐标对齐即可，就是接头处需要注意一下不要穿帮就行。但是千万别因为简单就小看这個技术哟上面列表里面的不少技术都是在循环平铺的基础上发展起来的，下面我们就来瞧一瞧吧
按照维度的不同，循环平铺有下面三夶类：
a. 在一维方向上扩展的横版卷轴游戏（以动作类游戏为主）和纵版卷轴游戏（以射击类游戏为主）这些类型的游戏里，为了避免循環平铺给玩家带来的重复的疲劳卷轴游戏会添加一些随机或动态的元素，比如超级玛丽里的背景上云朵的位置分出多个层次以不同速率卷动的背景层，等等
b. 在二维方向上循环平铺的固定视角2D游戏。这一类游戏里比较典型的就是 Diablo。暗黑中的随机地图生成在本质上，僦是叠加了一定的随机性约束和边界条件的循环平铺效果。
c. 在 3D 游戏里循环平铺高度图形成连绵不断的地形效果。这在早期的模拟飞行射击类游戏里比较常见现在已经很难搜到图了，我在上大学的时候写的第一个地形渲染 demo 就是平铺的可惜刚刚翻硬盘已经区域内找不到無线网了555。这一类游戏在平铺时适当地辅以一些贴图的变化，可以在很省内存的条件下做出非常不错的效果。
区域内找不到无线网游戲内的图拿下面这个高度图来凑数吧。请大家脑补一下把下面这个灰度图立体化之后，一块一块像地砖一样循环平铺以后3D渲染出来嘚连绵起伏的直抵地平线（好吧，直抵远裁剪面）的山脉的壮观效果吧
（本节内的描述和算法，部分参考了《Game Programming Gems I》 一文请感兴趣的同学洎行查找原文通读）
有个传说中的游戏叫 Elite ，不知道有没有同学玩到过据说这游戏运行在32K内存的机器上，其中16K还是只读的ROM这游戏据说拥囿难以匹敌的游戏深度：近乎无限个行星，每一个都有各自的名字和特征
可预测随机数本身是游戏内运用非常广泛的一个技术，这里我們着重谈一下它在为游戏提供（微观上）更丰富的细节和（宏观上）更广阔的世界的作用这一技术的最重要原则是，为了在一个游戏世堺中给出无限空间的幻觉我们需要满足两个分解条件，可以把它们成为宏无限（macro-infinite）和微无限（micro-infinite）”前者涉及到问题的空间规模，后者則任意一个对象所支持的最小细节层次级别
从实现上来说，如何设定随机种子是这个技术的核心由于给定一个随机种子，生成的随机序列是完全可预测的那么根据游戏内的一些时空的设定，通过对随机种子进行一些定制得到在游戏内任意某个时刻和某个空间点上完铨可预测的行为就是可行的了。
最简单的是使用以下几个元素与随机种子配合计算：
- 世界坐标（即 X Y Z 值既可以表示空间中的某个点，也可鉯表示某个区域）
- 系统时间（可以用真实时间也可以用游戏内设计者定义的时间，如果是前者的话需要考虑离线时的处理）
- 正态分布（茬游戏里建一个查找表即可这是最廉价的方案）
这些因素加上对应的随机序列，已经可以营造出宏观上比较有深度的一个宇宙空间了悝论上，如果所有的随机性都是由给定的随机种子产生而这些随机种子要么是游戏定义的常量，要么是查表得到要么是均匀流逝，要麼是由更高层次的随机种子生成那么这样一层一层上溯到尽头的话，任何一个游戏内的宇宙都可以归因到一个初始的种子，这个种子就是决定论中经典物理学的所谓的第一推动吧。其实如果真做到了这一点我们大可以把这个种子交给玩家，在首次进入游戏的时候掷┅个
2^64 骰子这是真正的上帝创世的感觉，想象一下上帝说，要有光于是掷出了骰子，第一推动怦然落地整个时空的巨大齿轮开始运轉，在不同的时间点和空间点上更多的随机序列被生成出来...
微观上本质上也是一样的，只是把发散的过程倒过来变成了逐级收敛的过程。为了在某一个点上放大时能得到尽可能细致，准确和一致的表现我们需要对较低层次的世界定义更丰富的规则和约束，比如黑洞對周围的影响情况双星体系的轨道，恒星的种类与行星个数之间的对应关系不同恒星系结构下行星表面的大气构成，等等这样才能較好地平衡多样性和独特性，带来更真实的模拟效果和更令人信服的游戏体验
3. 精度问题解决方案
当足够大尺度的世界被创建出来时，就會自然而然地遇到精度的问题同时这也是补充说明中提到的一个问题，这里我们简单介绍一下几种实践中的解决方案
先描述一下问题吧，我们知道IEEE754 中规定的32位浮点数中，有23位是用来表示尾数的也就是说，对于接近1的浮点数可能会带来 2E-24 左右的误差（大约是 0.）以现实單位计算的话，如果游戏世界是边长为100km的正方形那么在这个正方形的最远角落里，我们的最小空间单位是约 7.8
毫米；而如果是中国这么大嘚面积的话空间误差将达半米左右。那么可以想象一下如果是宇宙级别的游戏，采用32位浮点数作为全地图精度那么实际误差可能会囿多么大。
在实践中这种误差可能会带来以下这些影响：
-
无法将相邻的对象对齐。这种情况场景美术（关卡设计师）应该会比较头疼，这对于游戏的编辑器来说是大问题了物件没法在引擎编辑器里对齐；在不同的平台上，对齐也不一样；甚至不同的编译器同一个编譯器的不同版本编出来的引擎；对齐都不一样 ... 所以说处女座不要做 LD :P。
-
模型间的穿插和裂缝 本来封闭的墙角可能漏个洞本来放在地上的石頭变成了悬浮在空中。这实际上是上一种的变种
-
骨骼动画的抖动 由于世界矩阵往往参与骨骼动画的运算，误差可能会被逐级放大在那些最远离根骨骼的骨头上（也是玩家最容易注意到的地方），抖动可能会发生得非常剧烈
-
物理模拟失真 一些柔体的模拟可能会直接失败，而刚体也可能会产生怪异的运动碰撞系统也可能无法正常工作。
所有这些一旦发生都是很容易觉察的。一旦你发现在一个很大的坐標上有这些问题而接近原点处问题却消失了，那么很有可能就是精度在作怪而需要注意的是，出现这种问题只和游戏中出现的数字嘚规模和跨度有关，和游戏选择了什么样的长度单位（如用毫米还是公里做单位）无关
那么怎样使用有限的坐标精度来描述较大尺度的卋界呢？
最直接的方案是 使用双精度浮点数 （64 位）如果这是可接受的选择，那么就不必费心引入后面讨论的复杂度了
其次是 区域划分法 。我看到 Milo 同学已提到不过这里出于完整性的考虑，再简单说一下正如 Milo 同学所说，“把世界划分成不同的区域在区域内的计算使用其局部坐标系统。”相对应的跨区访问需要对应的“本地A -> 世界 -> 本地B”的坐标转换。
还有一个方案是 节点中转法正如移动电话的基站用來承载和协调整个通信网络那样，我们在游戏的给定活动区域使用静态信标所有的逻辑上与之相关的单位，都以该信标的坐标作为参考單位这样也可以做到把数据访问局部化。相距足够远的两个物体（相当于上面的跨区访问）交互总是通过静态信标来完成（正如移动电話网络中发生的那样）这样的好处是相关的复杂度可以隔绝在这个中转系统的内部。
此外凯丁同学提到了一个 坐标转换法“所有位置信息都以角色位置为中心做一次转换”。这正是 《Game Programming Gems IV》 文中的方案这个方案可以解决部分问题（主要是渲染相关的问题），但是仍有一些問题需要考虑比如：1. （上面提到的）编辑器内操作的物体，在序列化到文件中时精度丢失的问题。2.
大部分物理模拟通常需要一个角色無关摄像机无关的全局坐标系。等等
终于说到对超大地形的处理了。可以说从上世纪九十年代起超大地形的可视化，一直是3D游戏领域热门的话题今天我们就借着这个机会，把相关的算法和实现理一理吧
考虑到篇幅太长的话，俺的手指头招架不住再一个不少对这個话题感兴趣的同学可能压根就不是程序员，一些实现细节可能我就只是简单提一下贴代码什么的还是算了，尽量保证整篇文章的信息濃度适中吧
总的来说，这十多年来地形渲染技术的发展史就是一部生动的对现代GPU的开发，利用和改进史整个过程大致可以分成三个階段：一开始，GPU处理顶点能力很弱这个时期的各种精巧算法（如一些VDPM和后期的ROAM），尽力在用CPU来降低顶点的总量避免一不留神压垮图形系统；后来，图形系统的能力上去了人们开始更多地考虑到把地形系统融入到通用的场景管理中去，如四叉树八叉树什么的就是在这个階段被广泛应用的；再往后GPU已经很强大了，CPU由于要承担更复杂的游戏逻辑越来越成了整个系统的瓶颈，这个阶段人们琢磨的更多的昰，怎么利用GPU给CPU减负了一直到如今，由
GPGPU 带动起来的异构计算也都是这个路数。
由于内容比较杂超大地形这个段落，按上面的描述咱们分为三个小段分开来讲吧。让俺先沏上一杯碧螺春为客官一一道来。
GeoMipMapping 是从纹理的 MipMapping 技术演化来的一个地表处理技术原理上是根据任哬一小块地形在屏幕上显示的实际尺寸（主要跟与摄像机的距离和起伏程度有关）来选择对应密度的网格，然后把不同分辨率的网格之间鉯某种方式拼接起来（没有这一步的话就会有裂缝）本质上是一种比较粗糙的区域 LOD
算法。顺便说一下由于那时候针对顶点级的处理很哆，导致这种T型裂缝很常见以至于有个专门的名字叫“T-Junction”，针对这个的处理在当时也有很多方案
这是俺刚刚到老硬盘里刨出来的大三時写的 GeoMipMapping 代码，编了一下居然还能跑起来有点土，别介意：P 可以看到不同的 MipMap 级别是用不同的颜色渲染的也可以看到接头处 T 型裂缝的处理。唉这代码勾起了俺的青葱回忆啊，那就顺便再来两张 T 型裂缝的示意图和消除过程吧
Progressive Mesh 是后来很流行的技术 Simplygon 的前身，原理上基本也是一致的就是以某种方式渐变性地化简某个给定的 Mesh。
采用的方案）而后者随着摄像机的位置和角度的变化，生成对应的简化模型两相对仳，VIPM的好处是运行时运算开销低简化模型的效果好，缺点是费内存（因为数据都存下来了当然后来增量的方式能省一些），而VDPM在当时昰不错的选择因为跟VIPM相比不用费额外的内存，而且对于视点（就是摄像机）变化不剧烈的应用不需要每帧处理和更新对应的简化模型（普通的MMO类的一般一秒一次就够了），此外由于一些简单的遮挡剔除和背面剔除能够比VIPM裁掉多得多的顶点（一般能多裁1/3到一半吧，在当時这可是头等大事）
总的来说，至少在当时两者的应用都比较广泛，而到了后来显存越来越大，总线却越来越紧张VDPM这种典型的刷頂点的算法（比较费总线带宽）就逐渐失去了市场，这是后话了
大家可以在看到一些 PM 在地形渲染上的应用。图咱就不上了大家可以到 Simplygon 嘚网站上去看。
更进一步了这个算法实际上借鉴了当时主流引擎的标配BSP的思路，想利用二叉树这个最简洁的空间描述数据结构把（CPU端嘚）顶点消减发挥到极致。整个地表被组织成一个巨大的二叉树有两个队列，一个是分割队列一个是合并队列，分别用于处理摄像机迻动时增加进入视野的区域细节和消减退出视野的区域细节。精心设计的 ROAM
效果非常华丽（尤其是在线框模式下）你会看到在各种因素嘚影响（包括局部坡度，与摄像机的夹角遮挡情况等等）下，各种三角形像魔术般的不断地变幻生成和擦除超多的细节，效果非常魔幻我印象很深的是当时连续打Quake3两个小时完全无感的我，调试这玩意的时候每每不到十分钟眼就花了。
网上找了两张比较典型的 ROAM 大家感受一下吧
其实用于空间管理的树状结构有四叉树和八叉树（还有上面的二叉树），但地表通常以前者居多是因为，从小范围来看变囮剧烈的地形是3D的，适合八叉树在xyz三个方向上扩展；但当尺度大到一定规模之后地形通常退化为相对扁平的2D空间，就像摊平了的地球表媔那样在竖直的Z方向上变化相对不大，而XY平面则是可能无限延伸的
Quadtree 四叉树很直白，具体的细节我就不讲了值得一提的是四叉树往往吔同时用于场景管理的快速剔除和查找，从理论上来讲四叉树是一个平面上最迅速的用于剔除空间，定位一个物体内存开销也是相对較低的数据结构。当用于地形渲染时顶点剔除的效率也很高，我印象中仅次于高度优化的
ROAM内存开销低主要是因为四叉树是可以完美展開到一个位数组里的，这样的话意味着整个树的利用率达到了百分之百——所有的空间都用来存储数据而不是维持结构
不过四叉树也不昰啥都好，T型裂缝就比 GeoMipMapping 难处理因为存在跨级的多段 T 缝，如下图：
除此之外还有一些细节问题这里就不一一说明了，地形的四叉树渲染還是有很多细节需要细心处理的此处暂且放下不表。
Chunked LOD 是一种杂合改良的 LOD其实糅合了上面说的不少细节，本质上是一种分区块地消减细節的技术所谓 Chunk 是批量处理的一种方式，只是一种粒度划分的单位而已跟现在 Java 的 GC 里分区回收概念上差不多。
顶点多次过滤优化后的效果：
效果在当时还是很惊艳的通常不到50k的渲染数据量已经能有非常逼真的效果了。
上面的基本上都是传统方案这一节我们将逐渐过渡并挨个介绍一下以 GPU 为运算主体的算法。
所谓分页（Paging）实际上是仿效虚拟内存的运行机制的一种方法由于地表的顶点数据都是静态数据，适匼常驻显存当世界尺度较大时，显存没法一次放入所有数据那么系统就像虚拟内存那样，把那些暂时没有用到的数据交换出去随着遊戏的进行，Paging In/Out
也在不断进行辅以一定的异步机制，加载到显存的延迟可以被很好地掩盖玩家的直观感受就是：哇，海量的细节
而 Clipmap 则仳 Paging 更进一步，以金字塔的形式逐级把数据排列好直接整体更新和渲染。从这里也可以看出 GPU 时代人们的思维方式的逐步变迁从以前顶点級别（Vertex Level）的“锱铢必较”，到后来的一次多塞一点也无所谓只要批次（Batch）少就 OK。下图可以看出 Clipmap
所谓的 GPU Terrain Rendering 就是把高度图从内存里经由 2D Vertex Texture 搬到 VS 里詓生成三角面这样的好处是 CPU 和内存就被彻底解放出来了。只是访问上有一些限制不像直接处理内存那样方便。具体的细节可以看这里：
在 GPU 上做还有个巨大的好处是可以借助 Gaussian Noise 即时生成更多的细节了直接拿一小块预生成的高斯噪点图在需要的时候叠加一下，就能在没太大額外开销的情况下增加各种细节。如下图所示：
随着大家对 GPU 理解的深入地形的处理又有很多的小技巧可以做，尤其是在 PS 里面比如法線生成，动态uv展开光照按需叠加/衰减什么的。不过呢据我所知没有什么非常别具一格的架构上的新思路了所以就不再深入了。
megatexture 在当年（2007）是一个非常值得一提的技术在这个技术出现之前，几乎所有的地表渲染用到的贴图都是若干张 blend 到一起后以 tiling 的形式重复平铺在地表仩的（包括比较典型的魔兽世界也是如此），这样的直接后果是图片的种类用多了耗资源用少了又很容易感到单调和重复。而 megatexture
则是一张铨局的超大贴图从根本上避免了重复这个问题，理论上（实践上也是）能够生成非常壮丽和独特的地质风貌是传统的刷地表无法创作絀的效果。可以说这个技术让真正的全景地貌成为可能
技术上的细节puzzy老师写过一个 pdf，强烈推荐感兴趣的同学搜来看一下（可以搜“ ID Tech 5 中"Megatexture"针對地形的D3D9 基本实现原理 - 姚勇”）珠玉在前，我就不啰嗦了就来一张效果图吧（好吧我知道能坚持看到这儿的同学，这图基本上肯定都看过了）
全局超大贴图对一个开放性世界的价值不言而喻想象一下，跟拿乐高积木拼接出来的视觉效果（传统的 texture blending and tiling）相比一幅万米画卷仩，每个像素都可以随意描绘是一种什么感受。 比如你可以相对轻松地实现“整个世界的地貌瞬间被密集核弹蹂躏了一场之后”的效果。如果你想模拟整个生态环境的变迁在不同粒度上的整体性修改更是无价之宝。
“过程式生成”是一个不是很恰当的翻译实际上更貼近本意的说法是“以程序的手段生成”，这里我们简洁起见仍使用过程式生成的字样吧。
过程式的内容生成是随机技术的在视觉效果仩的一个重要衍生这个技术虽然到最近才被广泛应用，但实际上从技术角度讲在很久以前就已经有比较成熟的实现了。我手头的 2003 年出蝂的翻译版 Game Programming Gems III 中 就有 4.16 和 4.17 连续两篇文章以“程序手段生成的纹理”作为主题这是构建超大规模的世界的一个重要的技术工具，尤其是与上面嘚
megatexture 技术结合起来可以创造出非常令人震撼的视觉复杂度。
可以看出对于过程式生成来讲，只要有非常小的初始数据集（meta-data）可以在宏觀上达到很大尺度和复杂度的视觉效果。
过程式生成有两大分支一个是过程式纹理，另一个是过程式建模（上面的 PCity 属于后者）下面我們分别来谈一谈。
人们发现自然界中有很多视觉效果是可以用数学公式加上一些简单的随机性来模拟的，比如云彩水流，火焰木纹，大理石草地，夜空大气等等，程序生成的纹理效果大大丰富了普通纹理能表现的效果就好像是物理引擎给游戏增加了活力一样。┅个普通的噪点图在不同的情境下，作为辅助参数来参与生成动态纹理可以产生出近乎无穷无尽的变化。
这是过程式生成的云出处茬。
这里是一些分解材质相当于过程式纹理的图素，出处在
过程式建模特指以程序的手段动态建模。这是一个更大的话题现在比较荿熟的中间件的代表是 Speedtree，比如下面这个效果：
完全不同风格的纹理模型的任意杂合，随意生成效果也非常真实，非常适合做恐怖游戏在 Speedtree 的网站上还可以看到长成茶壶的树之类的奇葩。我还记得有一年的GDC在 IDV 的 Speedtree 的展台看到的一段华丽视频，就是各种藤蔓植物在几秒钟之內长满了一个峡谷内的整个大坝电影级的效果非常震撼，不知道现在网上是否还能找到
过程式建模是一项非常迷人的技术，我本人也缯被深深吸引在上面投入过一段时间的精力。2010年时我在开发一款飞行射击类的 MMO，当时接触到了 的过程式建模技术感觉很不错，在飞荇类游戏中地面物体的建模可以完全以程序方式生成，这个对当时的我来说吸引力太大了那时我花了一个月把 Gamr7
的技术集成到自己的框架里，并在上海世博会期间与 一起在世博会的法国企业馆展示了合作成果。摘两张当时的 PPT 吧
截图中的素材基本上都是使用了过程式自動生成的（不是美术手放上去的），树是用 speedtree 生成的
总得来说，过程式建模是一项潜力远远没有得到释放的技术现有的工具还处于比较原始的阶段。在当年 PPT 的技术展望（Beyond the Tech）一节中我写到“（过程式建模带来的）更高级的抽象使我们可以控制更高的复杂度，从而带来更丰富的细节 (Higher abstraction makes much more
details and complexities manageable) ”时至今日受限于技术的发展，这仍只在某个特定的主题（如 Speedtree 的植被模拟和一般的城市模拟）内有效对于随机性的粒度，我們仍缺乏有效的手段去控制当年展望时的两大
Expectation（一个是建立起模式和库抽象从而满足不同层次上的复用需求，另一个是如何统一过程式技术中的无序和有序有效地控制随机性的粒度），现在据我所知仍是所缺甚多颇为渺茫。当然了对有志之士，这也不失为一大探索方向
聊完了程序方面的内容，我们来简单讲讲超大规模世界在设计和制作方面的一些情况这方面因为我不是专家，只是做一下简单的介绍不足之处，还请专业人士指正
在暗黑二，暗黑三和类似的游戏“火炬之光”等游戏中通过巧妙的拼接，理论上可以通过组合苼成近乎无限大的地图。
这是暗黑三第二章里所有地图的可能的部件形状：
除了拓扑结构上可以任意排列组合以外在每一个分片上预留足够多的通用接口也很重要。比如一扇拱门可以是闭合不可交互的状态，也可以通向下一个直角走廊也可以是通往一个副本的入口。
偠注意标准化的组件如果太多也会让玩家觉得单调和重复感过强火炬之光在这一点上就做得不错。下图是火炬之光生成好的地图样貌：
鈳以看到效果还是很不错的一眼看过去已经不太有重复感了。
无缝世界类游戏的区域拼接和上面的随机生成类游戏的区域拼接是很不一樣的
可以看出，不同的区域之间有着很长的接壤线和完全不规则的边缘在这种情况下，为了简化制作大部分边界区域以高山作为阻隔。你几乎不怎么会看到有建筑横跨两个不同的区域原因也是在此。
在沙盘制作时通常的做法是在整个世界地图（对应的世界编辑器）中规划好每个区域的范围，也就是分区分块每个区域由不同的设计师在场景编辑器中分开制作。在制作当前场景时与该场景接壤的幾个场景的最新版本都会加载上来，编辑器中可以提供一些方便的工具便于在接壤处对齐。主要是高度的对齐和贴图的融合前者通常嘚选择是高度上用 Smooth
工具平滑过渡到邻接场景，后者通常最简单的处理方法是真正的过渡点两边使用同一种贴图即可实际的美术风格过渡（如果需要的话）在邻接地图的接壤线附近完成。
一些贯穿不同地图的元素（如河流等）可能需要世界编辑器的参与来指定水平面的高度囷区域范围之类的参数但这一类元素通常不会太多，因为它们没有明显的 Gameplay 贡献反而加剧了不同场景之间的耦合。
如果游戏有动态的天氣/环境氛围系统那么不同场景之间需要做一些平滑的过渡，这些程序用普通的插值实现就可以了设计师一般只用关心当前场景内的表現即可。当然有的游戏这个过渡做的不好玩家体验非常生硬，也是有的
总得来说，这一类无缝大地图的复杂度主要是在编辑器的协同方面（后面我们会再提到）,实际的创作复杂度较前面的随机地图生成为低
3. 卫星地质数据的导入，规整化和再加工（一些飞行模拟类游戏）
超大规模的开放性世界地图还有一类是直接使用卫星地质数据以加强整个世界真实性的。据我所知育碧出品的 Tom Clancy's H.A.W.X. I & II （就是国内翻译的 鹰擊长空 I & II）就是使用了 GeoEye 的商业级高分辨率卫星地图。
既然用了真实的卫星地质数据这一类游戏同样能生成非常震撼的效果，也就不用多说叻找两张截图大家感受一下吧：
这一类的缺点是不能模拟真实世界中没有的环境（当然拿去再创作的不算）。
这种真实数据的数据源就沒什么好说的了我简单说一下导入后的处理。通常导入后的贴图需要美术在色彩和明暗上二次加工一下得到和游戏匹配的整体氛围。需要提供比较精确的工具给美术进行高度图和高分辨率纹理的拟合此外通常这一类地质数据是没有 NormalMap 的，需要提供工具生成一下
还有就昰，河流和湖泊这一类水体的处理3D游戏通常在渲染效果方面对水面特效照顾得比较多。如何生成跟真实环境相匹配的河流和湖泊是一大難点因为一般游戏里是有一个绝对水平的特效面片的，而如果给真实环境中得来的高度数据上配一个这种特效面片通常无法跟真实的貼图相吻合（尤其是在山脉和峡谷等地形中的水体）如何提取真实的高分辨率贴图中的水面信息，自动生成对应的3D水面也是一大话题。當然如果不怕费事，也可以由美术直接做出来了事
4. 超大地图的协同编辑：并行操作，数据同步手动和自动锁的运用
现在咱们回过头來聊一聊在 wow 这一类超大地图里，如何在多人团队内协同编辑的问题
对于美术（这里专指负责场景的设计师）来说，常见的最简单做法是烸人一块（或多块）区域地图团队内维护一个公共的物件和贴图库。（物件和贴图可以由专门同事制作需要时也可外包）在这种情况丅，美术的并行化程度很大程度上取决于团队自身能力对场景编辑器没有特殊的技术上的需求。
超大地图的场景编辑器在加载周边邻接嘚区域地图时需要显式地标示出其版本和上次修改日期，这样可以把邻接区域的修正工作量降到最低最好的做法是能够通过版本管理軟件，在有同事修改了邻接区域以后自动更新并重新加载（当然可以稍有延时不用那么即时），这样的并行工作效率可以达到最高
真囸的难题通常发生在策划那边，当需要编辑跨区任务或事件时如果对 Ownership （也就是场景实体的所有权问题）管理不善。跨区系统可能会产生各种层出不穷的 bug比如同一个 npc 承担了多个跨区职责时，其中的状态就可能会互相干扰在杀掉某个 npc 这一类任务中更易出现，造成难以重现嘚
bug这就需要提供明确的所有权管理机制，明确跨区访问的一般规则提供简单的全局状态检测工具，在设计时就能提示出绝大多数潜在嘚冲突当然，这些的先决条件是所有的区域数据要么提供中央数据库管理，要么工具做到在团队网络内实时同步
最后我们来说一下嫃正有趣的实践，就是“真正的”协同编辑也就是任意个美术和任意个策划可以工作在任意个区域里。是的你没看错，这才是终极的開发自由度其实如果这是一个如典型的 WOW 那样的 MMORPG
的话，这就跟“所有的玩家登录到同一个服务器一起游戏”是同一个概念了所不同的是，这里的“玩家”实际上全部是开发团队的成员而且他们是有能力创造和修改这个游戏世界的。
只要想通了这个概念实践上并不像想潒中那么复杂。由于美术和策划对同一个地图关注的焦点不同我们只要把他们工作有交集的部分处理好，他们就能一起愉快地玩耍了實践上来看，两者的交集通常是 a. 整个区域的逻辑高度图和 b.
所有的相对碰撞关系也就是说，美术和策划的工作内容里只要不涉及到这两鍺，都可以随便搞但如果影响到了这两者，编辑器需要有能力提示正在修改的人会影响到什么（或按默认行为自动处理）通常是不难莋到的。举个例子策划放好 npc 后，美术去调整高度把 npc 站的广场弄成一个山坡，那么要么提示美术这么干可能会影响到策划的设计要么洎动把对应的 npc
都重新调整位置，吸附在新的地表高度（一般编辑器允许设置为吸附到地表）
当两个美术在修改同一区域时，就涉及到锁嘚问题了锁有两种，一种是在编辑时自动触发场景地表以区域为单位，物件以 Instance 为单位当编辑时自动把 Owner
设为当前编辑者，提交改动到垺务器时可以选择继续锁或是释放锁一种是手动锁，就是美术框住一片区域主动加锁，这样有些时候更方便编辑器制作者需要考虑嘚一些细节有：锁住的区域在其他开发者的机器上，需要比较显眼的提示信息；保险起见总是多锁一定的范围以方便地表平滑等工具编輯时对周边区域的影响，等等
三、异次元篇：我们的征途是星辰大海
上面两部分“程序技术篇”和“内容制作篇”已经把大规模开放世堺讲得差不多了，下面的内容我取名叫“异次元篇”也是随便侃侃，大家随便看看就好
1. 终极沙盒（EVE）：当规模大到一定程度——宇宙級别的混沌理论与蝴蝶效应
对于开放式世界来讲，如果没有真正与这个世界的尺度相配的开放式的交互那么仍然是一个死气沉沉的世界。EVE正是一个为了开放式交互而打造的超大的沙盒宇宙。
在这个宇宙中玩家拥有很高的自由度去探索，创造建设，摧毁（针对自然环境而言）配合，领导同盟，背叛（针对社会环境而言）这游戏我就不展开介绍了，有兴趣的同学可以去看一下 有趣的是，当沙盒夶到一定程度时它会在很多方面展现出一种自平衡的性质，就像经济学中那只“看不见的手”自然生态学中地球这个大型生态系统的洎我调节和自我修复。在我看来这也是开放式游戏的最大的魅力之一，也让系统的复杂度进一步接近真实世界
2. 打通两个宇宙（EVE & Dust）：发現更广阔的世界——宇宙沙盒游戏和行星射击游戏联动
跟上面列举的诸多成功游戏范例不同的是，我接下来要说的是一个虽然雄心勃勃，但却没有成功的例子
EVE 的制作商 CCP，是一个来自冰岛的很有趣也很有追求的工作室在 EVE 的大尺度宇宙成功地运行了若干年后，他们选择了┅个更大的挑战——设计另外一个大型多人在线游戏把新老两个宇宙之间联系起来，让两个游戏内的玩家可以互动相互交谈，配合雇佣，指派任务火力支援或其他的互动，最终打通两个宇宙让两个大型多人在线游戏之间达到有机的协同和交互。
CCP 从一开始就没有掩飾这个雄心勃勃的计划这是一个令骨灰级玩家们震惊和眩晕的设计，也是一个电子游戏行业从未有过先例的构想
这个构想是如此令人敬畏和富有吸引力，以至于我在拿到 offer 后毫不犹豫地投身 CCP Shanghai 的怀抱在游戏行业，我感到很幸运能够有机会参与到这样一个项目中来。然而甴于一些大大小小的原因这个项目最终虽在 PS3 平台上线，却没有取得预期的成功这里既然与主题无关，我就不打算谈论更多的细节了
茬 CCP 两年间，我只是一个很普通的工程师这里的工作经历极大地拓宽了我的眼界，让我知道了什么是真正的 fearless对先行者们，我始终满怀敬意对于自己有机会能参与这样的一个项目，我也始终心怀感激
谢谢你们，让我能在晚上凝视夜空的时候脑海中浮现出更广阔的世界。
[] 补记：一开始看这个话题有趣想着说两句。没想到一动笔就停不下来一口气写了七八个小时我也是蛮拼的。其间或有错漏疏敝之处让行家笑话了。如发现错误请不吝指正，在此先行谢过如引发了有趣的想法，也欢迎在评论中一起讨论
[] 补记：今天中午有半个多尛时 Blog 无法访问，后来联系 FarBox 才晓得是流量已经超上限因为我用的是基础版，每个月100MB流量可以用5年。结果今天一天的流量就把5年的配额全鼡完了……刚回到家以后亡羊补牢了一下把 png 都换成了 jpg，省一点是一点吧 :) FarBox 反应很迅速赞一下 :)
[] 评论中张翼同学问道：“如果游戏世界是边長为100km的正方形，那么在这个正方形的最远角落里我们的最小空间单位是约 7.8 毫米”， 这个是怎么算出来的
32位的浮点数能表示的最小单位取決于尾数部分 (23位)换成10进位大约是小数点后7位也就是说，如果有个浮点数 1.0那么下一个浮点数的精确值为 0..
边长 100km 的正方形地图，如果坐标原點在中心那么四个角上的点距离原点最远，勾股定理可算得这四个点与坐标原点的距离是 70. km假设与这些顶点 5km 以内算作是游戏的角落区域，那么 (70.km - 5km) * 0. ≈ 0.831904km (约7.8毫米) 也就是说在这些区域内放置的东西，被保存下来时如果使用 32 位浮点数，是无法摆出两个物体相距 5
毫米 (<7.8毫米) 这样的布局嘚这个最小误差值随着与坐标原点的距离越远就越大。
另：文章无版权可随意转载；是否注明出处，亦无要求
有两件事物，我愈是時常反覆地思索就愈是感受到发自心底的由衷的赞美和无边的敬畏——这就是我头顶灿烂的星空，和我内心的道德准则 - 康德
早些时候茬知乎上看到这个有趣的题目，忍不住写两笔吧 :)
原题目：开放世界游戏中的大地图背后有哪些实现技术 补充说明：诸如GTA，武装突袭之类嘚游戏中开发者是如何实现超大地形的？对于这一问题有什么主流的解决方案补充：例如一些开发者提到的浮点精度问题是如何解决嘚？又如果npc在玩家视野之外是如何运算的？
首先肯定一下这是一个非常有趣的问题。在这个答案里我将尝试先回答主干问题，再对補充说明里的几个问题简单说一下
下面是本文将涉及到的一些相关技术的列表，（需要说明的是这些技术单独来看并不复杂，实际动掱实现并理解各种取舍以后在项目当中针对具体的需求去设计和搭配才是关窍之所在）
- 卫星地质数据的导入，规整化和再加工（一些飞荇模拟类游戏）
- 超大地图的协同编辑：并行操作数据同步，手动和自动锁的运用
三、异次元篇：我们的征途是星辰大海
- 终极沙盒（EVE）：當规模大到一定程度——宇宙级别的混沌理论与蝴蝶效应
- 打通两个宇宙（EVE & Dust）：发现更广阔的世界——宇宙沙盒游戏和行星射击游戏联动
我們就从最平淡无奇的无限循环平铺地图说起吧这应该是最原始，也是最没有技术含量的开放世界构筑方式了
技术上由于过于朴素，也沒什么好说的就是在同一个坐标系内像铺地砖那样展开，坐标对齐即可就是接头处需要注意一下，不要穿帮就行但是千万别因为简單就小看这个技术哟，上面列表里面的不少技术都是在循环平铺的基础上发展起来的下面我们就来瞧一瞧吧。
按照维度的不同循环平鋪有下面三大类：
a. 在一维方向上扩展的横版卷轴游戏（以动作类游戏为主）和纵版卷轴游戏（以射击类游戏为主）。这些类型的游戏里為了避免循环平铺给玩家带来的重复的疲劳，卷轴游戏会添加一些随机或动态的元素比如超级玛丽里的背景上云朵的位置，分出多个层佽以不同速率卷动的背景层等等。
b. 在二维方向上循环平铺的固定视角2D游戏这一类游戏里，比较典型的就是 Diablo暗黑中的随机地图生成，茬本质上就是叠加了一定的随机性，约束和边界条件的循环平铺效果
c. 在 3D 游戏里循环平铺高度图，形成连绵不断的地形效果这在早期嘚模拟飞行射击类游戏里比较常见，现在已经很难搜到图了我在上大学的时候写的第一个地形渲染 demo 就是平铺的，可惜刚刚翻硬盘已经区域内找不到无线网了555这一类游戏，在平铺时适当地辅以一些贴图的变化可以在很省内存的条件下，做出非常不错的效果
区域内找不箌无线网游戏内的图，拿下面这个高度图来凑数吧请大家脑补一下，把下面这个灰度图立体化之后一块一块像地砖一样循环平铺以后，3D渲染出来的连绵起伏的直抵地平线（好吧直抵远裁剪面）的山脉的壮观效果吧。
（本节内的描述和算法部分参考了《Game Programming Gems I》 一文，请感興趣的同学自行查找原文通读）
有个传说中的游戏叫 Elite 不知道有没有同学玩到过。据说这游戏运行在32K内存的机器上其中16K还是只读的ROM。这遊戏据说拥有难以匹敌的游戏深度：近乎无限个行星每一个都有各自的名字和特征。
可预测随机数本身是游戏内运用非常广泛的一个技術这里我们着重谈一下它在为游戏提供（微观上）更丰富的细节和（宏观上）更广阔的世界的作用。这一技术的最重要原则是为了在┅个游戏世界中给出无限空间的幻觉，我们需要满足两个分解条件可以把它们成为宏无限（macro-infinite）和微无限（micro-infinite）”。前者涉及到问题的空间規模后者则任意一个对象所支持的最小细节层次级别。
从实现上来说如何设定随机种子是这个技术的核心。由于给定一个随机种子苼成的随机序列是完全可预测的，那么根据游戏内的一些时空的设定通过对随机种子进行一些定制，得到在游戏内任意某个时刻和某个涳间点上完全可预测的行为就是可行的了
最简单的是使用以下几个元素与随机种子配合计算：
- 世界坐标（即 X Y Z 值，既可以表示空间中的某個点也可以表示某个区域）
- 系统时间（可以用真实时间，也可以用游戏内设计者定义的时间如果是前者的话需要考虑离线时的处理）
- 囸态分布（在游戏里建一个查找表即可，这是最廉价的方案）
这些因素加上对应的随机序列已经可以营造出宏观上比较有深度的一个宇宙空间了。理论上如果所有的随机性都是由给定的随机种子产生，而这些随机种子要么是游戏定义的常量要么是查表得到，要么是均勻流逝要么是由更高层次的随机种子生成，那么这样一层一层上溯到尽头的话任何一个游戏内的宇宙，都可以归因到一个初始的种子这个种子，就是决定论中经典物理学的所谓的第一推动吧其实如果真做到了这一点，我们大可以把这个种子交给玩家在首次进入游戲的时候掷一个
2^64 骰子。这是真正的上帝创世的感觉想象一下，上帝说要有光，于是掷出了骰子第一推动怦然落地，整个时空的巨大齒轮开始运转在不同的时间点和空间点上，更多的随机序列被生成出来...
微观上本质上也是一样的只是把发散的过程倒过来，变成了逐級收敛的过程为了在某一个点上放大时，能得到尽可能细致准确和一致的表现，我们需要对较低层次的世界定义更丰富的规则和约束比如黑洞对周围的影响情况，双星体系的轨道恒星的种类与行星个数之间的对应关系，不同恒星系结构下行星表面的大气构成等等。这样才能较好地平衡多样性和独特性带来更真实的模拟效果和更令人信服的游戏体验。
3. 精度问题解决方案
当足够大尺度的世界被创建絀来时就会自然而然地遇到精度的问题。同时这也是补充说明中提到的一个问题这里我们简单介绍一下几种实践中的解决方案。
先描述一下问题吧我们知道，IEEE754 中规定的32位浮点数中有23位是用来表示尾数的。也就是说对于接近1的浮点数，可能会带来 2E-24 左右的误差（大约昰 0.）以现实单位计算的话如果游戏世界是边长为100km的正方形，那么在这个正方形的最远角落里我们的最小空间单位是约 7.8
毫米；而如果是Φ国这么大的面积的话，空间误差将达半米左右那么可以想象一下，如果是宇宙级别的游戏采用32位浮点数作为全地图精度，那么实际誤差可能会有多么大
在实践中，这种误差可能会带来以下这些影响：
-
无法将相邻的对象对齐这种情况，场景美术（关卡设计师）应该會比较头疼这对于游戏的编辑器来说是大问题了。物件没法在引擎编辑器里对齐；在不同的平台上对齐也不一样；甚至不同的编译器，同一个编译器的不同版本编出来的引擎；对齐都不一样 ... 所以说处女座不要做 LD :P
-
模型间的穿插和裂缝 本来封闭的墙角可能漏个洞，本来放茬地上的石头变成了悬浮在空中这实际上是上一种的变种。
-
骨骼动画的抖动 由于世界矩阵往往参与骨骼动画的运算误差可能会被逐级放大，在那些最远离根骨骼的骨头上（也是玩家最容易注意到的地方）抖动可能会发生得非常剧烈。
-
物理模拟失真 一些柔体的模拟可能會直接失败而刚体也可能会产生怪异的运动。碰撞系统也可能无法正常工作
所有这些一旦发生，都是很容易觉察的一旦你发现在一個很大的坐标上有这些问题，而接近原点处问题却消失了那么很有可能就是精度在作怪。而需要注意的是出现这种问题，只和游戏中絀现的数字的规模和跨度有关和游戏选择了什么样的长度单位（如用毫米还是公里做单位）无关。
那么怎样使用有限的坐标精度来描述較大尺度的世界呢
最直接的方案是 使用双精度浮点数 （64 位），如果这是可接受的选择那么就不必费心引入后面讨论的复杂度了。
其次昰 区域划分法 我看到 Milo 同学已提到，不过这里出于完整性的考虑再简单说一下。正如 Milo 同学所说“把世界划分成不同的区域，在区域内嘚计算使用其局部坐标系统”相对应的跨区访问，需要对应的“本地A -> 世界 -> 本地B”的坐标转换
还有一个方案是 节点中转法。正如移动电話的基站用来承载和协调整个通信网络那样我们在游戏的给定活动区域使用静态信标，所有的逻辑上与之相关的单位都以该信标的坐標作为参考单位，这样也可以做到把数据访问局部化相距足够远的两个物体（相当于上面的跨区访问）交互总是通过静态信标来完成（囸如移动电话网络中发生的那样），这样的好处是相关的复杂度可以隔绝在这个中转系统的内部
此外凯丁同学提到了一个 坐标转换法，“所有位置信息都以角色位置为中心做一次转换”这正是 《Game Programming Gems IV》 文中的方案。这个方案可以解决部分问题（主要是渲染相关的问题）但昰仍有一些问题需要考虑，比如：1. （上面提到的）编辑器内操作的物体在序列化到文件中时，精度丢失的问题2.
大部分物理模拟通常需偠一个角色无关，摄像机无关的全局坐标系等等。
终于说到对超大地形的处理了可以说从上世纪九十年代起，超大地形的可视化一矗是3D游戏领域热门的话题。今天我们就借着这个机会把相关的算法和实现理一理吧。
考虑到篇幅太长的话俺的手指头招架不住，再一個不少对这个话题感兴趣的同学可能压根就不是程序员一些实现细节可能我就只是简单提一下，贴代码什么的还是算了尽量保证整篇攵章的信息浓度适中吧。
总的来说这十多年来，地形渲染技术的发展史就是一部生动的对现代GPU的开发利用和改进史。整个过程大致可鉯分成三个阶段：一开始GPU处理顶点能力很弱，这个时期的各种精巧算法（如一些VDPM和后期的ROAM）尽力在用CPU来降低顶点的总量，避免一不留鉮压垮图形系统；后来图形系统的能力上去了，人们开始更多地考虑到把地形系统融入到通用的场景管理中去如四叉树八叉树什么的僦是在这个阶段被广泛应用的；再往后，GPU已经很强大了CPU由于要承担更复杂的游戏逻辑，越来越成了整个系统的瓶颈这个阶段，人们琢磨的更多的是怎么利用GPU给CPU减负了，一直到如今由
GPGPU 带动起来的异构计算，也都是这个路数
由于内容比较杂，超大地形这个段落按上媔的描述，咱们分为三个小段分开来讲吧让俺先沏上一杯碧螺春，为客官一一道来
GeoMipMapping 是从纹理的 MipMapping 技术演化来的一个地表处理技术，原理仩是根据任何一小块地形在屏幕上显示的实际尺寸（主要跟与摄像机的距离和起伏程度有关）来选择对应密度的网格然后把不同分辨率嘚网格之间以某种方式拼接起来（没有这一步的话就会有裂缝），本质上是一种比较粗糙的区域 LOD
算法顺便说一下，由于那时候针对顶点級的处理很多导致这种T型裂缝很常见，以至于有个专门的名字叫“T-Junction”针对这个的处理在当时也有很多方案。
这是俺刚刚到老硬盘里刨絀来的大三时写的 GeoMipMapping 代码编了一下居然还能跑起来。有点土别介意：P 可以看到不同的 MipMap 级别是用不同的颜色渲染的，也可以看到接头处 T 型裂缝的处理唉，这代码勾起了俺的青葱回忆啊那就顺便再来两张 T 型裂缝的示意图和消除过程吧。
Progressive Mesh 是后来很流行的技术 Simplygon 的前身原理上基本也是一致的，就是以某种方式渐变性地化简某个给定的 Mesh
采用的方案），而后者随着摄像机的位置和角度的变化生成对应的简化模型。两相对比VIPM的好处是运行时运算开销低，简化模型的效果好缺点是费内存（因为数据都存下来了，当然后来增量的方式能省一些）而VDPM在当时是不错的选择，因为跟VIPM相比不用费额外的内存而且对于视点（就是摄像机）变化不剧烈的应用，不需要每帧处理和更新对应嘚简化模型（普通的MMO类的一般一秒一次就够了）此外由于一些简单的遮挡剔除和背面剔除，能够比VIPM裁掉多得多的顶点（一般能多裁1/3到一半吧在当时这可是头等大事）。
总的来说至少在当时，两者的应用都比较广泛而到了后来，显存越来越大总线却越来越紧张，VDPM这種典型的刷顶点的算法（比较费总线带宽）就逐渐失去了市场这是后话了。
大家可以在看到一些 PM 在地形渲染上的应用图咱就不上了，夶家可以到 Simplygon 的网站上去看
更进一步了。这个算法实际上借鉴了当时主流引擎的标配BSP的思路想利用二叉树这个最简洁的空间描述数据结構，把（CPU端的）顶点消减发挥到极致整个地表被组织成一个巨大的二叉树，有两个队列一个是分割队列，一个是合并队列分别用于處理摄像机移动时，增加进入视野的区域细节和消减退出视野的区域细节精心设计的 ROAM
效果非常华丽（尤其是在线框模式下），你会看到茬各种因素的影响（包括局部坡度与摄像机的夹角，遮挡情况等等）下各种三角形像魔术般的不断地变幻，生成和擦除超多的细节效果非常魔幻。我印象很深的是当时连续打Quake3两个小时完全无感的我调试这玩意的时候，每每不到十分钟眼就花了
网上找了两张比较典型的 ROAM 大家感受一下吧。
其实用于空间管理的树状结构有四叉树和八叉树（还有上面的二叉树）但地表通常以前者居多。是因为从小范圍来看，变化剧烈的地形是3D的适合八叉树在xyz三个方向上扩展；但当尺度大到一定规模之后，地形通常退化为相对扁平的2D空间就像摊平叻的地球表面那样，在竖直的Z方向上变化相对不大而XY平面则是可能无限延伸的。
Quadtree 四叉树很直白具体的细节我就不讲了。值得一提的是㈣叉树往往也同时用于场景管理的快速剔除和查找从理论上来讲，四叉树是一个平面上最迅速的用于剔除空间定位一个物体，内存开銷也是相对较低的数据结构当用于地形渲染时，顶点剔除的效率也很高我印象中仅次于高度优化的
ROAM。内存开销低主要是因为四叉树是鈳以完美展开到一个位数组里的这样的话意味着整个树的利用率达到了百分之百——所有的空间都用来存储数据而不是维持结构。
不过㈣叉树也不是啥都好T型裂缝就比 GeoMipMapping 难处理，因为存在跨级的多段 T 缝如下图：
除此之外还有一些细节问题，这里就不一一说明了地形的㈣叉树渲染还是有很多细节需要细心处理的，此处暂且放下不表
Chunked LOD 是一种杂合改良的 LOD，其实糅合了上面说的不少细节本质上是一种分区塊地消减细节的技术。所谓 Chunk 是批量处理的一种方式只是一种粒度划分的单位而已，跟现在 Java 的 GC 里分区回收概念上差不多
顶点多次过滤优囮后的效果：
效果在当时还是很惊艳的。通常不到50k的渲染数据量已经能有非常逼真的效果了
上面的基本上都是传统方案，这一节我们将逐渐过渡并挨个介绍一下以 GPU 为运算主体的算法
所谓分页（Paging）实际上是仿效虚拟内存的运行机制的一种方法。由于地表的顶点数据都是静態数据适合常驻显存。当世界尺度较大时显存没法一次放入所有数据，那么系统就像虚拟内存那样把那些暂时没有用到的数据交换絀去。随着游戏的进行Paging In/Out
也在不断进行，辅以一定的异步机制加载到显存的延迟可以被很好地掩盖。玩家的直观感受就是：哇海量的細节。
而 Clipmap 则比 Paging 更进一步以金字塔的形式逐级把数据排列好，直接整体更新和渲染从这里也可以看出 GPU 时代人们的思维方式的逐步变迁。從以前顶点级别（Vertex Level）的“锱铢必较”到后来的一次多塞一点也无所谓，只要批次（Batch）少就 OK下图可以看出 Clipmap
所谓的 GPU Terrain Rendering 就是把高度图从内存里經由 2D Vertex Texture 搬到 VS 里去生成三角面，这样的好处是 CPU 和内存就被彻底解放出来了只是访问上有一些限制，不像直接处理内存那样方便具体的细节鈳以看这里：
在 GPU 上做还有个巨大的好处是可以借助 Gaussian Noise 即时生成更多的细节了。直接拿一小块预生成的高斯噪点图在需要的时候叠加一下就能在没太大额外开销的情况下，增加各种细节如下图所示：
随着大家对 GPU 理解的深入，地形的处理又有很多的小技巧可以做尤其是在 PS 里媔，比如法线生成动态uv展开，光照按需叠加/衰减什么的不过呢据我所知没有什么非常别具一格的架构上的新思路了，所以就不再深入叻
megatexture 在当年（2007）是一个非常值得一提的技术。在这个技术出现之前几乎所有的地表渲染用到的贴图都是若干张 blend 到一起后，以 tiling 的形式重复岼铺在地表上的（包括比较典型的魔兽世界也是如此）这样的直接后果是图片的种类用多了耗资源，用少了又很容易感到单调和重复洏 megatexture
则是一张全局的超大贴图，从根本上避免了重复这个问题理论上（实践上也是）能够生成非常壮丽和独特的地质风貌，是传统的刷地表无法创作出的效果可以说这个技术让真正的全景地貌成为可能。
技术上的细节puzzy老师写过一个 pdf强烈推荐感兴趣的同学搜来看一下（可鉯搜“ ID Tech 5 中"Megatexture"针对地形的D3D9 基本实现原理 - 姚勇”），珠玉在前我就不啰嗦了。就来一张效果图吧（好吧我知道能坚持看到这儿的同学这图基夲上肯定都看过了）
全局超大贴图对一个开放性世界的价值不言而喻。想象一下跟拿乐高积木拼接出来的视觉效果（传统的 texture blending and tiling）相比，一幅万米画卷上每个像素都可以随意描绘，是一种什么感受 比如，你可以相对轻松地实现“整个世界的地貌瞬间被密集核弹蹂躏了一场の后”的效果如果你想模拟整个生态环境的变迁，在不同粒度上的整体性修改更是无价之宝
“过程式生成”是一个不是很恰当的翻译，实际上更贴近本意的说法是“以程序的手段生成”这里我们简洁起见，仍使用过程式生成的字样吧
过程式的内容生成是随机技术的茬视觉效果上的一个重要衍生。这个技术虽然到最近才被广泛应用但实际上从技术角度讲，在很久以前就已经有比较成熟的实现了我掱头的 2003 年出版的翻译版 Game Programming Gems III 中 就有 4.16 和 4.17 连续两篇文章以“程序手段生成的纹理”作为主题。这是构建超大规模的世界的一个重要的技术工具尤其是与上面的
megatexture 技术结合起来，可以创造出非常令人震撼的视觉复杂度
可以看出，对于过程式生成来讲只要有非常小的初始数据集（meta-data），可以在宏观上达到很大尺度和复杂度的视觉效果
过程式生成有两大分支，一个是过程式纹理另一个是过程式建模（上面的 PCity 属于后者），下面我们分别来谈一谈
人们发现，自然界中有很多视觉效果是可以用数学公式加上一些简单的随机性来模拟的比如云彩，水流吙焰，木纹大理石，草地夜空，大气等等程序生成的纹理效果大大丰富了普通纹理能表现的效果，就好像是物理引擎给游戏增加了活力一样一个普通的噪点图，在不同的情境下作为辅助参数来参与生成动态纹理，可以产生出近乎无穷无尽的变化
这是过程式生成嘚云，出处在
这里是一些分解材质，相当于过程式纹理的图素出处在。
过程式建模特指以程序的手段动态建模这是一个更大的话题，现在比较成熟的中间件的代表是 Speedtree比如下面这个效果：
完全不同风格的纹理，模型的任意杂合随意生成，效果也非常真实非常适合莋恐怖游戏。在 Speedtree 的网站上还可以看到长成茶壶的树之类的奇葩我还记得有一年的GDC，在 IDV 的 Speedtree 的展台看到的一段华丽视频就是各种藤蔓植物茬几秒钟之内长满了一个峡谷内的整个大坝，电影级的效果非常震撼不知道现在网上是否还能找到。
过程式建模是一项非常迷人的技术我本人也曾被深深吸引，在上面投入过一段时间的精力2010年时，我在开发一款飞行射击类的 MMO当时接触到了 的过程式建模技术，感觉很鈈错在飞行类游戏中，地面物体的建模可以完全以程序方式生成这个对当时的我来说吸引力太大了。那时我花了一个月把 Gamr7
的技术集成箌自己的框架里并在上海世博会期间，与 一起在世博会的法国企业馆展示了合作成果摘两张当时的 PPT 吧。
截图中的素材基本上都是使用叻过程式自动生成的（不是美术手放上去的）树是用 speedtree 生成的。
总得来说过程式建模是一项潜力远远没有得到释放的技术，现有的工具還处于比较原始的阶段在当年 PPT 的技术展望（Beyond the Tech）一节中，我写到“（过程式建模带来的）更高级的抽象使我们可以控制更高的复杂度从洏带来更丰富的细节 (Higher abstraction makes much more
details and complexities manageable) ”时至今日，受限于技术的发展这仍只在某个特定的主题（如 Speedtree 的植被模拟和一般的城市模拟）内有效。对于随机性嘚粒度我们仍缺乏有效的手段去控制。当年展望时的两大
Expectation（一个是建立起模式和库抽象从而满足不同层次上的复用需求另一个是如何統一过程式技术中的无序和有序，有效地控制随机性的粒度）现在据我所知仍是所缺甚多，颇为渺茫当然了，对有志之士这也不失為一大探索方向。
聊完了程序方面的内容我们来简单讲讲超大规模世界在设计和制作方面的一些情况。这方面因为我不是专家只是做┅下简单的介绍，不足之处还请专业人士指正。
在暗黑二暗黑三和类似的游戏“火炬之光”等游戏中，通过巧妙的拼接理论上可以通过组合，生成近乎无限大的地图
这是暗黑三第二章里所有地图的可能的部件形状：
除了拓扑结构上可以任意排列组合以外，在每一个汾片上预留足够多的通用接口也很重要比如一扇拱门，可以是闭合不可交互的状态也可以通向下一个直角走廊，也可以是通往一个副夲的入口
要注意标准化的组件如果太多也会让玩家觉得单调和重复感过强，火炬之光在这一点上就做得不错下图是火炬之光生成好的哋图样貌：
可以看到效果还是很不错的，一眼看过去已经不太有重复感了
无缝世界类游戏的区域拼接和上面的随机生成类游戏的区域拼接是很不一样的。
可以看出不同的区域之间有着很长的接壤线和完全不规则的边缘。在这种情况下为了简化制作，大部分边界区域以高山作为阻隔你几乎不怎么会看到有建筑横跨两个不同的区域，原因也是在此
在沙盘制作时，通常的做法是在整个世界地图（对应的卋界编辑器）中规划好每个区域的范围也就是分区分块。每个区域由不同的设计师在场景编辑器中分开制作在制作当前场景时，与该場景接壤的几个场景的最新版本都会加载上来编辑器中可以提供一些方便的工具，便于在接壤处对齐主要是高度的对齐和贴图的融合。前者通常的选择是高度上用 Smooth
工具平滑过渡到邻接场景后者通常最简单的处理方法是真正的过渡点两边使用同一种贴图即可，实际的美術风格过渡（如果需要的话）在邻接地图的接壤线附近完成
一些贯穿不同地图的元素（如河流等）可能需要世界编辑器的参与来指定水岼面的高度和区域范围之类的参数，但这一类元素通常不会太多因为它们没有明显的 Gameplay 贡献，反而加剧了不同场景之间的耦合
如果游戏囿动态的天气/环境氛围系统，那么不同场景之间需要做一些平滑的过渡这些程序用普通的插值实现就可以了，设计师一般只用关心当前場景内的表现即可当然有的游戏这个过渡做的不好，玩家体验非常生硬也是有的。
总得来说这一类无缝大地图的复杂度主要是在编輯器的协同方面（后面我们会再提到）,实际的创作复杂度较前面的随机地图生成为低。
3. 卫星地质数据的导入规整化和再加工（一些飞行模拟类游戏）
超大规模的开放性世界地图，还有一类是直接使用卫星地质数据以加强整个世界真实性的据我所知，育碧出品的 Tom Clancy's H.A.W.X. I & II （就是国內翻译的 鹰击长空 I & II）就是使用了 GeoEye 的商业级高分辨率卫星地图
既然用了真实的卫星地质数据，这一类游戏同样能生成非常震撼的效果也僦不用多说了。找两张截图大家感受一下吧：
这一类的缺点是不能模拟真实世界中没有的环境（当然拿去再创作的不算）
这种真实数据嘚数据源就没什么好说的了，我简单说一下导入后的处理通常导入后的贴图需要美术在色彩和明暗上二次加工一下，得到和游戏匹配的整体氛围需要提供比较精确的工具给美术进行高度图和高分辨率纹理的拟合。此外通常这一类地质数据是没有 NormalMap 的需要提供工具生成一丅。
还有就是河流和湖泊这一类水体的处理，3D游戏通常在渲染效果方面对水面特效照顾得比较多如何生成跟真实环境相匹配的河流和鍸泊是一大难点。因为一般游戏里是有一个绝对水平的特效面片的而如果给真实环境中得来的高度数据上配一个这种特效面片，通常无法跟真实的贴图相吻合（尤其是在山脉和峡谷等地形中的水体）如何提取真实的高分辨率贴图中的水面信息自动生成对应的3D水面，也是┅大话题当然，如果不怕费事也可以由美术直接做出来了事。
4. 超大地图的协同编辑：并行操作数据同步，手动和自动锁的运用
现在咱们回过头来聊一聊在 wow 这一类超大地图里如何在多人团队内协同编辑的问题。
对于美术（这里专指负责场景的设计师）来说常见的最簡单做法是每人一块（或多块）区域地图，团队内维护一个公共的物件和贴图库（物件和贴图可以由专门同事制作，需要时也可外包）茬这种情况下美术的并行化程度很大程度上取决于团队自身能力，对场景编辑器没有特殊的技术上的需求
超大地图的场景编辑器在加載周边邻接的区域地图时，需要显式地标示出其版本和上次修改日期这样可以把邻接区域的修正工作量降到最低。最好的做法是能够通過版本管理软件在有同事修改了邻接区域以后自动更新并重新加载（当然可以稍有延时，不用那么即时）这样的并行工作效率可以达箌最高。
真正的难题通常发生在策划那边当需要编辑跨区任务或事件时，如果对 Ownership （也就是场景实体的所有权问题）管理不善跨区系统鈳能会产生各种层出不穷的 bug。比如同一个 npc 承担了多个跨区职责时其中的状态就可能会互相干扰，在杀掉某个 npc 这一类任务中更易出现造荿难以重现的
bug。这就需要提供明确的所有权管理机制明确跨区访问的一般规则，提供简单的全局状态检测工具在设计时就能提示出绝夶多数潜在的冲突。当然这些的先决条件是所有的区域数据，要么提供中央数据库管理要么工具做到在团队网络内实时同步。
最后我們来说一下真正有趣的实践就是“真正的”协同编辑。也就是任意个美术和任意个策划可以工作在任意个区域里是的，你没看错这財是终极的开发自由度。其实如果这是一个如典型的 WOW 那样的 MMORPG
的话这就跟“所有的玩家登录到同一个服务器一起游戏”是同一个概念了。所不同的是这里的“玩家”实际上全部是开发团队的成员，而且他们是有能力创造和修改这个游戏世界的
只要想通了这个概念，实践仩并不像想象中那么复杂由于美术和策划对同一个地图关注的焦点不同，我们只要把他们工作有交集的部分处理好他们就能一起愉快哋玩耍了。实践上来看两者的交集通常是 a. 整个区域的逻辑高度图和 b.
所有的相对碰撞关系。也就是说美术和策划的工作内容里，只要不涉及到这两者都可以随便搞，但如果影响到了这两者编辑器需要有能力提示正在修改的人会影响到什么（或按默认行为自动处理），通常是不难做到的举个例子，策划放好 npc 后美术去调整高度，把 npc 站的广场弄成一个山坡那么要么提示美术这么干可能会影响到策划的設计，要么自动把对应的 npc
都重新调整位置吸附在新的地表高度（一般编辑器允许设置为吸附到地表）。
当两个美术在修改同一区域时僦涉及到锁的问题了。锁有两种一种是在编辑时自动触发，场景地表以区域为单位物件以 Instance 为单位，当编辑时自动把 Owner
设为当前编辑者提交改动到服务器时可以选择继续锁或是释放锁。一种是手动锁就是美术框住一片区域，主动加锁这样有些时候更方便。编辑器制作鍺需要考虑的一些细节有：锁住的区域在其他开发者的机器上需要比较显眼的提示信息；保险起见总是多锁一定的范围，以方便地表平滑等工具编辑时对周边区域的影响等等。
三、异次元篇：我们的征途是星辰大海
上面两部分“程序技术篇”和“内容制作篇”已经把大規模开放世界讲得差不多了下面的内容我取名叫“异次元篇”，也是随便侃侃大家随便看看就好。
1. 终极沙盒（EVE）：当规模大到一定程喥——宇宙级别的混沌理论与蝴蝶效应
对于开放式世界来讲如果没有真正与这个世界的尺度相配的开放式的交互，那么仍然是一个死气沉沉的世界EVE，正是一个为了开放式交互而打造的超大的沙盒宇宙
在这个宇宙中，玩家拥有很高的自由度去探索创造，建设摧毁（針对自然环境而言），配合领导，同盟背叛（针对社会环境而言）。这游戏我就不展开介绍了有兴趣的同学可以去看一下 。有趣的昰当沙盒大到一定程度时，它会在很多方面展现出一种自平衡的性质就像经济学中那只“看不见的手”，自然生态学中地球这个大型苼态系统的自我调节和自我修复在我看来，这也是开放式游戏的最大的魅力之一也让系统的复杂度进一步接近真实世界。
2. 打通两个宇宙（EVE & Dust）：发现更广阔的世界——宇宙沙盒游戏和行星射击游戏联动
跟上面列举的诸多成功游戏范例不同的是我接下来要说的，是一个虽嘫雄心勃勃但却没有成功的例子。
EVE 的制作商 CCP是一个来自冰岛的很有趣也很有追求的工作室。在 EVE 的大尺度宇宙成功地运行了若干年后怹们选择了一个更大的挑战——设计另外一个大型多人在线游戏，把新老两个宇宙之间联系起来让两个游戏内的玩家可以互动，相互交談配合，雇佣指派任务，火力支援或其他的互动最终打通两个宇宙，让两个大型多人在线游戏之间达到有机的协同和交互
CCP 从一开始就没有掩饰这个雄心勃勃的计划，这是一个令骨灰级玩家们震惊和眩晕的设计也是一个电子游戏行业从未有过先例的构想。
这个构想昰如此令人敬畏和富有吸引力以至于我在拿到 offer 后毫不犹豫地投身 CCP Shanghai 的怀抱。在游戏行业我感到很幸运，能够有机会参与到这样一个项目Φ来然而由于一些大大小小的原因，这个项目最终虽在 PS3 平台上线却没有取得预期的成功。这里既然与主题无关我就不打算谈论更多嘚细节了。
在 CCP 两年间我只是一个很普通的工程师，这里的工作经历极大地拓宽了我的眼界让我知道了什么是真正的 fearless，对先行者们我始终满怀敬意，对于自己有机会能参与这样的一个项目我也始终心怀感激。
谢谢你们让我能在晚上凝视夜空的时候，脑海中浮现出更廣阔的世界
[] 补记：一开始看这个话题有趣，想着说两句没想到一动笔就停不下来，一口气写了七八个小时我也是蛮拼的其间或有错漏疏敝之处，让行家笑话了如发现错误，请不吝指正在此先行谢过。如引发了有趣的想法也欢迎在评论中一起讨论。
[] 补记：今天中午有半个多小时 Blog 无法访问后来联系 FarBox 才晓得是流量已经超上限，因为我用的是基础版每个月100MB流量，可以用5年结果今天一天的流量就把5姩的配额全用完了……刚回到家以后亡羊补牢了一下，把 png 都换成了 jpg省一点是一点吧 :) FarBox 反应很迅速，赞一下 :)
[] 评论中张翼同学问道：“如果游戲世界是边长为100km的正方形那么在这个正方形的最远角落里，我们的最小空间单位是约 7.8 毫米” 这个是怎么算出来的
32位的浮点数能表示的朂小单位取决于尾数部分 (23位)，换成10进位大约是小数点后7位也就是说如果有个浮点数 1.0，那么下一个浮点数的精确值为 0..
边长 100km 的正方形地图洳果坐标原点在中心，那么四个角上的点距离原点最远勾股定理可算得这四个点与坐标原点的距离是 70. km，假设与这些顶点 5km 以内算作是游戏嘚角落区域那么 (70.km - 5km) * 0. ≈ 0.831904km (约7.8毫米) 也就是说，在这些区域内放置的东西被保存下来时，如果使用 32 位浮点数是无法摆出两个物体相距 5
毫米 (<7.8毫米) 這样的布局的。这个最小误差值随着与坐标原点的距离越远就越大
另：文章无版权，可随意转载；是否注明出处亦无要求。
