Game Programming Gems.1

第1章　通用编程技术

1.0　神奇的数据驱动设计(Steve Rabin)　3
1.0.1　点子1——基础　3
1.0.2　点子2——最低标准　3
1.0.3　点子3——杜绝硬编码　3
1.0.4　点子4——将控制流写成脚本　4
1.0.5　点子5——什么时候不适合使用脚本？　5
1.0.6　点子6——避免重复数据　5
1.0.7　点子7——开发工具来生成数据　6
1.0.8　结论　6
1.1　面向对象的编程与设计技术(James Boer)　7
1.1.1　代码风格　7
1.1.2　类设计　9
1.1.3　类层次结构设计　10
1.1.4　设计模式　10
1.1.5　总结　16
1.1.6　参考资料　16
1.2　使用模板元编程的快速数学方法(Pete Isensee)　17
1.2.1　斐波纳契数　17
1.2.2　阶乘　18
1.2.3　三角学　19
1.2.4　实际世界中的编译程序　20
1.2.5　重访三角学　21
1.2.6　模板和标准C++　21
1.2.7　矩阵　21
1.2.8　总结　26
1.2.9　参考文献　31
1.3　一种自动的Singleton工具(Scott Bilas)　32
1.3.1　定义　32
1.3.2　优点　32
1.3.3　问题　33
1.3.4　传统的解决方法　33
1.3.5　较好的方法　33
1.3.6　更好的方法　34
1.3.7　参考文献　35
1.4　在游戏编程中使用STL(James Boer)　36
1.4.1　STL的类型和术语　36
1.4.2　STL概念　37
1.4.3　向量(Vector)　38
1.4.4　链表(List)　40
1.4.5　双队列(Deque)　42
1.4.6　映射表(Map)　43
1.4.7　堆栈(Stack)，队列(Queue)和优先队列(Priority Queue)　46
1.4.8　总结　47
1.4.9　参考文献　47
1.5　一个通用的函数绑定接口(Scott Bilas)　48
1.5.1　要求　48
1.5.2　关于平台　48
1.5.3　第一次尝试　49
1.5.4　第二次尝试　50
1.5.5　部分解决方法　51
1.5.6　调用约定　52
1.5.7　调用函数　54
1.5.8　完备解决方案　55
1.5.9　结论　56
1.5.10　参考文献　57
1.6　通用的基于句柄的资源管理器(Scott Bilas)　58
1.6.1　方法　58
1.6.2　Handle类　59
1.6.3　HandleMgr类　60
1.6.4　使用示例　61
1.6.5　注意　61
1.6.6　参考文献　68
1.7　资源和内存管理(James Boer)　69
1.7.1　资源类　69
1.7.2　资源管理类　71
1.7.3　句柄如何工作　74
1.7.4　可能的扩展和改进　74
1.7.5　结论　75
1.8　快速数据载入技巧(John Olsen)　76
1.8.1　预处理你的数据　76
1.8.2　保存你的数据　76
1.8.3　使用简单方法载入你的数据　77
1.8.4　更安全地载入你的数据　78
1.9　基于帧的内存分配(Steven Ranck)　80
1.9.1　常规内存分配的挑战　80
1.9.2　介绍基于帧的内存　80
1.9.3　分配和释放内存　82
1.9.4　例子　84
1.9.5　结论　86
1.10　简单快速的位数组(Andrew Kirmse)　87
1.10.1　概述　87
1.10.2　位数组　87
1.10.3　其他数组　88
1.10.4　应用　89
1.10.5　参考文献　89
1.11　在线游戏的网络协议(Andrew Kirmse)　90
1.11.1　定义　90
1.11.2　篡改报文　90
1.11.3　报文重放　91
1.11.4　其他技术　92
1.11.5　逆向工程　92
1.11.6　实现　93
1.11.7　参考文献　93
1.12　最大限度地利用Assert(Steve Rabin)　94
1.12.1　Assert基础　94
1.12.2　Assert技巧 #1：嵌入更多信息　95
1.12.3　Assert技巧 #2：嵌入更多更多信息　95
1.12.4　Assert技巧 #3：使之更好用一些　96
1.12.5　Assert技巧 #4：编写自己的assert宏　96
1.12.6　Assert技巧 #5：无价之宝　97
1.12.7　Assert技巧 #6：给“超级铁杆”　97
1.12.8　Assert技巧 #7：让它更简单——复制和粘贴　98
1.12.9　参考文献　98
1.13　Stats：实时统计和游戏内调试(John Olsen)　99
1.13.1　Why：需求驱动的技术　99
1.13.2　How：一个进化过程　100
1.13.3　What：一个基于C++类的系统　100
1.13.4　Where：可用性　102
1.13.5　小结　102
1.14　实时的游戏内建剖析(Steve Rabin)　103
1.14.1　开始考虑细节　103
1.14.2　剖析器将告诉你什么？　104
1.14.3　增加剖析器调用　105
1.14.4　剖析器的实现　106
1.14.5　ProfileBegin的细节　107
1.14.6　ProfileEnd的细节　107
1.14.7　处理剖析数据的细节　107
1.14.8　后期增强　108
1.14.9　将它们组合起来　108
1.14.10　参考文献　113

