●部分 AI和游戏
章 导论 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. 分层结构对路径发现的奇怪影响 255
4.6.5 实例几何 257
4.7 路径发现中的其他思路 263
4.7.1 开放目标路径发现 263
4.7.2 动态路径发现 263
4.7.3 其他类型的信息重用 2
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
6.3.5 使用战术航点 528
协调动作 529
.1 多层AI 530
.2 自发合作 536
.3 编写群体动作的脚本 538
.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.4 N-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.3 4种技术 576
7.5 朴素贝叶斯分类算法 577
7.5.1 伪代码 580
7.5.2 实现说明 582
7.6 决策树学习 582
7.6.1 ID3 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 伪随机数 1
8.1.1 数值混合和游戏种子 1
8.1.2 霍尔顿序列 3
8.1.3 叶序的角度 6
8.1.4 泊松圆盘 7
8.2 Lindenmayer系统 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 断层 6
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.5 AB修剪 722
9.2.6 AB搜索窗口 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.2 MTD算法 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 回合制策略游戏 7
9.9.1 不可能的树大小 7
9.9.2 回合制游戏中的实时AI 765
9.10 习题 766
第3部分 支持技术
0章 执行管理 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
1章 世界接口 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
2章 工具和内容创建 837
12.1 关于工具链 837
12.1.1 工具链AI 837
12.1.2 AI知识的来源 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.3 AI设计工具 854
12.5.4 远程调试 855
12.5.5 插件 856
12.6 习题 857
3章 游戏AI编程 859
13.1 实现语言 860
13.1.1 C 861
13.1.2 C# 861
13.1.3 Swift 863
13.1.4 Java 8
13.1.5 JavaScript 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
4章 游戏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.5 MOBA 911
14.5 体育类游戏 912
14.5.1 物理预测 913
14.5.2 战术套路库和内容创建 914
14.6 回合制战略游戏 914
14.6.1 计时 915
14.6.2 帮助玩家 916
5章 基于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