第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.7Rete算法 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
6.3.5使用戰術航點 528
6.4協調動作 529
6.4.1多層AI 530
6.4.2自發合作 536
6.4.3編寫群體動作的腳本 538
6.4.4軍事戰術 543
6.5習題 545
第7章　學習 549
7.1關于機器學習的基礎知識 549
7.1.1在線或離線學習 549
7.1.2行為內學習 550
7.1.3行為間學習 551
7.1.4對機器學習應用的警告 551
7.1.5過度學習 552
7.1.6混雜的學習算法 552
7.1.7工作量的平衡 552
7.2參數修改 553
7.2.1參數地形 553
7.2.2爬山算法 555
7.2.3基本爬山算法的擴展 558
7.2.4退火技術 561
7.3動作預測 565
7.3.1左還是右 565
7.3.2原始概率 566
7.3.3字符串匹配 566
7.3.4N-Gram預測器 567
7.3.5窗口大小 570
7.3.6分層N-Gram 572
7.3.7在格斗游戲中的應用 575
7.4決策學習 575
7.4.1決策學習的結構 575
7.4.2應該學習的東西 576
7.4.34種技術 576
7.5樸素貝葉斯分類算法 577
7.5.1偽代碼 580
7.5.2實現說明 582
7.6決策樹學習 582
7.6.1ID3 583
7.6.2具有連續屬性的ID3 590
7.6.3增量決策樹學習 595
7.7強化學習 599
7.7.1問題 599
7.7.2算法 600
7.7.3偽代碼 603
7.7.4數據結構和接口 604
7.7.5實現說明 605
7.7.6性能 605
7.7.7適應性調整參數 605
7.7.8弱點和現實應用 609
7.7.9強化學習中的其他思路 611
7.8人工神經網絡 613
7.8.1概述 615
7.8.2問題 617
7.8.3算法 618
7.8.4偽代碼 622
7.8.5數據結構和接口 624
7.8.6實現警告 626
7.8.7性能 626
7.8.8其他方法 626
7.9深度學習 630
7.9.1深度學習的定義 631
7.9.2數據 632
7.10習題 634
第8章程序化內容生成 639
8.1偽隨機數 641
8.1.1數值混合和游戲種子 641
8.1.2霍爾頓序列 643
8.1.3葉序的角度 646
8.1.4泊松圓盤 647
8.2Lindenmayer系統 651
8.2.1簡單的L系統 651
8.2.2將隨機性添加到L系統 655
8.2.3特定階段的規則 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深度優先的回溯迷宮 677
8.4.2最小生成樹算法 687
8.4.3遞歸細分 692
8.4.4生成和測試 696
8.5形狀語法 697
8.5.1運行語法 700
8.5.2規劃 703
8.6練習 707
第9章　棋盤游戲 709
9.1博弈論 710
9.1.1游戲類型 710
9.1.2博弈樹 712
9.2極小極大化算法 714
9.2.1靜態評估函數 714
9.2.2關于極小極大化 716
9.2.3使用極小極大化算法 717
9.2.4負值最大化算法 720
9.2.5AB修剪 722
9.2.6AB搜索窗口 726
9.2.7負值偵察 727
9.3置換表和內存 730
9.3.1哈希游戲狀態 731
9.3.2哈希表中存儲的內容 733
9.3.3哈希表實現 734
9.3.4替換策略 736
9.3.5完整的置換表 736
9.3.6置換表的問題 737
9.3.7使用對手的思考時間 738
9.4內存增強型測試算法 738
9.4.1實現測試 738
9.4.2MTD算法 740
9.4.3偽代碼 742
9.5蒙特卡洛樹搜索 743
9.5.1純蒙特卡洛樹搜索 743
9.5.2添加知識 748
9.6開局庫和其他固定進攻戰術 750
9.6.1實現開局庫 750
9.6.2學習開局庫 751
9.6.3固定進攻戰術庫 751
9.7進一步優化 752
9.7.1迭代加深 752
9.7.2可變深度算法 753
9.8游戲知識 755
9.8.1創建靜態評估函數 757
9.8.2學習靜態評估函數 760
9.9回合制策略游戲 764
9.9.1不可能的樹大小 764
9.9.2回合制游戲中的實時AI 765
9.10習題 766
第3部分支持技術
第10章　執行管理 769
10.1調度 769
10.1.1調度程序 770
10.1.2可中斷進程 776
10.1.3負載平衡調度程序 779
10.1.4分層調度 781
10.1.5優先級調度 782
10.2隨時算法 785
10.3細節層次 786
10.3.1圖形細節層次 786
10.3.2關于AI中的細節層次技術 787
10.3.3調度細節層次 788
10.3.4行為細節層次 789
10.3.5群體細節層次 794
10.3.6總結 797
10.4習題 797
第11章　世界接口 799
11.1通信 799
11.1.1輪詢 800
11.1.2事件 800
11.1.3確定使用的方法 801
11.2事件管理器 802
11.2.1實現 804
11.2.2事件播送 807
11.2.3代理間通信 809
11.3輪詢站點 809
11.3.1偽代碼 810
11.3.2性能 811
11.3.3實現說明 811
11.3.4抽象輪詢 811
11.4感知管理 813
11.4.1模擬才是王道 813
11.4.2內部知識和外部知識 814
11.4.3感知形態 815
11.4.4區域感知管理器 820
11.4.5有限元模型感知管理器 828
11.5習題 835
第12章　工具和內容創建 837
12.1關于工具鏈 837
12.1.1工具鏈限制AI 837
12.1.2AI知識的來源 838
12.2路徑發現和航點戰術的知識 838
12.2.1手動創建區域數據 839
12.2.2自動圖形創建 841
12.2.3幾何分析 841
12.2.4數據挖掘 844
12.3關于移動的知識 847
12.3.1障礙問題 847
12.3.2高級調度 848
12.4關于決策的知識 849
12.4.1對象類型 849
12.4.2具體動作 849
12.5工具鏈 850
12.5.1集成游戲引擎 851
12.5.2自定義數據驅動的編輯器 853
12.5.3AI設計工具 854
12.5.4遠程調試 855
12.5.5插件 856
12.6習題 857
第13章游戲AI編程 859
13.1實現語言 860
13.1.1C++ 861
13.1.2C# 861
13.1.3Swift 863
13.1.4Java 864
13.1.5JavaScript 865
13.2腳本AI 867
13.2.1腳本AI的定義 869
13.2.2優秀腳本語言的基本要件 869
13.2.3嵌入 871
13.2.4選擇開源語言 871
13.2.5語言選擇 872
13.3創建語言 877
13.3.1優點 878
13.3.2缺點 878
13.3.3創建自定義語言的實際操作 879
13.3.4工具：Lex和Yacc簡介 883
第4部分設計游戲AI
第14章　游戲AI設計 887
14.1設計 887
14.1.1示例 888
14.1.2評估行為 889
14.1.3選擇技術 891
14.1.4一款游戲的范圍 893
14.2射擊類游戲 894
14.2.1移動和射擊 895
14.2.2決策 897
14.2.3感知 898
14.2.4路徑發現和戰術AI 899
14.2.5射擊類風格游戲 900
14.2.6近戰格斗類游戲 901
14.3駕駛類游戲 904
14.3.1移動 905
14.3.2路徑發現和戰術AI 906
14.3.3類駕駛游戲 907
14.4即時戰略類游戲 907
14.4.1路徑發現 908
14.4.2群體移動 909
14.4.3戰術和戰略AI 909
14.4.4決策 910
14.4.5MOBA 911
14.5體育類游戲 912
14.5.1物理預測 913
14.5.2戰術套路庫和內容創建 914
14.6回合制戰略游戲 914
14.6.1計時 915
14.6.2幫助玩家 916
第15章　基于AI的游戲類型 917
15.1游戲角色教學 917
15.1.1表示動作 918
15.1.2表示游戲世界 918
15.1.3學習機制 919
15.1.4可預測的心理模型和病理狀態 921
15.2蜂擁算法和放牧游戲 922
15.2.1制造生物 922
15.2.2為交互調整轉向行為 923
15.2.3轉向行為的穩定性 924
15.2.4生態系統設計 925
附錄
參考資料 929
A.1圖書、期刊、論文和網站 929
A.2游戲 934