游戏编程精粹

第1章　通用编程

简介　2

Adam Lake

1.1　Lock-Free算法　4

Toby Jones

1.1.1　Compare-And-Swap及其他通用原语　4

1.1.2　Lock-Free参数化的堆栈　6

1.1.3　Lock-Free参数化的队列　9

1.1.4　Lock-Free参数化的Freelist　11

1.1.5　总结　13

1.1.6　参考文献　13

1.1.7　相关资源　14

1.2　通过OpenMP来充分利用多核处理器的能力　15

Pete Isensee

1.2.1　OpenMP应用实例：粒子系统　15

1.2.2　好处　16

1.2.3　性能　16

1.2.4　OpenMP应用实例：碰撞检测　17

1.2.5　线程组　18

1.2.6　函数的并行化　18

1.2.7　缺陷　19

1.2.8　结论　20

1.2.9　参考文献　21

1.2.10　相关资源　21

1.3　用OpenCV库实现游戏中的计算机视觉　22

Arnau Ramisa、Enric Vergara、Enric Marti

1.3.1　引子　22

1.3.2　游戏中的计算机视觉　22

1.3.3　开放的计算机视觉库　22

1.3.4　计算机视觉在游戏中一个简单的应用　23

1.3.5　未来的工作　31

1.3.6　参考文献　31

1.4　游戏对象的地理网格注册　33

Roger Smith

1.4.1　引子　33

1.4.2　四叉树和八叉树　34

1.4.3　游戏对象的组织形式　35

1.4.4　总结　39

1.4.5　参考文献　39

1.5　BSP技术　40

Octavian Marius Chincisan

1.5.1　什么是BSP？为什么要使用BSP？　40

1.5.2　基于节点的BSP　41

1.5.3　渲染一个基于节点的BSP树　43

1.5.4　基于节点的BSP树(不进行分割)　43

1.5.5　凸状叶子BSP树　44

1.5.6　凸状叶子BSP树出入口生成　47

1.5.7　凸状叶子BSP树潜在可视集　48

1.5.8　PVS压缩　51

1.5.9　地形BSP　53

1.5.10　总结　53

1.5.11　参考文献　54

1.6　最相似字串匹配算法　55

James Boer

1.6.1　基于字符串的ID查找难题　55

1.6.2　问题的定义　56

1.6.3　现有的一些解决方案　56

1.6.4　我们自己定制的字串匹配解决方案　56

1.6.5　解决方案的实际应用　62

1.6.6　总结　63

1.6.7　参考文献　63

1.7　利用CppUnit实现单元测试　64

Blake Madden

1.7.1　单元测试技术概览　64

1.7.2　CppUnit概述　65

1.7.3　运行测试夹具　67

1.7.4　利用CppUnit进行模型类测试　68

1.7.5　私有函数的单元测试　74

1.7.6　用CppUnit测试底层功能　75

1.7.7　总结　79

1.7.8　参考文献　80

1.8　为游戏的预发布版本添加数字指纹，威慑并侦测盗版行为　81

Steve Rabin

1.8.1　威慑策略　81

1.8.2　利用水印和指纹来进行侦测　82

1.8.3　添加数字指纹的流程　83

1.8.4　数字指纹添加过程的安全性　83

1.8.5　数字指纹的添加策略　83

1.8.6　破解数字指纹　85

1.8.7　总结　86

1.8.8　参考文献　86

1.9　通过基于访问顺序的二次文件排序，实现更快速的文件加载　87

David Koenig

1.9.1　问题的提出　87

1.9.2　解决方案　88

1.9.3　基于访问的二次文件排序的工作流程　89

1.9.4　优化效果　90

1.9.5　影响最终优化结果的因素　90

1.9.6　潜在的问题　91

1.9.7　其他一些通用的最佳实践方法　91

1.9.8　总结　92

1.9.9　参考文献　92

1.10　你不必退出游戏：资产热加载技术可以实现快速的反复调整　93

Charles Nicholson

1.10.1　资产热加载的工作流程　93

1.10.2　资产热加载过程的剖析　94

1.10.3　实际应用中需要考虑的事项　97

1.10.4　示范程序　98

1.10.5　总结　99

1.10.6　进阶参阅　99

第2章　数学与物理

