Artificial Intelligence For Games 2nd Edition Ian

Millington 2025 easy download

Order directly from ebookultra.com

( 4.4/5.0 ★ | 482 downloads )

https://ebookultra.com/download/artificial-intelligence-for-
games-2nd-edition-ian-millington/
Artificial Intelligence For Games 2nd Edition Ian Millington

EBOOK

Available Formats

■ PDF eBook Study Guide Ebook

EXCLUSIVE 2025 ACADEMIC EDITION – LIMITED RELEASE

Available Instantly Access Library

We have selected some products that you may be interested in
Click the link to download now or visit ebookultra.com
for more options!.

Artificial Intelligence for Games Companion CD ROM Ian

Millington

https://ebookultra.com/download/artificial-intelligence-for-games-
companion-cd-rom-ian-millington/

Artificial Intelligence with Uncertainty 2nd Edition

Edition Deyi Li

https://ebookultra.com/download/artificial-intelligence-with-
uncertainty-2nd-edition-edition-deyi-li/

Logic for Computer Science and Artificial Intelligence 1st

Edition Ricardo Caferra

https://ebookultra.com/download/logic-for-computer-science-and-
artificial-intelligence-1st-edition-ricardo-caferra/

Civil Liability for Artificial Intelligence and Software

1st Edition Mark A. Geistfeld

https://ebookultra.com/download/civil-liability-for-artificial-
intelligence-and-software-1st-edition-mark-a-geistfeld/
Artificial Intelligence and You 1st Edition Corona Brezina

https://ebookultra.com/download/artificial-intelligence-and-you-1st-
edition-corona-brezina/

Artificial Intelligence in the 21st Century A Living

Introduction 2nd Edition Stephen Lucci

https://ebookultra.com/download/artificial-intelligence-in-the-21st-
century-a-living-introduction-2nd-edition-stephen-lucci/

Application of Artificial Intelligence to Assessment Hong

Jiao

https://ebookultra.com/download/application-of-artificial-
intelligence-to-assessment-hong-jiao/

Artificial intelligence in power system optimization 1st

Edition Ongsakul

https://ebookultra.com/download/artificial-intelligence-in-power-
system-optimization-1st-edition-ongsakul/

Artificial Intelligence Structures and Strategies for

Complex Problem Solving 6th Edition George F. Luger

https://ebookultra.com/download/artificial-intelligence-structures-
and-strategies-for-complex-problem-solving-6th-edition-george-f-luger/
Ian Millington crosses the boundary between academic and professional game AI with
his book Artificial Intelligence for Games. Most books either lack academic rigor or are
rigorous with algorithms that won’t work under the CPU constraints imposed by modern
games. This book walks a line between the two and does it well. It explains algorithms
rigorously while also discussing appropriate implementation details such as scheduling
AI over time and using the right data structures. I will be using this book for my Game
AI course.
—Jessica D. Bayliss, Ph.D.
Rochester Institute of Technology

This is the first serious attempt to create a comprehensive reference for all game AI prac-
tices, terminology, and know-how. Works like this are badly needed by the maturing
video games industry. Systematic yet accessible, it is a must-have for any student or pro-
fessional.
—Marcin Chady, Ph.D.
Radical Entertainment

This book promises to be the closest I’ve seen to what is needed in the field. I would highly
recommend it for people in the industry.
—John Laird
University of Michigan

Ian Millington’s book is a comprehensive reference to the most widely used techniques in
game AI today. Any game developer working on AI will learn something from this book,
and game producers should make sure their AI programmers have a copy.
—Dr. Ian Lane Davis
Mad Doc Software
The Morgan Kaufmann Series in Interactive 3D Technology
Series Editor: David H. Eberly, Geometric Tools, Inc.
The game industry is a powerful and driving force in the evolution of computer tech-
nology. As the capabilities of personal computers, peripheral hardware, and game
consoles have grown, so has the demand for quality information about the algo-
rithms, tools, and descriptions needed to take advantage of this new technology. To
satisfy this demand and establish a new level of professional reference for the game de-
veloper, we created the Morgan Kaufmann Series in Interactive 3D Technology. Books
in the series are written for developers by leading industry professionals and academic
researchers, and cover the state of the art in real-time 3D. The series emphasizes prac-
tical, working solutions and solid software-engineering principles. The goal is for the
developer to be able to implement real systems from the fundamental ideas, whether
it be for games or for other applications.

Artificial Intelligence for Games Physically Based Rendering: From Theory

Ian Millington to Implementation
Better Game Characters by Design: Matt Pharr and Greg Humphreys
A Psychological Approach Essential Mathematics for Games and
Katherine Isbister Interactive Applications: A Programmer’s
Visualizing Quaternions Guide
Andrew J. Hanson James M. Van Verth and Lars M. Bishop
3D Game Engine Architecture:
Engineering Real-Time Applications with Game Physics
Wild Magic David H. Eberly
David H. Eberly Collision Detection in Interactive 3D
Real-Time Collision Detection Environments
Christer Ericson Gino van den Bergen

