腾讯游戏开发精粹

√ 本书来自行业一线前沿的经验案例

√ 所有方案均出自腾讯游戏上线项目

√ 精选游戏行业内具有独创性的技术

√ 腾讯游戏研发原创技术方案与经验

√ 代表腾讯游戏团队的集体研究成果

√ 覆盖多个至关重要的核心技术领域

√ 中国版Game Programming Gems

√ 提升全国游戏从业者整体开发水平

《腾讯游戏开发精粹》是腾讯游戏研发团队的技术结晶，由10多名腾讯游戏资深技术专家撰写而成，整理了团队在自主游戏研发的道路上积累沉淀的技术方案，具有较强的通用性及时效性，内容涵盖游戏脚本系统及开发工具、数学和物理、计算机图形、人工智能与后台架构等。

腾讯游戏十多位从事一线技术研发和前沿创新的骨干开发技术专家。

目 录
第一部分 游戏数学
第1 章 基于SDF的摇杆移动 2
摘要 2
1.1 引言 3
1.2 有号距离场（SDF 3
1.3 利用栅格数据预计算SDF  4
1.4 SDF 的碰撞检测与碰撞响应 5
1.5 避免往返 8
1.6 利用多边形数据预计算SDF  9
1.7 其他需求 10
1.7.1 如何将角色从障碍区域中移出 10
1.7.2 角色不能越过障碍物的远距离移动 11
1.8 动态障碍物 12
1.9 AI寻路 14
1.10 动态地图 14
1.11 总结 17
参考文献 17

第2 章 高性能的定点数实现方案 18
摘要 18
2.1 引言 18
2.1.1 浮点数简介 18
2.1.2 32 位浮点数（单精度）表示原理 19
2.2 基于整数的二进制表示的定点数原理 19
2.2.1 32 位定点数表示原理 19
2.2.2 64 位定点数表示原理 20
2.3 定点数的四则运算 21
2.3.1 加法与减法 22
2.3.2 乘法 22
2.3.3 除法 23
2.4 定点数开方与超越函数实现方法 23
2.4.1 多项式拟合 24
2.4.2 正弦/余弦函数 25
2.4.3 指数函数 26
2.4.4 对数函数 27
2.4.5 开方运算 27
2.4.6 开方求倒数 28
2.4.7 为什么不用查表法 30
2.5 定点数的误差对比与性能测试 30
2.5.1 超越函数及开方的误差测试 30
2.5.2 性能测试 30
2.6 总结 31
参考文献 31

第二部分 游戏物理
第3 章 一种高效的弧长参数化路径系统 34
摘要 34
3.1 引言 34
3.2 端点间二次样条的构建 35
3.3 路径的构建 38
3.4 曲线的弧长参数化 39
3.5 曲线上的简单运动 42
3.5.1 跑动 42
3.5.2 跳跃 43
3.5.3 相邻路径的切换 44
3.5.4 曲线上的旋转插值 45
3.6 总结 46
参考文献 46

第4 章 船的物理模拟及同步设计 47
摘要 47
4.1 浮力系统 48
4.1.1 浮力 48
4.1.2 升力 52
4.1.3 拉力 52
4.1.4 拍击力 53
4.1.5 阻力上限 54
4.2 引擎系统 55
4.2.1 移动、转向模拟 55
4.2.2 向心力计算 56
4.3 Entity-Component 及同步概览 56
4.4 浮力系统物理更新机制 57
4.5 总结 59
参考文献 59

第5 章 3D 游戏碰撞之体素内存、效率优化 60
摘要 60
5.1 背景介绍 60
5.2 体素生成 62
5.3 体素内存优化 62
5.3.1 体素合并的原理 62
5.3.2 体素合并的算法 64
5.3.3 地面处理 65
5.3.4 水的处理 66
5.3.5 范围控制 67
5.3.6 内存自管理 67
5.3.7 体素内存优化算法的效果 68
5.3.8 体素效率优化 69
5.4 NavMesh 生成 69
5.4.1 体素生成NavMesh 69
5.4.2 获取地面高度 70
5.4.3 后台阻挡图 71
5.4.4 前台优先级NavMesh 71
5.4.5 锯齿 72
5.5 行走、轻功、摄像机碰撞 73
5.5.1 行走 73
5.5.2 轻功 75
5.5.3 摄像机碰撞 75
参考文献 76

