游戏编程精粹（4）

第1章　通用编程
简介　Chris Corry　2
1.1　调试游戏程序的学问　Steve Rabin　4
1.1.1　五步调试法　4
1.1.2　第一步：始终如一地重现问题　4
1.1.3　第二步：搜集线索　5
1.1.4　第三步：查明错误的源头　6
1.1.5　第四步：纠正问题　7
1.1.6　第五步：对所作的修改进行测试　7
1.1.7　高级调试技巧　8
1.1.8　困难的调试情景和模式　10
1.1.9　理解底层系统　12
1.1.10　增加有助于调试的基础设施　12
1.1.11　预防bug　13
1.1.12　结论　14
1.1.13　致谢　15
1.1.14　参考文献　15
1.2　一个基于HTML的日志和调试系统　James Boer　16
1.2.1　于日志系统的优势　16
1.2.2　究竟什么是事件日志？　16
1.2.3　HTML和调用堆栈　17
1.2.4　工作原理　18
1.2.5　一些有用的心得　21
1.2.6　结论　21
1.3　时钟：游戏的脉搏尽在掌握　Noel Llopis　23
1.3.1　关于时间的基础　23
1.3.2　时钟系统的组成　24
1.3.3　避免失真　25
1.3.4　结论　29
1.4　设计和维护大型跨平台库　David Etherton　30
1.4.1　设计　30
1.4.2　Build系统　32
1.4.3　细节　33
1.4.4　结论　35
1.4.5　参考文献　35
1.5　利用模版化的空闲块列表克服内存碎片问题　Paul Glinker　36
1.5.1　内存操作　36
1.5.2　解决方案　37
1.5.3　实现细节　37
1.5.4　有效地使用我们的Freelist　40
1.5.5　结论　40
1.5.6　参考文献　41
1.6　一个用C++实现的泛型树容器类　Bill Budge　42
1.6.1　可重用的库　42
1.6.2　树的概念　43
1.6.3　树的实现　43
1.6.4　利用STL　46
1.6.5　结论　49
1.6.6　参考文献　49
1.7　弱引用和空对象　Noel Llopis　51
1.7.1　使用指针　51
1.7.2　弱引用　52
1.7.3　空对象　55
1.7.4　结论　56
1.7.5　参考文献　57
1.8　游戏中的实体管理系统　Matthew Harmon　58
1.8.1　概述　58
1.8.2　实体消息　60
1.8.3　实体代码　61
1.8.4　类的代码　63
1.8.5　实体管理器　63
1.8.6　基于消息的游戏循环　65
1.8.7　开始：消息类　65
1.8.8　从小处着手：基本实体消息　66
1.8.9　游戏和环境消息　67
1.8.10　系统成长：一些高级消息　67
1.8.11　处理碰撞　69
1.8.12　扩展到多玩家　69
1.8.13　开发和调试消息　70
1.8.14　好处　70
1.8.15　光盘中的内容　71
1.8.16　总结　71
1.9　Windows和Xbox平台上地址空间受控的动态数组　Matt Pritchard　72
1.9.1　传统的动态数组管理　72
1.9.2　深入观察　73
1.9.3　地址空间管理 != 存储管理　73
1.9.4　重新思考关于数组增大的问题　74
1.9.5　新的增长规则　74
1.9.6　使用地址空间受控的数组　75
1.9.7　结论　79
1.10　用临界阻尼实现慢入慢出的平滑　Thomas Lowe　80
1.10.1　可用的技术　80
1.10.2　阻尼弦与临界阻尼　82
1.10.3　实践　82
1.10.4　设置平滑速率的上限　84
1.10.5　结论　85
1.10.6　参考文献　85
1.11　一个易用的对象管理器　Natalya Tatarchuk　86
1.11.1　对象管理的传统做法　86
1.11.2　灵活的对象管理器　87
1.11.3　结论　91
1.11.4　参考文献　92
1.12　使用自定义的RTTI属性对对象进行流操作及编辑　Frederic My　93
1.12.1　扩展的RTTI　93
1.12.2　属性　95
1.12.3　编辑属性　97
1.12.4　保存　99
1.12.5　载入　100
1.12.6　与旧版本文件的兼容性问题：类的描述　101
1.12.7　与旧版本文件的兼容性问题：匹配　102
1.12.8　“函数”属性　103
1.12.9　技巧和提示　103
1.12.10　思考　104
1.12.11　结论　104
1.12.12　参考文献　104
1.13　使用XML而不牺牲速度　Mark T. Price　106
1.13.1　为什么要使用XML呢？　106
1.13.2　简单介绍XDS Meta格式　107
1.13.3　XDS工具集　108
1.13.4　使用XDS工具集　109
1.13.5　整合　115
1.13.6　总结　115
1.13.7　参考文献　115
第2章　数学
简介　Jonathan Blow　118
2.1　使用马其赛特旋转的Zobrist散列法　Toby Jones　120
2.1.1　Zobrist散列　120
2.1.2　实现Zobrist散列　121
2.1.3　马其赛特旋转(Mersenne Twister)　122
2.1.4　马其赛特旋转的实现　123
2.1.5　结论　124
2.1.6　参考文献　124
2.2　抽取截锥体和camera信息　Waldemar Celes　125
2.2.1　平面变换(Plane Transformation)　125
2.2.2　抽取锥体信息　127
2.2.3　抽取camera信息　128
2.2.4　任意投影变换　130
2.2.5　实现　131
2.2.6　结论　132
2.2.7　参考文献　132
2.3　解决大型游戏世界坐标中的精度问题　Peter Freese　133
2.3.1　问题描述　133
2.3.2　可能的解决方式　135
2.3.3　偏移位置　137
2.3.4　渲染流水线变化　140
2.3.5　对性能的思考　143
2.3.6　结论　143
2.3.7　参考文献　144
2.4　非均匀样条　Thomas Lowe　145
2.4.1　样条的种类　145
2.4.2　三次样条的基础理论　146
2.4.3　圆形的非均匀样条　147
2.4.4　平滑非均匀样条　149
2.4.5　时控的非均匀样条　151
2.4.6　计算起始和最终节点速率　152
2.4.7　在样条上获取速率和加速度　153
2.4.8　优化　153
2.4.9　结论　153
2.4.10　参考文献　154
2.5　用协方差矩阵计算更贴切的包围对象　Jim Van Verth　155
2.5.1　协方差矩阵　155
2.5.2　特征值和特征向量　158
2.5.3　计算协方差矩阵的特征向量　159
2.5.4　创建包围对象　159
2.5.5　结论　161
2.5.6　参考文献　162
2.6　应用于反向运动的雅可比转置方法　Marco Spoerl　163
2.6.1　我们的测试环境　163
2.6.2　雅可比矩阵是什么？　164
2.6.3　雅可比转置矩阵简介　165
2.6.4　实现算法　166
2.6.5　结果和比较　168
2.6.6　结论　171
2.6.7　参考文献　171
第3章　物理
简介　Graham Rhodes　174
3.1　死神的十指：战斗中的命中算法　Roger Smith、Don Stoner　176
3.1.1　射击带状物(Ribbon)　176
3.1.2　射击靶心　177
3.1.3　射击矩形　178
3.1.4　使用霰弹枪射击小目标　179
3.1.5　移动炮兵的攻击命中　179
3.1.6　死亡的4种主要形式　180
3.1.7　化学武器、火球及区域性魔法　182
3.1.8　弹片的楔入　182
3.1.9　攻击丛林　183
3.1.10　攻击有猎物分布的丛林　183
3.1.11　结论　184
3.1.12　参考文献　184
3.2　在低速CPU系统中交通工具的物理模拟　Marcin Pancewicz、Paul Bragiel　185
3.2.1　技术的概要和前提假设　185
3.2.2　交通工具沿当前行驶方向上的加速及减速　186
3.2.3　方向控制　188
3.2.4　把所有要素结合起来　189
3.2.5　地形的影响　189
3.2.6　实现中遇到的问题　190
3.2.7　可以改进的地方　191
3.2.8　结论　192
3.3　编写基于Verlet积分方程的物理引擎　Nick Porcino　193
3.3.1　关于物理引擎　193
3.3.2　刚体　194
3.3.3　积分器　194
3.3.4　物理引擎　196
3.3.5　针对特定平台的考虑　199
3.3.6　扩展引擎的功能　199
3.3.7　结论　200
3.3.8　参考文献　200
3.4　刚体动力学中的约束器　Russ Smith　201
3.4.1　基本要点　201
3.4.2　约束器构造模块　202
3.4.3　创建有用的游戏约束器　205
3.4.4　光盘中的内容　209
3.4.5　结论　209
3.4.6　参考文献　209
3.5　在动力学模拟中的快速接触消除法　ádám Moravánszky、Pierre Terdiman　210
3.5.1　减少接触　210
3.5.2　对预处理的详细分析　213
3.5.3　对接触的分组群的详细分析　214
3.5.4　对持续性的详细分析　217
3.5.5　结论　217
3.5.6　参考文献　218
3.6　互动水面　Jerry Tessendorf　219
3.6.1　线性的波浪　220
3.6.2　垂直导数操作符　221
3.6.3　波浪的传播　222
3.6.4　可以互动的障碍物及其发生源　224
3.6.5　环境波浪　225
3.6.6　网格的边界　225
3.6.7　表面张力　226
3.6.8　结论　226
3.6.9　参考文献　226
3.7　用多层物理模拟快速变形　Thomas Di Giacomo、Nadia Magnenat-Thalmann　228
3.7.1　基于物理的动画LOD及相关的工作　228
3.7.2　使用分层的质量块弹簧物理的快速变形　230
3.7.3　结论　235
3.7.4　参考文献　2363.8　快速且稳定的形变之模态分析　James F. O'Brien　237
3.8.1　模式分解　239
3.8.2　模式的理解和丢弃　241
3.8.3　模态模拟　242
3.8.4　总结　244
3.8.5　结论　244
3.8.6　参考文献　245
第4章　人工智能
简介　Paul Tozour　248
4.1　第三人称视角摄像镜头的运动规则　Jonathan Stone　250
4.1.1　Camera定位及运动　250
4.1.2　Camera与场景边界　253
4.1.3　Camera遮断　256
4.1.4　简化场景　258
4.1.5　结论　258
4.1.6　参考文献　258
4.2　叙述战斗：利用AI增强动作游戏中的张力　Borut Pfeifer　260
4.2.1　戏剧张力　260
4.2.2　系统概述　263
4.2.3　设计者的控制部分　263
4.2.4　难度计算　264
4.2.5　难度调节　265
4.2.6　系统评价　266
4.2.7　结论　267
4.2.8　参考文献　267
4.3　非玩家角色决策：处理随机问题　Karén Pivazyan　268
4.3.1　概要　268
4.3.2　动态规划算法　269
4.3.3　代码　273
4.3.4　优化　275
4.3.5　DP算法的其他应用　275
4.3.6　结论　276
4.3.7　参考文献　276
4.4　一个基于效用的面向对象决策架构　John Hancock　277
4.4.1　决策树　278
4.4.2　基于对象的更好的体系结构　278
4.4.3　期望值　280
4.4.4　其他的决策准则　281
4.4.5　结论　282
4.4.6　参考文献　283
4.5　一个分布式推理投票架构　John Hancock　284
4.5.1　分布式推理　284
4.5.2　操纵仲裁者(Steering Arbiter)范例　286
4.5.3　选择投票空间　289
4.5.4　结论　290
4.5.5　参考文献　291
4.6　吸引子和排斥子　John M. Olsen　292
4.6.1　合力　292
4.6.2　引力曲线　293
4.6.3　吸引曲线的和　294
4.6.4　对应于特定配对的特定曲线　295
4.6.5　动态曲线　295
4.6.6　点、线、面　297
4.6.7　AI控制的层次　298
4.6.8　动画系统的交互　298
4.6.9　移动(Steering)　299
4.6.10　结论　299
4.6.11　参考文献　299
4.7　高级RTS游戏造墙算法　Mario Grimani　301
4.7.1　算法　301
4.7.2　算法改进　302
4.7.3　输出链表的形式　306
4.7.4　结论　307
4.7.5　参考文献　307
4.8　利用可编程图形硬件处理人工神经元网络　Thomas Rolfes　308
4.8.1　CPU与GPU系统架构　308
4.8.2　人工神经元网络　309
4.8.3　实现　310
4.8.4　结论　311
4.8.5　参考文献　311
第5章　图形图像
简介　Alex Vlachos　314
5.1　具有海报质量的屏幕截图　Steve Rabin　316
5.1.1　提高分辨率　316
5.1.2　提升像素质量　318
5.1.3　使用一个磁盘均衡采样分布　320
5.1.4　为抗锯齿调整像素的采样宽度　321
5.1.5　增加分辨率同增加像素质量相结合　321
5.1.6　结论　323
5.1.7　参考文献　324
5.2　非封闭网络模型的GPU容积阴影构架　Warrick Buchanan　325
5.2.1　回到制图板　325
5.2.2　在顶点阴影中实现这项技术　326
5.2.3　需要注意的事项　329
5.2.4　结论　330
5.2.5　参考文献　330
5.3　透视阴影贴图　Marc Stamminger　331
5.3.1　引言　331
5.3.2　后透视空间　332
5.3.3　后透视空间中的光　334
5.3.4　透视阴影贴图　335
5.3.5　实现　338
5.3.6　结论　339
5.3.7　参考文献　340
5.4　结合使用深度和基于ID的阴影缓冲　Kurt Pelzer　341
5.4.1　已有的阴影映射技术　341
5.4.2　深度和基于ID的阴影缓冲　342
5.4.3　结合深度和ID缓冲　343
5.4.4　组合的阴影缓冲概述　344
5.4.5　第一次：从光照的视点渲染　345
5.4.6　第二次：阴影检测　347
5.4.7　在DX9 2.0级的阴影中的实现　351
5.4.8　结论　353
5.4.9　参考文献　353
5.5　在场景中投射静态阴影　Alex Vlachos　355
5.5.1　前期工作　355
5.5.2　光束基本知识　355
5.5.3　高级算法　356
5.5.4　T型连接　357
5.5.5　网格模型最优算法　358
5.5.6　实现细节　359
5.5.7　阴影中的动态物体　360
5.5.8　结果　360
5.5.9　结论　361
5.5.10　参考文献　361
5.6　为阴影体和优化的网格模型调整实时光照　Alex Vlachos、Chris Oat　362
5.6.1　光照问题　362
5.6.2　在面法线上操作　362
5.6.3　调整漫射光照　364
5.6.4　结论　366
5.6.5　参考文献　366
5.7　实时半调色法：快速而简单的样式化阴影　Bert Freudenberg、Maic Masuch、Thomas Strothotte　367
5.7.1　引言　367
5.7.2　原理　368
5.7.3　实例的实现　371
5.7.4　结论　372
5.7.5　参考文献　372
5.8　在3D模型中应用团队色的各种技术　Greg Seegert　373
5.8.1　什么是团队色?　373
5.8.2　团队色的算法　373
5.8.3　一个实际的例子　378
5.8.4　光盘中的内容　379
5.8.5　结论　379
5.9　快速的棕褐色色调转换　Marwan Y. Ansari　380
5.9.1　背景　380
5.9.2　常规的方法　380
5.9.3　优化　381
5.9.4　结论　382
5.9.5　参考文献　382
5.10　使用场景亮度采样实现动态的Gamma　 Michael Dougherty、Dave McCoy　383
5.10.1　光照系数　383
5.10.2　有限的动态范围　383
5.10.3　图像的优化　384
5.10.4　易变的光灵敏度　385
5.10.5　转换　386
5.10.6　算法　388
5.10.7　结论　392
5.11　热和薄雾的后处理效果　Chris Oat、Natalya Tatarchuk　393
5.11.1　热和闪光的薄雾　393
5.11.2　高级算法　393
5.11.3　计算失真值　394
5.11.4　失真值的解释　397
5.11.5　结论　400
5.11.6　参考文献　400
5.12　用四元数的硬件蒙皮　Jim Hejl　401
5.12.1　蒙皮的概念　402
5.12.2　四元数参数化　404
5.12.3　硬件实现　405
5.12.4　结论　407
5.12.5　参考文献　407
5.13　动作捕捉数据的压缩　Sφren Hannibal　409
5.13.1　处理的计划　409
5.13.2　组织数据通道　410
5.13.3　减少已储存的键的数量　410
5.13.4　包装剩余的键　412
5.13.5　运行时解压缩　412
5.13.6　未来的改进　413
5.13.7　结论　413
5.13.8　参考文献　413
5.14　基于骨骼的有关节的3D角色的快速碰撞检测　Oliver Heim、Carl S. Marshall、Adam Lake　414
5.14.1　碰撞检测与碰撞分解　414
5.14.2　术语　414
5.14.3　将碰撞检测集成到3D游戏引擎中　415
5.14.4　基于骨骼的快速碰撞检测算法　416
5.14.5　结论　423
5.14.6　感谢　423
5.14.7　参考文献　423
5.15　使用地平线进行地形的遮挡剔除　Glenn Fiedler　424
5.15.1　引言　424
5.15.2　地平线剔除基础　425
5.15.3　蛮力地平线剔除　426
5.15.4　近似值　426
5.15.5　近似地平线直线　427
5.15.6　一个更好的近似值　427
5.15.7　最小二次方线　428
5.15.8　将它放入到第三维中　429
5.15.9　最小二次方平面　430
5.15.10　用近似值的地平线剔除　431
5.15.11　被地形遮挡的对象　432
5.15.12　使它成为动态的　432
5.15.13　未来的方向　433
5.15.14　结论　433
5.15.15　参考文献　433
第6章　网络和多人游戏
简介 Pete Isensee　436
6.1　设计与开发游戏大厅　Shekhar Dhupelia　437
6.1.1　状态-事件系统的设计　437
6.1.2　探讨大厅的子系统　438
6.1.3　高级大厅子系统　439
6.1.4　结论　441
6.1.5　参考文献　442
6.2　支持成千上万个客户端的服务器　Adam Martin　443
6.2.1　服务器设计中的门槛　443
6.2.2　问题　444
6.2.3　主要技术　446
6.2.4　服务器设计　451
6.2.5　结论　452
6.2.6　参考文献　452
6.3　大型多人游戏状态的有效存储　Justine Quimby　454
6.3.1　MMP的问题　454
6.3.2　Qualities理论　455
6.3.3　Qualities API　456
6.3.4　使用Qualities的好处　459
6.3.5　结论　459
6.3.6　参考文献　460
6.4　在客户/服务器环境下运用并行状态机　Jay Lee　461
6.4.1　独立状态　461
6.4.2　角色状态管理器　463
6.4.3　使用CharacterStateMgr　464
6.4.4　保持客户端和服务器端的同步　464
6.4.5　状态依赖的子系统　466
6.4.6　结论　467
6.4.7　参考文献　467
6.5　位打包：一种网络压缩技术　Pete Isensee　468
6.5.1　一个实例　468
6.5.2　难点　469
6.5.3　位打包　469
6.5.4　用于可打包数据类型的通用接口　471
6.5.5　用于可打包数据类型的具体接口　471
6.5.6　编解码器　472
6.5.7　评价折衷　473
6.5.8　改进　473
6.5.9　结论　473
6.5.10　参考文献　474
6.6　多服务器网络游戏的时间和同步管理　石卫东(Larry Shi)、Tao Zhang　475
6.6.1　为什么需要时间和同步管理　475
6.6.2　时钟同步　475
6.6.3　同步和响应　476
6.6.4　用多时间管理来一石二鸟地实现同步和响应　476
6.6.5　实现　476
6.6.6　何时应使用多时管理　482
6.6.7　总结　482
6.6.8　致谢　482
6.6.9　参考文献　482
第7章　音频
简介　Eddie Edwards　486
7.1　OpenAL简介　Joe Valenzuela　487
7.1.1　OpenAL API　487
7.1.2　有关OpenAL的实现　493
7.1.3　实现一致性指南　495
7.1.4　未来OpenAL的发展蓝图　496
7.1.5　总结　496
7.1.6　参考文献　496
7.2　简单的实时Lip-Synching系统　Jake Simpson　497
7.2.1　实现　497
7.2.2　动画方面需要注意的事项　498
7.2.3　声音音量的水印标记　499
7.2.4　注意　500
7.2.5　总结　500
7.3　动态变量和音频编程　James Boer　501
7.3.1　动态变量是什么？　501
7.3.2　动态变量类　501
7.3.3　在音频编程中使用动态变量　503
7.3.4　其他改进　506
7.3.5　结论　506
7.3.6　参考文献　506
7.4　创建一个音频脚本系统　Borut Pfeifer　507
7.4.1　游戏中音频的类别　508
7.4.2　工具　510
7.4.3　基于XML的音频标记库　510
7.4.4　脚本系统组件　512
7.4.5　进一步的工作　515
7.4.6　总结　515
7.4.7　参考文献　515
7.5　使用EAX和ZoomFX API的环境音效解决方案　Scott Velasquez　516
7.5.1　什么是环境音效　516
7.5.2　音频引擎的系统要求　517
7.5.3　潜在可听集(PAS，Potentially Audible Set)　518
7.5.4　EAX介绍　520
7.5.5　总结　528
7.5.6　参考文献　528
7.6　在游戏的物理引擎中控制实时声音　Frank Luchs　529
7.6.1　游戏引擎　529
7.6.2　混合声音合成　531
7.6.3　可听见对象的属性　532
7.6.4　对象形状的影响　532
7.6.5　对象材质的影响　533
7.6.6　撞击和碰撞　533
7.6.7　演示　533
7.6.8　总结　534
7.6.9　参考文献　534
附录　536