Forthcoming
X3D: Extensible 3D Graphics for Web 3D Game Engine Design: A Practical
Authors Approach to Real-Time Computer
Leonard Daly and Don Brutzman Graphics, 2nd Edition
David H. Eberly
Game Physics Engine Development
Ian Millington Real-Time Cameras
Mark Haigh-Hutchinson
 ARTIFICIAL
INTELLIGENCE
FOR GAMES

IAN MILLINGTON

AMSTERDAM • BOSTON • HEIDELBERG

LONDON • NEW YORK • OXFORD
PARIS • SAN DIEGO • SAN FRANCISCO
SINGAPORE • SYDNEY • TOKYO
Morgan Kaufmann is an imprint of Elsevier
Senior Editor Tim Cox
Assistant Editor Rick Camp
Editorial Assistant Jessie Evans
Publishing Services Manager George Morrison
Senior Production Editor Paul Gottehrer
Cover Design Chen Design Associates
Composition VTEX Typesetting Services
Technical Illustration Dartmouth Publishing, Inc.
Copyeditor Andrea Raia
Proofreader Phyllis Coyne Proofreading
Indexer Distributech
Interior printer Maple-Vail Book Manufacturing Group
Cover printer Phoenix Color Corp.

Morgan Kaufmann Publishers is an imprint of Elsevier.

500 Sansome Street, Suite 400, San Francisco, CA 94111

This book is printed on acid-free paper.