简介　　102

Jim Van Verth

2.1　浮点编程技巧　104

Chris Lomont

2.1.1　浮点数的格式　105

2.1.2　例程的设计　108

2.1.3　总结　117

2.1.4　参考文献　118

2.2　利用齐次坐标实现投影空间中的GPU计算　119

Vaclav Skala

2.2.1　相关的数学背景知识　119

2.2.2　利用齐次坐标进行计算　121

2.2.3　直线交叉　124

2.2.4　总结　125

2.2.5　附录A　125

2.2.6　附录B　126

2.2.7　致谢　127

2.2.8　参考文献　127

2.3　利用叉乘积求解线性方程组　128

Anders Hast

2.3.1　简介　128

2.3.2　隐式直线　130

2.3.3　高效的扫描转换的设置运算　132

2.3.4　求解三元一次方程组　134

2.3.5　总结　135

2.3.6　致谢　135

2.3.7　参考文献　135

2.4　适用于游戏开发的序列索引技术　137

Palem GopalaKrishna

2.4.1　相关术语　137

2.4.2　序列　138

2.4.3　范围序列　139

2.4.4　排列序列　142

2.4.5　组合序列　144

2.4.6　总结　147

2.4.7　参考文献　149

2.5　多面体浮力的精确计算　150

Erin Catto

2.5.1　浮力　150

2.5.2　多边形的面积　152

2.5.3　多面体的体积　153

2.5.4　物体部分没入水中的情况　154

2.5.5　算法的鲁棒性　157

2.5.6　阻力　158

2.5.7　关于源代码　159

2.5.8　总结　159

2.5.9　致谢　159

2.5.10　参考文献　159

2.6　带有刚体交互作用的基于粒子的实时流体仿真系统　161

Takashi Amada

2.6.1　流体仿真与平滑粒子的流体动力学　161

2.6.2　扩展SPH方法，以支持流体和刚体的交互作用　165

2.6.3　与动态刚体的交互作用：仿真更新　169

2.6.4　具体的实现细节　170

2.6.5　相关的优化　173

2.6.6　总结　174

2.6.7　参考文献　174

第3章　人工智能

引言　　176

Brain Schwab

3.1　游戏的制作方法——应用基于模型的决策——在雷神之锤III中应用蝗虫人工智能引擎　178

Armand Prieditis

Mukesh Dalal

3.1.1　引言　178

3.1.2　目前的游戏人工智能：基于规则　179

3.1.3　规则的问题　180

3.1.4　基于模型的游戏人工智能方法　182

3.1.5　对游戏的接口　182

3.1.6　对游戏人工智能开发者的好处和推论　183

3.1.7　雷神之锤III竞技场和蝗虫人工智能引擎　184

3.1.8　相关工作　185

3.1.9　结论和未来的工作　186

3.1.10　参考文献　186

3.2　独立非玩家角色合作行为的实现　187

Diego Garcés

3.2.1　可能的解决方案　187

3.2.2　非玩家角色的结构　189

3.2.3　合作的机制　189

3.2.4　例子：合作寻找玩家　194

3.2.5　结论　195

3.2.6　参考文献　195

3.3　针对游戏的基于行为的机器人架构　196

Hugo Pinto、Luis Otavio Alvares

3.3.1　包容体结构　196

3.3.2　扩展的行为网络　199

3.3.3　讨论　201

3.3.4　结论　201

3.3.5　参考文献　202

3.4　使用模糊感知器、有限状态自动机和扩展的行为网络为虚幻竞技场游戏构建一个目标驱动的机器人　203

Hugo Pinto、Luis Otavio Alvares

3.4.1　扩展的行为网络设计　203

3.4.2　层次模糊感知器　208

3.4.3　有限状态自动机行为模块　210

3.4.4　结论　211

3.4.5　参考文献　212

3.5　一个目标驱动的虚幻竞技场游戏角色程序：使用扩展的行为网络制作目标驱动的具有个性的代理　213

Hugo Pinto、Luis Otavio Alvares

3.5.1　扩展的行为网络　214

3.5.2　行为选择的质量　216

3.5.3　个性设计　218

3.5.4　结论　220

3.5.5　参考文献　221

3.6　用支持向量机为短期记忆建模　223

