Artificial Intelligence For Games

by Millington

• ISBN13: 9780124977822
• ISBN10: 0124977820
• Edition: DVD
• Format: Hardcover
• Copyright: 2006-07-28
• Publisher: Elsevier Science

Summary

Creating robust artificial intelligence is one of the greatest challenges for game developers. The commercial success of a game is often dependent upon the quality of the AI, yet the engineering of AI is often begun late in the development process and is frequently misunderstood. In this book, Ian Millington brings extensive professional experience to the problem of improving the quality of AI in games. A game developer since 1987, he was founder of Mindlathe Ltd., at the time the largest specialist AI company in gaming. Ian shows how to think about AI as an integral part of game play. 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 books CD-ROM contains a library of C++ source code and demonstration programs, and provides access to a website with a complete commercial source code library of AI algorithms and techniques. * A comprehensive, professional tutorial and reference to implement true AI in games. * Walks through the entire development process from beginning to end. * Includes over 100 pseudo code examples of techniques used in commercial games, case studies for all major genres, a CD-ROM and companion website with extensive C++ source code implementations for Windows, and source code libraries for Linux and OS X available through the website.

Table of Contents

About the Author	vi
List of Figures	xxi
Acknowledgments	xxix
Preface	xxxi
About the CD-ROM	xxxiii
Part I Ai and Games	1	(38)
Introduction	3	(18)
What Is AI?	4	(5)
Academic AI	5	(2)
Game AI	7	(2)
My Model of Game AI	9	(4)
Movement	10	(1)
Decision Making	10	(1)
Strategy	11	(1)
Infrastructure	11	(1)
Agent-Based AI	12	(1)
In the Book	12	(1)
Algorithms, Data Structures, and Representations	13	(4)
Algorithms	13	(3)
Representations	16	(1)
On the CD	17	(2)
Programs	17	(1)
Libraries	18	(1)
Layout of the Book	19	(2)
Game AI	21	(18)
The Complexity Fallacy	21	(3)
When Simple Things Look Good	21	(1)
When Complex Things Look Bad	22	(1)
The Perception Window	23	(1)
Changes of Behavior	23	(1)
The Kind of AI in Games	24	(3)
Hacks	24	(1)
Heuristics	25	(2)
Algorithms	27	(1)
Speed and Memory	27	(8)
Processor Issues	28	(3)
Memory Concerns	31	(1)
PC Constraints	32	(1)
Console Constraints	32	(3)
The AI Engine	35	(4)
Structure of an AI Engine	35	(2)
Toolchain Concerns	37	(1)
Putting It All Together	38	(1)
PART II Techniques	39	(652)
Movement	41	(162)
The Basics of Movement Algorithms	42	(9)
Two-Dimensional Movement	43	(1)
Statics	44	(3)
Kinematics	47	(4)
Kinematic Movement Algorithms	51	(6)
Seek	52	(3)
Wandering	55	(2)
On the CD	57	(1)
Steering Behaviors	57	(43)
Steering Basics	58	(1)
Variable Matching	58	(1)
Seek and Flee	59	(3)
Arrive	62	(4)
Align	66	(3)
Velocity Matching	69	(1)
Delegated Behaviors	70	(1)
Pursue and Evade	71	(3)
Face	74	(1)
Looking Where You're Going	75	(1)
Wander	76	(3)
Path Following	79	(6)
Separation	85	(3)
Collision Avoidance	88	(6)
Obstacle and Wall Avoidance	94	(5)
Summary	99	(1)
Combining Steering Behaviors	100	(26)
Blending and Arbitration	100	(1)
Weighted Blending	101	(6)
Priorities	107	(4)
Cooperative Arbitration	111	(2)
Steering Pipeline	113	(13)
Predicting Physics	126	(14)
Aiming and Shooting	126	(1)
Projectile Trajectory	127	(2)
The Firing Solution	129	(3)
Projectiles with Drag	132	(2)
Iterative Targeting	134	(6)
Jumping	140	(11)
Jump Points	141	(4)
Landing Pads	145	(4)
Hole Fillers	149	(2)
Coordinated Movement	151	(29)
Fixed Formations	151	(2)
Scalable Formations	153	(1)
Emergent Formations	153	(2)
Two-Level Formation Steering	155	(3)
Implementation	158	(7)
Extending to More than Two Levels	165	(2)
Slot Roles and Better Assignment	167	(2)
Slot Assignment	169	(5)
Dynamic Slots and Plays	174	(3)
Tactical Movement	177	(3)
Motor Control	180	(7)
Output Filtering	181	(2)
Capability-Sensitive Steering	183	(1)
Common Actuation Properties	184	(3)
Movement in the Third Dimension	187	(16)
Rotation in Three Dimensions	188	(1)
Converting Steering Behaviors to Three Dimensions	189	(1)
Align	190	(1)
Align to Vector	191	(1)
Face	192	(3)
Look Where You're Going	195	(1)
Wander	195	(3)
Faking Rotation Axes	198	(5)
Pathfinding	203	(98)
The Pathfinding Graph	204	(7)
Graphs	205	(1)
Weighted Graphs	206	(2)
Directed Weighted Graphs	208	(1)
Terminology	209	(1)
Representation	210	(1)
Dijkstra	211	(12)
The Problem	211	(1)
The Algorithm	212	(4)
Pseudo-Code	216	(3)
Data Structures and Interfaces	219	(2)
Performance of Dijkstra	221	(1)
Weaknesses	221	(2)
A*	223	(23)
The Problem	223	(1)
The Algorithm	223	(4)
Pseudo-Code	227	(4)
Data Structures and Interfaces	231	(4)
Implementation Notes	235	(1)
Algorithm Performance	236	(1)
Node Array A*	236	(3)
Choosing a Heuristic	239	(7)
World Representations	246	(18)
Tile Graphs	248	(3)
Dirichlet Domains	251	(2)
Points of Visibility	253	(2)
Polygonal Meshes	255	(5)
Non-Translational Problems	260	(1)
Cost Functions	261	(1)
Path Smoothing	262	(2)
Improving on A*	264	(1)
Hierarchical Pathfinding	265	(16)
The Hierarchical Pathfinding Graph	265	(4)
Pathfinding on the Hierarchical Graph	269	(3)
Hierarchical Pathfinding on Exclusions	272	(1)
Strange Effects of Hierarchies on Pathfinding	272	(3)
Instanced Geometry	275	(6)
Other Ideas in Pathfinding	281	(5)
Open Goal Pathfinding	282	(1)
Dynamic Pathfinding	282	(1)
Other Kinds of Information Reuse	283	(1)
Low Memory Algorithms	283	(2)
Interruptible Pathfinding	285	(1)
Pooling Planners	285	(1)
Continuous Time Pathfinding	286	(7)
The Problem	286	(2)
The Algorithm	288	(4)
Implementation Notes	292	(1)
Performance	292	(1)
Weaknesses	293	(1)
Movement Planning	293	(8)
Animations	293	(2)
Movement Planning	295	(2)
Example	297	(1)
Footfalls	298	(3)
Decision Making	301	(172)
Overview of Decision Making	301	(2)
Decision Trees	303	(15)
The Problem	303	(1)
The Algorithm	304	(5)
Pseudo-Code	309	(2)
On the CD	311	(1)
Knowledge Representation	311	(1)
Implementation Nodes	312	(1)
Performance of Decision Trees	312	(1)
Balancing the Tree	312	(2)
Beyond the Tree	314	(1)
Random Decision Trees	315	(3)
State Machines	318	(26)
The Problem	320	(1)
The Algorithm	320	(1)
Pseudo-Code	320	(1)
Data Structures and Interfaces	321	(3)
On the CD	324	(1)
Performance	325	(1)
Implementation Notes	325	(1)
Hard-Coded FSM	325	(2)
Hierarchical State Machines	327	(14)
Combining Decision Trees and State Machines	341	(3)
Fuzzy Logic	344	(25)
Introduction to Fuzzy Logic	344	(10)
Fuzzy Logic Decision Making	354	(10)
Fuzzy State Machines	364	(5)
Markov Systems	369	(7)
Markov Processes	370	(3)
Markov State Machine	373	(3)
Goal-Oriented Behavior	376	(27)
Goal-Oriented Behavior	377	(1)
Simple Selection	378	(2)
Overall Utility	380	(3)
Timing	383	(5)
Overall Utility GOAP	388	(6)
GOAP with IDA*	394	(7)
Smelly GOB	401	(2)
Rule-Based Systems	403	(33)
The Problem	404	(5)
The Algorithm	409	(1)
Pseudo-Code	410	(1)
Data Structures and Interfaces	411	(5)
Implementation Notes	416	(2)
Rule Arbitration	418	(2)
Unification	420	(2)
Rete	422	(11)
Extensions	433	(3)
Where Next	436	(1)
Blackboard Architectures	436	(8)
The Problem	437	(1)
The Algorithm	437	(2)
Pseudo-Code	439	(1)
Data Structures and Interfaces	440	(2)
Performance	442	(1)
Other Things Are Blackboard Systems	443	(1)
Scripting	444	(15)
Language Facilities	445	(1)
Embedding	446	(1)
Choosing a Language	447	(2)
A Language Selection	449	(4)
Rolling Your Own	453	(6)
Scripting Languages and Other AI	459	(1)
Action Execution	459	(14)
Types of Action	460	(4)
The Algorithm	464	(1)
Pseudo-Code	465	(2)
Data Structures and Interfaces	467	(2)
Implementation Notes	469	(1)
Performance	470	(1)
Putting It All Together	470	(3)
Tactical and Strategic AI	473	(90)
Waypoint Tactics	473	(26)
Tactical Locations	474	(9)
Using Tactical Locations	483	(5)
Generating the Tactical Properties of a Waypoint	488	(6)
Automatically Generating the Waypoints	494	(1)
The Condensation Algorithm	495	(4)
Tactical Analyses	499	(39)
Representing the Game Level	500	(1)
Simple Influence Maps	500	(8)
Terrain Analysis	508	(2)
Learning with Tactical Analyses	510	(2)
A Structure for Tactical Analyses	512	(5)
Map Flooding	517	(4)
Convolution Filters	521	(12)
Cellular Automata	533	(5)
Tactical Pathfinding	538	(5)
The Cost Function	538	(1)
Tactic Weights and Concern Blending	538	(3)
Modifying the Pathfinding Heuristic	541	(1)
Tactical Graphs for Pathfinding	542	(1)
Using Tactical Waypoints	542	(1)
Coordinated Action	543	(20)
Multi-Tier AI	544	(7)
Emergent Cooperation	551	(3)
Scripting Group Actions	554	(5)
Military Tactics	559	(4)
Learning	563	(84)
Learning Basics	563	(4)
Online or Offline Learning	564	(1)
Intra-Behavior Learning	564	(1)
Inter-Behavior Learning	565	(1)
A Warning	565	(1)
Over-learning	566	(1)
The Zoo of Learning Algorithms	566	(1)
The Balance of Effort	567	(1)
Parameter Modification	567	(13)
The Parameter Landscape	567	(2)
Hill Climbing	569	(3)
Extensions to Basic Hill Climbing	572	(4)
Annealing	576	(4)
Action Prediction	580	(11)
Left or Right	581	(1)
Raw Probability	581	(1)
String Matching	582	(1)
N-Grams	582	(4)
Window Size	586	(2)
Hierarchical N-Grams	588	(3)
Application in Combat	591	(1)
Decision Learning	591	(2)
Structure of Decision Learning	592	(1)
What Should You Learn?	592	(1)
Three Techniques	593	(1)
Decision Tree Learning	593	(19)
ID3	594	(8)
ID3 with Continuous Attributes	602	(5)
Incremental Decision Tree Learning	607	(5)
Reinforcement Learning	612	(16)
The Problem	613	(1)
The Algorithm	613	(4)
Pseudo-Code	617	(1)
Data Structures and Interfaces	618	(1)
Implementation Notes	619	(1)
Performance	619	(1)
Tailoring Parameters	619	(4)
Weaknesses and Realistic Applications	623	(3)
Other Ideas in Reinforcement Learning	626	(2)
Artificial Neural Networks	628	(19)
Overview	629	(3)
The Problem	632	(1)
The Algorithm	633	(3)
Pseudo-Code	636	(2)
Data Structures and Interfaces	638	(2)
Implementation Caveats	640	(1)
Performance	641	(1)
Other Approaches	641	(6)
Board Games	647	(44)
Game Theory	648	(4)
Types of Games	648	(2)
The Game Tree	650	(2)
Minimaxing	652	(18)
The Static Evaluation Function	652	(2)
Minimaxing	654	(2)
The Minimaxing Algorithm	656	(3)
Negamaxing	659	(2)
AB Pruning	661	(4)
The AB Search Window	665	(1)
Negascout	666	(4)
Transposition Tables and Memory	670	(8)
Hashing Game States	670	(3)
What to Store in the Table	673	(1)
Hash Table Implementation	674	(2)
Replacement Strategies	676	(1)
A Complete Transposition Table	676	(1)
Transposition Table Issues	677	(1)
Using Opponent's Thinking Time	678	(1)
Memory-Enhanced Test Algorithms	678	(5)
Implementing Test	678	(3)
The MTD Algorithm	681	(1)
Pseudo-Code	682	(1)
Opening Books and Other Set Plays	683	(2)
Implementing an Opening Book	684	(1)
Learning for Opening Books	684	(1)
Set Play Books	685	(1)
Further Optimizations	685	(3)
Iterative Deepening	686	(1)
Variable Depth Approaches	687	(1)
Turn-Based Strategy Games	688	(3)
Impossible Tree Size	689	(1)
Real-Time AI in a Turn-Based Game	690	(1)
Part III Supporting Technologies	691	(98)
Execution Management	693	(34)
Scheduling	694	(18)
The Scheduler	694	(8)
Interruptible Processes	702	(3)
Load-Balancing Scheduler	705	(2)
Hierarchical Scheduling	707	(2)
Priority Scheduling	709	(3)
Anytime Algorithms	712	(1)
Level of Detail	712	(15)
Graphics Level of Detail	713	(1)
AI LOD	713	(1)
Scheduling LOD	714	(1)
Behavioral LOD	715	(6)
Group LOD	721	(3)
In Summary	724	(3)
World Interfacing	727	(42)
Communication	727	(1)
Getting Knowledge Efficiently	728	(2)
Polling	728	(1)
Events	729	(1)
Determining What Approach to Use	730	(1)
Event Managers	730	(9)
Implementation	733	(3)
Event Casting	736	(2)
Inter-Agent Communication	738	(1)
Polling Stations	739	(3)
Pseudo-Code	739	(1)
Performance	740	(1)
Implementation Notes	740	(1)
Abstract Polling	741	(1)
Sense Management	742	(27)
Faking It	743	(1)
What Do I Know?	743	(1)
Sensory Modalities	744	(6)
Region Sense Manager	750	(8)
Finite Element Model Sense Manager	758	(11)
Tools and Content Creation	769	(20)
Toolchains Limit AI	770	(1)
Where AI Knowledge Comes from	770	(1)
Knowledge for Pathfinding and Waypoint Tactics	770	(10)
Manually Creating Region Data	771	(3)
Automatic Graph Creation	774	(1)
Geometric Analysis	774	(4)
Data Mining	778	(2)
Knowledge for Movement	780	(3)
Obstacles	780	(2)
High-Level Staging	782	(1)
Knowledge for Decision Making	783	(1)
Object Types	783	(1)
Concrete Actions	783	(1)
The Toolchain	784	(5)
Data-Driven Editors	784	(1)
AI Design Tools	785	(1)
Remote Debugging	786	(1)
Plug-Ins	787	(2)
Part IV Designing Game Ai	789	(40)
Designing Game AI	791	(26)
The Design	791	(7)
Example	792	(1)
Evaluating the Behaviors	793	(3)
Selecting Techniques	796	(2)
The Scope of One Game	798	(1)
Shooters	798	(7)
Movement and Firing	799	(2)
Decision Making	801	(1)
Perception	802	(1)
Pathfinding and Tactical AI	802	(1)
Shooter-Like Games	803	(2)
Driving	805	(4)
Movement	805	(3)
Pathfinding and Tactical AI	808	(1)
Driving-Like Games	808	(1)
Real-Time Strategy	809	(3)
Pathfinding	810	(1)
Group Movement	810	(1)
Tactical and Strategic AI	811	(1)
Decision Making	811	(1)
Sports	812	(2)
Physics Prediction	813	(1)
Playbooks and Content Creation	814	(1)
Turn-Based Strategy Games	814	(3)
Timing	815	(1)
Helping the Player	816	(1)
AI-Based Game Genres	817	(12)
Teaching Characters	817	(6)
Representing Actions	818	(1)
Representing the World	818	(1)
Learning Mechanism	819	(2)
Predictable Mental Models and Pathological States	821	(2)
Flocking and Herding Games	823	(6)
Making the Creatures	823	(1)
Tuning Steering for Interactivity	823	(2)
Steering Behavior Stability	825	(1)
Ecosystem Design	825	(4)
Appendix
A. References	829	(6)
Books, Periodicals, and Papers	829	(1)
Games	830	(5)
Index	835