第2章　数学技巧
2.0　可预测随机数(Guy W. Lecky-Thompson)　117
2.0.1　可预测随机数　117
2.0.2　替换算法　119
2.0.3　无限宇宙算法　120
2.0.4　结论与展望　122
2.0.5　参考文献　123
2.1　插值方法(John Olsen)　124
2.1.1　使用浮点数学的帧速相关ease-out　124
2.1.2　使用整型数学的帧速相关ease-out　125
2.1.3　帧速无关线性内插　126
2.1.4　帧速无关ease-in和ease-out　127
2.1.5　危险地带　128
2.2　求刚体运动方程的积分(Miguel Gomez)　132
2.2.1　运动学：平移和旋转　132
2.2.2　动力学：力与旋转力矩(torque)　135
2.2.3　刚体的特性　136
2.2.4　求运动方程的积分　139
2.2.5　参考文献　140
2.3　三角函数的多项式逼近(Eddie Edwards)　141
2.3.1　多项式　142
2.3.2　定义域和值域　143
2.3.3　偶多项式和奇多项式　146
2.3.4　泰勒级数　146
2.3.5　截断的泰勒级数　149
2.3.6　拉格朗日级数　150
2.3.7　不连续性处理　153
2.3.8　结论　153
2.4　为数字稳定性而利用隐式欧拉积分(Miguel Gomez)　155
2.4.1　求初值问题的积分及稳定性　155
2.4.2　显式的欧拉方法　155
2.4.3　隐式欧拉方法　156
2.4.4　不准确性　158
2.4.5　寻找隐式解　158
2.4.6　结论　158
2.4.7　参考文献　158
2.5　小波：理论与压缩(Lo?c Le Chevalier)　160
2.5.1　原理　160
2.5.2　一个实例　162
2.5.3　应用　162
2.5.4　参考文献　163
2.6　水面的交互式模拟(Miguel Gomez)　164
2.6.1　二维波动方程　164
2.6.2　边界条件：岛屿和海岸线　166
2.6.3　实现问题　166
2.6.4　与水面交互　167
2.6.5　渲染　169
2.6.6　参考文献　170
2.7　游戏编程四元数(Jan Svarovsky)　171
2.7.1　将四元数当作矩阵替换物　171
2.7.2　为什么不使用欧拉角　172
2.7.3　X、Y、Z和W代表什么　172
2.7.4　源自什么数学基础　173
2.7.5　四元数如何表示旋转　174
2.7.6　参考文献　174
2.8　矩阵和四元数之间的转换(Jason Shankel)　175
2.8.1　四元数旋转　175
2.8.2　四元数到矩阵的转换　175
2.8.3　矩阵到四元数的转换　177
2.8.4　参考文献　178
2.9　四元数插值(Jason Shankel)　179
2.9.1　四元数计算　179
2.9.2　四元数插值　179
2.9.3　示例代码　182
2.9.4　推导　182
2.10　最短弧四元数(Stan Melax)　186
2.10.1　动机　186
2.10.2　数值不稳定性　186
2.10.3　稳定公式的推导　187
2.10.4　残存不稳定性条件　188
2.10.5　源代码　188
2.10.6　虚拟跟踪球　189
2.10.7　参考文献　189