Julien Hamaide

3.6.1　支持向量机简介　223

3.6.2　短期记忆模型化　226

3.6.3　CPU的消耗限制　227

3.6.4　结论　228

3.6.5　参考文献　228

3.7　使用战力值评估模型进行战争役分析　229

Michael Ramsey

3.7.1　基本公式　229

3.7.2　计算兵力　230

3.7.3　计算潜在兵力　230

3.7.4　为武器效力进行建模　231

3.7.5　获得一个理论上的战争结局　232

3.7.6　关于CEV　232

3.7.7　一个QJM系统的例子　232

3.7.8　局限性　233

3.7.9　结论　234

3.7.10　参考文献　234

3.8　设计一个多层可插拔的AI引擎　235

Sebastien Schertenleib

3.8.1　相关工作　235

3.8.2　AI引擎架构　236

3.8.3　数据驱动类和属性　237

3.8.4　分优先级的任务管理器　240

3.8.5　性能问题和技术　241

3.8.6　工具　243

3.8.7　结论　244

3.8.8　参考文献　245

3.9　一个管理场景复杂度的模糊控制方法　247

Gabriyel Wong、Jialiang Wang

3.9.1　关键思想　247

3.9.2　为什么使用模糊控制？　247

3.9.3　工具　248

3.9.4　系统设计　249

3.9.5　游戏中的应用　251

3.9.6　假设　251

3.9.7　实现考虑　252

3.9.8　测试和结果　252

3.9.9　结论　254

3.9.10　致谢　254

3.9.11　参考文献　254

第4章　脚本和数据驱动系统

简介　　256

Graham Rhodes

4.1　脚本语言总述　258

Diego Garcés

4.1.1　为什么要使用脚本语言　258

4.1.2　简介　258

4.1.3　语言编码　259

4.1.4　与C++的整合　262

4.1.5　性能特点　267

4.1.6　开发支持特点　269

4.1.7　总结　271

4.1.8　参考文献　271

4.2　把C++对象绑定到Lua　273

Waldemar Celes、Luiz Henrique de Figueiredo、Roberto Ierusalimschy

4.2.1　绑定函数　273

4.2.2　绑定宿主对象和Lua数值　276

4.2.3　绑定宿主对象和Lua对象　278

4.2.4　宿主和Lua表绑定　282

4.2.5　总结　283

4.2.6　参考文献　285

4.3　使用LUA协同程序实现高级控制机制　286

Luiz Henrique de Figueiredo、Waldemar Celes、Roberto Ierusalimschy

4.3.1　Lua协同程序　286

4.3.2　过滤器　287

4.3.3　迭代器　288

4.3.4　任务安排　291

4.3.5　协作式多线程　291

4.3.6　总结　296

4.3.7　参考文献　296

4.4　在多线程环境里处理高级脚本执行　297

Sebastien Schertenleib

4.4.1　基于组件的软件和脚本的解释程序　297

4.4.2　协同程序与微线程程序　298

4.4.3　微线程管理器　298

4.4.4　嵌入Python　300

4.4.5　试验和结果　304

4.4.6　总结　305

4.4.7　参考文献　305

4.5　使用非插入型代理导出角色属性　306

Matthew Campbell、Curtiss Murphy

4.5.1　角色、代理和属性　306

4.5.2　非插入型和动态体系结构　308

4.5.3　角色属性　308

4.5.4　角色代理　311

4.5.5　从理论到实践　313

4.5.6　总结　314

4.5.7　参考文献　314

4.6　基于组件的游戏对象系统　315

Chris Stoy

4.6.1　游戏对象　315

4.6.2　基本的游戏对象组件　316

4.6.3　在游戏对象中实现组建管理　317

4.6.4　组件间的通信　319

4.6.5　游戏组件模板　320

4.6.6　游戏对象模板　322

4.6.7　数据驱动的游戏对象创建　323

4.6.8　总结　324

第5章　图形学

简介　　326

Paul Rowan

5.1　交互角色真实的静止动作合成　328

Arjan Egges， Thomas Di Giacomo和Nadia Magnenat-Thalmann

5.1.1　简介　328

5.1.2　人体动画的主分量　329

5.1.3　姿势变换　331

5.1.4　姿势的连续微小变化　334

