游戲編程精粹（1）

第1章  通用編程技術
1.0  神奇的數(shù)據(jù)驅(qū)動設計  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——避免重復數(shù)據(jù)  5
1.0.7  點子7——開發(fā)工具來生成數(shù)據(jù)  6
1.0.8  結(jié)論  6
1.1  面向?qū)ο蟮木幊膛c設計技術  7
James Boer
1.1.1  代碼風格  7
1.1.2  類設計  9
1.1.3  類層次結(jié)構(gòu)設計  10
1.1.4  設計模式  10
1.1.5  總結(jié)  16
1.1.6  參考資料  16
1.2  使用模板元編程的快速數(shù)學方法  17
Pete Isensee
1.2.1  斐波納契數(shù)  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  總結(jié)  26
1.2.9  參考文獻  31
1.3  一種自動的Singleton工具  32
Scott Bilas
1.3.1  定義  32
1.3.2  優(yōu)點  32
1.3.3  問題  33
1.3.4  傳統(tǒng)的解決方法  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）和優(yōu)先隊列（Priority Queue）  46
1.4.8  總結(jié)  47
1.4.9  參考文獻  47
1.5  一個通用的函數(shù)綁定接口  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  調(diào)用約定  52
1.5.7  調(diào)用函數(shù)  54
1.5.8  完備解決方案  55
1.5.9  結(jié)論  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  資源和內(nèi)存管理  69
James Boer
1.7.1  資源類  69
1.7.2  資源管理類  71
1.7.3  句柄如何工作  74
1.7.4  可能的擴展和改進  74
1.7.5  結(jié)論  75
1.8  快速數(shù)據(jù)載入技巧  76
John Olsen
1.8.1  預處理你的數(shù)據(jù)  76
1.8.2  保存你的數(shù)據(jù)  76
1.8.3  使用簡單方法載入你的數(shù)據(jù)  77
1.8.4  更安全地載入你的數(shù)據(jù)  78
1.9  基于幀的內(nèi)存分配  80
Steven Ranck
1.9.1  常規(guī)內(nèi)存分配的挑戰(zhàn)  80
1.9.2  介紹基于幀的內(nèi)存  80
1.9.3  分配和釋放內(nèi)存  82
1.9.4  例子  84
1.9.5  結(jié)論  86
1.10  簡單快速的位數(shù)組  87
Andrew Kirmse
1.10.1  概述  87
1.10.2  位數(shù)組  87
1.10.3  其他數(shù)組  88
1.10.4  應用  89
1.10.5  參考文獻  89
1.11  在線游戲的網(wǎng)絡協(xié)議  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  實現(xiàn)  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：實時統(tǒng)計和游戲內(nèi)調(diào)試  99
John Olsen
1.13.1  Why：需求驅(qū)動的技術  99
1.13.2  How：一個進化過程  100
1.13.3  What：一個基于C++類的系統(tǒng)  100
1.13.4  Where：可用性  102
1.13.5  小結(jié)  102
1.14  實時的游戲內(nèi)建剖析  103
Steve Rabin
1.14.1  開始考慮細節(jié)  103
1.14.2  剖析器將告訴你什么？  104
1.14.3  增加剖析器調(diào)用  105
1.14.4  剖析器的實現(xiàn)  106
1.14.5  ProfileBegin的細節(jié)  107
1.14.6  ProfileEnd的細節(jié)  107
1.14.7  處理剖析數(shù)據(jù)的細節(jié)  107
1.14.8  后期增強  108
1.14.9  將它們組合起來  108
1.14.10  參考文獻  113
第2章　數(shù)學技巧
2.0  可預測隨機數(shù)  117
Guy W. Lecky-Thompson
2.0.1  可預測隨機數(shù)  117
2.0.2  替換算法  119
2.0.3  無限宇宙算法  120
2.0.4  結(jié)論與展望  122
2.0.5  參考文獻  123
2.1  插值方法  124
John Olsen
2.1.1  使用浮點數(shù)學的幀速相關ease-out  124
2.1.2  使用整型數(shù)學的幀速相關ease-out  125
2.1.3　幀速無關線性內(nèi)插  126
2.1.4　幀速無關ease-in和ease-out  127
2.1.5　危險地帶  128
2.2  求剛體運動方程的積分  132
Miguel Gomez
2.2.1  運動學：平移和旋轉(zhuǎn)  132
2.2.2  動力學：力與旋轉(zhuǎn)力矩（torque）  135
2.2.3  剛體的特性  136
2.2.4  求運動方程的積分  139
2.2.5  參考文獻  140
2.3  三角函數(shù)的多項式逼近  141
Eddie Edwards
2.3.1  多項式  142
2.3.2　定義域和值域  143
2.3.3　偶多項式和奇多項式  146
2.3.4　泰勒級數(shù)  146
2.3.5　截斷的泰勒級數(shù)  149
2.3.6　拉格朗日級數(shù)  150
2.3.7　不連續(xù)性處理  153
2.3.8　結(jié)論  153
2.4  為數(shù)字穩(wěn)定性而利用隱式歐拉積分  155
Miguel Gomez
2.4.1  求初值問題的積分及穩(wěn)定性  155
2.4.2  顯式的歐拉方法  155
2.4.3  隱式歐拉方法  156
2.4.4  不準確性  158
2.4.5  尋找隱式解  158
2.4.6  結(jié)論  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　實現(xiàn)問題  166
2.6.4　與水面交互  167
2.6.5  渲染  169
2.6.6  參考文獻  170
2.7  游戲編程四元數(shù)  171
Jan Svarovsky
2.7.1  將四元數(shù)當作矩陣替換物  171
2.7.2  為什么不使用歐拉角  172
2.7.3　X、Y、Z和W代表什么  172
2.7.4　源自什么數(shù)學基礎  173
2.7.5  四元數(shù)如何表示旋轉(zhuǎn)  174
2.7.6  參考文獻  174
2.8  矩陣和四元數(shù)之間的轉(zhuǎn)換  175
Jason Shankel
2.8.1  四元數(shù)旋轉(zhuǎn)  175
2.8.2  四元數(shù)到矩陣的轉(zhuǎn)換  175
2.8.3　矩陣到四元數(shù)的轉(zhuǎn)換  177
2.8.4　參考文獻  178
2.9  四元數(shù)插值  179
Jason Shankel
2.9.1  四元數(shù)計算  179
2.9.2  四元數(shù)插值  179
2.9.3　示例代碼  182
2.9.4  推導  182
2.10  最短弧四元數(shù)  186
Stan Melax
2.10.1  動機  186
2.10.2  數(shù)值不穩(wěn)定性  186
2.10.3　穩(wěn)定公式的推導  187
2.10.4　殘存不穩(wěn)定性條件  188
2.10.5  源代碼  188
2.10.6  虛擬跟蹤球  189
2.10.7  參考文獻  189
第3章　人工智能
3.0  設計一個通用、健壯的AI引擎  193
Steve Rabin
3.0.1  事件驅(qū)動與輪詢的對比  193
3.0.2  消息概念  194
3.0.3　狀態(tài)機  194
3.0.4　一個使用消息的事件驅(qū)動狀態(tài)機  194
3.0.5　交待時間（Confession Time）  197
3.0.6  另一個小交待  197
3.0.7  狀態(tài)機構(gòu)建單元  198
3.0.8  狀態(tài)機消息路由選擇  198
3.0.9  發(fā)送消息  200
3.0.10  發(fā)送延遲的消息  200
3.0.11  刪除游戲?qū)ο?nbsp; 201
3.0.12  增強：定義消息的范圍  201
3.0.13  增強：記錄所有的消息活動和狀態(tài)變遷  203
3.0.14  增強：交換狀態(tài)機  203
3.0.15  增強：多狀態(tài)機  203
3.0.16  增強：一個狀態(tài)機隊列  204
3.0.17  代碼外部腳本化行為  204
3.0.18  結(jié)論  204
3.0.19  參考文獻  207
3.1  一個有限狀態(tài)機類  208
Eric Dybsand
3.1.1  FSMclass和FSMstate  210
3.1.2　定義FSMstate  210
3.1.3　定義FSMclass  211
3.1.4　為FSM創(chuàng)建狀態(tài)  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*路徑規(guī)劃基礎  225
Bryan Stout
3.3.1  問題  225
3.3.2  方法概述  225
3.3.3  A*的特性  227
3.3.4　將A*應用到游戲路徑規(guī)劃  227
3.3.5  A*的弱點  231
3.3.6  進一步的工作  232
3.3.7  參考文獻  232
3.4  A*審美優(yōu)化  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  空曠區(qū)域上的分級尋徑  238
3.4.7  在分級搜尋過程中減少停頓  238
3.4.8  最大化響應率  239
3.4.9  結(jié)論  239
3.4.10　參考文獻  239
3.5  A*速度優(yōu)化  240
Steve Rabin
3.5.1  搜索空間優(yōu)化  240
3.5.2  算法優(yōu)化  244
3.5.3　結(jié)論  248
3.5.4  參考文獻  253
3.6  簡化的3D運動和使用導航網(wǎng)格進行尋徑  254
Greg Snook
3.6.1  簡述  254
3.6.2  構(gòu)造  255
3.6.3　滾動骰子并且移動鼠標  256
3.6.4　到此僅完成一半  258
3.6.5  它是有效的，但不是那么完美  260
3.6.6  結(jié)論  261
3.6.7  參考文獻  269
3.7  Flocking：一種模擬群體行為的簡單技術  270
Steven Woodcock
3.7.1  實現(xiàn)  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  結(jié)論  291
3.8.6  資源  291
3.9  神經(jīng)網(wǎng)絡初探  292
André LaMothe
3.9.1  生物學仿真  292
3.9.2  對游戲的應用  293
3.9.3  神經(jīng)網(wǎng)絡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  結(jié)論  309
第4章　多邊形技術
4.0  為OpenGL優(yōu)化頂點提交  313
Herbert Marselas
4.0.1  即時模式  313
4.0.2  交叉存取數(shù)據(jù)  314
4.0.3  步數(shù)據(jù)和流數(shù)據(jù)  315
4.0.4  編譯過的頂點數(shù)組  316
4.0.5  取消數(shù)據(jù)復制廠家指定擴展  317
4.0.6  數(shù)據(jù)格式  317
4.0.7  一般建議  318
4.0.8  結(jié)論  318
4.0.9  參考文獻  319
4.1  調(diào)整頂點的投影深度值  320
Eric Lengyel
4.1.1  考察投影矩陣  320
4.1.2  矯正深度值  321
4.1.3　選擇一個適當?shù)?nbsp;  321
4.1.4　實現(xiàn)  323
4.1.5　源代碼  323
4.2  矢量攝像機  324
David Paull
4.2.1  矢量攝像機初步  325
4.2.2  本地空間優(yōu)化  326
4.2.3  結(jié)論  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  實現(xiàn)  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  計算到區(qū)域內(nèi)部的距離  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　總結(jié)  379
4.9  永遠不要讓他們看到你的“抖動”——幾何體細節(jié)層次選擇問題  387
Yossarian King
4.9.1  LOD選擇  387
4.9.2　放大率因子  389
4.9.3　滯變閾值  389
4.9.4  實現(xiàn)  390
4.9.5  其他問題  391
4.10  八叉樹構(gòu)造  393
Dan Ginsburg
4.10.1  八叉樹概述  393
4.10.2  八叉樹數(shù)據(jù)  394
4.10.3  建立樹  394
4.10.4  多邊形重疊  395
4.10.5  相鄰節(jié)點  396
4.10.6  應用  396
4.10.7  結(jié)論  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  結(jié)論  406
4.12  獨立于觀察的漸進網(wǎng)格  407
Jan Svarovsky
4.12.1  漸進網(wǎng)格概述  407
4.12.2  關于這個主題的變種  408
4.12.3　邊緣選擇函數(shù)  410
4.12.4  難處理的邊  410
4.12.5　實現(xiàn)  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　總結(jié)  421
4.13.7　參考文獻  421
4.14  一種快速而簡單的皮膚構(gòu)造技術  422
Torgeir Hagland
4.14.1  為什么對低多邊形有價值  422
4.14.2  方法  422
4.14.3  總結(jié)  423
4.14.4  參考文獻  426
4.15  填充間隙——使用縫合和皮膚構(gòu)造的高級動畫  427
Ryan Woodland
4.15.1  縫合  428
4.15.2  皮膚構(gòu)造（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  不規(guī)則地形生成——斷層構(gòu)造  447
Jason Shankel
4.17.1  斷層構(gòu)造  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  不規(guī)則地形生成——中點置換  451
Jason Shankel
4.18.1  一維中點置換  451
4.18.2  二維中點置換——菱形正方形算法  452
4.18.3  高地中的菱形——正方形算法  454
4.19  不規(guī)則地形生成——粒子沉積  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  實現(xiàn)  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  結(jié)論  468
5.2  基于運動的靜態(tài)光照  469
Steven Ranck
5.2.1  傳統(tǒng)的靜態(tài)光照  469
5.2.2  基于運動的靜態(tài)光照  472
5.2.3  結(jié)論  477
5.3  使用定點顏色插值模擬實時光照  478
Jorge Freitas
5.3.1  光照方法  478
5.3.2  美工創(chuàng)作  479
5.3.3  插值光照  479
5.3.4  結(jié)論  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  結(jié)論  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  結(jié)論  499
5.6.7  參考文獻  500
5.7  底面陰影  501
Yossarian King
5.7.1  陰影數(shù)學  501
5.7.2  實現(xiàn)  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  創(chuàng)建陰影圖  507
5.8.5  在接收物體上投影陰影圖  513
5.8.6  渲染接收物體  514
5.8.7  對基本算法的擴展與改進  514
5.8.8  參考文獻  515
5.9  使用光滑預過濾和Fresnel項改善環(huán)境映射反射  516
Anis Ahmad
5.9.1  第一個不正確的假設  516
5.9.2  第二個不正確的假設  518
5.9.3  結(jié)論  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  實現(xiàn)  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  結(jié)論  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