游戲編程精粹（4）

第1章　通用編程
簡介　Chris Corry　2
1.1　調(diào)試游戲程序的學問　Steve Rabin　4
1.1.1　五步調(diào)試法　4
1.1.2　第一步：始終如一地重現(xiàn)問題　4
1.1.3　第二步：搜集線索　5
1.1.4　第三步：查明錯誤的源頭　6
1.1.5　第四步：糾正問題　7
1.1.6　第五步：對所作的修改進行測試　7
1.1.7　高級調(diào)試技巧　8
1.1.8　困難的調(diào)試情景和模式　10
1.1.9　理解底層系統(tǒng)　12
1.1.10　增加有助于調(diào)試的基礎設施　12
1.1.11　預防bug　13
1.1.12　結論　14
1.1.13　致謝　15
1.1.14　參考文獻　15
1.2　一個基于HTML的日志和調(diào)試系統(tǒng)　James Boer　16
1.2.1　于日志系統(tǒng)的優(yōu)勢　16
1.2.2　究竟什么是事件日志？　16
1.2.3　HTML和調(diào)用堆棧　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　時鐘系統(tǒng)的組成　24
1.3.3　避免失真　25
1.3.4　結論　29
1.4　設計和維護大型跨平臺庫　David Etherton　30
1.4.1　設計　30
1.4.2　Build系統(tǒng)　32
1.4.3　細節(jié)　33
1.4.4　結論　35
1.4.5　參考文獻　35
1.5　利用模版化的空閑塊列表克服內(nèi)存碎片問題　Paul Glinker　36
1.5.1　內(nèi)存操作　36
1.5.2　解決方案　37
1.5.3　實現(xiàn)細節(jié)　37
1.5.4　有效地使用我們的Freelist　40
1.5.5　結論　40
1.5.6　參考文獻　41
1.6　一個用C++實現(xiàn)的泛型樹容器類　Bill Budge　42
1.6.1　可重用的庫　42
1.6.2　樹的概念　43
1.6.3　樹的實現(xiàn)　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　游戲中的實體管理系統(tǒng)　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　基于消息的游戲循環(huán)　65
1.8.7　開始：消息類　65
1.8.8　從小處著手：基本實體消息　66
1.8.9　游戲和環(huán)境消息　67
1.8.10　系統(tǒng)成長：一些高級消息　67
1.8.11　處理碰撞　69
1.8.12　擴展到多玩家　69
1.8.13　開發(fā)和調(diào)試消息　70
1.8.14　好處　70
1.8.15　光盤中的內(nèi)容　71
1.8.16　總結　71
1.9　Windows和Xbox平臺上地址空間受控的動態(tài)數(shù)組　Matt Pritchard　72
1.9.1　傳統(tǒng)的動態(tài)數(shù)組管理　72
1.9.2　深入觀察　73
1.9.3　地址空間管理 != 存儲管理　73
1.9.4　重新思考關于數(shù)組增大的問題　74
1.9.5　新的增長規(guī)則　74
1.9.6　使用地址空間受控的數(shù)組　75
1.9.7　結論　79
1.10　用臨界阻尼實現(xiàn)慢入慢出的平滑　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　對象管理的傳統(tǒng)做法　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　“函數(shù)”屬性　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章　數(shù)學
簡介　Jonathan Blow　118
2.1　使用馬其賽特旋轉(zhuǎn)的Zobrist散列法　Toby Jones　120
2.1.1　Zobrist散列　120
2.1.2　實現(xiàn)Zobrist散列　121
2.1.3　馬其賽特旋轉(zhuǎn)(Mersenne Twister)　122
2.1.4　馬其賽特旋轉(zhuǎn)的實現(xiàn)　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　實現(xiàn)　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　計算起始和最終節(jié)點速率　152
2.4.7　在樣條上獲取速率和加速度　153
2.4.8　優(yōu)化　153
2.4.9　結論　153
2.4.10　參考文獻　154
2.5　用協(xié)方差矩陣計算更貼切的包圍對象　Jim Van Verth　155
2.5.1　協(xié)方差矩陣　155
2.5.2　特征值和特征向量　158
2.5.3　計算協(xié)方差矩陣的特征向量　159
2.5.4　創(chuàng)建包圍對象　159
2.5.5　結論　161
2.5.6　參考文獻　162
2.6　應用于反向運動的雅可比轉(zhuǎn)置方法　Marco Spoerl　163
2.6.1　我們的測試環(huán)境　163
2.6.2　雅可比矩陣是什么？　164
2.6.3　雅可比轉(zhuǎn)置矩陣簡介　165
2.6.4　實現(xiàn)算法　166
2.6.5　結果和比較　168
2.6.6　結論　171
2.6.7　參考文獻　171
第3章　物理
簡介　Graham Rhodes　174
3.1　死神的十指：戰(zhàn)斗中的命中算法　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　化學武器、火球及區(qū)域性魔法　182
3.1.8　彈片的楔入　182
3.1.9　攻擊叢林　183
3.1.10　攻擊有獵物分布的叢林　183
3.1.11　結論　184
3.1.12　參考文獻　184
3.2　在低速CPU系統(tǒng)中交通工具的物理模擬　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　實現(xiàn)中遇到的問題　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　創(chuàng)建有用的游戲約束器　205
3.4.4　光盤中的內(nèi)容　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　對持續(xù)性的詳細分析　217
3.5.5　結論　217
3.5.6　參考文獻　218
3.6　互動水面　Jerry Tessendorf　219
3.6.1　線性的波浪　220
3.6.2　垂直導數(shù)操作符　221
3.6.3　波浪的傳播　222
3.6.4　可以互動的障礙物及其發(fā)生源　224
3.6.5　環(huán)境波浪　225
3.6.6　網(wǎng)格的邊界　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　使用分層的質(zhì)量塊彈簧物理的快速變形　230
3.7.3　結論　235
3.7.4　參考文獻　2363.8　快速且穩(wěn)定的形變之模態(tài)分析　James F. O'Brien　237
3.8.1　模式分解　239
3.8.2　模式的理解和丟棄　241
3.8.3　模態(tài)模擬　242
3.8.4　總結　244
3.8.5　結論　244
3.8.6　參考文獻　245
第4章　人工智能
簡介　Paul Tozour　248
4.1　第三人稱視角攝像鏡頭的運動規(guī)則　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　敘述戰(zhàn)斗：利用AI增強動作游戲中的張力　Borut Pfeifer　260
4.2.1　戲劇張力　260
4.2.2　系統(tǒng)概述　263
4.2.3　設計者的控制部分　263
4.2.4　難度計算　264
4.2.5　難度調(diào)節(jié)　265
4.2.6　系統(tǒng)評價　266
4.2.7　結論　267
4.2.8　參考文獻　267
4.3　非玩家角色決策：處理隨機問題　Karén Pivazyan　268
4.3.1　概要　268
4.3.2　動態(tài)規(guī)劃算法　269
4.3.3　代碼　273
4.3.4　優(yōu)化　275
4.3.5　DP算法的其他應用　275
4.3.6　結論　276
4.3.7　參考文獻　276
4.4　一個基于效用的面向?qū)ο鬀Q策架構　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　動態(tài)曲線　295
4.6.6　點、線、面　297
4.6.7　AI控制的層次　298
4.6.8　動畫系統(tǒng)的交互　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　利用可編程圖形硬件處理人工神經(jīng)元網(wǎng)絡　Thomas Rolfes　308
4.8.1　CPU與GPU系統(tǒng)架構　308
4.8.2　人工神經(jīng)元網(wǎng)絡　309
4.8.3　實現(xiàn)　310
4.8.4　結論　311
4.8.5　參考文獻　311
第5章　圖形圖像
簡介　Alex Vlachos　314
5.1　具有海報質(zhì)量的屏幕截圖　Steve Rabin　316
5.1.1　提高分辨率　316
5.1.2　提升像素質(zhì)量　318
5.1.3　使用一個磁盤均衡采樣分布　320
5.1.4　為抗鋸齒調(diào)整像素的采樣寬度　321
5.1.5　增加分辨率同增加像素質(zhì)量相結合　321
5.1.6　結論　323
5.1.7　參考文獻　324
5.2　非封閉網(wǎng)絡模型的GPU容積陰影構架　Warrick Buchanan　325
5.2.1　回到制圖板　325
5.2.2　在頂點陰影中實現(xiàn)這項技術　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　實現(xiàn)　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級的陰影中的實現(xiàn)　351
5.4.8　結論　353
5.4.9　參考文獻　353
5.5　在場景中投射靜態(tài)陰影　Alex Vlachos　355
5.5.1　前期工作　355
5.5.2　光束基本知識　355
5.5.3　高級算法　356
5.5.4　T型連接　357
5.5.5　網(wǎng)格模型最優(yōu)算法　358
5.5.6　實現(xiàn)細節(jié)　359
5.5.7　陰影中的動態(tài)物體　360
5.5.8　結果　360
5.5.9　結論　361
5.5.10　參考文獻　361
5.6　為陰影體和優(yōu)化的網(wǎng)格模型調(diào)整實時光照　Alex Vlachos、Chris Oat　362
5.6.1　光照問題　362
5.6.2　在面法線上操作　362
5.6.3　調(diào)整漫射光照　364
5.6.4　結論　366
5.6.5　參考文獻　366
5.7　實時半調(diào)色法：快速而簡單的樣式化陰影　Bert Freudenberg、Maic Masuch、Thomas Strothotte　367
5.7.1　引言　367
5.7.2　原理　368
5.7.3　實例的實現(xiàn)　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　光盤中的內(nèi)容　379
5.8.5　結論　379
5.9　快速的棕褐色色調(diào)轉(zhuǎn)換　Marwan Y. Ansari　380
5.9.1　背景　380
5.9.2　常規(guī)的方法　380
5.9.3　優(yōu)化　381
5.9.4　結論　382
5.9.5　參考文獻　382
5.10　使用場景亮度采樣實現(xiàn)動態(tài)的Gamma　 Michael Dougherty、Dave McCoy　383
5.10.1　光照系數(shù)　383
5.10.2　有限的動態(tài)范圍　383
5.10.3　圖像的優(yōu)化　384
5.10.4　易變的光靈敏度　385
5.10.5　轉(zhuǎn)換　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　用四元數(shù)的硬件蒙皮　Jim Hejl　401
5.12.1　蒙皮的概念　402
5.12.2　四元數(shù)參數(shù)化　404
5.12.3　硬件實現(xiàn)　405
5.12.4　結論　407
5.12.5　參考文獻　407
5.13　動作捕捉數(shù)據(jù)的壓縮　Sφren Hannibal　409
5.13.1　處理的計劃　409
5.13.2　組織數(shù)據(jù)通道　410
5.13.3　減少已儲存的鍵的數(shù)量　410
5.13.4　包裝剩余的鍵　412
5.13.5　運行時解壓縮　412
5.13.6　未來的改進　413
5.13.7　結論　413
5.13.8　參考文獻　413
5.14　基于骨骼的有關節(jié)的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　使它成為動態(tài)的　432
5.15.13　未來的方向　433
5.15.14　結論　433
5.15.15　參考文獻　433
第6章　網(wǎng)絡和多人游戲
簡介 Pete Isensee　436
6.1　設計與開發(fā)游戲大廳　Shekhar Dhupelia　437
6.1.1　狀態(tài)-事件系統(tǒng)的設計　437
6.1.2　探討大廳的子系統(tǒng)　438
6.1.3　高級大廳子系統(tǒng)　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　大型多人游戲狀態(tài)的有效存儲　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　在客戶/服務器環(huán)境下運用并行狀態(tài)機　Jay Lee　461
6.4.1　獨立狀態(tài)　461
6.4.2　角色狀態(tài)管理器　463
6.4.3　使用CharacterStateMgr　464
6.4.4　保持客戶端和服務器端的同步　464
6.4.5　狀態(tài)依賴的子系統(tǒng)　466
6.4.6　結論　467
6.4.7　參考文獻　467
6.5　位打包：一種網(wǎng)絡壓縮技術　Pete Isensee　468
6.5.1　一個實例　468
6.5.2　難點　469
6.5.3　位打包　469
6.5.4　用于可打包數(shù)據(jù)類型的通用接口　471
6.5.5　用于可打包數(shù)據(jù)類型的具體接口　471
6.5.6　編解碼器　472
6.5.7　評價折衷　473
6.5.8　改進　473
6.5.9　結論　473
6.5.10　參考文獻　474
6.6　多服務器網(wǎng)絡游戲的時間和同步管理　石衛(wèi)東(Larry Shi)、Tao Zhang　475
6.6.1　為什么需要時間和同步管理　475
6.6.2　時鐘同步　475
6.6.3　同步和響應　476
6.6.4　用多時間管理來一石二鳥地實現(xiàn)同步和響應　476
6.6.5　實現(xiàn)　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的實現(xiàn)　493
7.1.3　實現(xiàn)一致性指南　495
7.1.4　未來OpenAL的發(fā)展藍圖　496
7.1.5　總結　496
7.1.6　參考文獻　496
7.2　簡單的實時Lip-Synching系統(tǒng)　Jake Simpson　497
7.2.1　實現(xiàn)　497
7.2.2　動畫方面需要注意的事項　498
7.2.3　聲音音量的水印標記　499
7.2.4　注意　500
7.2.5　總結　500
7.3　動態(tài)變量和音頻編程　James Boer　501
7.3.1　動態(tài)變量是什么？　501
7.3.2　動態(tài)變量類　501
7.3.3　在音頻編程中使用動態(tài)變量　503
7.3.4　其他改進　506
7.3.5　結論　506
7.3.6　參考文獻　506
7.4　創(chuàng)建一個音頻腳本系統(tǒng)　Borut Pfeifer　507
7.4.1　游戲中音頻的類別　508
7.4.2　工具　510
7.4.3　基于XML的音頻標記庫　510
7.4.4　腳本系統(tǒng)組件　512
7.4.5　進一步的工作　515
7.4.6　總結　515
7.4.7　參考文獻　515
7.5　使用EAX和ZoomFX API的環(huán)境音效解決方案　Scott Velasquez　516
7.5.1　什么是環(huán)境音效　516
7.5.2　音頻引擎的系統(tǒng)要求　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　對象材質(zhì)的影響　533
7.6.6　撞擊和碰撞　533
7.6.7　演示　533
7.6.8　總結　534
7.6.9　參考文獻　534
附錄　536