大地形数据加载方法

大地形加载思考到现有的内存机制，不也许一次性将其加入到内存中，这个难题是显而易见的，其实在游戏开发中经常遇到，比如大家常见的进度条，加载进度条的目的就是等待程序加载场景，进度条只一个蒙板遮罩而已。大地形的加载，别无他法，只能用分块，这个是大路线，因此作为程序来说，要做的事务是怎样分块？块的大致是几许？这些具体的难题大家要根据需求划分，比如飞行模拟器块大致也许就要大一些，由于俯瞰的视角相对大，场景漫游块可以小一些等等，下面大家就以游戏的典范之作——魔兽全球地形加载方法为例给读者先说明一下它的实现原理，魔兽全球这款游戏实现的就是无缝地图的拼接，因此特别具有参考价格，先看下图所示：

魔兽全球是怎样实现无限地图的？其实它也是很多的场景块拼接而成的，大家通过编辑器解析魔兽全球的地形块的大致划分，魔兽全球场景大家称为MapWorld是由一系列MapTile组成，这些MapTile的大致是1600/3≈ 533.33m，而每个MapTile又是由 16x16个MapChunk组成，由此可以计算出每个MapChunk≈33.33m。再就是每个MapChunk又由9x9＋8x8个地形顶点高度，法线，若干贴图层（一般为4层）组成的地表纹理。魔兽全球地形的大致，在这里大家就不讨论了，但它划分块的想法大家是可以借鉴的。

继续解析魔兽全球的分块方式：它们是根据矩阵的方法进行划分的，在XZ平面上进行的，每个块都会包含一定的信息数据的，比如：在XZ（3，3）位置的MapTile，每个MapTile都包含了该tile内运用的贴图、模型实例等等。所谓模型实例也就是大家的道具，可以领会成相同模型在tile内不同摆放位置、大致、角度的信息，它们都是被保存在二进制文件中的，为了节省文件尺寸，玩法实例是通过index模型方法保存的，同顶点索引类似，在每个MapTile里面还有贴图信息比如贴图的名字和UV信息等等。本篇课程的分块思考方法跟魔兽全球的类似，会在后面的章节中详细说明，块分好了以后，下面就是实现原理了。

实现原理：在任什么时候刻，程序总是保存着玩家所在的及其周围的3x3个MapTile，随着玩家的移动，这些MapTile会被动态更新，新的MapTile被加载以替换被卸载的旧MapTile。为了进步调度效率，魔兽引入了Cache机制，Cache中保存着最多16个MapTile数据。需要加载新的MapTile时，首先会在Cache中查找；卸载的旧MapTile也不会被立刻删除，而是保存在Cache中以备再次调用。由于一段时刻内玩家的活动主题范围通常不会有太大变化，这一Cache策略在应用中表现的特别出色，这是无缝地图的基本原理。地形的动态加载卸载大家会运用多线程去实现，大家会整两个线程：壹个线程专门用于加载地形，另壹个线程专门用于卸载或隐藏地形MapTile。让大家再来回忆一下游戏的典范之作，游戏场景效果如下所示：

本篇课程实现的方式可以运用两种方法处理块的加载显示难题，一种是利用对象池的方法，预先加载分块地形，根据视距进行检测判断显示那些地块以及隐藏那些地块，在这里并不删掉它们。这样只需要壹个线程就可以。另一种方法是利用多线程，起壹个线程专门用于移除卸载不在视线范围内的地块，这样可以提高效率，下面说明运用多线程的加载方法。

多线程实现大地形加载方法

多线程在PC端游戏中运用的相对多，比如可以起壹个线程专门进行资源的加载，游戏服务器中同样也会有多线程的运用，下面给读者说明多线程实现方法，多线程处理难题就是把全部的加载逻辑放到了新的进程中，和主线程做一些进程间的通信，接受主线程的加载提议，做按需加载，也会自主做一些提前预加载，放进分配的内存，就跟魔兽全球的处理方法一样，通过进程间的内存共享机制，把加载的地形数据，共享给主进程运用。主游戏进程，永远只要维护壹个很小的内存即可，大量的内存数据，都在另壹个进程中处理。这样就可以优化大地形块的加载，实现方法如下所示：