第三部分 计算机图形
第6 章 移动端体育类写实模型优化 78
摘要 78
6.1 引言 79
6.2 方案设计思路 79
6.2.1 角色统一与差异元素分析 79
6.2.2 角色表现=人体 服饰 80
6.2.3 角色资源整理 83
6.2.4 资源制作与实现 84
6.3 具体实现  92
6.3.1 实现流程 92
6.3.2 CPU 逻辑 93
6.3.3 GPU 渲染 97
6.4 效果收益、性能分析和结语 97
6.4.1 方案优劣势 98
6.4.2 方案补充 99
6.4.3 应用场景 99
参考文献 100

第7 章 大规模3D 模型数据的优化压缩与精细渐进加载 101
摘要 101
7.1 引言 102
7.2 顶点数据优化 102
7.2.1 顶点数据合并去重 103
7.2.2 索引数据合并 104
7.2.3 顶点数据排序 104
7.2.4 子网格的拆分与合并 105
7.2.5 顶点数据编码压缩 105
7.3 有利于渐进加载的数据组织方式 112
7.4 总结 113
参考文献 114

第四部分 人工智能及后台架构
第8 章 游戏AI 开发框架组件behaviac 和元编程 116
摘要 116
8.1 behaviac 的工作原理 117
8.1.1 类型信息 117
8.1.2 什么是行为树 118
8.1.3 例子1 119
8.1.4 执行说明 119
8.1.5 进阶 120
8.1.6 例子2 120
8.1.7 再进阶 123
8.1.8 总结 123
8.2 元编程在behaviac中的应用 125
8.2.1 模板特化 126
8.2.2 加载中的特例化 126
8.2.3 运行中的特例化 129
第9 章 跳点搜索算法的效率、内存、路径优化方法 131
摘要 131
9.1 引言 132
9.2 JPS算法 133
9.2.1 算法介绍 133
9.2.2 A*算法流程 133
9.2.3 JPS算法流程 135
9.2.4 JPS算法的“两个定义、三个规则 135
9.2.5 算法举例 137
9.3 JPS算法优化 138
9.3.1 JPS效率优化算法 138
9.3.2 JPS内存优化 144
9.3.3 路径优化 145
9.4 GPPC 比赛解读 146
9.4.1 GPPC 比赛与地图数据集 146
9.4.2 GPPC 的评价体系 148
9.4.3 GPPC 参赛算法及其比较 150
参考文献 151
第10 章 优化MMORPG开发效率及性能的有限多线程模型 152
摘要 152
10.1 引言 152
10.1.1 多进程单线程模型 153
10.1.2 单进程多线程模型 153
10.1.3 单进程单线程模型 153
10.2 有限多线程模型 154
10.3 使用OpenMP框架快速实现有限多线程模型 156
10.4 控制多线程逻辑代码 158
10.5 异步化解决数据安全问题 159
10.6 对“不安全”访问的防范 160
10.7 拆解大锁 161
10.8 其他建议 163
参考文献 164

第五部分 游戏脚本系统
第11 章 Lua翻译工具——C#转Lua 166
摘要 166
11.1 设计初衷 166
11.2 实现原理 167
11.2.1 参考对比行业内类似的解决方案 167
11.2.2 翻译原理 168
11.2.3 翻译流程 168
11.3 翻译示例 170
11.4 实现细节 174
11.4.1 连续赋值 175
11.4.2 switch  175
11.4.3 continue  176
11.4.4 不定参数 177
11.4.5 条件表达式 178
11.5 运行性能 179
11.6 TKLua 翻译蓝图 179
11.6.1 类关系 180
11.6.2 类成员 180
11.6.3 方法体 181
11.7 发展方向 182
11.8 总结 184
参考文献  185

第12 章 Unreal Engine 4集成Lua  186
摘要 186
12.1 引言 186
12.2 UE4 元信息 187
12.2.1 介绍 187
12.2.2 Lua 通过元信息与UE4交互 189
12.2.3 读写成员变量 189
12.2.4 函数调用 190
12.2.5 C 调用Lua  191
12.2.6 小结 192
12.3 通过模板元编程生成“胶水”代码 192
12.3.1 接口设计 193
12.3.2 实现 195
12.3.3 读写成员变量 197
12.3.4 引用类型 198
12.3.5 导出函数 199
12.3.6 默认实参 200
12.3.7 默认生成的函数 202
12.3.8 C 调用Lua  203
12.3.9 小结 203
12.4 优化 203
12.4.1 UObject 指针与Table  203
12.4.2 结构体 204
12.4.3 运行时热加载 205

