Contents......Page 5
List of Figures......Page 18
Acknowledgments......Page 25
Part I. AI and Games......Page 33
1. Introduction......Page 34
1.1 What Is AI?......Page 35
1.2 My Model of Game AI......Page 40
1.3 Algorithms, Data Structures, and Representations......Page 44
1.4 On the CD......Page 48
1.5 Layout of the Book......Page 50
2.1 The Complexity Fallacy......Page 51
2.2 The Kind of AI in Games......Page 54
2.3 Speed and Memory......Page 57
2.4 The AI Engine......Page 65
Part II. Techniques......Page 69
3. Movement......Page 70
3.1 The Basics of Movement Algorithms......Page 71
3.2 Kinematic Movement Algorithms......Page 80
3.3 Steering Behaviors......Page 86
3.4 Combining Steering Behaviors......Page 129
3.5 Predicting Physics......Page 155
3.6 Jumping......Page 169
3.7 Coordinated Movement......Page 180
3.8 Motor Control......Page 209
3.9 Movement in the Third Dimension......Page 216
4. Pathfinding......Page 232
4.1 The Pathfinding Graph......Page 233
4.2 Dijkstra......Page 240
4.3 A......Page 252
4.4 World Representations......Page 275
4.5 Improving on A......Page 293
4.6 Hierarchical Pathfinding......Page 294
4.7 Other Ideas in Pathfinding......Page 310
4.8 Continuous Time Pathfinding......Page 315
4.9 Movement Planning......Page 322
5.1 Overview of Decision Making......Page 329
5.2 Decision Trees......Page 331
5.3 State Machines......Page 346
5.4 Fuzzy Logic......Page 372
5.5 Markov Systems......Page 397
5.6 Goal-Oriented Behavior......Page 404
5.7 Rule-Based Systems......Page 431
5.8 Blackboard Architectures......Page 464
5.9 Scripting......Page 472
5.10 Action Execution......Page 487
6.1 Waypoint Tactics......Page 500
6.2 Tactical Analyses......Page 526
6.3 Tactical Pathfinding......Page 565
6.4 Coordinated Action......Page 570
7.1 Learning Basics......Page 589
7.2 Parameter Modification......Page 593
7.3 Action Prediction......Page 606
7.4 Decision Learning......Page 617
7.5 Decision Tree Learning......Page 619
7.6 Reinforcement Learning......Page 638
7.7 Artificial Neural Networks......Page 654
8. Board Games......Page 672
8.1 Game Theory......Page 673
8.2 Minimaxing......Page 677
8.3 Transposition Tables and Memory......Page 695
8.4 Memory-Enhanced Test Algorithms......Page 703
8.5 Opening Books and Other Set Plays......Page 708
8.6 Further Optimizations......Page 710
8.7 Turn-Based Strategy Games......Page 713
Part III. Supporting Technologies......Page 716
9. Execution Management......Page 717
9.1 Scheduling......Page 718
9.3 Level of Detail......Page 736
10.1 Communication......Page 750
10.2 Getting Knowledge Efficiently......Page 751
10.3 Event Managers......Page 753
10.4 Polling Stations......Page 762
10.5 Sense Management......Page 765
11. Tools and Content Creation......Page 792
11.1 Knowledge for Pathfinding and Waypoint Tactics......Page 793
11.2 Knowledge for Movement......Page 803
11.3 Knowledge for Decision Making......Page 806
11.4 The Toolchain......Page 807
Part IV. Designing Game AI......Page 811
12.1 The Design......Page 812
12.2 Shooters......Page 819
12.3 Driving......Page 826
12.4 Real-Time Strategy......Page 830
12.5 Sports......Page 833
12.6 Turn-Based Strategy Games......Page 835
13.1 Teaching Characters......Page 838
13.2 Flocking and Herding Games......Page 844
A.1 Books, Periodicals, and Papers......Page 849
A.2 Games......Page 850
Index......Page 854