游戲編程精粹6

第1章　通用編程
簡介　2
Adam Lake
1.1　Lock-Free算法　4
Toby Jones
1.1.1　Compare-And-Swap及其他通用原語　4
1.1.2　Lock-Free參數(shù)化的堆?！?
1.1.3　Lock-Free參數(shù)化的隊列　9
1.1.4　Lock-Free參數(shù)化的Freelist　11
1.1.5　總結(jié)　13
1.1.6　參考文獻(xiàn)　13
1.1.7　相關(guān)資源　14
1.2　通過OpenMP來充分利用多核處理器的能力　15
Pete Isensee
1.2.1　OpenMP應(yīng)用實例：粒子系統(tǒng)　15
1.2.2　好處　16
1.2.3　性能　16
1.2.4　OpenMP應(yīng)用實例：碰撞檢測　17
1.2.5　線程組　18
1.2.6　函數(shù)的并行化　18
1.2.7　缺陷　19
1.2.8　結(jié)論　20
1.2.9　參考文獻(xiàn)　21
1.2.10　相關(guān)資源　21
1.3　用OpenCV庫實現(xiàn)游戲中的計算機(jī)視覺　22
Arnau Ramisa、Enric Vergara、Enric Marti
1.3.1　引子　22
1.3.2　游戲中的計算機(jī)視覺　22
1.3.3　開放的計算機(jī)視覺庫　22
1.3.4　計算機(jī)視覺在游戲中一個簡單的應(yīng)用　23
1.3.5　未來的工作　31
1.3.6　參考文獻(xiàn)　31
1.4　游戲?qū)ο蟮牡乩砭W(wǎng)格注冊　33
Roger Smith
1.4.1　引子　33
1.4.2　四叉樹和八叉樹　34
1.4.3　游戲?qū)ο蟮慕M織形式　35
1.4.4　總結(jié)　39
1.4.5　參考文獻(xiàn)　39
1.5　BSP技術(shù)　40
Octavian Marius Chincisan
1.5.1　什么是BSP？為什么要使用BSP？　40
1.5.2　基于節(jié)點的BSP　41
1.5.3　渲染一個基于節(jié)點的BSP樹　43
1.5.4　基于節(jié)點的BSP樹(不進(jìn)行分割)　43
1.5.5　凸?fàn)钊~子BSP樹　44
1.5.6　凸?fàn)钊~子BSP樹出入口生成　47
1.5.7　凸?fàn)钊~子BSP樹潛在可視集　48
1.5.8　PVS壓縮　51
1.5.9　地形BSP　53
1.5.10　總結(jié)　53
1.5.11　參考文獻(xiàn)　54
1.6　最相似字串匹配算法　55
James Boer
1.6.1　基于字符串的ID查找難題　55
1.6.2　問題的定義　56
1.6.3　現(xiàn)有的一些解決方案　56
1.6.4　我們自己定制的字串匹配解決方案　56
1.6.5　解決方案的實際應(yīng)用　62
1.6.6　總結(jié)　63
1.6.7　參考文獻(xiàn)　63
1.7　利用CppUnit實現(xiàn)單元測試　64
Blake Madden
1.7.1　單元測試技術(shù)概覽　64
1.7.2　CppUnit概述　65
1.7.3　運行測試夾具　67
1.7.4　利用CppUnit進(jìn)行模型類測試　68
1.7.5　私有函數(shù)的單元測試　74
1.7.6　用CppUnit測試底層功能　75
1.7.7　總結(jié)　79
1.7.8　參考文獻(xiàn)　80
1.8　為游戲的預(yù)發(fā)布版本添加數(shù)字指紋，威懾并偵測盜版行為　81
Steve Rabin
1.8.1　威懾策略　81
1.8.2　利用水印和指紋來進(jìn)行偵測　82
1.8.3　添加數(shù)字指紋的流程　83
1.8.4　數(shù)字指紋添加過程的安全性　83
1.8.5　數(shù)字指紋的添加策略　83
1.8.6　破解數(shù)字指紋　85
1.8.7　總結(jié)　86
1.8.8　參考文獻(xiàn)　86
1.9　通過基于訪問順序的二次文件排序，實現(xiàn)更快速的文件加載　87
David Koenig
1.9.1　問題的提出　87
1.9.2　解決方案　88
1.9.3　基于訪問的二次文件排序的工作流程　89
1.9.4　優(yōu)化效果　90
1.9.5　影響最終優(yōu)化結(jié)果的因素　90
1.9.6　潛在的問題　91
1.9.7　其他一些通用的最佳實踐方法　91
1.9.8　總結(jié)　92
1.9.9　參考文獻(xiàn)　92
1.10　你不必退出游戲：資產(chǎn)熱加載技術(shù)可以實現(xiàn)快速的反復(fù)調(diào)整　93
Charles Nicholson
1.10.1　資產(chǎn)熱加載的工作流程　93
1.10.2　資產(chǎn)熱加載過程的剖析　94
1.10.3　實際應(yīng)用中需要考慮的事項　97
1.10.4　示范程序　98
1.10.5　總結(jié)　99
1.10.6　進(jìn)階參閱　99
第2章　數(shù)學(xué)與物理
簡介　　102
Jim Van Verth
2.1　浮點編程技巧　104
Chris Lomont
2.1.1　浮點數(shù)的格式　105
2.1.2　例程的設(shè)計　108
2.1.3　總結(jié)　117
2.1.4　參考文獻(xiàn)　118
2.2　利用齊次坐標(biāo)實現(xiàn)投影空間中的GPU計算　119
Vaclav Skala
2.2.1　相關(guān)的數(shù)學(xué)背景知識　119
2.2.2　利用齊次坐標(biāo)進(jìn)行計算　121
2.2.3　直線交叉　124
2.2.4　總結(jié)　125
2.2.5　附錄A　125
2.2.6　附錄B　126
2.2.7　致謝　127
2.2.8　參考文獻(xiàn)　127
2.3　利用叉乘積求解線性方程組　128
Anders Hast
2.3.1　簡介　128
2.3.2　隱式直線　130
2.3.3　高效的掃描轉(zhuǎn)換的設(shè)置運算　132
2.3.4　求解三元一次方程組　134
2.3.5　總結(jié)　135
2.3.6　致謝　135
2.3.7　參考文獻(xiàn)　135
2.4　適用于游戲開發(fā)的序列索引技術(shù)　137
Palem GopalaKrishna
2.4.1　相關(guān)術(shù)語　137
2.4.2　序列　138
2.4.3　范圍序列　139
2.4.4　排列序列　142
2.4.5　組合序列　144
2.4.6　總結(jié)　147
2.4.7　參考文獻(xiàn)　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　關(guān)于源代碼　159
2.5.8　總結(jié)　159
2.5.9　致謝　159
2.5.10　參考文獻(xiàn)　159
2.6　帶有剛體交互作用的基于粒子的實時流體仿真系統(tǒng)　161
Takashi Amada
2.6.1　流體仿真與平滑粒子的流體動力學(xué)　161
2.6.2　擴(kuò)展SPH方法，以支持流體和剛體的交互作用　165
2.6.3　與動態(tài)剛體的交互作用：仿真更新　169
2.6.4　具體的實現(xiàn)細(xì)節(jié)　170
2.6.5　相關(guān)的優(yōu)化　173
2.6.6　總結(jié)　174
2.6.7　參考文獻(xiàn)　174
第3章　人工智能
引言　　176
Brain Schwab
3.1　游戲的制作方法——應(yīng)用基于模型的決策——在雷神之錘III中應(yīng)用蝗蟲人工智能引擎　178
Armand Prieditis
Mukesh Dalal
3.1.1　引言　178
3.1.2　目前的游戲人工智能：基于規(guī)則　179
3.1.3　規(guī)則的問題　180
3.1.4　基于模型的游戲人工智能方法　182
3.1.5　對游戲的接口　182
3.1.6　對游戲人工智能開發(fā)者的好處和推論　183
3.1.7　雷神之錘III競技場和蝗蟲人工智能引擎　184
3.1.8　相關(guān)工作　185
3.1.9　結(jié)論和未來的工作　186
3.1.10　參考文獻(xiàn)　186
3.2　獨立非玩家角色合作行為的實現(xiàn)　187
Diego Garcés
3.2.1　可能的解決方案　187
3.2.2　非玩家角色的結(jié)構(gòu)　189
3.2.3　合作的機(jī)制　189
3.2.4　例子：合作尋找玩家　194
3.2.5　結(jié)論　195
3.2.6　參考文獻(xiàn)　195
3.3　針對游戲的基于行為的機(jī)器人架構(gòu)　196
Hugo Pinto、Luis Otavio Alvares
3.3.1　包容體結(jié)構(gòu)　196
3.3.2　擴(kuò)展的行為網(wǎng)絡(luò)　199
3.3.3　討論　201
3.3.4　結(jié)論　201
3.3.5　參考文獻(xiàn)　202
3.4　使用模糊感知器、有限狀態(tài)自動機(jī)和擴(kuò)展的行為網(wǎng)絡(luò)為虛幻競技場游戲構(gòu)建一個目標(biāo)驅(qū)動的機(jī)器人　203
Hugo Pinto、Luis Otavio Alvares
3.4.1　擴(kuò)展的行為網(wǎng)絡(luò)設(shè)計　203
3.4.2　層次模糊感知器　208
3.4.3　有限狀態(tài)自動機(jī)行為模塊　210
3.4.4　結(jié)論　211
3.4.5　參考文獻(xiàn)　212
3.5　一個目標(biāo)驅(qū)動的虛幻競技場游戲角色程序：使用擴(kuò)展的行為網(wǎng)絡(luò)制作目標(biāo)驅(qū)動的具有個性的代理　213
Hugo Pinto、Luis Otavio Alvares
3.5.1　擴(kuò)展的行為網(wǎng)絡(luò)　214
3.5.2　行為選擇的質(zhì)量　216
3.5.3　個性設(shè)計　218
3.5.4　結(jié)論　220
3.5.5　參考文獻(xiàn)　221
3.6　用支持向量機(jī)為短期記憶建模　223
Julien Hamaide
3.6.1　支持向量機(jī)簡介　223
3.6.2　短期記憶模型化　226
3.6.3　CPU的消耗限制　227
3.6.4　結(jié)論　228
3.6.5　參考文獻(xiàn)　228
3.7　使用戰(zhàn)力值評估模型進(jìn)行戰(zhàn)爭役分析　229
Michael Ramsey
3.7.1　基本公式　229
3.7.2　計算兵力　230
3.7.3　計算潛在兵力　230
3.7.4　為武器效力進(jìn)行建?！?31
3.7.5　獲得一個理論上的戰(zhàn)爭結(jié)局　232
3.7.6　關(guān)于CEV　232
3.7.7　一個QJM系統(tǒng)的例子　232
3.7.8　局限性　233
3.7.9　結(jié)論　234
3.7.10　參考文獻(xiàn)　234
3.8　設(shè)計一個多層可插拔的AI引擎　235
Sebastien Schertenleib
3.8.1　相關(guān)工作　235
3.8.2　AI引擎架構(gòu)　236
3.8.3　數(shù)據(jù)驅(qū)動類和屬性　237
3.8.4　分優(yōu)先級的任務(wù)管理器　240
3.8.5　性能問題和技術(shù)　241
3.8.6　工具　243
3.8.7　結(jié)論　244
3.8.8　參考文獻(xiàn)　245
3.9　一個管理場景復(fù)雜度的模糊控制方法　247
Gabriyel Wong、Jialiang Wang
3.9.1　關(guān)鍵思想　247
3.9.2　為什么使用模糊控制？　247
3.9.3　工具　248
3.9.4　系統(tǒng)設(shè)計　249
3.9.5　游戲中的應(yīng)用　251
3.9.6　假設(shè)　251
3.9.7　實現(xiàn)考慮　252
3.9.8　測試和結(jié)果　252
3.9.9　結(jié)論　254
3.9.10　致謝　254
3.9.11　參考文獻(xiàn)　254
第4章　腳本和數(shù)據(jù)驅(qū)動系統(tǒng)
簡介　　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　開發(fā)支持特點　269
4.1.7　總結(jié)　271
4.1.8　參考文獻(xiàn)　271
4.2　把C++對象綁定到Lua　273
Waldemar Celes、Luiz Henrique de Figueiredo、Roberto Ierusalimschy
4.2.1　綁定函數(shù)　273
4.2.2　綁定宿主對象和Lua數(shù)值　276
4.2.3　綁定宿主對象和Lua對象　278
4.2.4　宿主和Lua表綁定　282
4.2.5　總結(jié)　283
4.2.6　參考文獻(xiàn)　285
4.3　使用LUA協(xié)同程序?qū)崿F(xiàn)高級控制機(jī)制　286
Luiz Henrique de Figueiredo、Waldemar Celes、Roberto Ierusalimschy
4.3.1　Lua協(xié)同程序　286
4.3.2　過濾器　287
4.3.3　迭代器　288
4.3.4　任務(wù)安排　291
4.3.5　協(xié)作式多線程　291
4.3.6　總結(jié)　296
4.3.7　參考文獻(xiàn)　296
4.4　在多線程環(huán)境里處理高級腳本執(zhí)行　297
Sebastien Schertenleib
4.4.1　基于組件的軟件和腳本的解釋程序　297
4.4.2　協(xié)同程序與微線程程序　298
4.4.3　微線程管理器　298
4.4.4　嵌入Python　300
4.4.5　試驗和結(jié)果　304
4.4.6　總結(jié)　305
4.4.7　參考文獻(xiàn)　305
4.5　使用非插入型代理導(dǎo)出角色屬性　306
Matthew Campbell、Curtiss Murphy
4.5.1　角色、代理和屬性　306
4.5.2　非插入型和動態(tài)體系結(jié)構(gòu)　308
4.5.3　角色屬性　308
4.5.4　角色代理　311
4.5.5　從理論到實踐　313
4.5.6　總結(jié)　314
4.5.7　參考文獻(xiàn)　314
4.6　基于組件的游戲?qū)ο笙到y(tǒng)　315
Chris Stoy
4.6.1　游戲?qū)ο蟆?15
4.6.2　基本的游戲?qū)ο蠼M件　316
4.6.3　在游戲?qū)ο笾袑崿F(xiàn)組建管理　317
4.6.4　組件間的通信　319
4.6.5　游戲組件模板　320
4.6.6　游戲?qū)ο竽０濉?22
4.6.7　數(shù)據(jù)驅(qū)動的游戲?qū)ο髣?chuàng)建　323
4.6.8　總結(jié)　324
第5章　圖形學(xué)
簡介　　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　姿勢的連續(xù)微小變化　334
5.1.5　總結(jié)　337
5.1.6　參考文獻(xiàn)　337
5.2　用自適應(yīng)二叉樹進(jìn)行空間剖分　339
Martin Fleisz
5.2.1　如何建立自適應(yīng)二叉樹　339
5.2.2　ABT實現(xiàn)細(xì)節(jié)　340
5.2.3　找到合適的分割面　343
5.2.4　在動態(tài)場景中使用ABT　345
5.2.5　渲染ABT　346
5.2.6　總結(jié)　347
5.2.7　致謝　348
5.2.8　參考文獻(xiàn)　348
5.3　用有向包圍盒增強(qiáng)對象裁減　349
Ben St. John
5.3.1　方法概要　349
5.3.2　傳統(tǒng)技術(shù)　350
5.3.3　針對二維的有效解決方案　350
5.3.4　傳統(tǒng)技術(shù)上的改進(jìn)　352
5.3.5　對包圍盒進(jìn)行篩選　354
5.3.6　進(jìn)一步改進(jìn)　355
5.3.7　總結(jié)　356
5.3.8　參考文獻(xiàn)　356
5.4　皮膚分離的優(yōu)化渲染　357
Dominic Filion
5.4.1　簡介　357
5.4.2　分割的概念　358
5.4.3　權(quán)重分割的啟發(fā)式算法　359
5.4.4　骨骼調(diào)色板的啟發(fā)式算法　359
5.4.5　啟發(fā)式算法的細(xì)節(jié)　361
5.4.6　總結(jié)　364
5.5　GPU地形渲染　365
Harald Vistnes
5.5.1　算法　365
5.5.2　細(xì)節(jié)層次　366
5.5.3　避免裂縫　368
5.5.4　視錐體裁減　369
5.5.5　法線計算　369
5.5.6　碰撞檢測　370
5.5.7　實現(xiàn)細(xì)節(jié)　370
5.5.8　運行結(jié)果　371
5.5.9　總結(jié)　372
5.5.10　參考文獻(xiàn)　372
5.6　基于GPU的交互式流體動力學(xué)與渲染　373
Frank Luna
5.6.1　數(shù)學(xué)背景知識　374
5.6.2　GPU實現(xiàn)　376
5.6.3　流體互動　382
5.6.4　補(bǔ)充材料　383
5.6.5　總結(jié)　384
5.6.6　參考文獻(xiàn)　384
5.7　基于多光源的快速逐像素光照渲染　386
Frank Puig Placeres
5.7.1　延遲解決方案　386
5.7.2　高端硬件的延遲著色實現(xiàn)　387
5.7.3　基本存儲優(yōu)化　389
5.7.4　著色器優(yōu)化和硬件限制　391
5.7.5　擴(kuò)展圖像空間(Extending Image-Space)的后處理特效(Post-Processing Effects)　394
5.7.6　總結(jié)　394
5.7.7　參考文獻(xiàn)　394
5.8　路標(biāo)渲染的清晰化　395
J?rn Loviscach
5.8.1　反走樣閾值劃分紋理(Antialiasing Thresholded Textures)　396
5.8.2　閾值劃分的優(yōu)化紋理(Optimal Textures for Thresholding)　400
5.8.3　創(chuàng)作程序(The Authoring Application)　403
5.8.4　總結(jié)與展望　405
5.8.5　參考文獻(xiàn)　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　進(jìn)入地平線之下　414
5.9.8　總結(jié)　414
5.9.9　參考文獻(xiàn)　415
5.10　基于OpenGL幀緩沖區(qū)對象的高動態(tài)范圍渲染　416
Allen Sherrod
5.10.1　幀緩沖區(qū)對象簡介　416
5.10.2　設(shè)置幀緩沖區(qū)對象　417
5.10.3　基于幀緩沖區(qū)對象的高動態(tài)范圍渲染　419
5.10.4　總結(jié)　421
5.10.5　補(bǔ)充材料　421
5.10.6　參考文獻(xiàn)　422
第6章　音頻
簡介　424
Alexander Brandon
6.1　由可變形網(wǎng)格(Deformable Meshes)實時生成聲音　426
Marq Singer
6.1.1　對《游戲編程精粹4》的回顧　426
6.1.2　概述　427
6.1.3　對模態(tài)分析的簡要回顧　427
6.1.4　聲音要求　429
6.1.5　從變形到聲音　429
6.1.6　總結(jié)　430
6.1.7　進(jìn)一步閱讀　430
6.1.8　參考文獻(xiàn)　431
6.2　實時音效輕量級生成器　432
Frank Luchs
6.2.1　環(huán)境聲引擎　432
6.2.2　聲音合成　432
6.2.3　真實世界范例　434
6.2.4　總結(jié)　435
6.2.5　范例　436
6.2.6　參考文獻(xiàn)　436
6.3　實時混音總線　437
James Boer
6.3.1　并非不重要的任務(wù)　437
6.3.2　實現(xiàn)音量總線鏈　438
6.3.3　以比率或分貝的形式來表示音量　440
6.3.4　執(zhí)行效率問題　440
6.3.5　其他增強(qiáng)　441
6.3.6　總結(jié)　441
6.3.7　參考文獻(xiàn)　441
6.4　可聽集(Potentially Audible Sets)　442
Dominic Filion
6.4.1　PVS入門　442
6.4.2　PAS基礎(chǔ)　443
6.4.3　直接聲音路徑　443
6.4.4　為門窗創(chuàng)建動態(tài)PAS　447
6.4.5　PAS擴(kuò)展：傳導(dǎo)(transmission)　448
6.4.6　PAS擴(kuò)展：反射　449
6.4.7　總結(jié)　450
6.4.8　參考文獻(xiàn)　450
6.5　一種開銷較低的多普勒效果　451
Julien Hamaide
6.5.1　多普勒效果　451
6.5.2　編寫多普勒效果程序　454
6.5.3　線性插值　454
6.5.4　根據(jù)R來計算下標(biāo)　455
6.5.5　非恒定速度　456
6.5.6　信號對齊(Aliasing)　457
6.5.7　實現(xiàn)　457
6.5.8　總結(jié)　457
6.5.9　資源　458
6.6　仿造實時DSP效果　459
Robert Sparks
6.6.1　仿造　459
6.6.2　例子：收音機(jī)在房間中播放音樂　459
6.6.3　聲音能量恒定曲線(Constant Power Volume Curve)　461
6.6.4　對聲道音量進(jìn)行進(jìn)一步控制　461
6.6.5　在DirectSound中播放多聲道文件　462
6.6.6　代價和好處　462
6.6.7　總結(jié)　462
6.6.8　致謝　462
第7章　網(wǎng)絡(luò)及多人在線
簡介　　464
Scott Jacobs
7.1　3D動畫角色數(shù)據(jù)的動態(tài)自適應(yīng)流　465
Thomas Di Giacomo、HyungSeok Kim、Stephane Garchery和Nadia Magnenat-Thalmann
Chris Joslin
7.1.1　簡介　465
7.1.2　背景介紹與相關(guān)方法　465
7.1.3　處理可縮放3D數(shù)據(jù)的準(zhǔn)備和實施　466
7.1.4　自適應(yīng)數(shù)據(jù)的傳輸　471
7.1.5　總結(jié)　473
7.1.6　參考文獻(xiàn)　473
7.2　大規(guī)模多人在線游戲基于復(fù)雜系統(tǒng)的高階架構(gòu)　475
Viknashavaran Narayanasamy、Kok-Wai Wong和Chun Che Fung
7.2.1　復(fù)雜系統(tǒng)和突發(fā)性事件　475
7.2.2　多重架構(gòu)　476
7.2.3　基于回饋的決策系統(tǒng)　484
7.2.4　總結(jié)　485
7.2.5　參考文獻(xiàn)　485
7.3　為游戲物件生成全局唯一標(biāo)識符　487
Yongha Kim
7.3.1　游戲物件GUID建立的需求　487
7.3.2　生成GUID　488
7.3.3　對于特殊情況的處理　489
7.3.4　總結(jié)　490
7.3.5　參考文獻(xiàn)　490
7.4　利用Second Life為大規(guī)模多人在線游戲原形設(shè)計游戲概念原形　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中的設(shè)計要點　495
7.4.5　原形的開發(fā)　496
7.4.6　一個成功的例子　498
7.4.7　總結(jié)　499
7.4.8　參考文獻(xiàn)　499
7.5　穩(wěn)定的P2P游戲TCP連接及敏感NAT　501
Larry Shi
7.5.1　問題　501
7.5.2　技術(shù)水平　502
7.5.3　方法　503
7.5.4　應(yīng)用方面　507
7.5.5　局限性　507
7.5.6　結(jié)論　508
7.5.7　參考文獻(xiàn)　508