游戲中的人工智能（第3版） AI for Games, Third Edition

1部分  AI和遊戲
1章 導論 3
1.1 AI的定義 4
1.1.1 學術派AI 5
1.1.2 遊戲AI 9
1.2 遊戲AI模型 11
1.2.1 移動 12
1.2.2 決策 13
1.2.3 策略 13
1.2.4 基礎架構 14
1.2.5 基於代理的AI 14
1.2.6 該模型在本書中的意義 15
1.3 算法和數據結構 15
1.3.1 算法 16
1.3.2 表示方式 18
1.3.3  實現 19
1.4  本書的佈局結構 20

2章 遊戲AI 21
2.1  複雜度謬誤 21
2.1.1  簡單的AI也能做得很好 21
2.1.2  複雜的AI也可能很糟糕 22
2.1.3  感知窗口 23
2.1.4  行為的變化 24
2.2  遊戲中的AI類型 24
2.2.1  借鑒技術 25
2.2.2  啟發式方法 26
2.2.3  算法 28
2.3  速度和內存限制 28
2.3.1  處理器問題 29
2.3.2  低級語言問題 29
2.3.3  內存問題 31
2.3.4  平台 33
2.4  遊戲AI引擎 36
2.4.1  遊戲AI引擎的結構 37
2.4.2  工具問題 38
2.4.3  綜述 39

2部分  技    術
3章 移動 43
3.1  移動算法基礎 44
3.1.1  二維移動 45
3.1.2  靜止狀態 46
3.1.3  運動學 49
3.2  運動學移動算法 52
3.2.1  尋找 53
3.2.2  漫遊 56
3.3  轉向行為 58
3.3.1  轉向基礎知識 58
3.3.2  變量匹配 59
3.3.3  尋找和逃跑 60
3.3.4  到達 62
3.3.5  對齊 65
3.3.6  速度匹配 68
3.3.7  委託行為 69
3.3.8  追逐和躲避 70
3.3.9  朝向 73
3.3.10  直視移動的方向 74
3.3.11  漫遊 75
3.3.12  路徑跟隨 77
3.3.13  分離 82
3.3.14  避免碰撞 85
3.3.15  避開障礙物和避免撞牆 90
3.3.16  小結 94
3.4  組合轉向行為 95
3.4.1  混合和仲裁 95
3.4.2  加權混合 96
3.4.3  優先級 101
3.4.4  合作仲裁 104
3.4.5  轉向管道 106
3.5 預測物理 117
3.5.1  瞄準和擊 118
3.5.2  拋物軌跡 118
3.5.3  擊問題求解 120
3.5.4  具有阻力的拋物 123
3.5.5  迭代定位目標 125
3.6  跳躍 131
3.6.1  跳躍點 131
3.6.2  著陸墊 134
3.6.3  坑洞填充物 138
3.7  協調移動 139
3.7.1  固定編隊 140
3.7.2  可擴展的格式 141
3.7.3  自然編隊 142
3.7.4  兩級編隊轉向 143
3.7.5  實現 146
3.7.6  擴展到兩個以上的級別 151
3.7.7  槽位的職業角色和更好的分配 153
3.7.8  槽位分配 156
3.7.9  動態槽位和隊形 160
3.7.10  戰術移動 162
3.8  馬達控制 165
3.8.1  輸出過濾 165
3.8.2  與能力匹配的轉向 167
3.8.3  常見執行屬性 169
3.9  三維中的移動 171
3.9.1  三維旋轉 172
3.9.2  將轉向行為轉換為三維 173
3.9.3  對齊 174
3.9.4  對齊向量 175
3.9.5  朝向行為 176
3.9.6  直視移動的方向 179
3.9.7  漫遊 179
3.9.8  假旋轉軸 181
3.10  習題 185

