第1部分 AI和游戲
第1章　導(dǎo)論 3
1.1　AI的定義 4
1.1.1　學(xué)術(shù)派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　基礎(chǔ)架構(gòu) 14
1.2.5　基于代理的AI 14
1.2.6　該模型在本書中的意義 15
1.3　算法和數(shù)據(jù)結(jié)構(gòu) 15
1.3.1　算法 16
1.3.2　表示方式 18
1.3.3 實現(xiàn) 19
1.4 本書的布局結(jié)構(gòu) 20
第2章　游戲AI 21
2.1 復(fù)雜度謬誤 21
2.1.1 簡單的AI也能做得很好 21
2.1.2 復(fù)雜的AI也可能很糟糕 22
2.1.3 感知窗口 23
2.1.4 行為的變化 24
2.2 游戲中的AI類型 24
2.2.1 借鑒技術(shù) 25
2.2.2 啟發(fā)式方法 26
2.2.3 算法 28
2.3 速度和內(nèi)存限制 28
2.3.1 處理器問題 29
2.3.2 低級語言問題 29
2.3.3 內(nèi)存問題 31
2.3.4 平臺 33
2.4 游戲AI引擎 36
2.4.1 游戲AI引擎的結(jié)構(gòu) 37
2.4.2 工具問題 38
2.4.3 綜述 39
第2部分 技 術(shù)
第3章　移動 43
3.1 移動算法基礎(chǔ) 44
3.1.1 二維移動 45
3.1.2 靜止狀態(tài) 46
3.1.3 運動學(xué) 49
3.2 運動學(xué)移動算法 52
3.2.1 尋找 53
3.2.2 漫游 56
3.3 轉(zhuǎn)向行為 58
3.3.1 轉(zhuǎn)向基礎(chǔ)知識 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 小結(jié) 94
3.4 組合轉(zhuǎn)向行為 95
3.4.1 混合和仲裁 95
3.4.2 加權(quán)混合 96
3.4.3 優(yōu)先級 101
3.4.4 合作仲裁 104
3.4.5 轉(zhuǎn)向管道 106
3.5　預(yù)測物理 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 協(xié)調(diào)移動 139
3.7.1 固定編隊 140
3.7.2 可擴展的格式 141
3.7.3 自然編隊 142
3.7.4 兩級編隊轉(zhuǎn)向 143
3.7.5 實現(xiàn) 146
3.7.6 擴展到兩個以上的級別 151
3.7.7 槽位的職業(yè)角色和更好的分配 153
3.7.8 槽位分配 156
3.7.9 動態(tài)槽位和隊形 160
3.7.10 戰(zhàn)術(shù)移動 162
3.8 馬達控制 165
3.8.1 輸出過濾 165
3.8.2 與能力匹配的轉(zhuǎn)向 167
3.8.3 常見執(zhí)行屬性 169
3.9 第三維中的移動 171
3.9.1 三維旋轉(zhuǎn) 172
3.9.2 將轉(zhuǎn)向行為轉(zhuǎn)換為三維 173
3.9.3 對齊 174
3.9.4 對齊向量 175
3.9.5 朝向行為 176
3.9.6 直視移動的方向 179
3.9.7 漫游 179
3.9.8 假旋轉(zhuǎn)軸 181
3.10 習(xí)題 185
第4章　路徑發(fā)現(xiàn) 189
4.1 路徑發(fā)現(xiàn)圖形 190
4.1.1 圖形 190
4.1.2 加權(quán)圖形 191
4.1.3 有向加權(quán)圖形 194
4.1.4 術(shù)語 195
4.1.5 表示方式 195
4.2 迪杰斯特拉算法 196
4.2.1 問題 197
4.2.2 算法 198
4.2.3 偽代碼 202
4.2.4 數(shù)據(jù)結(jié)構(gòu)和接口 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 數(shù)據(jù)結(jié)構(gòu)和接口 216
4.3.5 實現(xiàn)說明 220
4.3.6 算法性能 220
4.3.7 節(jié)點數(shù)組A*算法 221
4.3.8 選擇啟發(fā)式算法 223
4.4 游戲世界的表示方式 230
4.4.1 圖塊圖形 232
4.4.2 狄利克雷域 234
4.4.3 可見性點 236
4.4.4 導(dǎo)航網(wǎng)格 238
4.4.5 非平移問題 242
4.4.6 成本函數(shù) 243
4.4.7 路徑平滑 244
4.5 改進A*算法 246
4.6 分層路徑發(fā)現(xiàn)技術(shù) 247
4.6.1 分層路徑發(fā)現(xiàn)圖形 248
4.6.2 分層圖形上的路徑發(fā)現(xiàn) 251
4.6.3 基于排除法的分層路徑發(fā)現(xiàn)技術(shù) 254
4.6.4 分層結(jié)構(gòu)對路徑發(fā)現(xiàn)的奇怪影響 255
4.6.5 實例幾何 257
4.7 路徑發(fā)現(xiàn)中的其他思路 263
4.7.1 開放目標路徑發(fā)現(xiàn) 263
4.7.2 動態(tài)路徑發(fā)現(xiàn) 263
4.7.3 其他類型的信息重用 264
4.7.4 低內(nèi)存算法 265
4.7.5 可中斷路徑發(fā)現(xiàn) 266
4.7.6 匯集路徑規(guī)劃請求 266
4.8 連續(xù)時間路徑發(fā)現(xiàn) 267
4.8.1 問題 268
4.8.2 算法 269
4.8.3 實現(xiàn)說明 272
4.8.4 性能 273
4.8.5 弱點 273
4.9 關(guān)于移動路徑規(guī)劃 273
4.9.1 動作 274
4.9.2 移動路徑規(guī)劃 275
4.9.3 示例 276
4.9.4 腳步規(guī)劃 278
4.10 習(xí)題 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 實現(xiàn)節(jié)點 292
5.2.6 決策樹的性能 293
5.2.7 平衡決策樹 293
5.2.8 超越?jīng)Q策樹 294
5.2.9 隨機決策樹 295
5.3 狀態(tài)機 297
5.3.1 問題 299
5.3.2 算法 299
5.3.3 偽代碼 300
5.3.4 數(shù)據(jù)結(jié)構(gòu)和接口 301
5.3.5 性能 303
5.3.6 實現(xiàn)說明 303
5.3.7 硬編碼的FSM 304
5.3.8 分層狀態(tài)機 306
5.3.9 組合決策樹和狀態(tài)機 319
5.4 行為樹 321
5.4.1 實現(xiàn)行為樹 328
5.4.2 偽代碼 328
5.4.3 裝飾器 332
5.4.4　并發(fā)和計時 338
5.4.5 向行為樹添加數(shù)據(jù) 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 模糊狀態(tài)機 376
5.6 馬爾可夫系統(tǒng) 381
5.6.1 馬爾可夫過程 382
5.6.2 馬爾可夫狀態(tài)機 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 散發(fā)氣味的GOB 411
5.8 基于規(guī)則的系統(tǒng) 413
5.8.1 問題 413
5.8.2 算法 418
5.8.3 偽代碼 419
5.8.4 數(shù)據(jù)結(jié)構(gòu)和接口 419
5.8.5 規(guī)則仲裁 425
5.8.6 統(tǒng)一 428
5.8.7 Rete算法 430
5.8.8 擴展 439
5.8.9 發(fā)展前瞻 443
5.9 黑板架構(gòu) 443
5.9.1 問題 443
5.9.2 算法 444
5.9.3 偽代碼 445
5.9.4 數(shù)據(jù)結(jié)構(gòu)和接口 446
5.9.5 性能 449
5.9.6 其他的黑板系統(tǒng) 449
5.10 動作執(zhí)行 450
5.10.1 動作的類型 450
5.10.2 算法 455
5.10.3 偽代碼 456
5.10.4 數(shù)據(jù)結(jié)構(gòu)和接口 457
5.10.5 實現(xiàn)說明 459
5.10.6 性能 460
5.10.7 綜述 460
5.11 練習(xí) 461
第6章　戰(zhàn)略和戰(zhàn)術(shù)AI 465
6.1 航點戰(zhàn)術(shù) 466
6.1.1 戰(zhàn)術(shù)位置 466
6.1.2 使用戰(zhàn)術(shù)位置 474
6.1.3 生成航點的戰(zhàn)術(shù)屬性 479
6.1.4 自動生成航點 484
6.1.5 簡化算法 485
6.2 戰(zhàn)術(shù)分析 489
6.2.1 表示游戲關(guān)卡 489
6.2.2 簡單的影響地圖 490
6.2.3 地形分析 496
6.2.4 用戰(zhàn)術(shù)分析學(xué)習(xí) 498
6.2.5 戰(zhàn)術(shù)分析的結(jié)構(gòu) 500
6.2.6 關(guān)于地圖覆蓋 504
6.2.7 卷積濾鏡 509
6.2.8 細胞自動機 518
6.3 戰(zhàn)術(shù)性路徑發(fā)現(xiàn) 524
6.3.1 成本函數(shù) 524
6.3.2 戰(zhàn)術(shù)權(quán)重和關(guān)注事項的混合 525
6.3.3 修改路徑發(fā)現(xiàn)啟發(fā)式算法 527
6.3.4 路徑發(fā)現(xiàn)的戰(zhàn)術(shù)圖形 528
6.3.5 使用戰(zhàn)術(shù)航點 528
6.4 協(xié)調(diào)動作 529
6.4.1 多層AI 530
6.4.2 自發(fā)合作 536
6.4.3 編寫群體動作的腳本 538
6.4.4 軍事戰(zhàn)術(shù) 543
6.5 習(xí)題 545
第7章　學(xué)習(xí) 549
7.1 關(guān)于機器學(xué)習(xí)的基礎(chǔ)知識 549
7.1.1 在線或離線學(xué)習(xí) 549
7.1.2 行為內(nèi)學(xué)習(xí) 550
7.1.3 行為間學(xué)習(xí) 551
7.1.4 對機器學(xué)習(xí)應(yīng)用的警告 551
7.1.5 過度學(xué)習(xí) 552
7.1.6 混雜的學(xué)習(xí)算法 552
7.1.7 工作量的平衡 552
7.2 參數(shù)修改 553
7.2.1 參數(shù)地形 553
7.2.2 爬山算法 555
7.2.3 基本爬山算法的擴展 558
7.2.4 退火技術(shù) 561
7.3 動作預(yù)測 565
7.3.1 左還是右 565
7.3.2 原始概率 566
7.3.3 字符串匹配 566
7.3.4 N-Gram預(yù)測器 567
7.3.5 窗口大小 570
7.3.6 分層N-Gram 572
7.3.7 在格斗游戲中的應(yīng)用 575
7.4 決策學(xué)習(xí) 575
7.4.1 決策學(xué)習(xí)的結(jié)構(gòu) 575
7.4.2 應(yīng)該學(xué)習(xí)的東西 576
7.4.3 4種技術(shù) 576
7.5 樸素貝葉斯分類算法 577
7.5.1 偽代碼 580
7.5.2 實現(xiàn)說明 582
7.6 決策樹學(xué)習(xí) 582
7.6.1 ID3 583
7.6.2 具有連續(xù)屬性的ID3 590
7.6.3 增量決策樹學(xué)習(xí) 595
7.7 強化學(xué)習(xí) 599
7.7.1 問題 599
7.7.2 算法 600
7.7.3 偽代碼 603
7.7.4 數(shù)據(jù)結(jié)構(gòu)和接口 604
7.7.5 實現(xiàn)說明 605
7.7.6 性能 605
7.7.7 適應(yīng)性調(diào)整參數(shù) 605
7.7.8 弱點和現(xiàn)實應(yīng)用 609
7.7.9 強化學(xué)習(xí)中的其他思路 611
7.8 人工神經(jīng)網(wǎng)絡(luò) 613
7.8.1 概述 615
7.8.2 問題 617
7.8.3 算法 618
7.8.4 偽代碼 622
7.8.5 數(shù)據(jù)結(jié)構(gòu)和接口 624
7.8.6 實現(xiàn)警告 626
7.8.7 性能 626
7.8.8 其他方法 626
7.9 深度學(xué)習(xí) 630
7.9.1 深度學(xué)習(xí)的定義 631
7.9.2 數(shù)據(jù) 632
7.10 習(xí)題 634
第8章 程序化內(nèi)容生成 639
8.1 偽隨機數(shù) 641
8.1.1 數(shù)值混合和游戲種子 641
8.1.2 霍爾頓序列 643
8.1.3 葉序的角度 646
8.1.4 泊松圓盤 647
8.2 Lindenmayer系統(tǒng) 651
8.2.1 簡單的L系統(tǒng) 651
8.2.2 將隨機性添加到L系統(tǒng) 655
8.2.3 特定階段的規(guī)則 657
8.3 地形生成 659
8.3.1 修飾器和高度圖 659
8.3.2 噪聲 660
8.3.3 佩林噪聲 661
8.3.4 斷層 664
8.3.5 熱侵蝕 666
8.3.6 水力侵蝕 667
8.3.7 高地過濾 672
8.4 地下城與迷宮的生成 676
8.4.1 深度優(yōu)先的回溯迷宮 677
8.4.2 小生成樹算法 687
8.4.3 遞歸細分 692
8.4.4 生成和測試 696
8.5 形狀語法 697
8.5.1 運行語法 700
8.5.2 規(guī)劃 703
8.6 練習(xí) 707
第9章　棋盤游戲 709
9.1 博弈論 710
9.1.1 游戲類型 710
9.1.2 博弈樹 712
9.2 極小極大化算法 714
9.2.1 靜態(tài)評估函數(shù) 714
9.2.2 關(guān)于極小極大化 716
9.2.3 使用極小極大化算法 717
9.2.4 負值化算法 720
9.2.5 AB修剪 722
9.2.6 AB搜索窗口 726
9.2.7 負值偵察 727
9.3 置換表和內(nèi)存 730
9.3.1 哈希游戲狀態(tài) 731
9.3.2 哈希表中存儲的內(nèi)容 733
9.3.3 哈希表實現(xiàn) 734
9.3.4 替換策略 736
9.3.5 完整的置換表 736
9.3.6 置換表的問題 737
9.3.7 使用對手的思考時間 738
9.4 內(nèi)存增強型測試算法 738
9.4.1 實現(xiàn)測試 738
9.4.2 MTD算法 740
9.4.3 偽代碼 742
9.5 蒙特卡洛樹搜索 743
9.5.1 純蒙特卡洛樹搜索 743
9.5.2 添加知識 748
9.6 開局庫和其他固定進攻戰(zhàn)術(shù) 750
9.6.1 實現(xiàn)開局庫 750
9.6.2 學(xué)習(xí)開局庫 751
9.6.3 固定進攻戰(zhàn)術(shù)庫 751
9.7 進一步優(yōu)化 752
9.7.1 迭代加深 752
9.7.2 可變深度算法 753
9.8 游戲知識 755
9.8.1 創(chuàng)建靜態(tài)評估函數(shù) 757
9.8.2 學(xué)習(xí)靜態(tài)評估函數(shù) 760
9.9 回合制策略游戲 764
9.9.1 不可能的樹大小 764
9.9.2 回合制游戲中的實時AI 765
9.10 習(xí)題 766
第3部分 支 持 技 術(shù)
第10章　執(zhí)行管理 769
10.1 調(diào)度 769
10.1.1 調(diào)度程序 770
10.1.2 可中斷進程 776
10.1.3 負載平衡調(diào)度程序 779
10.1.4 分層調(diào)度 781
10.1.5 優(yōu)先級調(diào)度 782
10.2 隨時算法 785
10.3 細節(jié)層次 786
10.3.1 圖形細節(jié)層次 786
10.3.2 關(guān)于AI中的細節(jié)層次技術(shù) 787
10.3.3 調(diào)度細節(jié)層次 788
10.3.4 行為細節(jié)層次 789
10.3.5 群體細節(jié)層次 794
10.3.6 總結(jié) 797
10.4 習(xí)題 797
第11章　世界接口 799
11.1 通信 799
11.1.1 輪詢 800
11.1.2 事件 800
11.1.3 確定使用的方法 801
11.2 事件管理器 802
11.2.1 實現(xiàn) 804
11.2.2 事件播送 807
11.2.3 代理間通信 809
11.3 輪詢站點 809
11.3.1 偽代碼 810
11.3.2 性能 811
11.3.3 實現(xiàn)說明 811
11.3.4 抽象輪詢 811
11.4 感知管理 813
11.4.1 模擬才是王道 813
11.4.2 內(nèi)部知識和外部知識 814
11.4.3 感知形態(tài) 815
11.4.4 區(qū)域感知管理器 820
11.4.5 有限元模型感知管理器 828
11.5 習(xí)題 835
第12章　工具和內(nèi)容創(chuàng)建 837
12.1 關(guān)于工具鏈 837
12.1.1 工具鏈限制AI 837
12.1.2 AI知識的來源 838
12.2 路徑發(fā)現(xiàn)和航點戰(zhàn)術(shù)的知識 838
12.2.1 手動創(chuàng)建區(qū)域數(shù)據(jù) 839
12.2.2 自動圖形創(chuàng)建 841
12.2.3 幾何分析 841
12.2.4 數(shù)據(jù)挖掘 844
12.3 關(guān)于移動的知識 847
12.3.1 障礙問題 847
12.3.2 高級調(diào)度 848
12.4 關(guān)于決策的知識 849
12.4.1 對象類型 849
12.4.2 具體動作 849
12.5 工具鏈 850
12.5.1 集成游戲引擎 851
12.5.2 自定義數(shù)據(jù)驅(qū)動的編輯器 853
12.5.3 AI設(shè)計工具 854
12.5.4 遠程調(diào)試 855
12.5.5 插件 856
12.6 習(xí)題 857
第13章 游戲AI編程 859
13.1 實現(xiàn)語言 860
13.1.1 C 861
13.1.2 C# 861
13.1.3 Swift 863
13.1.4 Java 864
13.1.5 JavaScript 865
13.2 腳本AI 867
13.2.1 腳本AI的定義 869
13.2.2 優(yōu)秀腳本語言的基本要件 869
13.2.3 嵌入 871
13.2.4 選擇開源語言 871
13.2.5 語言選擇 872
13.3 創(chuàng)建語言 877
13.3.1 優(yōu)點 878
13.3.2 缺點 878
13.3.3 創(chuàng)建自定義語言的實際操作 879
13.3.4 工具：Lex和Yacc簡介 883
第4部分 設(shè)計游戲AI
第14章　游戲AI設(shè)計 887
14.1 設(shè)計 887
14.1.1 示例 888
14.1.2 評估行為 889
14.1.3 選擇技術(shù) 891
14.1.4 一款游戲的范圍 893
14.2 射擊類游戲 894
14.2.1 移動和射擊 895
14.2.2 決策 897
14.2.3 感知 898
14.2.4 路徑發(fā)現(xiàn)和戰(zhàn)術(shù)AI 899
14.2.5 射擊類風(fēng)格游戲 900
14.2.6 近戰(zhàn)格斗類游戲 901
14.3 駕駛類游戲 904
14.3.1 移動 905
14.3.2 路徑發(fā)現(xiàn)和戰(zhàn)術(shù)AI 906
14.3.3 類駕駛游戲 907
14.4 即時戰(zhàn)略類游戲 907
14.4.1 路徑發(fā)現(xiàn) 908
14.4.2 群體移動 909
14.4.3 戰(zhàn)術(shù)和戰(zhàn)略AI 909
14.4.4 決策 910
14.4.5 MOBA 911
14.5 體育類游戲 912
14.5.1 物理預(yù)測 913
14.5.2 戰(zhàn)術(shù)套路庫和內(nèi)容創(chuàng)建 914
14.6 回合制戰(zhàn)略游戲 914
14.6.1 計時 915
14.6.2 幫助玩家 916
第15章　基于AI的游戲類型 917
15.1 游戲角色教學(xué) 917
15.1.1 表示動作 918
15.1.2 表示游戲世界 918
15.1.3 學(xué)習(xí)機制 919
15.1.4 可預(yù)測的心理模型和病理狀態(tài) 921
15.2 蜂擁算法和放牧游戲 922
15.2.1 制造生物 922
15.2.2 為交互調(diào)整轉(zhuǎn)向行為 923
15.2.3 轉(zhuǎn)向行為的穩(wěn)定性 924
15.2.4 生態(tài)系統(tǒng)設(shè)計 925
附 錄
參考資料 929
A.1 圖書、期刊、論文和網(wǎng)站 929
A.2 游戲 934