第六部分 开发工具
第13 章 使用FASTBuild助力Unreal Engine 4  208
摘要 208
13.1 引言 209
13.2 UE4 分布式工具 209
13.2.1 Derived Data Cache（DDC 209
13.2.2 Swarm  210
13.2.3 IncrediBuild  210
13.2.4 FASTBuild  211
13.3 在Windows系统下搭建FASTBuild 工作环境 213
13.3.1 网络架构 213
13.3.2 搭建基本环境 214
13.3.3 可用性验证 215
13.4 使用FASTBuild 分布式编译UE4代码和项目代码 219
13.4.1 准备工作 219
13.4.2 部署多机FASTBuild 环境 220
13.4.3 编译UE4 代码及对比测试 220
13.4.4 优化FASTBuild  224
13.4.5 再次测试分布式编译UE4代码 227
13.5 “秒”编UE4着色器 228
13.5.1 准备工作 229
13.5.2 大规模着色器编译测试 237
13.5.3 材质编辑器内着色器编译测试 240
13.6 总结 243
第14 章 一种高效的帧同步全过程日志输出方案 244
摘要 244

编者序

游戏开发对于一般软件开发者来说，总像蒙上了一层神秘面纱。这可能是由多个原因造成的。首先，游戏开发的技术范畴比较广，一些技术如计算机图形学、物理模拟、实时网络同步等比较少应用在一般软件开发中。其次，游戏开发属于创意工业，对各类型游戏的需求有很多区别，不少技术没有形成标准，各家的技术方案、工作流程等也会有不少差异。最后，公司之间甚至公司之内也可能有技术壁垒，影响知识和技术的流通。这些情况不利于有兴趣的朋友进入此行业，从业者的进步也会受限，长远影响行业的发展，难以面对全球的激烈竞争。

编者在20 世纪90 年代的香港，互联网未普及之前，只能通过BBS收集一些国外“漂流”过来的游戏开发技术文档，例如《德军总部3D》的三维室内场景渲染及纹理贴图技术、如何使用非标准的 Mode X 去做 VGA 256 色双缓冲区渲染等。在那个资讯匮乏的年代，每次遇到新技术的解密文档，编者都兴奋得如获至宝。

而在国内做游戏开发的“老鸟”，大概都会翻过千禧年代的《游戏编程精粹（Game Programming Gems）》系列丛书。这套丛书影响了一整代的开发者，让我们能一窥世界各地游戏开发者的各种秘技，解决在游戏开发中遇到的各种共同问题，同时可以激发灵感，研发比书中更好的解决方案。

进入互联网信息爆炸的年代，我们能在网上接触无数的博客、问答等信息，可以更快速地知悉各种新技术。但同时，网上信息相对于传统出版来说，通常较为零散，品质参差不齐。从业者也基于保密原因，不会随便公开一些游戏开发中使用到的新技术。

本书受《游戏编程精粹》系列丛书的启发，希望鼓励腾讯游戏的工程师与业界同行分享一些实际应用在游戏里的技术，与行业共享。通过内部审核及编辑等机制，尽量筛选可对外公开、品质的文章，也保证技术具有一定的通用性及时效性。对国内业界而言，希望这本书能成为一小步，促进更开放的未来，提升整体技术水平。

本书从提案到出版长达一年半的时间，除了依靠各位作者在忙碌的开发任务中抽空撰文，还必须感谢腾讯游戏学院院长夏琳女士的大力支持，也要感谢腾讯游戏学院的董磊、刘雅和陈若毅使项目成功推进。我也衷心感谢本书的编委郭智、刘安健、匡西尼、安柏霖、王杨军和沙鹰（排名不分先后），他们都是腾讯游戏各个部门的技术专家，悉心为文章的内容把关。也非常感谢电子工业出版社的张春雨和葛娜协助出版事宜。

最后，希望本书能对读者有所帮助，如有任何意见请不吝通过邮件反馈给我们：[email protected]，期望在续篇再见。

——叶劲峰 《腾讯游戏开发精粹》主编  腾讯互动娱乐 魔方工作室群技术总监

推荐序