4章 路徑發現 189
4.1  路徑發現圖形 190
4.1.1  圖形 190
4.1.2  加權圖形 191
4.1.3  有向加權圖形 194
4.1.4  術語 195
4.1.5  表示方式 195
4.2  迪傑斯特拉算法 196
4.2.1  問題 197
4.2.2  算法 198
4.2.3  偽代碼 202
4.2.4  數據結構和接口 205
4.2.5  迪傑斯特拉算法的性能 206
4.2.6  弱點 207
4.3 A*算法 208
4.3.1  問題 208
4.3.2  算法 208
4.3.3  偽代碼 212
4.3.4  數據結構和接口 216
4.3.5  實現說明 220
4.3.6  算法性能 220
4.3.7  節點數組A*算法 221
4.3.8  選擇啟發式算法 223
4.4  遊戲世界的表示方式 230
4.4.1  圖塊圖形 232
4.4.2  狄利克雷域 234
4.4.3  可見性點 236
4.4.4  導航網格 238
4.4.5  非平移問題 242
4.4.6  成本函數 243
4.4.7  路徑平滑 244
4.5  改進A*算法 246
4.6  分層路徑發現技術 247
4.6.1  分層路徑發現圖形 248
4.6.2  分層圖形上的路徑發現 251
4.6.3  基於排除法的分層路徑發現技術 254
4.6.4  分層結構對路徑發現的奇怪影響 255
4.6.5  實例幾何 257
4.7  路徑發現中的其他思路 263
4.7.1  開放目標路徑發現 263
4.7.2  動態路徑發現 263
4.7.3  其他類型的信息重用 264
4.7.4  低內存算法 265
4.7.5  可中斷路徑發現 266
4.7.6  匯集路徑規劃請求 266
4.8  連續時間路徑發現 267
4.8.1  問題 268
4.8.2  算法 269
4.8.3  實現說明 272
4.8.4  性能 273
4.8.5  弱點 273
4.9  關於移動路徑規劃 273
4.9.1  動作 274
4.9.2  移動路徑規劃 275
4.9.3  示例 276
4.9.4  腳步規劃 278
4.10  習題 278

5章 決策 283
5.1  決策概述 283
5.2  決策樹 284
5.2.1  問題 285
5.2.2  算法 285
5.2.3  偽代碼 290
5.2.4  知識的表示方式 292
5.2.5  實現節點 292
5.2.6  決策樹的性能 293
5.2.7  平衡決策樹 293
5.2.8  越決策樹 294
5.2.9  隨機決策樹 295
5.3  狀態機 297
5.3.1  問題 299
5.3.2  算法 299
5.3.3  偽代碼 300
5.3.4  數據結構和接口 301
5.3.5  性能 303
5.3.6  實現說明 303
5.3.7  硬編碼的FSM 304
5.3.8  分層狀態機 306
5.3.9  組合決策樹和狀態機 319
5.4  行為樹 321
5.4.1  實現行為樹 328
5.4.2  偽代碼 328
5.4.3  裝飾器 332
5.4.4 並發和計時 338
5.4.5  向行為樹添加數據 347
5.4.6  重用行為樹 351
5.4.7  行為樹的局限性 356
5.5  模糊邏輯 357
5.5.1  討論之前的重要說明 358
5.5.2  模糊邏輯簡介 358
5.5.3  模糊邏輯決策 367
5.5.4  模糊狀態機 376
5.6  馬爾可夫系統 381
5.6.1  馬爾可夫過程 382
5.6.2  馬爾可夫狀態機 384
5.7  面向目標的行為 386
5.7.1  面向目標的行為概述 387
5.7.2  簡單選擇 389
5.7.3  整體效用 391
5.7.4  計時 394
5.7.5  整體效用GOAP 398
5.7.6  使用IDA*的GOAP 403
5.7.7  “散發氣味”的GOB 411
5.8  基於規則的系統 413
5.8.1  問題 413
5.8.2  算法 418
5.8.3  偽代碼 419
5.8.4  數據結構和接口 419
5.8.5  規則仲裁 425
5.8.6  統一 428
5.8.7  Rete算法 430
5.8.8  擴展 439
5.8.9  發展前瞻 443
5.9  黑板架構 443
5.9.1  問題 443
5.9.2  算法 444
5.9.3  偽代碼 445
5.9.4  數據結構和接口 446
5.9.5  性能 449
5.9.6  其他的黑板系統 449
5.10  動作執行 450
5.10.1  動作的類型 450
5.10.2  算法 455
5.10.3  偽代碼 456
5.10.4  數據結構和接口 457
5.10.5  實現說明 459
5.10.6  性能 460
5.10.7  綜述 460
5.11  練習 461

6章 戰略和戰術AI 465
6.1  航點戰術 466
6.1.1  戰術位置 466
6.1.2  使用戰術位置 474
6.1.3  生成航點的戰術屬性 479
6.1.4  自動生成航點 484
6.1.5  簡化算法 485
6.2  戰術分析 489
6.2.1  表示遊戲關卡 489
6.2.2  簡單的影響地圖 490
6.2.3  地形分析 496
6.2.4  用戰術分析學習 498
6.2.5  戰術分析的結構 500
6.2.6  關於地圖覆蓋 504
6.2.7  卷積濾鏡 509
6.2.8  細胞自動機 518
6.3  戰術性路徑發現 524
6.3.1  成本函數 524
6.3.2  戰術權重和關注事項的混合 525
6.3.3  修改路徑發現啟發式算法 527
6.3.4  路徑發現的戰術圖形 528