游戏编程精粹1 (2008 年度畅销榜NO.423 )

本书是由40多位国外游戏开发行业最为优秀的程序员撰稿的技术文集。每篇文章都针对游戏编程中的某个特定问题，不仅提供了解决思路，还给出了能立即应用到代码中的算法和源码。全书分为通用编程技术、数学技巧、人工智能、多边形技术和像素特效五章；附录部分提供了两个非常有用的工具库，矩阵工具库和文本工具库；随书附带光盘中包含有全书所有的源程序、演示程序、附录中的两个工具库以及glSetup和GLUT等开发工具。
本书适合游戏开发专业人员阅读。专家级开发人员可以立刻应用书中介绍的技巧，而初中级程序员通过阅读本书将增强其技能和知识。本书是游戏程序员必备的参考资料。

第1章 通用编程技术
1.0 神奇的数据驱动设计 3
Steve Rabin
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 面向对象的编程与设计技术 7
James Boer
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 使用模板元编程的快速数学方法 17
Pete Isensee
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工具 32
Scott Bilas
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 36
James Boer
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 一个通用的函数绑定接口 48
Scott Bilas
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 通用的基于句柄的资源管理器 58
Scott Bilas
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 资源和内存管理 69
James Boer
1.7.1 资源类 69
1.7.2 资源管理类 71
1.7.3 句柄如何工作 74
1.7.4 可能的扩展和改进 74
1.7.5 结论 75
1.8 快速数据载入技巧 76
John Olsen
1.8.1 预处理你的数据 76
1.8.2 保存你的数据 76
1.8.3 使用简单方法载入你的数据 77
1.8.4 更安全地载入你的数据 78
1.9 基于帧的内存分配 80
Steven Ranck
1.9.1 常规内存分配的挑战 80
1.9.2 介绍基于帧的内存 80
1.9.3 分配和释放内存 82
1.9.4 例子 84
1.9.5 结论 86
1.10 简单快速的位数组 87
Andrew Kirmse
1.10.1 概述 87
1.10.2 位数组 87
1.10.3 其他数组 88
1.10.4 应用 89
1.10.5 参考文献 89
1.11 在线游戏的网络协议 90
Andrew Kirmse
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 94
Steve Rabin
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：实时统计和游戏内调试 99
John Olsen
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 实时的游戏内建剖析 103
Steve Rabin
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 可预测随机数 117
Guy W. Lecky-Thompson
2.0.1 可预测随机数 117
2.0.2 替换算法 119
2.0.3 无限宇宙算法 120
2.0.4 结论与展望 122
2.0.5 参考文献 123
2.1 插值方法 124
John Olsen
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 求刚体运动方程的积分 132
Miguel Gomez
2.2.1 运动学：平移和旋转 132
2.2.2 动力学：力与旋转力矩（torque） 135
2.2.3 刚体的特性 136
2.2.4 求运动方程的积分 139
2.2.5 参考文献 140
2.3 三角函数的多项式逼近 141
Eddie Edwards
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 为数字稳定性而利用隐式欧拉积分 155
Miguel Gomez
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 小波：理论与压缩 160
Loïc Le Chevalier
2.5.1 原理 160
2.5.2 一个实例 162
2.5.3 应用 162
2.5.4 参考文献 163
2.6 水面的交互式模拟 164
Miguel Gomez
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 游戏编程四元数 171
Jan Svarovsky
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 矩阵和四元数之间的转换 175
Jason Shankel
2.8.1 四元数旋转 175
2.8.2 四元数到矩阵的转换 175
2.8.3　矩阵到四元数的转换 177
2.8.4　参考文献 178
2.9 四元数插值 179
Jason Shankel
2.9.1 四元数计算 179
2.9.2 四元数插值 179
2.9.3　示例代码 182
2.9.4 推导 182
2.10 最短弧四元数 186
Stan Melax
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引擎 193
Steve Rabin
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 一个有限状态机类 208
Eric Dybsand
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 博弈树 220
Jan Svarovsky
3.2.1　极小极大算法的负极大改进算法 221
3.2.2　 剪枝 222
3.2.3　走步排序方法 223
3.2.4　 求精 224
3.2.5 参考文献 224
3.3 A*路径规划基础 225
Bryan Stout
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*审美优化 233
Steve Rabin
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*速度优化 240
Steve Rabin
3.5.1 搜索空间优化 240
3.5.2 算法优化 244
3.5.3　结论 248
3.5.4 参考文献 253
3.6 简化的3D运动和使用导航网格进行寻径 254
Greg Snook
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：一种模拟群体行为的简单技术 270
Steven Woodcock
3.7.1 实现 271
3.7.2 代码 273
3.7.3 局限性与可能的改进 276
3.7.4 资源与致谢 282
3.8 用于视频游戏的模糊逻辑 283
Mason McCuskey
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 神经网络初探 292
André LaMothe
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优化顶点提交 313
Herbert Marselas
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 调整顶点的投影深度值 320
Eric Lengyel
4.1.1 考察投影矩阵 320
4.1.2 矫正深度值 321
4.1.3　选择一个适当的 321
4.1.4　实现 323
4.1.5　源代码 323
4.2 矢量摄像机 324
David Paull
4.2.1 矢量摄像机初步 325
4.2.2 本地空间优化 326
4.2.3 结论 327
4.3 摄像机控制技术 328
Dante Treglia II
4.3.1 一种基本的第一人称摄像机 328
4.3.2　脚本摄像机 330
4.3.3　摄像机技巧 333
4.4 一种快速的圆柱棱台相交测试算法 337
Eric Lengyel
4.4.1 视域棱台 337
4.4.2 计算有效半径 338
4.4.3 算法 339
4.4.4 实现 341
4.5 3D碰撞检测 346
Kevin Kaiser
4.5.1 算法概述 346
4.5.2 包围球碰撞检测 346
4.5.3 三角形对三角形的碰撞检测 348
4.6 用于交互检测的多分辨率地图 358
Jan Svarovsky
4.6.1 使用栅格 358
4.6.2 对象大小变化的问题 358
4.6.3　多分辨率地图 359
4.6.4 源代码 360
4.7 计算到区域内部的距离 368
Steven Ranck
4.7.1 问题 368
4.7.2 算法描述 369
4.7.3　应用 371
4.8 对象阻塞剔除 376
Tim Round
4.8.1 可视棱台裁剪 376
4.8.2 阻塞剔除 378
4.8.3　总结 379
4.9 永远不要让他们看到你的“抖动”——几何体细节层次选择问题 387
Yossarian King
4.9.1 LOD选择 387
4.9.2　放大率因子 389
4.9.3　滞变阈值 389
4.9.4 实现 390
4.9.5 其他问题 391
4.10 八叉树构造 393
Dan Ginsburg
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 松散的八叉树 398
Thatcher Ulrich
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 独立于观察的渐进网格 407
Jan Svarovsky
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关键帧动画 416
Herbert Marselas
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 一种快速而简单的皮肤构造技术 422
Torgeir Hagland
4.14.1 为什么对低多边形有价值 422
4.14.2 方法 422
4.14.3 总结 423
4.14.4 参考文献 426
4.15 填充间隙——使用缝合和皮肤构造的高级动画 427
Ryan Woodland
4.15.1 缝合 428
4.15.2 皮肤构造（Skinning） 430
4.15.3 进一步的问题 432
4.15.4 参考文献 434
4.16 实时真实地形生成 434
Guy W. Lecky-Thompson
4.16.1 风景设计 434
4.16.2 建筑物 439
4.16.3　命名算法 442
4.16.4 参考文献 446
4.17 不规则地形生成——断层构造 447
Jason Shankel
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 不规则地形生成——中点置换 451
Jason Shankel
4.18.1 一维中点置换 451
4.18.2 二维中点置换——菱形正方形算法 452
4.18.3 高地中的菱形——正方形算法 454
4.19 不规则地形生成——粒子沉积 455
Jason Shankel
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镜头光晕 461
Yossarian King
5.0.1 方法 461
5.0.2 实现 462
5.0.3 源代码 464
5.1 将3D硬件用于2D子画面特效 465
Mason McCuskey
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 基于运动的静态光照 469
Steven Ranck
5.2.1 传统的静态光照 469
5.2.2 基于运动的静态光照 472
5.2.3 结论 477
5.3 使用定点颜色插值模拟实时光照 478
Jorge Freitas
5.3.1 光照方法 478
5.3.2 美工创作 479
5.3.3 插值光照 479
5.3.4 结论 480
5.4 衰减图 485
Sim Dietrich
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 使用纹理坐标生成技术的高级纹理 490
Ryan Woodland
5.5.1 简单纹理坐标动画 490
5.5.2 纹理投影 490
5.5.3 反射映射 493
5.5.4 参考文献 494
5.6 硬件凹凸贴图 495
Sim Dietrich
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 底面阴影 501
Yossarian King
5.7.1 阴影数学 501
5.7.2 实现 503
5.7.3 扩展 504
5.8 复杂对象上的实时阴影 505
Gabor Nagy
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项改善环境映射反射 516
Anis Ahmad
5.9.1 第一个不正确的假设 516
5.9.2 第二个不正确的假设 518
5.9.3 结论 518
5.9.4 致谢 519
5.9.5 参考文献 519
5.10 游戏中玻璃的效果 520
Gabor Nagy
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 用于容器中液体的折射贴图 527
Alex Vlachos，Jason L. Mitchell
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 矩阵工具库 534
Dante Treglia II，Mark A. DeLoura
6.1 文本工具库 536
Dante Treglia II
6.2 关于随书光盘 537
Mark A. DeLoura
作者索引 539

Mark是“游戏编程精粹”系列丛书的创始人，是《游戏编程精粹1》和《游戏编程精粹2》的主编。他现在任职于索尼（美国）计算机娱乐公司，职位是开发人员协调经理，正在努力引导开发人员达到SIMD的理想境界。他曾在任天堂（美国）公司当过主力软件工程师，“耕耘”代码；亦有过在Game Developer杂志担任主编，剪裁文章的经历。Mark现在仍然是虚拟现实的“铁杆球迷”，他仍将实时在线，在多玩家第一人称视角游戏里面与你对战。