AI Game Engine Programming, Second Edition

Contents......Page 8
Preface......Page 28
Introduction......Page 30
1 Basic Definitions and Concepts......Page 32
What Is \"Game AI\"?......Page 33
What Game AI Is Not......Page 37
How This Definition Differs from That of Academic AI......Page 39
Brain Organization......Page 41
Knowledge Base and Learning......Page 42
Cognition......Page 46
Theory of Mind......Page 48
Bounded Optimality......Page 55
Theory of Mind......Page 57
Multiple Layered Decision Architectures......Page 58
Summary......Page 59
Decision Making and Inference......Page 62
Types of Solutions......Page 63
System Realism......Page 64
Genre......Page 65
Platform......Page 66
Development Limitations......Page 68
Entertainment Limitations......Page 70
Perception Type......Page 71
Load Balancing......Page 72
Computation Cost and Preconditions......Page 73
Grid-Based......Page 74
Simple Avoidance and Potential Fields......Page 75
Map Node Networks......Page 76
Navigation Mesh......Page 78
Obstacle Avoidance......Page 79
Bringing It All Together......Page 80
Summary......Page 82
3 AIsteroids: Our AI Test Bed......Page 84
The GameObj Class......Page 85
The Ship Object......Page 88
The Other Game Objects......Page 90
The GameSession Class......Page 91
Primary Logic and Collision Checking......Page 93
Object Cleanup......Page 94
Spawning Main Ship and Powerups......Page 95
End of Level and Game......Page 96
The AI System Hooks......Page 97
Summary......Page 99
4 Role-Playing Games (RPGs)......Page 100
Enemies......Page 105
Bosses......Page 106
Nonplayer Characters (NPCs)......Page 107
Shopkeepers......Page 108
Party Members......Page 109
Scripting......Page 111
Finite-State Machines (FSMs)......Page 112
Examples......Page 113
Exceptions......Page 114
Role Playing Does Not Equal Combat......Page 115
Quest Generators......Page 117
Better Party Member AI......Page 118
Better Enemies......Page 119
Fully-Realized Towns......Page 120
Summary......Page 121
5 Adventure Games......Page 124
Enemy AI......Page 126
Perception Systems......Page 127
Finite-State Machines (FSMs)......Page 128
Fuzzy Logic......Page 129
Better NPC Communication......Page 132
Summary......Page 133
Common AI Elements......Page 136
Economic Individual Units......Page 137
High-Level Strategic AI......Page 138
Town Building......Page 139
Pathfinding......Page 140
Tactical and Strategic Support Systems......Page 141
Messaging......Page 143
Hierarchical AI......Page 144
Scripting......Page 145
Data-Driven AI......Page 146
Examples......Page 147
Areas That Need Improvement......Page 148
Determining When an AI Element Is Stuck......Page 149
Opponent Personality......Page 150
More Strategy, Less Tactics......Page 151
Summary......Page 152
7 First-Person Shooters/Third-Person Shooters (FTPS)......Page 154
Enemies......Page 157
Deathmatch Opponents......Page 158
Squad Members......Page 159
Pathfinding......Page 160
Finite-State Machines (FSMs)......Page 161
Messaging Systems......Page 165
Examples......Page 166
Areas That Need Improvement......Page 167
Learning and Opponent Modeling......Page 168
Creativity......Page 169
Motivations......Page 170
Summary......Page 171
8 Platform Games......Page 174
Enemies......Page 180
Camera......Page 181
Scripted Systems......Page 183
Examples......Page 184
Help Systems......Page 185
Summary......Page 186
9 Shooter Games......Page 188
Boss Enemies......Page 194
Finite-State Machines (FSMs)......Page 195
Exceptions......Page 196
Examples......Page 197
Innovative Gameplay Mechanics......Page 199
Summary......Page 200
10 Sports Games......Page 202
Common AI Elements......Page 203
Player-Level AI......Page 204
Camera......Page 206
Miscellaneous Elements......Page 207
Finite-State Machines (FSMs) and Fuzzy-State Machines (FuSMs)......Page 208
Messaging Systems......Page 216
Examples......Page 217
Game Balance......Page 218
Gameplay Innovation......Page 219
Summary......Page 220
11 Racing Games......Page 222
Track AI......Page 224
Pedestrians......Page 226
Other Competitive Behavior......Page 227
Messaging Systems......Page 228
Areas That Need Improvement......Page 229
Persistent Worlds......Page 230
Summary......Page 231
12 Classic Strategy Games......Page 234
Helper AI......Page 246
Alpha-Beta Search......Page 247
Genetic Algorithms (GAs)......Page 248
Speed......Page 249
Summary......Page 250
13 Fighting Games......Page 252
Common AI Elements......Page 254
Boss Enemies......Page 255
Finite-State Machines (FSMs)......Page 256
Scripting Systems......Page 257
Areas That Need Improvement......Page 258
Summary......Page 259
Civilization Games......Page 262
God Games......Page 271
War Games......Page 274
Flight Simulators (SIMS)......Page 280
Rhythm Games......Page 285
Puzzle Games......Page 286
Artificial Life (Alife) Games......Page 287
Summary......Page 290
FSM Overview......Page 292
FSM Skeletal Code......Page 297
The FSMState Class......Page 298
The FSMMachine Class......Page 299
The FSMAIControl Class......Page 301
Implementing an FSM-Controlled Ship into Our Test Bed......Page 302
Example Implementation......Page 303
Coding the Control Class......Page 304
Coding the States......Page 306
Performance of the AI with This System......Page 316
Pros of FSM-Based Systems......Page 318
Cons of FSM-Based Systems......Page 319
Hierarchical FSMs......Page 320
FSMs with Fuzzy Transitions......Page 321
Multiple-Concurrent FSMs......Page 322
Data-Driven FSMs......Page 323
Inertial FSMs......Page 324
Load Balancing Both FSMs and Perceptions......Page 326
Level-of-Detail (LOD) AI Systems......Page 327
Types of Solutions......Page 328
Genre......Page 329
Development Limitations......Page 330
Summary......Page 331
FuSM Overview......Page 334
The FuSMState Class......Page 339
The FuSMMachine Class......Page 341
The FuSMAIControl Class......Page 343
A New Addition, the Saucer......Page 344
The FuSM System......Page 345
Coding the Control Class......Page 347
Coding the Fuzzy States......Page 349
Performance of the AI with This System......Page 354
Pros of FuSM-Based Systems......Page 356
Cons of FuSM-Based Systems......Page 357
FuSMS with a Limited Number of Concurrent States......Page 358
Hierarchical FuSMs......Page 359
Types of Solutions......Page 360
Genre......Page 361
Entertainment Limitations......Page 362
Summary......Page 363
Messaging Overview......Page 366
Messaging Skeletal Code......Page 368
The Message Object......Page 369
The MessagePump......Page 370
Client Handlers......Page 374
The MessState Class......Page 375
The MessMachine Class......Page 376
The MessAIControl Class......Page 377
Coding the States......Page 383
Pros of Messaging Systems......Page 386
Cons of Messaging Systems......Page 387
Message Arbitration......Page 388
Automatic and Extended Message Types......Page 389
Types of Solutions......Page 390
Development Limitations......Page 391
Summary......Page 392
Scripting Overview......Page 394
A Configuration Script System......Page 396
Embedding Lua......Page 403
Lua Language Fundamentals......Page 404
Integration......Page 408
Example Implementation in the AIsteroids Test Bed......Page 412
A Description of a Better System......Page 416
Performance of the AI with This System......Page 417
Pros of Scripting Systems......Page 418
Cons of Scripted Systems......Page 420
Built-In Debugging Tools......Page 423
Automatic Integration with the Game......Page 424
Optimizations......Page 425
Types of Solutions......Page 426
System Realism......Page 427
Summary......Page 428
Location-Based Information Systems Overview......Page 430
Influence Maps (IMs)......Page 431
Terrain Analysis (TA)......Page 432
Occupance Data......Page 433
Pathfinding System Helper Data......Page 434
Simple Terrain Analysis......Page 435
Advanced Terrain Analysis......Page 436
Influence Mapping Skeletal Code and Test-Bed Implementation......Page 437
The OccupanceInfluenceMap......Page 444
Uses Within the Test Bed for an Occupance IM......Page 449
The ControlInfluenceMap......Page 450
The BitwiseInfluenceMap......Page 453
Other Implementations......Page 460
Extensions to the Paradigm......Page 463
Design Considerations......Page 464
Genre and Platform......Page 465
Summary......Page 466
Steering Behavior Overview......Page 468
The SteeringBehavior Class......Page 471
The SteeringBehaviorManager Class......Page 473
Implementing a Steering-Controlled Ship into Our Test Bed......Page 479
Coding the Control Class......Page 493
Performance of the AI with This System......Page 496
Pros of Steering-Based Systems......Page 497
Cons of FSM-Based Systems......Page 498
Layered Steering......Page 499
Learning Behaviors......Page 500
Other Common Behaviors......Page 501
Data-Driven Steering Behaviors......Page 502
Load Balancing......Page 503
Design Considerations......Page 504
System Realism......Page 505
Platform......Page 506
Summary......Page 507
The Demo......Page 510
FSM Changes......Page 515
Steering Changes......Page 529
Performance of the AI with This System......Page 533
FSMS......Page 538
Influence Mapping......Page 539
Scripting......Page 540
Messaging......Page 541
Summary......Page 542
Overview......Page 544
Evolution in Nature......Page 545
Evolution in Games......Page 546
Generate New Individuals Using Reproduction......Page 548
The Gene and Genome......Page 549
The Fitness Function......Page 552
Reproduction......Page 553
Implementing a Genetic Algorithm System into the AIsteroids Test Bed......Page 558
Performance Within the Test Bed......Page 575
Pros of Genetic Algorithm-Based Systems......Page 576
Cons of Genetic Algorithm-Based Systems......Page 578
Extensions to the Paradigm......Page 580
Coevolution......Page 581
Types of Solutions......Page 582
Platform......Page 583
Summary......Page 584
Neural Nets in Nature......Page 586
Artificial Neural Nets Overview......Page 588
Structure......Page 591
Creating Training Data......Page 593
An Aside on Neural Network Activity......Page 594
Implementing a Neural Net Within the AIsteroids Test Bed......Page 597
The NeuralNet Class......Page 598
The NLayer Class......Page 603
The NNAIControl Class......Page 607
Performance Within the Test Bed......Page 614
Optimization......Page 615
Cons of Neural Net-Based Systems......Page 616
Other Types of NNs......Page 618
Other Types of NN Learning......Page 620
System Realism......Page 621
Summary......Page 622
Artificial Life......Page 624
Artificial Life Disciplines......Page 625
Pros......Page 627
Areas for Exploitation Within Games......Page 628
Planning Algorithms......Page 629
Current Usage in Games......Page 630
Pros......Page 632
Areas for Exploitation Within Games......Page 633
Production Systems......Page 634
Pros......Page 635
Decision Trees......Page 637
Pros......Page 639
Areas for Exploitation Within Games......Page 640
Fuzzy Logic......Page 641
Areas for Exploitation Within Games......Page 643
Summary......Page 644
Basic Overview......Page 646
A Real-Life Example......Page 647
The Real-Life Example Revisited......Page 648
The Behavior Layer......Page 650
The Animation Layer......Page 652
The Motion Layer......Page 655
Long-Term Decision Making (LT)......Page 656
Location-Based Information Layer (LBI)......Page 657
Brooks Subsumption Architectures......Page 658
Distributed Super Mario Bros.......Page 659
AI Enemies Implementation......Page 660
AI Player Implementation......Page 666
Summary......Page 670
Design Considerations......Page 672
Concerns with Data-Driven AI Systems......Page 673
The One-Track-Mind Syndrome......Page 675
Level-of-Detail (LOD) AI......Page 676
Support AI......Page 679
General AI Design Thinking......Page 681
Entertainment Considerations......Page 682
The All-Important Fun Factor......Page 683
Perceived Randomness......Page 684
Some Things That Make an AI System Look Stupid......Page 686
Coherent AI Behavior......Page 688
Thinking About Tuning Ahead of Time......Page 689
Consider Designer-Used Tools Differently......Page 690
Summary......Page 691
General Debugging of AI Systems......Page 692
Debugging and Tuning......Page 693
Double-Duty Influence Mapping......Page 694
Implementation......Page 695
BasicButton......Page 699
RadioButton......Page 700
OnOffButton......Page 701
ScrubberWidget......Page 702
Integration Within a Program......Page 703
Summary......Page 708
28 Conclusions, and the Future......Page 710
What Game AI Will Be in the Future......Page 711
Appendix A: About the CD......Page 714
Appendix B: References......Page 716
A......Page 718
C......Page 720
D......Page 723
E......Page 724
F......Page 725
G......Page 726
H......Page 728
L......Page 729
M......Page 730
N......Page 731
O......Page 732
P......Page 733
R......Page 735
S......Page 736
T......Page 739
W......Page 740
Z......Page 741