前不久，一位高中生物老师，也是我小孩同班同学的妈妈，主动问我这几年新开设的游戏设计和电子竞技专业是否值得报考，她的孩子对制作游戏非常有兴趣。听到这个咨询，我长舒了一口气：游戏正逐渐被越来越多的人认可。

我们知道，电子游戏是“第九艺术”，是各种艺术和技术能力的集大成者。记得在10 多年前，我参与开发腾讯第一款自研游戏《QQ 幻想》的时候，随着项目的进展，我深深体会到，开发出一款高质量的MMORPG 游戏需要很强的、综合的技术能力。比如一些技术细节：如何在最大限度限制瞬移外挂的情况下，处理弱网络环境下角色的移动拉扯和同步？怎样高效地实现基于决策树的各种NPC 的AI，使得NPC 的行为更贴近自然和有趣？游戏内经济系统的平衡，各种角色之间能力的平衡，还有上百万用户同时在线时的稳定性、热更新、热切换……诸如此类，在当时的技术背景下，是颇为严峻的挑战。

我们也知道，知识只有分享才更有价值。站在巨人的肩膀上，会看得更远；有了前辈的经验加持，也会成长得更快。《腾讯游戏开发精粹》这本书汇集了腾讯游戏在游戏开发中的部分精华，从客户端到服务器端，从物理引擎到工具链，从图形学到AI，各领域均有被验证过的解决方案呈现。腾讯是一家具有高度社会责任感的企业，它愿意将这些能力和经验无私奉献给大家，为行业的发展贡献自己的一点力量。互相学习，一起进步，是我们的希望。

我们还知道，电子游戏的特征之一是互动，在饭桌、在房间、在地铁……我们都可以看到各种玩游戏情景的开心愉快，它已经融入我们的日常生活之中。娱乐是人的天性，但让生活更美好，是我们每一个游戏从业者的使命。从虚拟世界到现实生活，再从现实生活到虚拟世界，用技术的手段来改变生活，未来就靠你了！

——崔晓春 腾讯互动娱乐 公共研发运营体系负责人

过去数十年，信息技术的高速发展将人类从工业文明迅速带入数字文明。在这一剧烈的数字化进程中，互联网公司必须坚持“科技向善”，确保这一轮技术革命真正惠及人类，实现数字社会福祉的*化。我们希望利用技术增进并改善人们的生活，游戏本身就是基于*的计算机技术和网络技术的互动式数字产物。在《腾讯游戏开发精粹》一书中，读者将了解到腾讯在游戏研发方面应用的一些新技术。期待在未来，随着3D、AI，以及连接人与人的网络等新技术的发展，游戏会有越来越多的创新，充分发挥新科技的巨大潜力，为全球用户带来更多娱乐和精神层面的享受，帮助人类拥有更好的数字文明。

——腾讯集团高级副总裁 马晓轶

秉承一贯的开放、共赢精神，《腾讯游戏开发精粹》收录腾讯游戏在上线项目中得到验证的前沿技术精华，涵盖游戏脚本系统及开发工具、数学和物理、计算机图形、人工智能与后台架构等诸多方面。期待与行业里的伙伴共享、探讨本书，共同探索游戏事业的更多可能。

——腾讯游戏学院院长 夏琳

本书由10多位优秀的腾讯游戏技术人员撰写而成，包含了游戏技术各领域的多个技术方案，且不同章节内容相对独立，可以作为工具书，随时阅读参考。无论是初学者还是从业者，都能从本书中收获经验知识和开发灵感。

——掌趣科技CEO 刘惠城

游戏开发技术覆盖的计算机科学领域广泛，众多资深的技术专家在《腾讯游戏开发精粹》一书中分享了从项目中提炼的多方面的经验。书中每一篇文章都有一个独立而完整的主题，从重要的基础概念开始一直讲到深入的技术细节，具有非常强的实践和参考意义，无论新手还是有经验的开发者都可以从中找到感兴趣的内容并开启学习旅程。相信其他从业人员在阅读完本书之后一定能像本人一样受益良多。

——Epic Games 中国资深技术工程师 王祢

游戏技术研发的实践性很强，真正有用的技术会在项目中不断被验证和优化。《腾讯游戏开发精粹》凝聚了腾讯游戏资深技术专家们的智慧，与大家分享了从多个成功项目中提炼出的优选方案和原创技术。对于立志从事游戏研发的学子们而言，这是一本能够帮助提高实践能力的好书。

——清华大学软件学院党委书记兼副院长 王斌