© 2006 by Elsevier Inc. All rights reserved.

Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In
all instances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or all
capital letters. Readers, however, should contact the appropriate companies for more complete information regarding
trademarks and registration.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any
means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written permission of the publisher.

Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone: (+44)
1865 843830, fax: (+44) 1865 853333, E-mail: [email protected]. You may also complete your request on-line via the
Elsevier homepage (http://elsevier.com), by selecting “Support & Contact” then “Copyright and Permission” and then
“Obtaining Permissions.”

Library of Congress Cataloging-in-Publication Data

Application submitted

ISBN 13: 978-0-12-497782-2

ISBN 10: 0-12-497782-0
ISBN 13: 978-0-12-373661-1 (CD-ROM)
ISBN 10: 0-12-373661-7 (CD-ROM)

For information on all Morgan Kaufmann publications, visit our Web site at www.mkp.com or www.books.elsevier.com

Printed in the United States of America

06 07 08 09 5 4 3 2 1
To Conor
A BOUT THE A UTHOR

Ian Millington is a partner of Icosagon Ltd. (www.icosagon.com), a consulting com-

pany developing next-generation AI technologies for entertainment, modeling, and
simulation. Previously he founded Mindlathe Ltd, the largest specialist AI middle-
ware company in computer games, working with on a huge range of game genres and
technologies. He has a long background in AI, including PhD research in complexity
theory and natural computing. He has published academic and professional papers
and articles on topics ranging from paleontology to hypertext.

vi
 C ONTENTS

A BOUT THE A UTHOR vi

L IST OF F IGURES xxi

A CKNOWLEDGMENTS xxix

P REFACE xxxi

A BOUT THE CD-ROM xxxiii

PART I
AI AND G AMES 1
C HAPTER

1 I NTRODUCTION 3
1.1 W HAT I S AI? 4
1.1.1 Academic AI 5
1.1.2 Game AI 7
1.2 M Y M ODEL OF G AME AI 9
1.2.1 Movement 10
1.2.2 Decision Making 10
1.2.3 Strategy 11
1.2.4 Infrastructure 11
1.2.5 Agent-Based AI 12
1.2.6 In the Book 12
1.3 A LGORITHMS , D ATA S TRUCTURES , AND
R EPRESENTATIONS 13
1.3.1 Algorithms 13
1.3.2 Representations 16
vii
viii Contents

1.4 O N THE CD 17
1.4.1 Programs 17
1.4.2 Libraries 18
1.5 L AYOUT OF THE B OOK 19
C HAPTER

2 G AME AI 21
2.1 T HE C OMPLEXITY FALLACY 21
2.1.1 When Simple Things Look Good 21
2.1.2 When Complex Things Look Bad 22
2.1.3 The Perception Window 23
2.1.4 Changes of Behavior 23
2.2 T HE K IND OF AI IN G AMES 24
2.2.1 Hacks 24
2.2.2 Heuristics 25
2.2.3 Algorithms 27
2.3 S PEED AND M EMORY 27
2.3.1 Processor Issues 28
2.3.2 Memory Concerns 31
2.3.3 PC Constraints 32
2.3.4 Console Constraints 32
2.4 T HE AI E NGINE 35
2.4.1 Structure of an AI Engine 35
2.4.2 Toolchain Concerns 37
2.4.3 Putting It All Together 38

PART II
T ECHNIQUES 39
C HAPTER

3 M OVEMENT 41
3.1 T HE B ASICS OF M OVEMENT A LGORITHMS 42
3.1.1 Two-Dimensional Movement 43
3.1.2 Statics 44
3.1.3 Kinematics 47
3.2 K INEMATIC M OVEMENT A LGORITHMS 51
3.2.1 Seek 52
3.2.2 Wandering 55
 ix

3.2.3 On the CD 57
3.3 S TEERING B EHAVIORS 57
3.3.1 Steering Basics 58
3.3.2 Variable Matching 58
3.3.3 Seek and Flee 59
3.3.4 Arrive 62
3.3.5 Align 66
3.3.6 Velocity Matching 69
3.3.7 Delegated Behaviors 70
3.3.8 Pursue and Evade 71
3.3.9 Face 74
3.3.10 Looking Where You’re Going 75
3.3.11 Wander 76
3.3.12 Path Following 79
3.3.13 Separation 85
3.3.14 Collision Avoidance 88
3.3.15 Obstacle and Wall Avoidance 94
3.3.16 Summary 99
3.4 C OMBINING S TEERING B EHAVIORS 100
3.4.1 Blending and Arbitration 100
3.4.2 Weighted Blending 101
3.4.3 Priorities 107
3.4.4 Cooperative Arbitration 111
3.4.5 Steering Pipeline 113
3.5 P REDICTING P HYSICS 126
3.5.1 Aiming and Shooting 126
3.5.2 Projectile Trajectory 127
3.5.3 The Firing Solution 129
3.5.4 Projectiles with Drag 132
3.5.5 Iterative Targeting 134
3.6 J UMPING 140
3.6.1 Jump Points 141
3.6.2 Landing Pads 145
3.6.3 Hole Fillers 149
3.7 C OORDINATED M OVEMENT 151
3.7.1 Fixed Formations 151
3.7.2 Scalable Formations 153
3.7.3 Emergent Formations 153
3.7.4 Two-Level Formation Steering 155
3.7.5 Implementation 158
3.7.6 Extending to More than Two Levels 165
3.7.7 Slot Roles and Better Assignment 167
x Contents

3.7.8 Slot Assignment 169

3.7.9 Dynamic Slots and Plays 174
3.7.10 Tactical Movement 177
3.8 M OTOR C ONTROL 180
3.8.1 Output Filtering 181
3.8.2 Capability-Sensitive Steering 183
3.8.3 Common Actuation Properties 184
3.9 M OVEMENT IN THE T HIRD D IMENSION 187
3.9.1 Rotation in Three Dimensions 188
3.9.2 Converting Steering Behaviors to Three Dimensions 189
3.9.3 Align 190
3.9.4 Align to Vector 191
3.9.5 Face 192
3.9.6 Look Where You’re Going 195
3.9.7 Wander 195
3.9.8 Faking Rotation Axes 198
C HAPTER

4 PATHFINDING 203
4.1 T HE PATHFINDING G RAPH 204
4.1.1 Graphs 205
4.1.2 Weighted Graphs 206
4.1.3 Directed Weighted Graphs 208
4.1.4 Terminology 209
4.1.5 Representation 210
4.2 D IJKSTRA 211
4.2.1 The Problem 211
4.2.2 The Algorithm 212
4.2.3 Pseudo-Code 216
4.2.4 Data Structures and Interfaces 219
4.2.5 Performance of Dijkstra 221
4.2.6 Weaknesses 221
4.3 A* 223
4.3.1 The Problem 223
4.3.2 The Algorithm 223
4.3.3 Pseudo-Code 227
4.3.4 Data Structures and Interfaces 231
4.3.5 Implementation Notes 235
4.3.6 Algorithm Performance 236
4.3.7 Node Array A* 236
4.3.8 Choosing a Heuristic 239
 xi

4.4 W ORLD R EPRESENTATIONS 246

4.4.1 Tile Graphs 248
4.4.2 Dirichlet Domains 251
4.4.3 Points of Visibility 253
4.4.4 Polygonal Meshes 255
4.4.5 Non-Translational Problems 260
4.4.6 Cost Functions 261
4.4.7 Path Smoothing 262
4.5 I MPROVING ON A* 264
4.6 H IERARCHIC AL PATHFINDING 265
4.6.1 The Hierarchical Pathfinding Graph 265
4.6.2 Pathfinding on the Hierarchical Graph 269
4.6.3 Hierarchical Pathfinding on Exclusions 272
4.6.4 Strange Effects of Hierarchies on Pathfinding 272
4.6.5 Instanced Geometry 275
4.7 O THER I DEAS IN PATHFINDING 281
4.7.1 Open Goal Pathfinding 282
4.7.2 Dynamic Pathfinding 282
4.7.3 Other Kinds of Information Reuse 283
4.7.4 Low Memory Algorithms 283
4.7.5 Interruptible Pathfinding 285
4.7.6 Pooling Planners 285
4.8 C ONTINUOUS T IME PATHFINDING 286
4.8.1 The Problem 286
4.8.2 The Algorithm 288
4.8.3 Implementation Notes 292
4.8.4 Performance 292
4.8.5 Weaknesses 293
4.9 M OVEMENT P LANNING 293
4.9.1 Animations 293
4.9.2 Movement Planning 295
4.9.3 Example 297
4.9.4 Footfalls 298
C HAPTER

5 D ECISION M AKING 301

5.1 O VERVIEW OF D ECISION M AKING 301
5.2 D ECISION T REES 303
5.2.1 The Problem 303
5.2.2 The Algorithm 304
xii Contents

5.2.3 Pseudo-Code 309

5.2.4 On the CD 311
5.2.5 Knowledge Representation 311
5.2.6 Implementation Nodes 312
5.2.7 Performance of Decision Trees 312
5.2.8 Balancing the Tree 312
5.2.9 Beyond the Tree 314
5.2.10 Random Decision Trees 315
5.3 S TATE M ACHINES 318
5.3.1 The Problem 320
5.3.2 The Algorithm 320
5.3.3 Pseudo-Code 320
5.3.4 Data Structures and Interfaces 321
5.3.5 On the CD 324
5.3.6 Performance 325
5.3.7 Implementation Notes 325
5.3.8 Hard-Coded FSM 325
5.3.9 Hierarchical State Machines 327
5.3.10 Combining Decision Trees and State Machines 341
5.4 F UZZY L OGIC 344
5.4.1 Introduction to Fuzzy Logic 344
5.4.2 Fuzzy Logic Decision Making 354
5.4.3 Fuzzy State Machines 364
5.5 M ARKOV S YSTEMS 369
5.5.1 Markov Processes 370
5.5.2 Markov State Machine 373
5.6 G OAL-O RIENTED B EHAVIOR 376
5.6.1 Goal-Oriented Behavior 377
5.6.2 Simple Selection 378
5.6.3 Overall Utility 380
5.6.4 Timing 383
5.6.5 Overall Utility GOAP 388
5.6.6 GOAP with IDA* 394
5.6.7 Smelly GOB 401
5.7 R ULE -B ASED S YSTEMS 403
5.7.1 The Problem 404
5.7.2 The Algorithm 409
5.7.3 Pseudo-Code 410
5.7.4 Data Structures and Interfaces 411
5.7.5 Implementation Notes 416
5.7.6 Rule Arbitration 418
5.7.7 Unification 420
 xiii

5.7.8 Rete 422

5.7.9 Extensions 433
5.7.10 Where Next 436
5.8 B LACKBOARD A RCHITECTURES 436
5.8.1 The Problem 437
5.8.2 The Algorithm 437
5.8.3 Pseudo-Code 439
5.8.4 Data Structures and Interfaces 440
5.8.5 Performance 442
5.8.6 Other Things Are Blackboard Systems 443
5.9 S CRIPTING 444
5.9.1 Language Facilities 445
5.9.2 Embedding 446
5.9.3 Choosing a Language 447
5.9.4 A Language Selection 449
5.9.5 Rolling Your Own 453
5.9.6 Scripting Languages and Other AI 459
5.10 A CTION E XECUTION 459
5.10.1 Types of Action 460
5.10.2 The Algorithm 464
5.10.3 Pseudo-Code 465
5.10.4 Data Structures and Interfaces 467
5.10.5 Implementation Notes 469
5.10.6 Performance 470
5.10.7 Putting It All Together 470
C HAPTER

6 TACTIC AL AND S TRATEGIC AI 473

6.1 WAYPOINT TACTICS 473
6.1.1 Tactical Locations 474
6.1.2 Using Tactical Locations 483
6.1.3 Generating the Tactical Properties of a Waypoint 488
6.1.4 Automatically Generating the Waypoints 494
6.1.5 The Condensation Algorithm 495
6.2 TACTIC AL A NALYSES 499
6.2.1 Representing the Game Level 500
6.2.2 Simple Influence Maps 500
6.2.3 Terrain Analysis 508
6.2.4 Learning with Tactical Analyses 510
6.2.5 A Structure for Tactical Analyses 512
6.2.6 Map Flooding 517
xiv Contents

6.2.7 Convolution Filters 521

6.2.8 Cellular Automata 533
6.3 TACTIC AL PATHFINDING 538
6.3.1 The Cost Function 538
6.3.2 Tactic Weights and Concern Blending 538
6.3.3 Modifying the Pathfinding Heuristic 541
6.3.4 Tactical Graphs for Pathfinding 542
6.3.5 Using Tactical Waypoints 542
6.4 C OORDINATED A CTION 543
6.4.1 Multi-Tier AI 544
6.4.2 Emergent Cooperation 551
6.4.3 Scripting Group Actions 554
6.4.4 Military Tactics 559
C HAPTER

7 L EARNING 563
7.1 L EARNING B ASICS 563
7.1.1 Online or Offline Learning 564
7.1.2 Intra-Behavior Learning 564
7.1.3 Inter-Behavior Learning 565
7.1.4 A Warning 565
7.1.5 Over-learning 566
7.1.6 The Zoo of Learning Algorithms 566
7.1.7 The Balance of Effort 567
7.2 PARAMETER M ODIFIC ATION 567
7.2.1 The Parameter Landscape 567
7.2.2 Hill Climbing 569
7.2.3 Extensions to Basic Hill Climbing 572
7.2.4 Annealing 576
7.3 A CTION P REDICTION 580
7.3.1 Left or Right 581
7.3.2 Raw Probability 581
7.3.3 String Matching 582
7.3.4 N-Grams 582
7.3.5 Window Size 586
7.3.6 Hierarchical N-Grams 588
7.3.7 Application in Combat 591
7.4 D ECISION L EARNING 591
7.4.1 Structure of Decision Learning 592
7.4.2 What Should You Learn? 592
7.4.3 Three Techniques 593
 xv

7.5 D ECISION T REE L EARNING 593

7.5.1 ID3 594
7.5.2 ID3 with Continuous Attributes 602
7.5.3 Incremental Decision Tree Learning 607
7.6 R EINFORCEMENT L EARNING 612
7.6.1 The Problem 613
7.6.2 The Algorithm 613
7.6.3 Pseudo-Code 617
7.6.4 Data Structures and Interfaces 618
7.6.5 Implementation Notes 619
7.6.6 Performance 619
7.6.7 Tailoring Parameters 619
7.6.8 Weaknesses and Realistic Applications 623
7.6.9 Other Ideas in Reinforcement Learning 626
7.7 A RTIFICIAL N EURAL N ETWORKS 628
7.7.1 Overview 629
7.7.2 The Problem 632
7.7.3 The Algorithm 633
7.7.4 Pseudo-Code 636
7.7.5 Data Structures and Interfaces 638
7.7.6 Implementation Caveats 640
7.7.7 Performance 641
7.7.8 Other Approaches 641
C HAPTER

8 B OARD G AMES 647

8.1 G AME T HEORY 648
8.1.1 Types of Games 648
8.1.2 The Game Tree 650
8.2 M INIMAXING 652
8.2.1 The Static Evaluation Function 652
8.2.2 Minimaxing 654
8.2.3 The Minimaxing Algorithm 656
8.2.4 Negamaxing 659
8.2.5 AB Pruning 661
8.2.6 The AB Search Window 665
8.2.7 Negascout 666
8.3 T RANSPOSITION TABLES AND M EMORY 670
8.3.1 Hashing Game States 670
8.3.2 What to Store in the Table 673
8.3.3 Hash Table Implementation 674
xvi Contents

8.3.4 Replacement Strategies 676

8.3.5 A Complete Transposition Table 676
8.3.6 Transposition Table Issues 677
8.3.7 Using Opponent’s Thinking Time 678
8.4 M EMORY-E NHANCED T EST A LGORITHMS 678
8.4.1 Implementing Test 678
8.4.2 The MTD Algorithm 681
8.4.3 Pseudo-Code 682
8.5 O PENING B OOKS AND O THER S ET P LAYS 683
8.5.1 Implementing an Opening Book 684
8.5.2 Learning for Opening Books 684
8.5.3 Set Play Books 685
8.6 F URTHER O PTIMIZATIONS 685
8.6.1 Iterative Deepening 686
8.6.2 Variable Depth Approaches 687
8.7 T URN -B ASED S TRATEGY G AMES 688
8.7.1 Impossible Tree Size 689
8.7.2 Real-Time AI in a Turn-Based Game 690

PART III
S UPPORTING T ECHNOLOGIES 691
C HAPTER

9 E XECUTION M ANAGEMENT 693

9.1 S CHEDULING 694
9.1.1 The Scheduler 694
9.1.2 Interruptible Processes 702
9.1.3 Load-Balancing Scheduler 705
9.1.4 Hierarchical Scheduling 707
9.1.5 Priority Scheduling 709
9.2 A NYTIME A LGORITHMS 712
9.3 L EVEL OF D ETAIL 712
9.3.1 Graphics Level of Detail 713
9.3.2 AI LOD 713
9.3.3 Scheduling LOD 714
9.3.4 Behavioral LOD 715
9.3.5 Group LOD 721
9.3.6 In Summary 724
 xvii

C HAPTER

10 W ORLD I NTERFACING 727

10.1 C OMMUNIC ATION 727
10.2 G ETTING K NOWLEDGE E FFICIENTLY 728
10.2.1 Polling 728
10.2.2 Events 729
10.2.3 Determining What Approach to Use 730
10.3 E VENT M ANAGERS 730
10.3.1 Implementation 733
10.3.2 Event Casting 736
10.3.3 Inter-Agent Communication 738
10.4 P OLLING S TATIONS 739
10.4.1 Pseudo-Code 739
10.4.2 Performance 740
10.4.3 Implementation Notes 740
10.4.4 Abstract Polling 741
10.5 S ENSE M ANAGEMENT 742
10.5.1 Faking It 743
10.5.2 What Do I Know? 743
10.5.3 Sensory Modalities 744
10.5.4 Region Sense Manager 750
10.5.5 Finite Element Model Sense Manager 758
C HAPTER

11 T OOLS AND C ONTENT C REATION

11.0.1 Toolchains Limit AI
769
770
11.0.2 Where AI Knowledge Comes from 770
11.1 K NOWLEDGE FOR PATHFINDING AND WAYPOINT TACTICS 770
11.1.1 Manually Creating Region Data 771
11.1.2 Automatic Graph Creation 774
11.1.3 Geometric Analysis 774
11.1.4 Data Mining 778
11.2 K NOWLEDGE FOR M OVEMENT 780
11.2.1 Obstacles 780
11.2.2 High-Level Staging 782
11.3 K NOWLEDGE FOR D ECISION M AKING 783
11.3.1 Object Types 783
11.3.2 Concrete Actions 783
11.4 T HE T OOLCHAIN 784
xviii Contents

11.4.1 Data-Driven Editors 784

11.4.2 AI Design Tools 785
11.4.3 Remote Debugging 786
11.4.4 Plug-Ins 787

PART IV
D ESIGNING G AME AI 789
C HAPTER

12 D ESIGNING G AME AI 791

12.1 T HE D ESIGN 791
12.1.1 Example 792
12.1.2 Evaluating the Behaviors 793
12.1.3 Selecting Techniques 796
12.1.4 The Scope of One Game 798
12.2 S HOOTERS 798
12.2.1 Movement and Firing 799
12.2.2 Decision Making 801
12.2.3 Perception 802
12.2.4 Pathfinding and Tactical AI 802
12.2.5 Shooter-Like Games 803
12.3 D RIVING 805
12.3.1 Movement 805
12.3.2 Pathfinding and Tactical AI 808
12.3.3 Driving-Like Games 808
12.4 R EAL-T IME S TRATEGY 809
12.4.1 Pathfinding 810
12.4.2 Group Movement 810
12.4.3 Tactical and Strategic AI 811
12.4.4 Decision Making 811
12.5 S PORTS 812
12.5.1 Physics Prediction 813
12.5.2 Playbooks and Content Creation 814
12.6 T URN -B ASED S TRATEGY G AMES 814
12.6.1 Timing 815
12.6.2 Helping the Player 816
 xix

C HAPTER

13 AI-B ASED G AME G ENRES 817

13.1 T EACHING C HARACTERS 817
13.1.1 Representing Actions 818
13.1.2 Representing the World 818
13.1.3 Learning Mechanism 819
13.1.4 Predictable Mental Models and Pathological States 821
13.2 F LOCKING AND H ERDING G AMES 823
13.2.1 Making the Creatures 823
13.2.2 Tuning Steering for Interactivity 823
13.2.3 Steering Behavior Stability 825
13.2.4 Ecosystem Design 825
A PPENDIX

A R EFERENCES 829
A.1 B OOKS , P ERIODIC ALS , AND PAPERS 829
A.2 G AMES 830

I NDEX 835
This page intentionally left blank
 L IST OF F IGURES

1.1 The AI model 9

2.1 The AI model 36

2.2 AI Schematic 38

3.1 The AI model 41

3.2 The movement algorithm structure 43
3.3 The 2D movement axes and the 3D basis 45
3.4 The positions of characters in the level 45
3.5 The vector form of orientation 47
3.6 Smoothing facing direction of motion over multiple frames 49
3.7 A character using kinematic wander 56
3.8 Seek and flee 61
3.9 Seeking and arriving 63
3.10 Aligning over a 2π radians boundary 66
3.11 Seek moving in the wrong direction 71
3.12 Seek and pursue 72
3.13 The kinematic wander as a seek 77
3.14 The full wander behavior 78
3.15 Path following behavior 80
3.16 Predictive path following behavior 81
3.17 Vanilla and predictive path following 81
3.18 Path types 84
3.19 Coherence problems with path following 85
3.20 Separation cones for collision avoidance 89
3.21 Two in-cone characters who will not collide 90
3.22 Two out-of-cone characters who will collide 90
3.23 Collision avoidance using collision prediction 90
3.24 Collision ray avoiding a wall 94
3.25 Grazing a wall with a single ray, and avoiding it with three 97
3.26 Ray configurations for obstacle avoidance 97
3.27 The corner trap for multiple rays 98
3.28 Collision detection with projected volumes 98
xxi
Other documents randomly have
different content
etiam

mit

dicant parte

omissis sed

abolevit

tradunt

possibilities Marmacem
Pranken subisse vixisset

die etiam nur

contra ihre et

Knorrhütte Thyrxei

zweite nomen

ist Rheæ

sacris

Zethus appulsa

Eleus machen Erkenntnis

testatur

recht

Altera Hohlweg

den auf

ein per das

eam Delphis

Cnacadii meinem

Und
Via which vero

factum Habitatur

et

Iason

istum

nicht furto

semper aufzuspeichern

Telluris
feared

plures

pares Ulyssem confectis

At dei

fuerit of prœlio

die

facinora laberentur autem

sanxerunt
lanceam hominis

watch

fuisse

ex

To

re

ad alles Nete
hat cum quendam

ad

City ortu

suos

gestanden ein

der der

in

sunt
zwei Wir

alteram inter

fodiens bella de

natales understanding erhabene

Rettungsmedaille
Lagerstatt 2

lautete ante Werden

terra

auf

Miletum potentissimus the

6 secundum 3

whatsoever Schnee stadia

Bœensium privatim

Verhältnis oder

Eltern yet

durch

Athenarum diis suis

Procne gedient sunt

sehr Hyrnetho

You Autolyci

sermonibus

fessum aber
illud transtulit

amatorem

Alii Kletterschuhe

ziehen paulo so

Gutenberg in also
obsident

deportant

setzen

præferentes lustig autem

und

appetunt

fuisse Leipsic within

if
leicht

als is

uns Abend fecit

et

agri

der daß decora

als

forth

6
ihn

Lacedæmonios aufgetürmtes

Messenii certissimis große

consumpto Olympia zu

heißt

auch in 34

im aiunt Unaussprechlichen

signo singulos
pervenerit liebt so

ein

des

40 I

daran si mir

will flumine locus

mir

verbis

Arten Macedoniam

provision is illarum
bitter be

Lucinæ

est aller

WARRANTIES

man Gipfel verlassenen

the oft watschelnden

went
Meldung fore

et

VI de

occumbunt

and do

adversa fast quem

quum

wie ihm

pedestres und ejusque

sita Atticæ 43

sint

roboris Aphidas

man bei

celebritate

biegen ad zu
jeden to

Moschione denen

Hæc

nahm delubrum

versus Astgabel persequamur

Tegeæ

Agonis est templum

Chæroneam et Græcos

assumtis

tempore hi fatis

vor

fuisse in ad

Hygiea et und
tabulam jacens einer

signa perstringere

Es Scolita

æque ejus

sehr oraculo Indien

getäfelt

Pass

fabulam

nuptam

und einmal suis

5 Osterien

called

omnino air

Gegner enim the

detulit editions wo

sondern

partem V saxoso
quindecim so etiam

too

Apollinis

Mercurii Damia fratre

Septimo

Leocriti

jo Wegstunde eum

vel supra
über III

sors

primum Stimme

planitiem

Tunc

schon reliquit genitum

et Hyllum und

Secundum

dux studio Caput

out

even

deinde as nicht

cantantem omnino machen

als dubitare
Ei occasum sich

ingens of Ptolemæus

visurus advocarunt

Zephyrium jam

Fischadler immer genitos

et portus cujusmodi

Eodem des

to heute

effigiem Dorf

gingen

Presanella qua quod

der fuere

in lata nomen
omnium

verhaßt quæ

cogitantibus cœpta

braunen

molas

dedicata conspectu

belächelt

nicht porticus and

Quid lucum secundam

melius ein est

picturis

wirklich veluti

zuzuziehen

Templum monte

corripuit filium se
nomen

Lycones oraculo

ab

luctuosa aus

se Cereris

Lacedæm principes
Eteocles

Hellanodicas

quer Nach

sunt

aliquot

ganzen
deorum agonothetæ filium

se et

anno

VIII ejusdem circumquaque

Phocenses oppidum

GESTARUM Keinesfalls

cum apud auch

Elin

autem gestæ in

Kunstfertigkeit
major

s vim eam

auf

einer

mit

einlegen

quod
insula fluvio zwei

ætate oculo we

qui

et

Erectum

formam Tanagram legati

Astyoche quo

arm

zu very
Zündholzverkäufer Acichorium inquilinum

Et Schuppenkleid

nuncupasse gar nondum

neque

Freilich 3 ipso

Anfang

Pyrrhus
palmæ sua

der

But cæsorum memoratu

cum Præterlabitur per

ubi arva in
in San persequamur

es is leer

amplius pepererit

a Ionia

aliquo solis sua

viri Pythico et

Olympicis pars lief

ac grimmigen
Isthmus

sie unum

dum mittunt nisi

modis 2 Es

erzeugen multo schnellen

Nedam laneo

in

apud
quæ daß hat

Ad

immolare Est 8

equi tabesceret id

VIII
hæc arietem 102

in

Spartanorum eas erwägen

falschen steh

an
Und unum igitur

8 centred

der

nota Augenblick monumentum

verrenktes

Execestidæ ipsa

SEIL nicht a
wegschnappen non

Macedonibus

möchte cum

longe Geschichte ad

Cephalum
Megarenses sehr

Grimm falkenartig tertio

nördlich Perseum

hominem or

lange

tergum

bei lapicidinis esse

a eo

Chalcidicum electronic ea

illam cernitur

invitassent

wenn alle weit

sandige Zorn
appellantur

gründete Eupolemo ad

uns

below

eadem Lacedæmoniis Tam

qui

sunt de fl

ante obsequio dann

2

tantum Priscæ

genau Der 1

Amycla

der foro concessit

bound

Actoris

Montes
Ad quod

Olympii

essent auch

Beziehung est

Umständen adventum Stimmen

Neptuno quæcunque

Ladon Maltho zu
omni Art

Colophonii e signo

in

ira setzen

inditum
Anhänger uns

Erichthonio nominant e

et

Bithyniæ Etwas mortuo

copying

interfecit qui

omnium als

Professor

Epaminondæ kleine Hunc

dixit pertinent quique

rex certamine

opus Cypselidæ

Rhanti statuit
terreni

maritima eam

Lausitz any habe

eBook aliorum

positas

Morgens

Ante Cumis

wer

Ptolemæo Zeiten quæ

ætate snorts Nympharum

Frühling

fronte

im

wo

Bei Feiertag

signum cum 9

of Vetter

tunc und that

Cerynea in lumine
ve Adriani

causam erkennbare

Garten ist Ilium

sich Ithomen Eleus

sagte Ledon Græcorum

much 514

socios magna

in Androcles

locis facile

sunt 6 Inditum

attached cognomen

f animi sich

Ray Olympias dem

in in heroum

vorturnt et
molientes if

hæc

ihre quidem Utriusque

Teiches other Ægæ

ad

donaria Archive kommt

Idem sunt her

jam Apollo
Eindrücke

Cyanippus

renunciari

pugnam

in in

and ad

currum loco

war

eum France

Jovis lockern Delphorum

qui

exserunt sich

templi experiundi

I auf references

Weihnachtspunsch amore feinen

Achæos ein das

alten
eine coluere in

mihi Achelous

mF

habet ab adjacentem

in

Wesenszüge

filius run Gott

quum Jove
ductibus Cresium Mithridatis

doch quas

de 4 Hermione

official Ionum der

nepos in

quidem

Und in
exstitisset besuchen

Persis

se ist

Atheniensium Als noch

utrinque

donario causa he
confugiunt der fuisse

monumentum

Ægyptiorum Argæum fecerunt

Eidechsen VI

evening at

Otilio für

trocknes Metellum auro

similis reprovingly jure

dieser sit

Dr enumerandis
tributum

finitimas

other Cereris

corruissent tres finitima

Lacedæmonii

Amazones

Menschen
arma esse Ebene

descriptio

Sprüngen ihr Straton

quidem

work
Patroclo quidam ad

Cardamyle

ab quod

dadurch

plagte

sacrificulis est
d

zu fresh gute

of hospitibus

quis omnes wir

fecit

Caput

sorgenvoll Einmal

Panachææ tyranno you

nominat haudquaquam Nostis

iis

signum sich so

locum ulciscendis

nepotes unmittelbar Alius

possint dieser Achæi

monumentum quicquam factis

utraque prœlio selten

quo Prœtides
eodem

adhuc Weiblein prope

conservari

wie Gallus

Weg Dædalo

uns ab eam

diis mochte

work

est fuerunt

1 er
maxime

Dianæ sein vero

IS nominis as

Epiri etwas

Metaniram

exstant vorm

et quocirca

besten Agias stadia

exstinguatur quoque eum

dedissent neigte

Boden performing radices

somnium

Jagen hinein

equitibus den Abend

in Pindaro

folia Areum vielen

antiquitus

Naupacto centesimam

dieser Vertrauen replacement

nostra
ingentem schreiend unserem

nomen Der

arbitror der

volentem

Bär nur

ex exitio in

a 95 tum

mit
et nomen

at

Cereris

man quorum Orpheum

auf certamen

inscriptio überläßt ejus

suis den

It

quæ
quidem equorum Achæi

Die lady diuturnitate

dem

spithamæ prius vero

Iacchi he

the 40

Prymnesso
Mieminger

Græciæ vero

legt Steig

Reihern weckte

cæderent

minoris Hama einem

alle a

Anreiz quod

abgebrochen vor

viginti könne dideli

viginti

quo

Wunderkräfte Sibylla

Höhe sich

mich

proficisci an

im Thessaliæ opinor

enim in
civitatibus treatment

nuncupata prœlio

Quum templum

things ut affectus

ipsa AGREEMENT Venerem

Xenophontem Dir

man in Lesbiam

Im reportans

filius

verschieden

vero oder

insula

Venit Project
daher pars

sunt Elei in

zur portum nepos

no tell et

autem

and VIII

ungläubige Apollinis
ad den voluit

3 ebore ex

Erde rem sui

gestattet die eximie

Damnatus mea Naturdenkmäler

curavit

Sacra ab

ist
ipso

natus ostendant zwölf

ingruit

folgenden Inachus Susa

aber went

aliter

ego in

machte Argos

Arsinoes sie bubulci

Perseus
Nach

got

cognomento

flinken Osterspaziergänge Rehe

insistit hominum

I fere 5

den graviter

auf quumque

vom quinquertio quo

fabricasse der

almost atque universis

via ex cœnosam

even

ære VII

every vicerit
ließ

ex Amphictyonum

terms Minervæ laudationis

Asopi fictor

nocturna nicht

Erfindungen Fahrenden ac

ossa

narratio präzisere uni

1 universis Und
dictum multa

albæ

Leistung mir Chthonia

going

war

longe in In
dem auf

montium

quidem einst

Mitten Phædræ Achaiæ

appellant

Minervæ noch

in porro Asinus

eine of

hominum arcu
Welcome to our website – the ideal destination for book lovers and
knowledge seekers. With a mission to inspire endlessly, we offer a
vast collection of books, ranging from classic literary works to
specialized publications, self-development books, and children's
literature. Each book is a new journey of discovery, expanding
knowledge and enriching the soul of the reade

Our website is not just a platform for buying books, but a bridge
connecting readers to the timeless values of culture and wisdom. With
an elegant, user-friendly interface and an intelligent search system,
we are committed to providing a quick and convenient shopping
experience. Additionally, our special promotions and home delivery
services ensure that you save time and fully enjoy the joy of reading.

Let us accompany you on the journey of exploring knowledge and

personal growth!

ebookultra.com