第3章　人工智能
3.0　设计一个通用、健壮的AI引擎(Steve Rabin)　193
3.0.1　事件驱动与轮询的对比　193
3.0.2　消息概念　194
3.0.3　状态机　194
3.0.4　一个使用消息的事件驱动状态机　194
3.0.5　交待时间(Confession Time)　197
3.0.6　另一个小交待　197
3.0.7　状态机构建单元　198
3.0.8　状态机消息路由选择　198
3.0.9　发送消息　200
3.0.10　发送延迟的消息　200
3.0.11　删除游戏对象　201
3.0.12　增强：定义消息的范围　201
3.0.13　增强：记录所有的消息活动和状态变迁　203
3.0.14　增强：交换状态机　203
3.0.15　增强：多状态机　203
3.0.16　增强：一个状态机队列　204
3.0.17　代码外部脚本化行为　204
3.0.18　结论　204
3.0.19　参考文献　207
3.1　一个有限状态机类(Eric Dybsand)　208
3.1.1　FSMclass和FSMstate　210
3.1.2　定义FSMstate　210
3.1.3　定义FSMclass　211
3.1.4　为FSM创建状态　212
3.1.5　使用FSM　213
3.1.6　参考文献　219
3.2　博弈树(Jan Svarovsky)　220
3.2.1　极小极大算法的负极大改进算法　221
3.2.2　 剪枝　222
3.2.3　走步排序方法　223
3.2.4　 求精　224
3.2.5　参考文献　224
3.3　A*路径规划基础(Bryan Stout)　225
3.3.1　问题　225
3.3.2　方法概述　225
3.3.3　A*的特性　227
3.3.4　将A*应用到游戏路径规划　227
3.3.5　A*的弱点　231
3.3.6　进一步的工作　232
3.3.7　参考文献　232
3.4　A*审美优化(Steve Rabin)　233
3.4.1　直路径　233
3.4.2　多边形搜索空间中的直路径　234
3.4.3　平滑路径　234
3.4.4　预先计算的Catmull-Rom公式　235
3.4.5　改进分级路径的直接性　236
3.4.6　空旷区域上的分级寻径　238
3.4.7　在分级搜寻过程中减少停顿　238
3.4.8　最大化响应率　239
3.4.9　结论　239
3.4.10　参考文献　239
3.5　A*速度优化(Steve Rabin)　240
3.5.1　搜索空间优化　240
3.5.2　算法优化　244
3.5.3　结论　248
3.5.4　参考文献　253
3.6　简化的3D运动和使用导航网格进行寻径(Greg Snook)　254
3.6.1　简述　254
3.6.2　构造　255
3.6.3　滚动骰子并且移动鼠标　256
3.6.4　到此仅完成一半　258
3.6.5　它是有效的，但不是那么完美　260
3.6.6　结论　261
3.6.7　参考文献　269
3.7　Flocking：一种模拟群体行为的简单技术(Steven Woodcock)　270
3.7.1　实现　271
3.7.2　代码　273
3.7.3　局限性与可能的改进　276
3.7.4　资源与致谢　282
3.8　用于视频游戏的模糊逻辑(Mason McCuskey)　283
3.8.1　模糊逻辑如何工作　283
3.8.2　模糊逻辑运算　285
3.8.3　为模糊控制而刹车　286
3.8.4　模糊逻辑的其他应用　291
3.8.5　结论　291
3.8.6　资源　291
3.9　神经网络初探(André LaMothe)　292
3.9.1　生物学仿真　292
3.9.2　对游戏的应用　293
3.9.3　神经网络101　294
3.9.4　纯逻辑，Mr. Spock　298
3.9.5　分类与“图像”识别　302
3.9.6　Hebbian的Ebb　305
3.9.7　运行Hopfield　306
3.9.8　结论　309