首先主线程会先加载九块地形，主线程只负责维护这九块地形，无论人物如何移动，人物所在的整个区域永远是九块地形，如上图所示的，这九块可以直接运用主线程加载到内存中，剩下的16块大家通过另壹个线程将其放到缓存中，人物的位置是在已经加载好的九块地形中间，也就是在A所在的位置。随着人物的移动，会有新的地形块加入进来，同时现有的地形块会被置换出去，这样一直显示九块地形，被置换的地形并不会马上卸载掉，会根据人物移动情况做预判，它会等主线程通知，按照一定的制度进行卸载地块和加载地块。其实这种实现方法就是大家通常所说的双缓存-多线程技术。实现的效果如下所示：

地形分块加载完事了后，下面就要思考地形上面的纹理贴图难题了，地形的贴图资源也会占用大的内存，下面说明怎样加载海量贴图数据。

大地形海量图片的加载方法

大地形中的场景图片特别多，地形中的贴图至少会有四层，这么多贴图大家在加载时需要思考的，大家分块时也需要思考这些影响，另外场景中运用的LightMap烘培也是要思考的难题，为了缓解内存压力，大家事先会将不同块中的地形材质以及建筑物材质进行打包，先说明怎样分块加载场景贴图？它实现方法如下所示：

该思路就是将场景中的贴图根据大家划分的块打成不同的图集，当然也可以将两个块中的贴图打成壹个图集，图集大致对于PC端来说，最大是4096，在移动端最大是2048。这个也是为了避免内存频繁的加载卸载会导致很多内存碎片，不利于后面大内存的分配。在打图集之前大家需要做点事务就是需要将地形块中的纹理贴图和大家的打包图集之间建立一一对应关系，方便对号入座。由于大家打包的图集跟实际地形之间不会有任何关系，要确立二者之间的对应关系大家需要在它们中间再整一张索引文件表格，它是连接图集和实际地形纹理的桥梁，通过大家建的索引文件，大家可以找到实际地形中纹理和图集纹理之间的对应关系，大家建的索引表格是要加载到内存中的，而大家的图集是根据加载任务后期才加到内存中的，这就标准大家的索引文件尽也许的少，由于它们是常驻内存的，除了海量图片的加载，大家还需要处理密集建筑的加载。

-密集建筑的加载方法

密集的建筑加载，大家试想一下，如果把场景中全部的建筑一次性加载到内存中，内存瞬间就会占满，帧数瞬间下降，这也是何故大家在游戏场景中移动时，遇到密集的建筑就会卡顿一下的缘故。以前处理方法是运用LOD处理，被遮挡的物体运用简模，这样也会加大内存的负载效果，如果人物一直在建筑物之间来回穿梭，这样不同LOD模型就需要来回切换，对内存也一个负担，效果不理想。这些难题对于程序员面来说必须化解的难题，怎样化解呢？很多人想到了合并大Mesh，这种方式行不通的，大网格并不适合做裁剪操作，试想一下，大家合并的网格，如果摄像机只看其一小部分，由于它们一个整体这样就需要把他们一起加载到内存中，而实际上大家并不需要这么多模型数据，在合并网格时，在这里也给读者壹个提议，尽量把靠的很近的模型进行合并，避免上述难题发生。其实最有效化解方法还是划分块，这个划分块可以利用地形划分的想法进行，它是和地形块紧密相关的，每个地形块中的建筑物跟随地形块一起加载。如果块中的建筑特别密集，这种方式还不能够完全化解，还需要进一步的处理，就是要加入OC遮挡算法结合LOD算法，这样就可以完全化解大家当前的难题了，这也是本篇课程

要讲解的方式，再进一步的优化方式是可以将OC遮挡算法和LOD算法放到GPU中计算，这样效率还会提高，在Siggraph2024发表了一篇文章GPU-Driven Rendering Pipelines，它的想法就是运用GPU进行遮挡裁剪处理，主要分两个阶段，运用的是DX12图形API，如下图所示：

它的想法就是第一步先做壹个初略的遮挡裁剪列表，而后在此基础上再根据视线距离或者射线检测做进一步的细化裁剪操作，这个想法跟大家的碰撞检测算法类似，引擎中碰撞检测算法也是基于这个原理实现的，给读者说明一下：实际可用的碰撞检测算法，一般要分2个阶段：

第一阶段，broad phase快速找出潜在的碰撞物体对列表，不在这个列表里的是完全没也许碰撞的。broad phase确定了一批需要进一步检查的物体对。

第二阶段，narrow phase准确找出发生碰撞的物体对列表。由于上壹个阶段的部分物体对实际上是没有碰撞的，需要在这个阶段剔除。