5.1.5　总结　337

5.1.6　参考文献　337

5.2　用自适应二叉树进行空间剖分　339

Martin Fleisz

5.2.1　如何建立自适应二叉树　339

5.2.2　ABT实现细节　340

5.2.3　找到合适的分割面　343

5.2.4　在动态场景中使用ABT　345

5.2.5　渲染ABT　346

5.2.6　总结　347

5.2.7　致谢　348

5.2.8　参考文献　348

5.3　用有向包围盒增强对象裁减　349

Ben St. John

5.3.1　方法概要　349

5.3.2　传统技术　350

5.3.3　针对二维的有效解决方案　350

5.3.4　传统技术上的改进　352

5.3.5　对包围盒进行筛选　354

5.3.6　进一步改进　355

5.3.7　总结　356

5.3.8　参考文献　356

5.4　皮肤分离的优化渲染　357

Dominic Filion

5.4.1　简介　357

5.4.2　分割的概念　358

5.4.3　权重分割的启发式算法　359

5.4.4　骨骼调色板的启发式算法　359

5.4.5　启发式算法的细节　361

5.4.6　总结　364

5.5　GPU地形渲染　365

Harald Vistnes

5.5.1　算法　365

5.5.2　细节层次　366

5.5.3　避免裂缝　368

5.5.4　视锥体裁减　369

5.5.5　法线计算　369

5.5.6　碰撞检测　370

5.5.7　实现细节　370

5.5.8　运行结果　371

5.5.9　总结　372

5.5.10　参考文献　372

5.6　基于GPU的交互式流体动力学与渲染　373

Frank Luna

5.6.1　数学背景知识　374

5.6.2　GPU实现　376

5.6.3　流体互动　382

5.6.4　补充材料　383

5.6.5　总结　384

5.6.6　参考文献　384

5.7　基于多光源的快速逐像素光照渲染　386

Frank Puig Placeres

5.7.1　延迟解决方案　386

5.7.2　高端硬件的延迟着色实现　387

5.7.3　基本存储优化　389

5.7.4　着色器优化和硬件限制　391

5.7.5　扩展图像空间(Extending Image-Space)的后处理特效(Post-Processing Effects)　394

5.7.6　总结　394

5.7.7　参考文献　394

5.8　路标渲染的清晰化　395

J?rn Loviscach

5.8.1　反走样阈值划分纹理(Antialiasing Thresholded Textures)　396

5.8.2　阈值划分的优化纹理(Optimal Textures for Thresholding)　400

5.8.3　创作程序(The Authoring Application)　403

5.8.4　总结与展望　405

5.8.5　参考文献　405

5.9　天空渲染在游戏中的实际运用　407

Aurelio Reis

5.9.1　所需与所得相悖　407

5.9.2　天空的组成　408

5.9.3　瓶颈　409

5.9.4　立方体天空贴图概要　411

5.9.5　特殊时间　412

5.9.6　演示程序的黎明　413

5.9.7　进入地平线之下　414

5.9.8　总结　414

5.9.9　参考文献　415

5.10　基于OpenGL帧缓冲区对象的高动态范围渲染　416

Allen Sherrod

5.10.1　帧缓冲区对象简介　416

5.10.2　设置帧缓冲区对象　417

5.10.3　基于帧缓冲区对象的高动态范围渲染　419

5.10.4　总结　421

5.10.5　补充材料　421

5.10.6　参考文献　422

第6章　音频

简介　424

Alexander Brandon

6.1　由可变形网格(Deformable Meshes)实时生成声音　426

Marq Singer

6.1.1　对《游戏编程精粹4》的回顾　426

6.1.2　概述　427

6.1.3　对模态分析的简要回顾　427

6.1.4　声音要求　429

6.1.5　从变形到声音　429

6.1.6　总结　430

6.1.7　进一步阅读　430

6.1.8　参考文献　431

6.2　实时音效轻量级生成器　432

Frank Luchs

6.2.1　环境声引擎　432

6.2.2　声音合成　432

6.2.3　真实世界范例　434

6.2.4　总结　435

6.2.5　范例　436

6.2.6　参考文献　436

6.3　实时混音总线　437

James Boer

6.3.1　并非不重要的任务　437