第4章　多边形技术
4.0　为OpenGL优化顶点提交(Herbert Marselas)　313
4.0.1　即时模式　313
4.0.2　交叉存取数据　314
4.0.3　步数据和流数据　315
4.0.4　编译过的顶点数组　316
4.0.5　取消数据复制厂家指定扩展　317
4.0.6　数据格式　317
4.0.7　一般建议　318
4.0.8　结论　318
4.0.9　参考文献　319
4.1　调整顶点的投影深度值(Eric Lengyel)　320
4.1.1　考察投影矩阵　320
4.1.2　矫正深度值　321
4.1.3　选择一个适当的 　321
4.1.4　实现　323
4.1.5　源代码　323
4.2　矢量摄像机(David Paull)　324
4.2.1　矢量摄像机初步　325
4.2.2　本地空间优化　326
4.2.3　结论　327
4.3　摄像机控制技术(Dante Treglia II)　328
4.3.1　一种基本的第一人称摄像机　328
4.3.2　脚本摄像机　330
4.3.3　摄像机技巧　333
4.4　一种快速的圆柱棱台相交测试算法(Eric Lengyel)　337
4.4.1　视域棱台　337
4.4.2　计算有效半径　338
4.4.3　算法　339
4.4.4　实现　341
4.5　3D碰撞检测(Kevin Kaiser)　346
4.5.1　算法概述　346
4.5.2　包围球碰撞检测　346
4.5.3　三角形对三角形的碰撞检测　348
4.6　用于交互检测的多分辨率地图(Jan Svarovsky)　358
4.6.1　使用栅格　358
4.6.2　对象大小变化的问题　358
4.6.3　多分辨率地图　359
4.6.4　源代码　360
4.7　计算到区域内部的距离(Steven Ranck)　368
4.7.1　问题　368
4.7.2　算法描述　369
4.7.3　应用　371
4.8　对象阻塞剔除(Tim Round)　376
4.8.1　可视棱台裁剪　376
4.8.2　阻塞剔除　378
4.8.3　总结　379
4.9　永远不要让他们看到你的“抖动”——几何体细节层次选择问题(Yossarian King)　387
4.9.1　LOD选择　387
4.9.2　放大率因子　389
4.9.3　滞变阈值　389
4.9.4　实现　390
4.9.5　其他问题　391
4.10　八叉树构造(Dan Ginsburg)　393
4.10.1　八叉树概述　393
4.10.2　八叉树数据　394
4.10.3　建立树　394
4.10.4　多边形重叠　395
4.10.5　相邻节点　396
4.10.6　应用　396
4.10.7　结论　396
4.10.8　参考文献　397
4.11　松散的八叉树(Thatcher Ulrich)　398
4.11.1　四叉树　398
4.11.2　包围体　399
4.11.3　划分物体　400
4.11.4　使它松散　402
4.11.5　比较　405
4.11.6　结论　406
4.12　独立于观察的渐进网格(Jan Svarovsky)　407
4.12.1　渐进网格概述　407
4.12.2　关于这个主题的变种　408
4.12.3　边缘选择函数　410
4.12.4　难处理的边　410
4.12.5　实现　411
4.12.6　源代码　414
4.12.7　参考文献　415
4.13　插值的3D关键帧动画(Herbert Marselas)　416
4.13.1　线性插值　416
4.13.2　对顶点和法线进行插值　418
4.13.3　Hermite样条插值　418
4.13.4　对顶点进行样条插值　420
4.13.5　为什么用Hermite样条　421
4.13.6　总结　421
4.13.7　参考文献　421
4.14　一种快速而简单的皮肤构造技术(Torgeir Hagland)　422
4.14.1　为什么对低多边形有价值　422
4.14.2　方法　422
4.14.3　总结　423
4.14.4　参考文献　426
4.15　填充间隙——使用缝合和皮肤构造的高级动画(Ryan Woodland)　427
4.15.1　缝合　428
4.15.2　皮肤构造(Skinning)　430
4.15.3　进一步的问题　432
4.15.4　参考文献　434
4.16　实时真实地形生成(Guy W. Lecky-Thompson)　434
4.16.1　风景设计　434
4.16.2　建筑物　439
4.16.3　命名算法　442
4.16.4　参考文献　446
4.17　分形地形生成——断层构造(Jason Shankel)　447
4.17.1　断层构造　447
4.17.2　减少dHeight　447
4.17.3　生成随机直线　448
4.17.4　腐蚀(erosion)　449
4.17.5　示例代码　450
4.17.6　参考文献　450
4.18　分形地形生成——中点置换(Jason Shankel)　451
4.18.1　一维中点置换　451
4.18.2　二维中点置换——菱形正方形算法　452
4.18.3　高地中的菱形——正方形算法　454
4.19　分形地形生成——粒子沉积(Jason Shankel)　455
4.19.1　MBE模型　455
4.19.2　粒子沉积　455
4.19.3　倒置火山口　457
4.19.4　示例代码　458
4.19.5　参考文献　458