broad phase其中有壹个简单算法叫sweep and prune(SAP)，本质上是利用了排序算法。第一步是初始化排序列表，列表中的元素是包围盒，可以用任意排序算法完成，例如快排；之后的排序就不是用快排了，而是用冒泡排序，何故用冒泡排序更好呢？是由于壹个默认的前提：物体的运动有时刻相关性（temporal coherence），即当前帧和下一帧的位置是相近的，因此在冒泡排序经过中，发生的位置交换预期都很靠近。

其实算法中有很多类似的地方，这里大家也要互相借鉴它们化解难题的想法用于化解大家的难题。笔者以前做的是端游，端游中很多优化想法同样适用于移动端，移动端跟PC端比，就是一台配置相对低的PC而已。接着大家的遮挡裁剪继续给读者说明，论文作者也做了壹个效率测试，以250’000物体，1G的网格为例，测试效果如下所示：

是不是很酷啊！在项目开发中完全可以用它化解难题，下面大家再谈谈运用GPU去优化大家的大地形场景。

GPU大地形渲染优化化解方法

大家的大地形首先会有自己的地表贴图，常用的地表贴图是四张纹理融合，最多可以有八张贴图融合，地形纹理渲染会涉及到LOD算法，远处的地形网格可以简化一些，对应的贴图也是最低的，这就是MipMap的运用。另外肯定有草有花以及其他大量相同的物件渲染，先说说草和花的绘制，他们在游戏中会特别的多，常用的行为是引擎提供的面片或者是十字交叉，或者三张图片交叉，接着将带有Alpha通道的贴图映射在上面，如下图所示效果：

CPU绘制这些草或者花在PC端是可以的，由于现在的PC都是多核的，在手机端就会影响到效率难题了。运用CPU绘制，DrawBlack会特别的多，而且草或者花还需要摆动，计算量很大的，这严重影响了运行效率，CPU有难，GPU可以帮忙，大家可以将草或者花的绘制放到GPU中执行，效果如下所示：

二、放开全球游戏中的大地图背后有哪些实现技术