6.3.2　实现音量总线链　438

6.3.3　以比率或分贝的形式来表示音量　440

6.3.4　执行效率问题　440

6.3.5　其他增强　441

6.3.6　总结　441

6.3.7　参考文献　441

6.4　可听集(Potentially Audible Sets)　442

Dominic Filion

6.4.1　PVS入门　442

6.4.2　PAS基础　443

6.4.3　直接声音路径　443

6.4.4　为门窗创建动态PAS　447

6.4.5　PAS扩展：传导(transmission)　448

6.4.6　PAS扩展：反射　449

6.4.7　总结　450

6.4.8　参考文献　450

6.5　一种开销较低的多普勒效果　451

Julien Hamaide

6.5.1　多普勒效果　451

6.5.2　编写多普勒效果程序　454

6.5.3　线性插值　454

6.5.4　根据R来计算下标　455

6.5.5　非恒定速度　456

6.5.6　信号对齐(Aliasing)　457

6.5.7　实现　457

6.5.8　总结　457

6.5.9　资源　458

6.6　仿造实时DSP效果　459

Robert Sparks

6.6.1　仿造　459

6.6.2　例子：收音机在房间中播放音乐　459

6.6.3　声音能量恒定曲线(Constant Power Volume Curve)　461

6.6.4　对声道音量进行进一步控制　461

6.6.5　在DirectSound中播放多声道文件　462

6.6.6　代价和好处　462

6.6.7　总结　462

6.6.8　致谢　462

第7章　网络及多人在线

简介　　464

Scott Jacobs

7.1　3D动画角色数据的动态自适应流　465

Thomas Di Giacomo、HyungSeok Kim、Stephane Garchery和Nadia Magnenat-Thalmann

Chris Joslin

7.1.1　简介　465

7.1.2　背景介绍与相关方法　465

7.1.3　处理可缩放3D数据的准备和实施　466

7.1.4　自适应数据的传输　471

7.1.5　总结　473

7.1.6　参考文献　473

7.2　大规模多人在线游戏基于复杂系统的高阶架构　475

Viknashavaran Narayanasamy、Kok-Wai Wong和Chun Che Fung

7.2.1　复杂系统和突发性事件　475

7.2.2　多重架构　476

7.2.3　基于回馈的决策系统　484

7.2.4　总结　485

7.2.5　参考文献　485

7.3　为游戏物件生成全局唯一标识符　487

Yongha Kim

7.3.1　游戏物件GUID建立的需求　487

7.3.2　生成GUID　488

7.3.3　对于特殊情况的处理　489

7.3.4　总结　490

7.3.5　参考文献　490

7.4　利用Second Life为大规模多人在线游戏原形设计游戏概念原形　491

Peter A. Smith

7.4.1　简介　491

7.4.2　为什么要用到Second Life　491

7.4.3　初试“第二人生(Second Life)”　494

7.4.4　在Second Life中的设计要点　495

7.4.5　原形的开发　496

7.4.6　一个成功的例子　498

7.4.7　总结　499

7.4.8　参考文献　499

7.5　稳定的P2P游戏TCP连接及敏感NAT　501

Larry Shi

7.5.1　问题　501

7.5.2　技术水平　502

7.5.3　方法　503

7.5.4　应用方面　507

7.5.5　局限性　507

7.5.6　结论　508

7.5.7　参考文献　508

读者将在本书中找到来自20多个国家和地区具有不同背景和专长的游戏专家所撰写的50多篇文章。本书是游戏编程精粹系列书的最新版本，内容涉及通用编程、数学和物理、人工智能、脚本和数据驱动系统、图形学、音频音效、网络与多人在线游戏，以及游戏测试和手机游戏等内容，具有较强的先进性和实用性。随书附带光盘中提供了全书所有的源程序、演示程序及需要的各种游戏开发的第三方工具。
　　因此，无论你是一个刚刚起步的游戏开发新手，还是资深业界专家，都能够在本书中找到灵感，增强洞察力及开发的技能。应用书中介绍的开发经验和技巧于实际项目中，将缩短开发时间，提高效率。

《游戏编程精粹GAME PROGRAMMING6》读者将在本书中找到来自20多个国家和地区具有不同背景和专长的游戏专家所撰写的50多篇文章。