Creating robust artificial intelligence is one of the greatest challenges for game developers, yet the commercial success of a game is often dependent upon the quality of the AI. In this book, Ian Millington brings extensive professional experience to the problem of improving the quality of AI in games. He describes numerous examples from real games and explores the underlying ideas through detailed case studies. He goes further to introduce many techniques little used by developers today. The book's associated web site contains a library of C++ source code and demonstration programs, and a complete commercial source code library of AI algorithms and techniques.
"Artificial Intelligence for Games - 2nd edition" will be highly useful to academics teaching courses on game AI, in that it includes exercises with each chapter. It will also include new and expanded coverage of the following: AI-oriented gameplay; Behavior driven AI; Casual games (puzzle games).
* The first comprehensive, professional tutorial and reference to implement true AI in games written by an engineer with extensive industry experience.
* Walks through the entire development process from beginning to end.
* Includes examples from over 100 real games, 10 in-depth case studies, and web site with sample code.
Author(s): Ian Millington, John Funge
Edition: 2
Publisher: Morgan Kaufmann
Year: 2009
Language: English
Pages: 895
Title page......Page 4
Copyright page......Page 5
About the Author......Page 7
Contents......Page 8
List of Figures......Page 22
Acknowledgments......Page 30
Preface......Page 32
About the CD-ROM......Page 34
Part I. AI and Games......Page 40
1. Introduction......Page 42
1.1 What Is AI?......Page 43
1.2 My Model of Game AI......Page 48
1.3 Algorithms, Data Structures, and Representations......Page 52
1.4 On the CD......Page 56
1.5 Layout of the Book......Page 58
2.1 The Complexity Fallacy......Page 60
2.2 The Kind of AI in Games......Page 63
2.3 Speed and Memory......Page 66
2.4 The AI Engine......Page 74
Part II. Techniques......Page 78
3. Movement......Page 80
3.1 The Basics of Movement Algorithms......Page 81
3.2 Kinematic Movement Algorithms......Page 90
3.3 Steering Behaviors......Page 96
3.4 Combining Steering Behaviors......Page 139
3.5 Predicting Physics......Page 165
3.6 Jumping......Page 179
3.7 Coordinated Movement......Page 190
3.8 Motor Control......Page 219
3.9 Movement in the Third Dimension......Page 226
4. Pathfinding......Page 242
4.1 The Pathfinding Graph......Page 243
4.2 Dijkstra......Page 250
4.3 A*......Page 262
4.4 World Representations......Page 285
4.5 Improving on A*......Page 303
4.6 Hierarchical Pathfinding......Page 304
4.7 Other Ideas in Pathfinding......Page 320
4.8 Continuous Time Pathfinding......Page 325
4.9 Movement Planning......Page 332
5.1 Overview of Decision Making......Page 340
5.2 Decision Trees......Page 342
5.3 State Machines......Page 357
5.4 Fuzzy Logic......Page 383
5.5 Markov Systems......Page 408
5.6 Goal-Oriented Behavior......Page 415
5.7 Rule-Based Systems......Page 442
5.8 Blackboard Architectures......Page 475
5.9 Scripting......Page 483
5.10 Action Execution......Page 498
6.1 Waypoint Tactics......Page 512
6.2 Tactical Analyses......Page 538
6.3 Tactical Pathfinding......Page 577
6.4 Coordinated Action......Page 582
7.1 Learning Basics......Page 602
7.2 Parameter Modification......Page 606
7.3 Action Prediction......Page 619
7.4 Decision Learning......Page 630
7.5 Decision Tree Learning......Page 632
7.6 Reinforcement Learning......Page 651
7.7 Artificial Neural Networks......Page 667
8. Board Games......Page 686
8.1 Game Theory......Page 687
8.2 Minimaxing......Page 691
8.3 Transposition Tables and Memory......Page 709
8.4 Memory-Enhanced Test Algorithms......Page 717
8.5 Opening Books and Other Set Plays......Page 722
8.6 Further Optimizations......Page 724
8.7 Turn-Based Strategy Games......Page 727
Part III. Supporting Technologies......Page 730
9. Execution Management......Page 732
9.1 Scheduling......Page 733
9.3 Level of Detail......Page 751
10.1 Communication......Page 766
10.2 Getting Knowledge Efficiently......Page 767
10.3 Event Managers......Page 769
10.4 Polling Stations......Page 778
10.5 Sense Management......Page 781
11. Tools and Content Creation......Page 808
11.1 Knowledge for Pathfinding and Waypoint Tactics......Page 809
11.2 Knowledge for Movement......Page 819
11.3 Knowledge for Decision Making......Page 822
11.4 The Toolchain......Page 823
Part IV. Designing Game AI......Page 828
12.1 The Design......Page 830
12.2 Shooters......Page 837
12.3 Driving......Page 844
12.4 Real-Time Strategy......Page 848
12.5 Sports......Page 851
12.6 Turn-Based Strategy Games......Page 853
13.1 Teaching Characters......Page 856
13.2 Flocking and Herding Games......Page 862
A.1 Books, Periodicals, and Papers......Page 868
A.2 Games......Page 869
Index......Page 874