首先肯定一下，这一个特别有趣的难题。在这个答案里，我将尝试先回答主干难题，再对补充说明里的多少难题简单说一下。下面是这篇文章小编将将涉及到的一些相关技术的列表，（需要说明的是，这些技术单独来看并不复杂，实际动手实现并领会各种取舍以后，在项目当中针对具体的需求去设计和组合才是关窍之所在）----------------------------一、程序技术篇：算法和架构（Programming Algorithms& Architecture）1.无限循环的平铺地图（Infinite Tiling）2.可预测随机数和无限宇宙（Predictable Random）3.精度难题化解方法（Precision Problem Solving）4.超大地形的处理（Terrain Visualization） 4.1古典算法（从 GeoMipMapping，Progressive Mesh到 ROAM） 4.2层次的艺术（Quadtree和 Chunked LOD） 4.3以GPU为主的技术（Paging，Clipmap到 GPU Terrain）5. id tech 5的 megatexture（超大地表上的非重复性海量贴图）6.经过式内容生成（Procedural Content Generation） 6.1经过式纹理（Procedural Texturing） 6.2经过式建模（Procedural Modeling）二、内容制作篇：设计和创新（Content Design& Creation）1.随机地图类游戏(Diablo II)中地图的拼接2.无缝大全球(World of Warcraft)中区域地图的拼接3.卫星地质数据的导入，规整化和再加工（一些飞行模拟类游戏）4.超大地图的协同编辑：并行操作，数据同步，手动和自动锁的运用三、异次元篇：大家的征途是星辰大海1.终极沙盒（EVE）：当规模大到一定程度——宇宙级别的混沌学说和蝴蝶效应2.打通两个宇宙（EVE& Dust）：发现更广阔的全球——宇宙沙盒游戏和行星STG游戏联动----------------------------##一、程序技术篇：算法和架构（Programming Algorithms& Architecture）### 1.无限循环的平铺地图（Infinite Tiling）大家就从最平淡无奇的无限循环平铺地图说起吧。这应该是最原始，也是最没有技术含量的放开全球构筑方法了。技术上由于过于朴素，也没啥子好说的，就是在同壹个坐标系内像铺地砖那样展开，坐标对齐即可，就是接头处需要注意一下，不要穿帮就行。然而千万别由于简单就小看这个技术哟，上面列表里面的不少技术都是在循环平铺的基础上进步起来的，下面大家就来瞧一瞧吧。按照维度的不同，循环平铺有下面三大类：a.在一维路线上扩展的横版卷轴游戏（以动作类游戏为主）和纵版卷轴游戏（以STG类游戏为主）。这些类型的游戏里，为了避免循环平铺给玩家带来的重复的疲劳，卷轴游戏会添加一些随机或动态的元素，比如超级玛丽里的背景上云朵的位置，分出多个层次以不同速率卷动的背景层，等等。.在二维路线上循环平铺的固定视角2D游戏。这一类游戏里，相对典型的就是 Diablo。暗黑中的随机地图生成，在本质上，就是叠加了一定的随机性，约束和边界条件的循环平铺效果。width="550" data-original="">c.在 3D游戏里循环平铺高度图，形成连绵不断的地形效果。这在早期的模拟飞行STG类游戏里相对常见，现在已经很难搜到图了，我在上大学的时候写的第壹个地形渲染 demo就是平铺的，可惜刚刚翻硬盘已经找差点了555。这一类游戏，在平铺时适当地辅以一些贴图的变化，可以在很省内存的条件下，做出特别不错的效果。找差点游戏内的图，拿下面这个高度图来凑数吧。请大家脑补一下，把下面这个灰度图立体化之后，一块一块像地砖一样循环平铺以后，3D渲染出来的连绵起伏的直抵地平线（好吧，直抵远裁剪面）的山脉的壮观效果吧。-------------------------### 2.可预测随机数和无限宇宙（Predictable Random）（本节内的描述和算法，部分参考了《Game Programming Gems I》 [“2.0 Predictable Random Numbers”](Graphics and Game Gems Database)一文，请感兴趣的同学自行查找原文通读）有个传说中的游戏叫 Elite，不了解有没有同学玩到过。据说这游戏运行在32K内存的机器上，其中16K还是只读的ROM。这游戏据说拥有难以匹敌的游戏深度：近乎无限个行星，每壹个都有各自的名字和特征。可预测随机数本身是游戏内运用特别广泛的壹个技术，这里大家着重谈一下它在为游戏提供（微观上）更丰盛的细节和（宏观上）更广阔的全球的影响。这一技术的最重要守则是，为了在壹个游戏全球中给出无限空间的幻觉，大家需要满足两个分解条件，可以把它们成为宏无限（macro-infinite）和微无限（micro-infinite）”。前者涉及到难题的空间规模，后者则任意壹个对象所支持的最小细节层次级别。----------------------------从实现上来说，怎样设定随机种子是这个技术的核心。由于给定壹个随机种子，生成的随机序列是完全可预测的，那么根据游戏内的一些时空的设定，通过对随机种子进行一些定制，得到在游戏内任意某个时刻和某个空间点上完全可预测的行为就是可行的了。最简单的是运用下面内容多少元素和随机种子配合计算：1.全球坐标（即 X Y Z值，既可以表示空间中的某个点，也可以表示某个区域）2.体系时刻（可以用真正时刻，也可以用游戏内设计者定义的时刻，如果是前者的话需要思考离线时的处理）3.正态分布（在游戏里建壹个查找表即可，这是最廉价的方法）这些影响加上对应的随机序列，已经可以营造出宏观上相对有深度的壹个宇宙空间了。学说上，如果全部的随机性都是由给定的随机种子产生，而这些随机种子要么是游戏定义的常量，要么是查表得到，要么是均匀流逝，要么是由更高层次的随机种子生成，那么这样一层一层上溯到尽头的话，任何壹个游戏内的宇宙，都可以归因到壹个初始的种子，这个种子，就是决定论中典范物理学的所谓的第一推动吧。其实如果真做到了这一点，大家大可以把这个种子交给玩家，在第一次进入游戏的时候掷壹个 2^64骰子。这是真正的上帝创世的感觉，想象一下，上帝说，要有光，于是掷出了骰子，第一推动怦然落地，整个时空的巨大齿轮开始运转，在不同的时刻点和空间点上，更多的随机序列被生成出来...

三、有啥子有全球地图的游戏

记得以前有玩过壹个游戏叫《大航海时代2》，游戏亦被设定于16世纪，内容延续前一代的故事。1994年，公开SFC和MD版本。而且游戏中的很多人物在历史上都有真正原型可寻。在游戏中，共有6名主角供玩家选择，每壹个主角在游戏中都有不同的剧情。其中就有画全球地图的经过，全球各地的一些港口的坐标等。现在好像已经到第五代了《大航海时代5》了，还有大航海时代OL等。