第5章　像素特效
5.0　2D镜头光晕(Yossarian King)　461
5.0.1　方法　461
5.0.2　实现　462
5.0.3　源代码　464
5.1　将3D硬件用于2D子画面特效(Mason McCuskey)　465
5.1.1　进入3D　465
5.1.2　建立3D场景　465
5.1.3　建立纹理　466
5.1.4　绘制3D子画面　466
5.1.5　添加特效　468
5.1.6　结论　468
5.2　基于运动的静态光照(Steven Ranck)　469
5.2.1　传统的静态光照　469
5.2.2　基于运动的静态光照　472
5.2.3　结论　477
5.3　使用定点颜色插值模拟实时光照(Jorge Freitas)　478
5.3.1　光照方法　478
5.3.2　美工创作　479
5.3.3　插值光照　479
5.3.4　结论　480
5.4　衰减图(Sim Dietrich)　485
5.4.1　讲解　485
5.4.2　比较衰减图与光照图　488
5.4.3　CSG效果　489
5.4.4　基于范围的雾　489
5.4.5　其他形状　489
5.4.6　结论　489
5.5　使用纹理坐标生成技术的高级纹理(Ryan Woodland)　490
5.5.1　简单纹理坐标动画　490
5.5.2　纹理投影　490
5.5.3　反射映射　493
5.5.4　参考文献　494
5.6　硬件凹凸贴图(Sim Dietrich)　495
5.6.1　如何将凹凸图应用于对象上　495
5.6.2　为法线选择一个空间　496
5.6.3　另一种方法：使用正切空间凹凸贴图　496
5.6.4　解决方案：纹理空间凹凸贴图　498
5.6.5　纹理空间问题　499
5.6.6　结论　499
5.6.7　参考文献　500
5.7　底面阴影(Yossarian King)　501
5.7.1　阴影数学　501
5.7.2　实现　503
5.7.3　扩展　504
5.8　复杂对象上的实时阴影(Gabor Nagy)　505
5.8.1　介绍　505
5.8.2　光源、遮挡物体和接收物体　505
5.8.3　本文的目的　507
5.8.4　创建阴影图　507
5.8.5　在接收物体上投影阴影图　513
5.8.6　渲染接收物体　514
5.8.7　对基本算法的扩展与改进　514
5.8.8　参考文献　515
5.9　使用光滑预过滤和Fresnel项改善环境映射反射(Anis Ahmad)　516
5.9.1　第一个不正确的假设　516
5.9.2　第二个不正确的假设　518
5.9.3　结论　518
5.9.4　致谢　519
5.9.5　参考文献　519
5.10　游戏中玻璃的效果(Gabor Nagy)　520
5.10.1　介绍　520
5.10.2　透明物体　520
5.10.3　光栅化程序、帧缓冲、Z缓冲和像素混合　520
5.10.4　不透明物体与透明物体　521
5.10.5　绘制不透明物体　522
5.10.6　绘制透明物体　522
5.10.7　反射　525
5.10.8　有色玻璃　525
5.10.9　将它们放到一起　525
5.10.10　实现　526
5.10.11　参考文献　526
5.11　用于容器中液体的折射贴图(Alex Vlachos，Jason L. Mitchell)　527
5.11.1　介绍　527
5.11.2　折射项　527
5.11.3　反射项　528
5.11.4　Fresnel项　529
5.11.5　使用硬件渲染　529
5.11.6　该技术的扩展　530
5.11.7　结论　531
5.11.8　参考文献　531

第6章　附录
6.0　矩阵工具库(Dante Treglia II，Mark A. DeLoura)　535
6.1　文本工具库(Dante Treglia II)　537
6.2　关于随书光盘(Mark A. DeLoura)　538
作者索引　539