- Author / Uploaded
- Brian Schwab
AI Game Engine Programming
BRIAN SCHWAB Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States , 2e
4,059 1,087 6MB
Pages 741 Page size 252 x 316.08 pts
Recommend Papers
File loading please wait...
Citation preview
AI GAME ENGINE PROGRAMMING
BRIAN SCHWAB
Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States
AI Game Engine Programming, 2e
© 2009, Course Technology, a part of Cengage Learning
Brian Schwab
ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored, or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher.
Publisher and General Manager, Course Technology PTR: Stacy L. Hiquet Associate Director of Marketing: Sarah Panella Content Project Manager: Jessica McNavich Marketing Manager: Jordan Casey Acquisitions Editor: Heather Hurley Copy Editor: Erica Orloff Technical Reviewer: Steven Woodcock CRM Editorial Services Coordinator: Jennifer Blaney Cover Designer: Sherry Stinson CD-ROM Producer: Brandon Penticuff Indexer: Jean Skipp Proofreader: Andrew Jones Compositor: S4Carlisle Publishing Services
For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, 1-800-354-9706 For permission to use material from this text or product, submit all requests online at cengage.com/permissions. Further permissions questions can be e-mailed to [email protected]
Library of Congress Control Number: 2008938147 ISBN-13: 978-1-5845-0572-3 ISBN-10: 1-58450-572-9 eISBN-10: 1-58450-628-8 Course Technology 25 Thomson Place Boston, MA 02210 USA
Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil, and Japan. Locate your local office at: international. cengage.com/region Cengage Learning products are represented in Canada by Nelson Education, Ltd. For your lifelong learning solutions, visit courseptr.com Visit our corporate website at cengage.com
Printed in Canada 1 2 3 4 5 6 7 12 11 10 09 08
To Harley: Give Lori the strength. To Beluga: I’ll always be sorry, Blue. To Lori: You are the reason, Little Bird.
This page intentionally left blank
About the Author
Brian Schwab has officially been in the game industry since 1993. He got his first “Out of Memory” error two days after he bought his first computer, a Mattel Aquarius (which cost him 6 months of his allowance), when he was 10 years old. This allows him to truthfully state that he has been optimizing game code for over 25 years. He spent almost a year living in Austin, Texas as a homeless man trying to get his first game job. Since then, he has worked at everything from a three-man studio to his current job at Sony Computer Entertainment of America, where he works as an AI/Gameplay Lead Programmer. He has also worked as a game designer for several products, including Lead Designer on two titles. Over the years, he has created almost every type of game: educational, role playing, flight sim, a squad-based real-time strategy game, an arcade game, a fighter, a first-person shooter, and a sports franchise. He has found that no matter what the genre, there is always the challenge of creating good AI-controlled characters. In addition to this book, he has also been the AI editor for Game Gems 6 and 7. He is a member of the AI Game Programmer’s Guild, the AI Interface Standards Committee, and is active in the planning of the AIIDE conference.
This page intentionally left blank
Contents Preface Introduction 1
xxvii xxix
Basic Definitions and Concepts What Is Intelligence?
2
What Is “Game AI”?
2
What Game AI Is Not
6
How This Definition Differs from That of Academic AI
8
Applicable Mind Science and Psychology Theory
10
Brain Organization
10
Knowledge Base and Learning
11
Cognition
15
Theory of Mind
17
Bounded Optimality
24
Lessons from Robotics
26
Simplicity of Design and Solution
26
Theory of Mind
26
Multiple Layered Decision Architectures
27
Summary 2
1
An AI Engine: The Basic Components and Design Decision Making and Inference
28 31 31
Types of Solutions
32
Agent Reactivity
33
System Realism
33
Genre
34 vii
viii
Contents
Content
35
Platform
35
Development Limitations
37
Entertainment Limitations
39
Input Handlers and Perception
40
Perception Type
40
Update Regularity
41
Reaction Time
41
Thresholds
41
Load Balancing
41
Computation Cost and Preconditions
42
Navigation
3
43
Grid-Based
43
Simple Avoidance and Potential Fields
44
Map Node Networks
45
Navigation Mesh
47
Combination Systems
48
Obstacle Avoidance
48
Bringing It All Together
49
Summary
51
AIsteroids: Our AI Test Bed
53
The GameObj Class
54
The GameObj Update Function
57
The Ship Object
57
The Other Game Objects
59
The GameSession Class
60
Primary Logic and Collision Checking
62
Object Cleanup
63
Spawning Main Ship and Powerups
64
Bonus Lives
65
End of Level and Game
65
Contents
4
The Control Class
66
The AI System Hooks
66
Game Main Loop
68
Summary
68
Role-Playing Games (RPGs) Common AI Elements
69 74
Enemies
74
Bosses
75
Nonplayer Characters (NPCs)
76
Shopkeepers
77
Party Members
78
Useful AI Techniques
80
Scripting
80
Finite-State Machines (FSMs)
81
Messaging
82
Examples
82
Exceptions
83
Specific Game Elements That Need Improvement
84
Role Playing Does Not Equal Combat
5
ix
84
Grammar Machines
86
Quest Generators
86
Better Party Member AI
87
Better Enemies
88
Fully-Realized Towns
89
Summary
90
Adventure Games Common AI Elements
93 95
Enemy AI
95
Nonplayer Characters (NPCs)
96
Cooperative Elements
96
x
Contents
Perception Systems
96
Camera
97
Useful AI Techniques Finite-State Machines (FSMs)
97
Scripting Systems
98
Messaging Systems
98
Fuzzy Logic
98
Areas That Need Improvement
101
Additional Types of Stealth Goals
101
A Return to Traditional Adventure Roots
101
Better NPC Communication
101
User Interface
102
Summary 6
97
Real-Time Strategy (RTS) Games
102 105
Common AI Elements
105
Individual Units
106
Economic Individual Units
106
High-Level Strategic AI
107
Commanders and Medium-Level Strategic Elements
108
Town Building
108
Indigenous Life
109
Pathfinding
109
Tactical and Strategic Support Systems
110
Useful AI Techniques
112
Messaging
112
Finite-State Machines (FSMs)
113
Fuzzy-State Machines (FuSMs)
113
Hierarchical AI
113
Planning
114
Scripting
114
Contents
Data-Driven AI
115
Examples
116
Areas That Need Improvement
117
Learning
118
Determining When an AI Element Is Stuck
118
Helper AI
119
Opponent Personality
119
More Strategy, Less Tactics
120
Summary 7
xi
First-Person Shooters/Third-Person Shooters (FTPS) Common AI Elements
121 123 126
Enemies
126
Boss Enemies
127
Deathmatch Opponents
127
Weapons
128
Cooperative Agents
128
Squad Members
128
Pathfinding
129
Spatial Reasoning
130
Useful AI Techniques
130
Finite-State Machines (FSMs)
130
Fuzzy-State Machines (FuSMs)
134
Messaging Systems
134
Scripting Systems
135
Examples
135
Areas That Need Improvement
136
Learning and Opponent Modeling
137
Personality
138
Creativity
138
Anticipation
139
xii
Contents
Better Conversation Engines
139
Motivations
139
Better Squad AI
140
Summary 8
Platform Games Common AI Elements
143 149
Enemies
149
Boss Enemies
150
Cooperative Elements
150
Camera
150
Useful AI Techniques
152
Finite-State Machines (FSMs)
152
Messaging Systems
152
Scripted Systems
152
Data-Driven Systems
153
Examples
153
Areas That Need Improvement
154
Camerawork
154
Help Systems
154
Summary 9
140
Shooter Games Common AI Elements
155 157 163
Enemies
163
Boss Enemies
163
Cooperative Elements
164
Useful AI Techniques
164
Finite-State Machines (FSMs)
164
Scripted Systems
165
Data-Driven Systems
165
Exceptions
165
Contents
10
Examples
166
Areas That Need Improvement
168
Infusion of Actual AI
168
Story-Driven Content
168
Innovative Gameplay Mechanics
168
Summary
169
Sports Games
171
Common AI Elements
172
Coach- or Team-Level AI
173
Player-Level AI
173
Pathfinding
175
Camera
175
Miscellaneous Elements
176
Mini-Games
177
Useful AI Techniques
11
xiii
177
Finite-State Machines (FSMs) and Fuzzy-State Machines (FuSMs)
177
Data-Driven Systems
185
Messaging Systems
185
Examples
186
Areas That Need Improvement
187
Learning
187
Game Balance
187
Gameplay Innovation
188
Summary
189
Racing Games
191
Common AI Elements
193
Track AI
193
Traffic
195
Pedestrians
195
xiv
Contents
Enemy and Combat
196
Nonplayer Characters (NPC)
196
Other Competitive Behavior
196
Useful AI Techniques Finite-State Machines (FSMs)
197
Scripted Systems
197
Messaging Systems
197
Genetic Algorithms
198
Areas That Need Improvement
199
More Intelligent AI Enemies
199
Persistent Worlds
199 200
Classic Strategy Games
203
Common AI Elements
215
Opponent AI
215
Helper AI
215
Useful AI Techniques
216
Finite-State Machines (FSMs)
216
Alpha-Beta Search
216
Neural Nets (NNs)
217
Genetic Algorithms (GAs)
217
Areas That Need Improvement
218
Creativity
218
Speed
218
Summary 13
198
Areas of Interest Other Than Crime
Summary 12
197
Fighting Games Common AI Elements
218 221 223
Enemies
224
Collision Systems
224
Contents
Boss Enemies
224
Camera
225
Action and Adventure Elements
225
Useful AI Techniques
225
Data-Driven Systems
226
Scripting Systems
226 227
Learning
228
Additional Crossover/Story Elements
228
Summary
15
225
Finite-State Machines (FSMs)
Areas That Need Improvement
14
xv
Miscellaneous Genres of Note
228 231
Civilization Games
231
God Games
240
War Games
243
Flight Simulators (SIMS)
249
Rhythm Games
254
Puzzle Games
255
Artificial Life (Alife) Games
256
Summary
259
Finite-State Machines
261
FSM Overview
261
FSM Skeletal Code
266
The FSMState Class
267
The FSMMachine Class
268
The FSMAIControl Class
270
Implementing an FSM-Controlled Ship into Our Test Bed
271
Example Implementation
272
Coding the Control Class
273
Coding the States
275
xvi
Contents
Performance of the AI with This System Pros of FSM-Based Systems
287
Cons of FSM-Based Systems
288
Extensions to the Paradigm
289
Hierarchical FSMs
289
Message- and Event-Based FSMs
290
FSMs with Fuzzy Transitions
290
Stack-Based FSMs
291
Multiple-Concurrent FSMs
291
Data-Driven FSMs
292
Inertial FSMs
293
Optimizations
295
Load Balancing Both FSMs and Perceptions
295
Level-of-Detail (LOD) AI Systems
296
Shared Data Structures
297
Design Considerations
297
Types of Solutions
297
Agent Reactivity
298
System Realism
298
Genre
298
Content
299
Platform
299
Development Limitations
299
Entertainment Limitations
300
Summary 16
285
Fuzzy-State Machines (FuSMs)
300 303
FuSM Overview
303
FuSM Skeletal Code
308
The FuSMState Class
308
The FuSMMachine Class
310
The FuSMAIControl Class
312
Contents
Implementing an FuSM-Controlled Ship into Our Test Bed
313
Example Implementation
313
A New Addition, the Saucer
313
Other Game Modifications
314
The FuSM System
314
Coding the Control Class Coding the Fuzzy States Performance of the AI with This System
316 318 323
Pros of FuSM-Based Systems
325
Cons of FuSM-Based Systems
326
Extensions to the Paradigm
327
FuSMS with a Limited Number of Concurrent States
327
An FuSM Used as a Support System for a Character
328
An FuSM Used as a Single State in a Larger FSM
328
Hierarchical FuSMs
328
Data-Driven FuSMs
329
Optimizations
329
Design Considerations
329
Types of Solutions
329
Agent Reactivity
330
System Realism
330
Genre
330
Platform
331
Development Limitations
331
Entertainment Limitations
331
Summary 17
xvii
332
Message-Based Systems
335
Messaging Overview
335
Messaging Skeletal Code
337
The Message Object
338
The MessagePump
339
xviii
Contents
Client Handlers
343
Example Implementation in Our AIsteroids Test Bed
344
The MessState Class
344
The MessMachine Class
345
The MessAIControl Class
346
Coding the States
352
Performance of the AI with This System
355
Pros of Messaging Systems
355
Cons of Messaging Systems
356
Extensions to the Paradigm Message Priority
357
Message Arbitration
357
Automatic and Extended Message Types
358
Optimizations
359
Design Considerations
359
Types of Solutions
359
Agent Reactivity
360
System Realism
360
Genre and Platform
360
Development Limitations
360
Entertainment Limitations
361
Summary 18
357
Scripting Systems
361 363
Scripting Overview
363
Example Implementation in Our AIsteroids Test Bed
365
A Configuration Script System Performance of the AI with This System Extensions to the Configuration Script Paradigm
365 372 372
Embedding Lua
372
Lua Overview
373
Lua Language Fundamentals
373
Contents
Integration Example Implementation in the AIsteroids Test Bed A Description of a Better System Performance of the AI with This System
377 381 385 386
Pros of Scripting Systems
387
Cons of Scripted Systems
389
Extensions to the Scripting Paradigm
392
Completely Custom Languages
392
Built-In Debugging Tools
392
A Smart IDE for Writing Scripts
393
Automatic Integration with the Game
393
Self-Modifying Scripts
394
Optimizations
394
Design Considerations
395
Types of Solutions
395
Agent Reactivity
396
System Realism
396
Development Limitations
397
Entertainment Limitations
397
Summary 19
xix
Location-Based Information Systems Location-Based Information Systems Overview
397 399 399
Influence Maps (IMs)
400
Smart Terrain
401
Terrain Analysis (TA)
401
How These Techniques Are Used
402
Occupance Data
402
Ground Control
403
Pathfinding System Helper Data
403
Danger Signification
404
Rough Battlefield Planning
404
xx
Contents
Simple Terrain Analysis
404
Advanced Terrain Analysis
405
Influence Mapping Skeletal Code and Test-Bed Implementation The OccupanceInfluenceMap
413
Uses Within the Test Bed for an Occupance IM
418
The ControlInfluenceMap
419
Uses Within the Test Bed for a Control-Based IM
422
The BitwiseInfluenceMap
422
Uses Within the Test Bed for a Bitwise IM
429
Other Implementations
429
Pros of Location-Based Information Systems
432
Cons of Location-Based Information Systems
432
Extensions to the Paradigm
432
Optimizations
433
Design Considerations
433
Types of Solutions
434
Agent Reactivity
434
System Realism
434
Genre and Platform
434
Development Limitations
435
Entertainment Limitations
435
Summary 20
406
Steering Behaviors
435 437
Steering Behavior Overview
437
Steering Skeletal Code
440
The SteeringBehavior Class
440
The SteeringBehaviorManager Class
442
The SteeringControl Class
448
Implementing a Steering-Controlled Ship into Our Test Bed Coding the Control Class
448 462
Contents
Performance of the AI with This System
465
Pros of Steering-Based Systems
466
Cons of FSM-Based Systems
467
Extensions to the Paradigm
468
Layered Steering
468
Learning Behaviors
469
Other Common Behaviors
470
Data-Driven Steering Behaviors
471
Optimizations
472
Load Balancing
472
Priority/Weight Adjustments
473
Design Considerations
473
Types of Solutions
474
Agent Reactivity
474
System Realism
474
Genre
475
Content
475
Platform
475
Development Limitations
476
Entertainment Limitations
476
Summary 21
xxi
Combination Systems
476 479
The Demo
479
FSM Changes
484
Steering Changes
498
Performance of the AI with This System
502
Extensions to the Paradigm
507
FSMS
507
Steering
508
Influence Mapping
508
xxii
Contents
Scripting
509
Messaging
510
Summary 22
Genetic Algorithms Overview
510 513 513
Evolution in Nature
514
Evolution in Games
515
Basic Genetic Method
517
Initialize a Starting Population of Individuals
517
Evaluate Each Individual’s Success Within the Problem Space
517
Generate New Individuals Using Reproduction
517
Representing the Problem
518
The Gene and Genome
518
The Fitness Function
521
Reproduction
522
Implementing a Genetic Algorithm System into the AIsteroids Test Bed
527
Performance Within the Test Bed
544
Pros of Genetic Algorithm-Based Systems
545
Cons of Genetic Algorithm-Based Systems
547
Extensions to the Paradigm
549
Ant Colony Algorithms
550
Coevolution
550
Self-Adapting GAs
551
Genetic Programming
551
Design Considerations
551
Types of Solutions
551
Agent Reactivity
552
System Realism
552
Genre
552
Platform
552
Contents
Development Limitations
553
Entertainment Limitations
553
Summary 23
xxiii
Neural Networks
553 555
Neural Nets in Nature
555
Artificial Neural Nets Overview
557
Using a Neural Net
560
Structure
560
Learning Mechanism
562
Creating Training Data
562
An Aside on Neural Network Activity
563
Implementing a Neural Net Within the AIsteroids Test Bed
566
The NeuralNet Class
567
The NLayer Class
572
The NNAIControl Class
576
Performance Within the Test Bed
583
Optimization
584
Pros of Neural Net-Based Systems
585
Cons of Neural Net-Based Systems
585
Extensions to the Paradigm
587
Other Types of NNs
587
Other Types of NN Learning
589
Design Considerations
590
Types of Solutions
590
Agent Reactivity
590
System Realism
590
Genre and Platform
591
Development Limitations
591
Entertainment Limitations
591
Summary
591
xxiv 24
Contents
Other Techniques of Note Artificial Life
593
Artificial Life Usage in Games
594
Artificial Life Disciplines
594
Pros
596
Cons
597
Areas for Exploitation Within Games
597
Planning Algorithms
598
Current Usage in Games
599
Pros
601
Cons
602
Areas for Exploitation Within Games
602
Production Systems
603
Pros
604
Cons
606
Areas for Exploitation Within Games
606
Decision Trees
606
Pros
608
Cons
609
Areas for Exploitation Within Games
609
Fuzzy Logic
610
Pros
612
Cons
612
Areas for Exploitation Within Games
612
Summary 25
593
Distributed AI Design Basic Overview
613 615 615
A Real-Life Example
616
The Distributed Layers
617
The Real-Life Example Revisited
617
Contents
The Perceptions and Events Layer
619
The Behavior Layer
619
The Animation Layer
621
The Motion Layer
624
Short-Term Decision Making (ST)
625
Long-Term Decision Making (LT)
625
Location-Based Information Layer (LBI)
626
Brooks Subsumption Architectures
627
Game Breakdown Goals
628
Distributed Super Mario Bros.
628
AI Enemies Implementation
629
AI Player Implementation
635
Summary 26
xxv
Common AI Development Concerns Design Considerations
639 641 641
Concerns with Data-Driven AI Systems
642
The One-Track-Mind Syndrome
644
Level-of-Detail (LOD) AI
645
Support AI
648
General AI Design Thinking
650
Entertainment Considerations
651
The All-Important Fun Factor
652
Perceived Randomness
653
Some Things That Make an AI System Look Stupid
655
Production Concerns
657
Coherent AI Behavior
657
Thinking About Tuning Ahead of Time
658
Idiot-Proof Your AI
659
Consider Designer-Used Tools Differently
659
Summary
660
xxvi 27
Contents
Debugging General Debugging of AI Systems
661
Visual Debugging
662
A Variety of Information
662
Debugging and Tuning
662
Timing Information
663
State Oscillation
663
Console Debugging
663
Debugging Scripting Languages
663
Double-Duty Influence Mapping
663
Widgets
664
Implementation
664
BasicButton
668
Watcher
669
RadioButton
669
OnOffButton
670
ScrubberWidget
671
Integration Within a Program
672
Summary 28
661
Conclusions, and the Future What Game AI Will Be in the Future
677 679 680
Appendix A
About the CD
683
Appendix B
References
685
Index
687
Preface
There are not many books on general game programming, and even fewer on game artificial intelligence (AI) programming. This text will provide the reader with four principal elements that will extend the current library. 1. A clear definition of “game AI.” Many books use a general or far too widesweeping meaning for the term AI, and as such, the reader never feels completely satisfied with the solutions provided. This lack of satisfaction may further the “mystical” nature of AI that pervades the common knowledge of both the general public and industry people. 2. Genre-by-genre breakdown of AI elements and solutions. Too many books rely on one type of game, or one narrow demonstration program. This text breaks apart the majority of the modern game genres and gives concrete examples of AI usage in actual released titles. By seeing the reasoning behind the different genre choices of AI paradigms, the reader will gain greater understanding of the paradigms themselves. 3. Implemented code for the majority of commonly-used AI paradigms. In the latter parts of the book, real code is given for each AI technique, both in skeletal form, and as part of a real-world example application. The code is broken down and fully discussed to help show the actual handling of the system. 4. A discussion of future directions for improvement. With each genre and AI technique, the text gives examples of ways the system could be extended. This is done by pointing out common AI failings in current and classic games, as well as by detailing ways in which systems could be optimized for space, speed, or some other limitation.
xxvii
This page intentionally left blank
Introduction
The book is divided into a few major areas: theory and background, major genre divisions, AI techniques with code, and AI engine development concerns. Readers of the book should note that there might be some confusion if read from start to finish, since the genre chapters make mention of some of the AI techniques discussed later in the book. However, discussion of the AI techniques first would have made mention of game genre issues, so the current ordering was thought to be best.
Content Overview Chapters 1–3 provides an overall look at game AI, covers the basic terminology that will be used throughout the book, looks at some of the underlying concepts of game AI, and dissects the parts of a game AI engine. Chapters 4–14 cover specific game genres and how they use the differing AI paradigms. Although the book cannot be all-inclusive (by detailing how each and every game “did it”), it does discuss the more common solutions to the problems posed by games of each genre. Chapters 15–21 provides the actual code implementations for the basic AI techniques, and Chapters 22–24 covers the more advanced ones. In the last four chapters, a variety of concepts and concerns are broken down, dealing with real game AI development: general design and development issues, distributed AI as an overall paradigm that can help with the organization of almost any AI engine, debugging AI systems, and the future of AI.
Audience This book was written to provide game developers with the tools necessary to create modern game artificial intelligence (AI) engines, and to survey the capabilities of the differing techniques used in some current AI engines. AI programming is a xxix
xxx
Introduction
very challenging aspect of game production, and although many books have been written on generic game-related data structures and coding styles, very few have been written specifically for this important and tech-heavy subject. This book is specifically written for the professional game AI programmer, or the programmer interested in expanding his area of interest into AI. If you are having difficulties determining which techniques to use, have questions about, or need working code for the engine best suited for a particular game, this is the book for you. This book provides a clean, usable interface for a variety of useful game AI techniques. The book emphasizes primary decision-making paradigms, and as such does not delve into the important areas of pathfinding (at least, not directly; many of the techniques presented could be used to run a pathfinder) or perception, although they are discussed. This book assumes a working knowledge of C++, the classical data structures, and a basic knowledge of object-oriented programming. The demonstration programs are written in Microsoft Visual C++® under the Windows® platform, but only the rendering is platform specific, and the rendering API used is the GLUT extension to OpenGL, so that you could easily port to another system if necessary. See the CD-ROM for information on GLUT and OpenGL. After reading this book, you will be familiar with a good portion of the huge landscape of knowledge that a game AI programmer has to master. The genre discussions will supply the programmer with insights into how to build an AI system from start to finish, given the realities of the product and the schedule. The code in the book is generic enough to build almost any type of AI system and it provides clear ways to combine techniques into much more complex and usable game-specific AI engines.
1
Basic Definitions and Concepts In This Chapter What Is Intelligence? What Is “Game AI”? What Game AI Is Not How this Definition Differs from that of Academic AI Applicable Mind Science and Psychology Theory Lessons from Robotics Summary
W
elcome to AI Game Engine Programming. This book is meant to give the game artificial intelligence (AI) programmer the knowledge and tools needed to create AI engines for modern commercial games. What exactly do we mean by “game AI”? It turns out this isn’t as straightforward a question as you would think. First, the term “game” is somewhat hazy itself. A “game” could refer to a spoken ritual that a class full of kids might play or to a complex technological undertaking by our government for training purposes. For this book, we’ll be referring to electronic video games exclusively, although some of the concepts that we’ll cover would probably be applicable to board games, or other strategic competitive gamelike activities. Second, we come to the term “AI.” Seeing as its foundations were created in the 1950s, the science of AI is relatively young. The usage of AI techniques within games is even more contemporary, because of the computation and storage-space limitations of earlier game machines (not to mention the simplistic nature of many early games). The field’s immaturity means that the definition of game AI is not clear for most people, even those who practice game production. This chapter will define the term game AI, identify practices and techniques that are commonly mistaken for game AI, and discuss areas of future expansion. Later in the chapter, relevant concepts from other fields, including mind science, psychology, and robotics, will be discussed regarding game AI systems. 1
2
AI Game Engine Programming
W HAT I S I NTELLIGENCE ? The word intelligence is fairly nebulous. The dictionary will tell you it is the capacity to acquire and apply knowledge, but this is far too general. This definition, interpreted literally, could mean that your thermostat is intelligent. It acquires the knowledge that the room is too cold and applies what it learned by turning on the heater. The dictionary goes on to suggest that intelligence demonstrates the faculty of thought and reason. Although this is a little better (and more limiting; the thermostat has been left behind), it really just expands our definition problem by introducing two even more unclear terms, thought and reason. In fact, the feat of providing a true definition of intelligence is an old and harried debate that is far beyond the scope of this text. Thankfully, making good games does not require this definition. Actually, this text will agree with our first dictionary definition, as it fits nicely with what we expect game systems to exhibit to be considered intelligent. For our purposes, an intelligent game agent is one that acquires knowledge about the world, and then acts on that knowledge. This is not to say that our notion of intelligence is completely reactive, since the “action” we might take is to build a complex plan for solving the game scenario. The quality and effectiveness of these actions then become a question of game balance and design.
W HAT I S “G AM E AI”? Let us start with a rigorous, academic definition of AI. In their seminal AI Bible, Artificial Intelligence: A Modern Approach, Russel and Norvig [Russel 95] say that AI is the creation of computer programs that emulate acting and thinking like a human, as well as acting and thinking rationally. This definition encompasses both the cognitive and the behavioral views of intelligence (by requiring emulation of both actions and thinking). It also includes, yet separates, the notions of rationality and “humanity” (because being human is sometimes far from rational, but is still considered intelligent; like running into a burning building to save your child). In contrast, games don’t require such a broad, all-encompassing notion of AI. Game AI is specifically the code in a game that makes the computer-controlled elements appear to make smart decisions when the game has multiple choices for a given situation, resulting in behaviors that are relevant, effective, and useful. Note the word “appear” in the last sentence. The AI-spawned behaviors in games are very results-oriented, and thus, we can say that the game world is primarily concerned with the behavioralist wing of AI science. We’re really only interested with the responses that the system will generate, and don’t really care how the system arrived
Chapter 1
Basic Definitions and Concepts
3
at it. We care about how the system acts, not how it thinks. People playing the game don’t care if the game is using a huge database of scripted decisions, is making directed searches of a decision tree, or is building an accurate knowledge base of its surroundings and making inferred choices based on logical rules. The proof is in the pudding as far as game AI goes. Modern game developers also use the term AI in other ways. For instance: Some people refer to the behavioral mechanics of the game as AI. These elements should actually be thought of as gameplay, but any time the AI controlled agents do something, people tend to think of it as AI, even if it’s using the exact mechanism that the human players use. Many people think of game AI primarily as animation selection. Once a game entity makes a decision as to what to do, animation selection then makes a lower level decision as to how (on a visual level) to perform the move. Say that your AI controlled baseball pitcher has decided to throw a curveball. The exact animation that he goes through performing that decision is animation selection. How does the windup go, where does he look, does he tip his hat, etc.? Perceptions are polled, and an intelligent contextual decision is made. But this kind of low-level decision making is much more short range than the kind of intelligence we are talking about. People that think of animation selection as AI tend to be working on games with very simple AI requirements, games that don’t require heavily strategic solutions. Even the algorithms that govern movement and collision can sometimes fall under this label (if the game uses animation-driven movement, rather than physics-based methods). In fact, the term “AI” is a broadly-used moniker in the game-development world. When discussing AI with someone else in the industry (or even within the company at which you work), it’s important to know that you both agree on the meaning and scope of the term; miscommunication can occur if your notion of AI is vastly different from the other person’s (be it simpler or more complex, or just at opposite ends of the responsibility spectrum). So, let’s be clear. When this book refers to AI, it will use the rather narrow definition of character-based behavioral intelligence. We care only about the behavioral smarts exhibited by some character within the game (the main character, a camera, an overseeing “god,” or any other agent within a game world). In the old days, AI programming was more commonly referred to as “gameplay programming,” because there really wasn’t anything intelligent about the behaviors exhibited by the CPU-controlled characters. See Figure 1.1 for an overall game AI timeline.
FIGURE 1.1
4
Game AI timeline.
Chapter 1
Basic Definitions and Concepts
5
In the early days of video gaming, most coders relied on patterns or some repetitive motions for their enemies (for example, Galaga or Donkey Kong), or they used enemies that barely moved at all but were vulnerable to attack only in certain “weak points” (like R-Type). The whole point of many of these early games was for the player to find the predetermined behavior patterns so that the player could easily beat that opponent (or wave of opponents) and move on to another. The extreme restraints of early processor speed and memory storage lead naturally to this type of game. Patterns could be stored easily, requiring minimal code to drive them, and required no calculation; the game simply moved the enemies around in the prescribed patterns, with whatever other behavior they exhibited layered on top (for instance, the Galaga enemies shoot while moving in a pattern when a player is beneath them). In fact, some games that used supposed “random” movement could sometimes lead to a pattern. The random number generator in many early games used a hard-coded table of pseudo-random numbers, eventually exposing a discernable sequence of overall game behavior. Another commonly used technique in the past (and sadly, the present) to make games appear smarter was to allow the computer opponents to cheat; that is, to have additional information about the game world that the human player does not have. The computer reads that a player pushed the punch button (before the player has even started the punch animation) and responds with a perfectly timed blocking move. A real-time strategy (RTS) game employing AI cheating might have its workers heading toward valuable resource sites early in the game, before they had explored the terrain to legitimately find those resources. AI cheating is also achieved when the game grants gifts to the computer opponent, by providing the opponent additional (and strategically timed) abilities, resources, and so forth that the opponent uses outright, instead of planning ahead and seeing the need for these resources on its own. These tactics lead to more challenging but ultimately less satisfying opponents because a human player can almost always pick up on the notion that the computer is accomplishing things that are impossible for the human player to accomplish, because the “cheats” are not available or given to the human player. One of the easier-to-notice and most frustrating examples of this impossible behavior is the use of what is called rubber banding in racing games. Toward the end of a race, if a player is beating the AI-controlled cars by too much, some games simply speed up the other cars until they’ve caught up with the human player, after which the AI-controlled cars return to normal. Sure, it makes the race more of a battle, but for a human player, watching a previously clueless race car suddenly perform miracles to catch up to him or her borders on ridiculous. The opposite case can be equally frustrating. The AI-controlled cars are so far ahead of the player that the game reacts by having the leaders suddenly crash, screw up, or just slow down until the human catches up. Most players realize they’re being coddled; they don’t feel as much of a sense of accomplishment when the computer gives up.
6
AI Game Engine Programming
In modern games, the old techniques are being abandoned. The primary selling point of games is slowly but surely evolving into the realm of AI accomplishments and abilities, instead of the graphical look of the game as it was during the last big phase of game development. This emphasis on visuals is actually somewhat causal in this new expansion of AI importance and quality; the early emphasis on graphics eventually led to specialized graphics processors on almost every platform, and the main CPU is increasingly being left open for more and more sophisticated AI routines. Now that the norm for game graphics is so high, the “wow” factor of game graphics is finally wearing thin, and people are increasingly concentrating on other elements of the game itself. So, the fact that we now have more CPU time is very advantageous, considering that the current consumer push is now for games that contain much better AI-controlled enemies. In the 8-bit days of gaming or before, 1 to 2 percent of total CPU time was the norm, if not an overestimation, for a game’s AI elements to run in. Now, games are routinely budgeting 10 to 35 percent of the CPU time to the AI system [Woodcock 01], with some games going even higher. Today’s game opponents can find better game solutions without cheating and can use more adaptive and emergent means—if for no reason other than that they have access to faster and more powerful processors driving them. Modern game AI is increasingly leading towards “real” intelligence techniques (as defined by academic AI), instead of the old standby of pre-scripted patterns or behaviors that only mimic intelligent behavior. As games (and gamers’ tastes) become more complex, game AI work will continue to be infused with more complex AI techniques (heuristic search, learning, planning, etc.).
W HAT G AM E AI I S N OT The term game AI can be used as quite the broad label, often loosely used when referring to all sorts of areas within a game: the collision avoidance (or pathfinding) system, the player controls, the user interface, and sometimes the entire animation system. To some extent, these elements do have something to add to the AI world and are elements that, if done poorly, will make the game seem “stupider,” but they are not the primary AI system in a game. An exception to this might be a game in which the gameplay is simple enough that the entire smarts of the enemies are in moving around or choosing the right animations to play. The difference is this: Game AI makes intelligent decisions when there are multiple options or directions for play. The above-mentioned secondarysupport systems, while making decisions from a pool of options/animations/paths, are more “find the optimal” (read: singular) solution for any particular input. The main AI in contrast might have many equally good solutions, but needs to
Chapter 1
Basic Definitions and Concepts
7
consider planning, resources, player attributes (including esoteric attributes like personality type or things like character flaws), and so on to make decisions for the game’s bigger picture. An alternative way of thinking about this differentiation is that these support systems are much more low-level intelligence, whereas this book will focus mostly on the high-level decisions that an AI system needs to make. For example, you get out of your chair and walk across the room to the refrigerator. The thought in your mind was, “I want a soda out of the fridge.” But look at all the low-level intelligence you used to accomplish the task: your mind determined the right sequence of muscle contractions to get you out of the chair (animation picking), and then started you moving toward the fridge (behavior selection), threading you through all the things on the floor (pathfinding). In addition, you slightly lost your balance but regained it quickly (physics simulation) and scratched your head on the way there (secondary behavior layering), in addition to a myriad of other minor actions. None of these secondary concerns changed the fact that your entire plan was to go get a soda, which you eventually accomplished. Most games split up the various levels of decision making into separate systems that barely communicate. The point is that these low-level systems do support the intelligence of the agent but, for this book’s purposes, do not define the intelligence of an AI-controlled agent. A completely separate point to consider is that creating better game AI is not necessarily a result of writing better code. This is what puts the “A” in AI. Many programmers believe that AI creation is a technical problem that can be solved purely with programming skill, but there’s much more to it than that. When building game AI, a good software designer must consider balancing issues from such disparate areas as gameplay, aesthetics, animation, audio, and behavior of both the AI and the game interface. It is true that a vast number of highly technical challenges must be overcome by the AI system. However, the ultimate goal of the AI is to provide the player with an entertaining experience, not to be a demonstration for your clever code. Gamers will not care about your shiny new algorithm if it doesn’t feel smart and fun. Game AI is not the best code; it is the best use of code and a large dollop of “whatever works.” Some of the smartest-looking games have used very questionable methods to achieve their solutions, and although this book is not advocating poorly written code, nothing should be thrown away if it helps to give the illusion of intelligence and enhances the fun factor of the game. Plus, some of the most elegant game code in the world started out as a mindless hack, which blossomed into a clever algorithm later, upon retrospection and cleanup. On a less serious note, game AI is also not some kind of new life form—a disconnected brain that will eventually take over your PlayStation® and command you to feed it regularly. Hollywood routinely tells us that something sinister is probably what AI has in store for us, but the truth is likely far less dramatic. In the future,
8
AI Game Engine Programming
we will most likely have access to a truly generic AI paradigm that will learn to competently play any game, but for now this is not the case. Right now, game AI is still very game-specific and very much in the hands of the coders who work on it. The field is still widely misunderstood by the non-programming public, however, and even by those people working in game development who don’t regularly work with AI systems.
H OW T H IS D EFI N ITION D I FFERS
FROM
T HAT
OF
A CADEM IC AI
The world of academic AI has two main goals. First is to help us understand intelligent entities, which will, in turn, help us to understand ourselves. Second is to build intelligent entities, for fun and profit, you might say, because it turns out that these intelligent entities can be useful in our everyday lives. The first goal is also the goal of more esoteric fields, such as philosophy and psychology, but in a much more functional way. Rather than the philosophical, “Why are we intelligent?,” or the psychological, “Where in the brain does intelligence come from?,” AI is more concerned with the question, “How is that guy finding the smart-sounding answer?” The second goal mirrors the nature of the practical economy (especially in the western world), in that the research that is most likely to result in the largest profits is also the most likely to win the largest funding. As stated earlier, Russel and Norvig [Russel 95] define AI as the creation of computer programs that emulate four things: 1. 2. 3. 4.
thinking humanly thinking rationally acting humanly acting rationally
In academic study, all four parts of this definition have been the basis for building intelligent programs. The Turing test is a prime example of a program specifically created for acting humanly—the test states that if you cannot tell the difference between the actions of the program and the actions of a person, that program is intelligent. Some cognitive theorists, who are helping to blend traditional human mind science into AI creation, hope to lead towards human-level intelligence by actually getting a computer to think humanly. Sheer logic systems try to solve problems without personal bias or emotion, purely by thinking rationally. Lastly, many AI systems are concerned with acting rationally—always trying to come up with the correct answer that, in turn, directs the system to behave correctly.
Chapter 1
Basic Definitions and Concepts
9
But, the vast majority of academic AI study is heavily biased towards the rationality side. If you think about it, rationality lends itself much more cleanly to a computing environment, since it is algorithmic in nature. If you start with a true statement, you can apply standard logical operators to it and retain a true statement. In contrast, game AI focuses on acting “human,” with much less dependence on total rationality. This is because game AI needs to model the highs and lows of human task performance, instead of a rigorous search toward the best decision at all times. Games are played for entertainment, of course, and nobody wants to be soundly beaten every time. Say you’re making a chess game. If you’re making this chess game as part of an academic study, you probably want it to play the best game possible, given time and memory constraints. You are going to try to achieve perfect rationality, using highly-tuned AI techniques to help you navigate the sea of possible actions. If instead, you are building your chess game to give a human player an entertaining opponent to play against, then your goal shifts dramatically. Now you want a game that provides the person with a suitable challenge, but doesn’t overwhelm the human by always making the best move. Yes, the techniques used to achieve these two programs might parallel in some ways, but because the primary goal of each program is different, the coding of the two systems will dramatically diverge. The people who coded Big Blue did not care if Kasparov was having fun when playing against it. But the people behind the very popular Chessmaster games surely spend a lot of time thinking about the fun factor, especially at the default difficulty setting. Chess is an odd example because humans playing a chess program usually expect it to perform pretty well (unless they’re just learning and have specifically set the difficulty rating of the program to a low level). But imagine an AI-controlled Quake “bot” deathmatch opponent. If the bot came into the room, dodged perfectly, aimed perfectly, and knew exactly where and when powerups spawned in the map, it wouldn’t be very fun to play against (not for very long, anyway). Instead, we want a much more human level of performance from a game AI opponent. We want to play against an enemy that occasionally misses, runs out of ammo in the middle of a fight, jumps wrong and falls, and everything else that makes an opponent appear human. We still want competent opponents, but because our measure of competence, as humans, involves a measure of error, we expect shortcomings and quirks when determining how intelligent, as well as how real, something is. Anything that is too perfect isn’t seen as more intelligent; it is usually seen as either cheating, or alien (some might say “like a computer”). Academic AI systems are generally not trying to model humanity (although there is the odd rare case). They are mostly trying to model intelligence—the ability to produce the most rational decision given all the possible decisions and the rules. This is usually their one and only requirement and, as such, the reason why
10
AI Game Engine Programming
all our limitations in games (such as time or memory) are not given thought. Also, by distancing themselves from the issues of humanity, they don’t run into the sticky problems in dealing with questions about what constitutes human intelligence and proper problem solving. They just happily chug along, searching vast seas of agreed-upon possibility for the maximum total value. Eventually, computing power, memory capacity, and software engineering will become so great that these two separate fields of AI research may no longer be dissociated. AI systems may achieve the kind of performance necessary to solve even the most complex of problems in real time, and as such, programming them might be more like simply communicating the problem to the system. Game programmers would then use the same general intelligence systems that any programmer would.
A PPLICABLE M I N D S CI ENCE
AN D
P SYCHOLOGY T H EORY
Thinking about the way that the human mind works is a great way to flavor your AI programming with structural and procedural lessons from reality. Try to take this section with a grain of salt, and note that different theories exist on the workings and organization of the brain. This section is meant to give you ideas and notions of how to break down intelligence tasks in the same ways that the human mind does. BRAIN ORGANIZATION Classically, the brain is divided up into three main subsections: the hindbrain (or brain stem), the midbrain, and the forebrain. Most people may have heard these divisions somewhat wrongly referred to as the reptilian brain, the mammalian brain, and the human brain, but recent research has shown this sort of clear-cut, speciesrelated division to be false. Almost all animal brains have all three parts, just in different sizes and, in some cases, in dramatically different locations (thus, snakes have a mammalian brain region). These brain regions can be divided into smaller working structures, each of which operate independently by using local working memory areas and accessing neighboring synaptic connections to do specific tasks for the organism (fear conditioning in humans is mostly centered in a brain structure called the amygdala, for example). But these regions are also interconnected, some areas heavily so, to perform global-level tasking as well (the above-mentioned amygdala, through the thalamus and some cortical regions, is also a primary first-step collection spot for emotional data, which will then be sent to another brain structure called the hippocampus for blending with other sensory input and eventual storage into long-term memory). If you think of the brain as being an object-oriented class, the amygdala
Chapter 1
Basic Definitions and Concepts
11
would be a small class, with its own internal functions and data members. But it would also be an internal structure within other classes, like Long-Term Memory, or Forebrain. This object-oriented, hierarchical organizational model of the brain has merit when setting up an AI engine, as seen in Figure 1.2, which shows a nice mirroring between brain and game systems. By breaking down your AI tasks into atomic modules that require little knowledge of each other (like the brain’s small, independent structures), you’ll find it much easier to follow good object-oriented programming principles. Combinations of the atomic modules can be blended into more complex representations as needed, without replicating code. This also represents the kind of efficiency we should be trying to achieve in our AI systems. Avoid single-use calculations and code whenever possible, or input conditions that are so rare as to be practically hard-coded. Alas, inefficiency cannot be completely overcome, but most inefficiencies can be eliminated with clever thinking and programming. KNOWLEDGE BASE
AND
LEARNING
Although the inner workings of the human memory system are not fully understood, the common idea is that information is stored in the form of small changes in brain nerve cells at the synapse level. These changes cause differences in the electrical conductivity of different routes through the network and, as such, affect the firing potential of specific nerve cells as well as whole sub-networks. If you use a particular neural pathway, it gets stronger. The reverse is also true. Thus, memory systems use a technique that game designers could learn a lot from (no pun intended), that of plasticity. Instead of creating a set-in-stone list of AI behaviors and reactions to human actions, we can keep the behavior mix exhibited by the AI malleable through plasticity. The AI system could keep track of its actions and make note of whether or not the human consistently chooses certain behaviors in response. It could then recognize trends and bias its behaviors (or the requisite counter measures, as a defense) to plastically change the overall behavior mix that the AI uses. Of course, an AI memory system would require a dependable way of determining what is “good” to learn. We humans rely on teaching conventions and retrospection to gain insight into which information to value, and which to discard. Without these aids, the human brain would just store everything, leading to misconception, miscommunication, and even delusion. Although very contextually complex, a filter on AI learning would keep the human player from exploiting a learning system by teaching it misleading behaviors, knowing that the system will respond in kind. Does the AI always use a low block to stop the next incoming punch after the player has punched three times in a row? An advanced player would perceive that and punch three times followed by a high punch to get a free
FIGURE 1.2 Object-oriented nature of the brain related to game AI systems.
12
Chapter 1
Basic Definitions and Concepts
13
hit in on the low-blocking AI. But another level of AI memory performance would have the AI noticing that pattern, and making adjustments to how it would handle the situation in the future. This would be tantamount to learning about how the player is learning. Another useful lesson from nature is that the rate of memory reinforcement and degradation in the human brain is not the same for all systems. Usually, memories are created only after repeated exposure to the information. Likewise, already existing memories tend to take a period of time before they either wither through misuse, or will require conscious counter-association in order to quell. Memories associated with pain aversion, however, may never fully extinguish, even if the person only experienced the relation once. This is a good example of nature using dynamic hard coding. The usually plastic changes in the brain can be “locked in” (by stopping the learning process or moving these changes into a more long-term memory) and thus not be allowed to degrade over time. But like the brain, too much hardcoding used in the wrong place can lead to odd behavior, turning people (or your game characters) into apparent phobics or amnesiacs. Another concept to think about is long-term versus short-term memory. Short-term, or working memory, can be thought of as perception data that can only be held onto for a short time, in a small queue. The items sitting in short-term memory can be filtered for importance, and then stored away into longer-term memories, or simply forgotten about by sitting idle until a time duration is hit or additional data comes in and bumps it off the end of the queue. Varying the size of the queue and the rates of storage creates such concepts as attention span, as well as single-mindedness. Many games have essentially digital memory. An enemy will see a player and pursue the character for a while. But if the player hides, the enemy eventually forgets about the player and goes back to what he was doing. This is classic state-based AI behavior, but it is also very unrealistic and unintelligent behavior. It’s even more unrealistic when the enemy didn’t just see the player, but was shot and injured during the exchange. By using a more analog memory model for our opponent, he could still go back to his post, but he’d be much more sensitive to future attacks, would most likely spend the time at his post bandaging his wounds, would probably make it a priority to call for backup, and so forth. For sure, some games do use these types of memory systems. But the vast majority does not. The brain also makes use of modulators, chemicals that are released into the blood, affect some change in brain state, and take a while to degrade. These are things like adrenaline or oxytocin. These chemicals’ main job is to inhibit or enhance the firing of neurons in specific brain areas. This leads to a more focused mind-set, as well as flavoring the memories of the particular situation in a contextual way. In a game AI system, a modulator could override the overall AI state, or just adjust the behavior exhibited within a certain state. In this way, conventional
14
AI Game Engine Programming
state-based AI could be made more flexible by borrowing the concept of modulation. The earlier-mentioned enemy character that the player alarmed could transition to an entirely different Alerted state, which would slowly degrade and then transition back down to a Normal state. But using a state system with modifiers, the enemy could stay in his normal Guard state, with an aggressive or alerted modulator. Although keeping the state diagram of a character simpler, this would require a much more general approach to coding the Guard state. More on this in Chapter 15, under finite state machine extensions. The human brain stores things in different memory centers. It does this in a few different ways: direct experience, imitation, or imaginative speculation. With the possible exception of speculation, which would require quite a sophisticated mental model, game characters may gather information in the same ways. Keeping statistics on the strategies that seem to work against the human and then biasing future AI behavior could be thought of as learning by direct experience. Imitation would involve recording the strategies that the human player is successfully using and employing them in return. The problem that games have had with classical AI learning algorithms is that they usually take many iterations of exposure to induce learning. It is a slippery slope to do learning in the fast-paced, short-lived world of the AI opponent. Most games that use these techniques do all the learning before hand, during production, and then ship the games with the learning disabled, so that the behavior is stable. This will change as additional techniques, infused with both speed and accuracy, are found and made public. But learning need not be “conscious.” Influence maps (see Chapter 19) can be used by a variety of games to create much lower level, or “subconscious” learning, making AI enemies seem smarter without any of the iteration issues of normal learning. A simple measure of how many units from each side have died on each spot of the map could give an RTS game’s pathfinding algorithm valuable information necessary to avoid kill zones where an opponent (human or otherwise) has set up a trap along some commonly traveled map location. This learning effect could even erode over time or be influenced by units relaying back that they have destroyed whatever was causing the kill zone in the first place. Influence maps are also being used successfully in some sports games. For example, by slightly perturbing the default positions of the players on a soccer field to be better positioned for the passes the human has made in the past. The same system can also be used by the defensive team to allow them to be better able to possibly block these passes. Influence map systems allow cumulative kinds of information to be readily stored in a quick and accessible way, while keeping the number of iterations that have to occur to see the fruition of this type of learning very low. Because the nature of the information stored is so specific, the problem of storing misleading information is also somewhat minimized.
Chapter 1
Basic Definitions and Concepts
15
COGNITION The flood of data coming from our senses bombards us at all times. How does the brain know which bits of information to deal with first? Which pieces to throw away? When to override the processing it is currently doing for a more lifethreatening situation? It does this by using the brain’s various systems to quickly categorize and prioritize incoming data. Cognition can be thought of as taking all your incoming sense data, also called perceptions, and filtering them through your innate knowledge (both instinctual and intuitive) as well as your reasoning centers (which includes your stored memories), to come up with some understanding of what those perceptions mean to you. Logic, reason, culture, and all of your personally stored rules can be thought as merely ways of sorting out the important perceptions from the background noise. Think of the sheer volume of input coursing into the mind of a person living in a big city. He must contend with the sights, sounds, and smells of millions of people and cars, the constant pathfinding through the crowd, the hawkers, and homeless vying for his attention, and countless other distractions. Perceptions are also not all external. The pressures of the modern world cause stress and anxiety that split your attention and fragment your thoughts. Your mind also needs to try to distill the important thoughts inside your own head from the sea of transient, flighty ideas that everyone is constantly engaged in. If your brain tried to keep all this in mind, it would never be able to concentrate sufficiently to perform any task at all. Only by boiling all this information down to the most critical half-dozen perceptions or so at any given time can you hope to accomplish anything. In game AI, we don’t suffer as much from the flood of data because we can pick and choose our perceptions at any level in the process, and this makes the whole procedure a bit less mystical. In Figure 1.3, you can see a mock-up of a sports game using different perceptions for the various decisions being made by the AI player in the foreground. Make sure, when coding any particular AI subsystem that you only use those perceptions you truly need. Be careful not to oversimplify, or you may make the output behaviors from this subsystem too predictable. An auditory subsystem that only causes an enemy character to hear a sound when its location is within some range to the enemy would seem strange when a player sets off a particularly loud noise just outside of that range. A game design should take into account distance and starting volume, so that sounds would naturally trail off as they travel. You might also want to take into account the acoustics of the environment because sounds will travel much longer distances in a canyon than in an office building (or underwater versus open air). These are very simple examples, but you see the notion involved. Perceptions are much more than a single value, because there are usually many ways to interpret the data that each perception represents.
16
AI Game Engine Programming
FIGURE 1.3
A visual depiction of various perceptions being taken into account by a game character.
We can think of the systems used in the AI world as filters as well. Whatever technique we are using as our primary decision-making system, to determine the right action to perform, is really just a method of filtering the current game state through all the possible things that the AI can do (or some subset of these possibilities, as defined by some rule or game state). Thus, we see the primary observation many people make about AI in general—that it all boils down to focused searching, in some way or another. This is true to some degree. Most AI systems are just different ways of searching through the variety of possibilities, and as such, the topography of your game’s possibilities can be used to conceptually consider the best AI technique to use. This topography is generally called the “state space” of the game. If your game’s possible outcomes to different perceptions are mostly isolated islands of response, with no real gray conditions, a state-based system might be the way to go. You’re dealing with a set of exclusive possible responses, an almost enumerated state space. However, if the full range of possible responses is more continuous, and would graph out more like a rolling hillside with occasional dips (or another metaphor with more than three dimensions, but you get the idea), a fuzzy system or one using neural nets might be a better fit, as they tend to work
Chapter 1
Basic Definitions and Concepts
17
better at identifying local minima and maxima in continuous fields of response. We will cover these and the other AI systems in Part III and Part IV of the book; this was merely for illustration. THEORY
OF
MIND
One psychological construct that is again being embraced as a major field of investigation by both behavioralists and cognitive scientists is that of the so-called Theory of Mind (ToM). This concept has a good deal of merit in the field of game AI because our primary job is creating systems that seem intelligent. A ToM is actually more of a cognitive capacity of human beings, rather than a theory. It fundamentally means that one person has the ability to understand others as having minds and a worldview that are separate from his own. In a slightly more technical fashion, ToM is defined as knowing that others are intentional agents, and to interpret their minds through theoretical concepts of intentional states such as beliefs and desires [Premack 78]. This isn’t as complicated as it sounds. Think of this as having the ability to see intent, rather than just strict recognition of action. We do it all the time as adults, and humanize even the most nonhuman of environmental elements. Listing 1.1 shows a bit of code from a Java version (written by Robert C. Goerlich, 1997) of the early AI program Eliza, which, in its time, did a remarkable job of making people believe it was much more than it really was. The idea of attributing agency to objects in our environment is almost innate in humans, especially objects that move. In simple experiments in which subjects were asked to explain what they saw when shown a scene consisting of a colored spot on a computer screen moving from left to right, closely followed by a different-colored dot, a large portion of people described it as “the first dot was being chased by the second.” People give their cars personalities, and even think (at some superstitious level) that if you talk bad about it, or suggest getting rid of it, it will perform poorly. In human terms, the ability to form a ToM about others usually develops at about the age of three. A commonly used test to determine if the child has developed this cognitive trait is to question the child about the classic “False Belief Task” [Wimmer 83]. In this problem, the child is presented with a scene in which a character named Bobby puts a personal belonging, such as a book, into his closet. He then leaves, and while he’s away, his little brother comes and takes out the book and puts it in a cupboard. The child is then asked where Bobby will look for his book when he comes back. If the child indicates the cupboard, he reveals that he has yet to develop the understanding that Bobby wouldn’t have the same information in his mind that the child does. He, therefore, does not have an abstract frame of reference, or theory, about Bobby’s mind, hence no ToM about Bobby. If the child gives the correct answer, it shows that he can not only determine facts about
18
AI Game Engine Programming
the world but can also form a theoretical, simplified model of others’ minds that includes the facts, desires, and beliefs that they might have; thus providing a theory of this other’s mind. LISTING 1.1
Some sample code from a Java version of Eliza.
public class Eliza extends Applet { ElizaChat cq[]; ElizaRespLdr ChatLdr; static ElizaConjugate ChatConj; boolean _started=false; Font _font; String _s; public void init() { super.init(); ChatLdr = new ElizaRespLdr(); ChatConj = new ElizaConjugate(); //{{INIT_CONTROLS setLayout(null); addNotify(); resize(425,313); setBackground(new Color(16776960)); list1 = new java.awt.List(0,false); list1.addItem(“Hi! I’m Eliza. Let’s talk.”); add(list1); list1.reshape(12,12,395,193); list1.setFont(new Font(“TimesRoman”, Font.BOLD, 14)); list1.setBackground(new Color(16777215)); button1 = new java.awt.Button (“Depress the Button or depress to send to Eliza”); button1.reshape(48,264,324,26); button1.setFont(new Font(“Helvetica”, Font.PLAIN, 12)); button1.setForeground(new Color(0)); add(button1); textField1 = new java.awt.TextField(); textField1.reshape(36,228,348,24);
Chapter 1
Basic Definitions and Concepts
textField1.setFont(new Font(“TimesRoman”, Font.BOLD, 14)); textField1.setBackground(new Color(16777215)); add(textField1); //}} textField1.requestFocus(); } public boolean action(Event event, Object arg) { if (event.id == Event.ACTION_EVENT && event.target == button1) { clickedButton1(); textField1.requestFocus(); return true; } if (event.id == Event.ACTION_EVENT && event.target == textField1) { clickedButton1(); textField1.requestFocus(); return true; } return super.handleEvent(event); } public void clickedButton1() { parseWords(textField1.getText()); textField1.setText(“”); textField1.setEditable(true); textField1.requestFocus(); } public void parseWords(String s_) { int idx=0, idxSpace=0; int _length=0; // actual no of elements in set int _maxLength=200; // capacity of set int _w; list1.addItem(s_); list1.makeVisible(list1.getVisibleIndex()+1); s_=s_.toLowerCase()+” “;
19
20
AI Game Engine Programming
while(s_.indexOf(“‘“)>=0) s_=s_.substring(0,s_.indexOf(“‘“))+ s_.substring(s_.indexOf(“‘“)+1,s_.length()); bigloop: for(_length=0; _length= s_.length()) { _resp=ChatLdr.cq[ElizaChat.num_chats-1] .converse(“nokeyfound”); list1.addItem(_resp); list1.makeVisible(list1.getVisibleIndex()+1); } } } //{{DECLARE_CONTROLS java.awt.List list1; java.awt.Button button1; java.awt.TextField textField1; //}} } //--------------------
Chapter 1
Basic Definitions and Concepts
class ElizaChat { static int private String private String private int private int private boolean private boolean public String private String public int public int public int private char private char
num_chats=0; _keyWordList[]; _responseList[]; _idx=0; _rIdx=0; _started=false; _kw=true; _response; _dbKeyWord; _widx = 0; _w = 0; _x; _space; _plus;
public ElizaChat() { num_chats++; _keyWordList= new String[20]; _responseList=new String[20]; _rIdx=0; _idx=0; _keyWordList[_idx]=” “; _space=” “.charAt(0); _plus=”+”.charAt(0); } public String converse(String kw_) { _response = null; for(int i=0; i =_dbKeyWord.length()&& _keyWordList[i].equals (kw_.substring(0,_dbKeyWord.length()))) { _widx = (int) Math.round(Math.random()*_rIdx-.5); _response = _responseList[_widx];
21
22
AI Game Engine Programming
_x=_response.indexOf(“*”); if(_x>0) { _response=_response.substring(0,_x)+ kw_.substring(_dbKeyWord.length(), kw_.length()); if(_xm_active) { obj->Explode(); obj->DoCollision(this); } m_active=false; if(m_parent) { Game.IncrementScore(ASTEROID_SCORE_VAL); m_parent->TerminateBullet(); } }
60
AI Game Engine Programming
In this simple function, the bullet also increments the score, and calls its parent’s function (this depends on whether you set this bullet to have a ship parent because bullets can be freely instantiated as well), which just decrements the number of shots the ship has active. The bullet will also kill off the other object with which it collides. The general collision system only calls the—Explode() and DoCollision() functions for the first object in the collision, for optimization reasons. Therefore bullets, which require both objects to run collide code, need this special case consideration. TerminateBullet()
TH E
GameSession
C LASS
The overall game structure is shown in Listing 3.5. Most of the class is public because it will be accessed by the main game functions. The game is divided into a few high-level states: STATE_PLAY, STATE_PAUSE, STATE_NEXTWAVE, and STATE_GAMEOVER. These are very basic game flow states and serve only as modifiers to the draw and control codes. For this demonstration program, there are two Control classes that are instantiated, a HumanControl class that handles the keyboard events, and an AIControl class, which for right now does nothing but will eventually be where we put our AI code for the game. LISTING 3.5
The GameSession class header.
typedef std::list GameObjectList; Class GameSession { public: //constructor/functions GameSession(); void Update(float dt); void Draw(); void DrawLives(); void Clip(Point3f &p); void PostGameObj(GameObj*obj) {m_activeObj.push_back(obj);} //game controls enum { CONTROL_THRUST_ON, CONTROL_THRUST_REVERSE, CONTROL_THRUST_OFF,
Chapter 3
AIsteroids: Our AI Test Bed
CONTROL_RIGHT_ON, CONTROL_LEFT_ON, CONTROL_STOP_TURN, CONTROL_STOP, CONTROL_SHOOT, CONTROL_HYPERSPACE, CONTROL_PAUSE, CONTROL_AION, CONTROL_AIOFF }; void UseControl(int control); //score functions void IncrementScore(int inc) void ResetScore()
{m_score += inc;} {m_score = 0;}
//game related functions void StartGame(); void StartNextWave(); void LaunchAsteroidWave(); void WaveOver(); void GameOver(); void KillShip(GameObj *ship); //data Ship* m_mainShip; HumanControl* m_humanControl; AIControl* m_AIControl; bool int int int float float int int int int int bool enum {
m_bonusUsed; m_screenW; m_screenH; m_spaceSize; m_respawnTimer; m_powerupTimer; m_state; m_score; m_numLives; m_waveNumber; m_numAsteroids; m_AIOn;
61
62
AI Game Engine Programming
STATE_PLAY, STATE_PAUSE, STATE_NEXTWAVE, STATE_GAMEOVER }; private: GameObjList m_activeObj; };
The list of dynamic objects for the game is stored in a Standard Template Library (STL) list structure called m_activeObj. This program was written for simplicity, so it does things like new and delete memory while in game, whereas most real games try to achieve a solid memory allocation beforehand to prevent memory fragmentation (one method could be to allocate a large pool of the different GameObj structures, and then manage their use as needed). By placing all the game objects in this structure, the Update() function for GameSession is very simple and generic. The discussion of this function will be shown split into eight parts, so that each part of the update can be discussed separately. See Listings 3.6.1 through 3.6.7. PRIMARY LOGIC
AND
COLLISION CHECKING
Listing 3.6.1 is the primary part of the update loop. It sets up a for loop to iterate through all the game objects, and then for each object, runs its Update() method and clips its position to the viewport (which also wraps the position around, asteroids style). The function then checks for any collisions with other objects, by looping through the objects and calling the IsColliding() method on each. The collision calculations are optimized by the following rules: 1. An object must be registered to collide by having its m_collisionFlags variable not contain the GameObj::OBJ_NONE bit. 2. The object will only do collision checks against objects of the types for which it is registered. 3. An object cannot collide with another object that isn’t active (it m_active member is false). 4. Objects cannot collide with themselves.
LISTING 3.6.1
GameSession’s update loop, section 1: update and collision checking.
void GameSession::Update(float dt) {
Chapter 3
AIsteroids: Our AI Test Bed
63
GameObjectList::iterator list1; for(list1=m_activeObj.begin(); list1!=m_activeObj.end();++list1) { //update logic and positions if((*list1)>m_active) { (*list1)>Update(dt); Clip((*list1)–>m_position); } else continue; //check for collisions if((*list1)–>m_collisionFlags != GameObj::OBJ_NONE) { GameObjectList::iterator list2; for(list2=m_activeObj.begin(); list2!=m_activeObj.end();++list2) { //don’t collide with yourself if(list1 == list2) continue; if((*list2)–>m_active && ((*list1)–>m_collisionFlags & (*list2)–>m_type) && (*list1)–>IsColliding(*list2)) { (*list1)–>Explode(); (*list1)–>DoCollision((*list2)); } } } if(list1==m_activeObj.end()) break; }//main for loop }
OBJECT CLEANUP Objects that were destroyed by a collision or an object that has outlived its life counter variable will be removed from the object list by the code shown in Listing 3.6.2, and then erased. The functor that checks for the inactive condition (RemoveNotActive) is also in charge of deleting the actual memory taken up by the object; the erase function just takes it out of the GameSession object list.
64
AI Game Engine Programming
LISTING 3.6.2
GameSession’s update loop, section 2: killed object cleanup.
//get rid of inactive objects GameObjectList::iterator end = m_activeObj.end(); GameObjectList::iterator newEnd = remove_if(m_activeObj.begin(), m_activeObj.end(),RemoveNotActive); if(newEnd != end) m_activeObj.erase(newEnd,end);
SPAWNING MAIN SHIP
AND
POWERUPS
Listings 3.6.3 and 3.6.4 are simple parts of the update function that check a couple of timers, m_respawnTimer and m_powerupTimer. The respawn timer is used when the main ship has been destroyed; it takes a small pause before respawning. This is so the player has time to realize his ship has exploded. The powerup timer provides for the pause between each powerup spawning. If this time is up, the game spawns a new powerup with random position and velocity and adds it to the main object list. LISTING 3.6.3
GameSession’s update loop, section 3: respawn main ship.
//check for no main ship, respawn if(m_mainShip == NULL || m_respawnTimer>=0) { m_respawnTimer–=dt; if(m_respawnTimer SetShip(m_mainShip); m_AIControl–>SetShip(m_mainShip); } } }
LISTING 3.6.4
GameSession’s update loop, section 4: spawn powerups.
//occasionally spawn a powerup m_powerupTimer – =dt; if(m_powerupTimer m_position.x()= randFlt()*m_screenW; pow–>m_position.y()= randFlt()*m_screenH; pow–>m_position.z()= 0; pow–>m_velocity.x()= randFlt()*40 – 20; pow–>m_velocity.y()= randFlt()*40 – 20; pow–>m_velocity.z()= 0; PostGameObj(pow); } }
BONUS LIVES Listing 3.6.5 does a simple score check, and every 10,000 points, it awards the player another life. This is fairly straightforward and is a common practice in these kinds of games. LISTING 3.6.5
GameSession’s update loop, section 5: bonus lives.
//check for additional life bonus each 10K points if(m_score >= m_bonusScore) { m_numLives++; m_bonusScore += BONUS_LIFE_SCORE; }
END
OF
LEVEL
AND
GAME
The next two listings (3.6.6 and 3.6.7) check for two important game conditions, the end of the current level (determined when no asteroids are left for the player to shoot), and end of the game (determined when the player has no more lives left). Each of these conditions calls a function, WaveOver() or GameOver(), which sets some critical flags, and also advances the overall game state to either STATE_NEXTWAVE or STATE_GAMEOVER. LISTING 3.6.6
GameSession’s update loop, section 6: end of level.
//check for finished wave if(!m_numAsteroids) {
66
AI Game Engine Programming
m_waveNumber++; WaveOver(); }
LISTING 3.6.7
GameSession’s update loop, section 7: game over.
//check for finished game, and reset if(!m_numLives) GameOver();
TH E
Control
C LASS
To give commands to a ship, the system makes use of the Control class. Control’s base class contains the barebones structure, including Update(), Init(), and an m_ship pointer to the ship to be controlled. This class is the parent to both the human control system (HumanControl) and to the AI (AIControl). The HumanControl class is a bit different in that it doesn’t use its update function. Rather, it’s just the depository for the global callbacks that the program passes to GLUT to perform keyboard checks and notifications. If the game were more complex, we would implement a state-based control scheme (or some other way of separating the system functionality) and use the full functionality of the Control class. Later in the book, when we implement the various AI methodologies, we’ll start by creating a specific AIControl class to house the particulars of each AI method.
T H E AI S YSTEM H OOKS The
class checks to see if the AI system is turned on, and if so, the Update() function for the AIControl class is called. This update function is stubbed out in AIControl.cpp, meaning that the AI system does nothing here. Again, this is just the framework for the future implementations of each AI technique. We will later make child classes of this barebones AIControl class that will run specific code for each technique. The only other things of note in the base class are some debug data fields, which were used in developing the demo programs in this book and were left in to serve as a good start for any additional debugging information you might add. It’s good practice to include debugging hooks in your system right from the start, so that you don’t have to spend precious time during development trying to patch debugging output into your AI engine. GameSession
Chapter 3
FIGURE 3.2
AIsteroids: Our AI Test Bed
67
AIsteroids screenshot.
The two update functions, Update() and UpdatePerceptions(), deal with systemlevel data objects. These functions are separated to emphasize the separation of game objects from game perceptions. UpdatePerceptions handles the refreshing of all the game variables that the objects in your game will use to make decisions (all of these inputs to the system could be called perceptions), whereas the regular update function handles all the functions for the game objects themselves. Figure 3.2 shows a screenshot of the test bed running the finite state machines (FSM) AI system from Chapter 15.
68
AI Game Engine Programming
G AM E M AI N L OOP AIsteroids.cpp is the main game file for the project. It initializes GLUT and sets up
the callback pointers for updating the game, drawing the game, and handling all the input from Windows or the user (the global functions that handle the keyboard are in the HumanControl.cpp file).
S U M MARY This chapter described the primary test-bed application the book will use for implementing each AI technique in Parts III and IV. The overall class structure was discussed, as were the notable sections of the base class code. GameObj is the basic game object class. It takes care of
physics and handles object drawing and updating. The current objects in the game include asteroids, bullets, explosions, powerups, ships, and a debugging target object. GameSession is the singular game class. It takes care of all the variables and structures needed to run a game. It has the primary update and draw functions for the game. It spawns all additional game elements and manages object-toobject collision checking. Aisteroids.cpp is the main loop file, and it includes all the initialization of GLUT and all the GLUT callbacks for running the game. The Control class handles the logic for a ship object. This logic can be in the form of an AI technique or keyboard functionality for a human player. The AIControl class will be the branching point for our AI to hook into the system. By overriding the class with a specific AI method class (for example, FSMAIControl, discussed in Chapter 15), we can use this game application with CPU-controlled opponents. The keyboard control will still be enabled, but this is to facilitate the application as a test bed (we still want to be able to send keyboard events to the game when the AI system is running).
4
Role-Playing Games (RPGs)
In This Chapter Common AI Elements Useful AI Techniques Examples Exceptions Specific Game Elements That Need Improvement Grammar Machines Quest Generators Better Party Member AI Better Enemies Fully-Realized Towns Summary
A
s personal computers became more mainstream, one of the first new game genres to appear was the role-playing game, or RPG. RPGs became popular because they were a radical departure from the fast, twitch-based action games that had dominated the arcades. They allowed for more thoughtful strategy, and were able to give the player much more interesting input opportunities by using the keyboard found on personal computers rather then an arcade-style controller and a button or two. They also enveloped the player in a rich storyline, and gave the player a high degree of identification with the hero since the game took so long to complete. Arcade-style games, which in those days were mostly shooters or platformers, were typically designed to be over quickly (for profit reasons, but also because of limited complexity) so a game that takes a long investment in time and effort was a complete departure from the arcade norm. The RPG allowed for characters that grew and morphed over time, thus permitting players to really get to know, and affect the development of the main characters. The earliest RPGs were either text based (like Adventure or Wumpus) or had art crafted out of ASCII characters like Rogue and NetHack (see Listing 4.1 for a code snippet from NetHack—the listed function is a generic method for 69
70
AI Game Engine Programming
determining and defining missile attacks from an AI-controlled enemy). The gameplay tended to be mostly exploratory (leading many of these games to be called “dungeon crawlers”), with random monster encounters and turn-based combat systems. Typically, the dungeon itself is randomly generated, and as such you could continue to advance and discover deeper dungeons pretty much forever. The next wave of RPGs finally came out with graphical art, but the images were static, like The Bard’s Tale and Wizardry. Typically, these games were just graphically upgraded versions of early RPGs, but some started to craft specific locations and included backstory and secondary characters. They also typically had an “ending,” in which players actually defeated the final bad guy and saved the world (or something along those lines). Modern RPGs are generally fully open, sprawling worlds filled with other characters, monsters, places to explore, and tons of interaction with both people and objects in the game. Today, both console and computer RPGs have blurred the platform line, with games like Diablo being a computer game with simple, console-like action-oriented gameplay; and the new online persistent RPGs on the consoles are all but identical to their personal computer brothers. LISTING 4.1
Code snippet from the Open Source ASCII RPG, NetHack.
Distributed under the NetHack GPL. /* monster attempts ranged weapon attack against player */ void thrwmu(mtmp) struct monst *mtmp; { struct obj *otmp, *mwep; xchar x, y; schar skill; int multishot; const char *onm; /* Rearranged beginning so monsters can use polearms not in a line */ if (mtmp->weapon_check == NEED_WEAPON || !MON_WEP(mtmp)) { mtmp->weapon_check = NEED_RANGED_WEAPON; /* mon_wield_item resets weapon_check as appropriate */ if(mon_wield_item(mtmp) != 0) return; } /* Pick a weapon */ otmp = select_rwep(mtmp);
Chapter 4
Role-Playing Games (RPGs)
if (!otmp) return; if (is_pole(otmp)) { int dam, hitv; if (dist2(mtmp->mx, mtmp->my, mtmp->mux, mtmp->muy) > POLE_LIM || !couldsee(mtmp->mx, mtmp->my)) return; /* Out of range, or intervening wall */ if (canseemon(mtmp)) { onm = xname(otmp); pline(“%s thrusts %s.”, Monnam(mtmp), obj_is_pname(otmp) ? the(onm) : an(onm)); } dam = dmgval(otmp, &youmonst); hitv = 3 - distmin(u.ux,u.uy, mtmp->mx,mtmp->my); if (hitv < -4) hitv = -4; if (bigmonst(youmonst.data)) hitv++; hitv += 8 + otmp->spe; if (dam < 1) dam = 1; (void) thitu(hitv, dam, otmp, (char *)0); stop_occupation(); return; } x = mtmp->mx; y = mtmp->my; /* If you are coming toward the monster, the monster * should try to soften you up with missiles. If you are * going away, you are probably hurt or running. Give * chase, but if you are getting too far away, throw. */ if (!lined_up(mtmp) || (URETREATING(x,y) && rn2(BOLT_LIM - distmin(x,y,mtmp->mux,mtmp->muy)))) return; skill = objects[otmp->otyp].oc_skill; mwep = MON_WEP(mtmp); /* wielded weapon */ /* Multishot calculations */ multishot = 1; if ((ammo_and_launcher(otmp, mwep) || skill == P_DAGGER ||
71
72
AI Game Engine Programming
skill == -P_DART || skill == -P_SHURIKEN) && !mtmp->mconf) { /* Assumes lords are skilled, princes are expert */ if (is_prince(mtmp->data)) multishot += 2; else if (is_lord(mtmp->data)) multishot++; switch (monsndx(mtmp->data)) { case PM_RANGER: multishot++; break; case PM_ROGUE: if (skill == P_DAGGER) multishot++; break; case PM_NINJA: case PM_SAMURAI: if (otmp->otyp == YA && mwep && mwep->otyp == YUMI) multishot++; break; default: break; } /* racial bonus */ if ((is_elf(mtmp->data) && otmp->otyp == ELVEN_ARROW && mwep && mwep->otyp == ELVEN_BOW) || (is_orc(mtmp->data) && otmp->otyp == ORCISH_ARROW && mwep && mwep->otyp == ORCISH_BOW)) multishot++; if ((long)multishot > otmp->quan) multishot = (int)otmp->quan; if (multishot < 1) multishot = 1; else multishot = rnd(multishot); } if (canseemon(mtmp)) { char onmbuf[BUFSZ]; if (multishot > 1) { /* “N arrows”; multishot > 1 implies otmp->quan > 1, so xname()’s result will already be pluralized */ Sprintf(onmbuf, “%d %s”, multishot, xname(otmp)); onm = onmbuf; } else {
Chapter 4
Role-Playing Games (RPGs)
73
/* “an arrow” */ onm = singular(otmp, xname); onm = obj_is_pname(otmp) ? the(onm) : an(onm); } m_shot.s = ammo_and_launcher(otmp,mwep) ? TRUE : FALSE; pline(“%s %s %s!”, Monnam(mtmp), m_shot.s ? “shoots” : “throws”, onm); m_shot.o = otmp->otyp; } else { m_shot.o = STRANGE_OBJECT; /* don’t give multishot feedback */ } m_shot.n = multishot; for (m_shot.i = 1; m_shot.i mx, mtmp->my, sgn(tbx), sgn(tby), distmin(mtmp->mx, mtmp->my, mtmp->mux, mtmp->muy), otmp); m_shot.n = m_shot.i = 0; m_shot.o = STRANGE_OBJECT; m_shot.s = FALSE; nomul(0); }
RPGs, in general, follow a simple formula: the player starts with nothing, performs tasks for treasure and money (mostly killing monsters and going on quests), trains his or her skills, and eventually builds his or her character into a powerhouse figure that can then right the ultimate wrongs of the land. Some games include a whole party of adventurers, so the player is in effect building up a whole team of characters. Whatever the technical details, the name of the game is immersion: getting the player to identify with the main character, and caring enough to invest the vast amount of time necessary to build the character up and eventually finish the game. The enemy-filled, constantly hostile world of most RPGs might seem odd, but not to teenagers. In a way, young people somewhat relate to a character who is solitary in the world, against everyone, universally misunderstood and attacked. It’s what gives RPGs their appeal to many of the youth who play them. The inclusion of a small band of party members ties nicely into the clique-ish world of most teens, in which they form a small group of intense friends, and extend the “me against the world” fight to include these people as well. This argument is not to say that older
74
AI Game Engine Programming
or younger people cannot enjoy RPGs but, rather, speaks to a theoretical reason why some people find these types of games popular. RPGs are fairly AI-intensive, because they are usually expansive games, with varying types of gameplay and many hours of gaming experiences per title. As such, the apparent intelligence of the varying game elements has to be higher than most, or at least more heavily scripted. The sheer number of hours people invest in an RPG will make any behavioral repetition much more obvious, as well as making small annoyances (like pathfinding hangups) in AI behavior appear larger. On home computers, users demand a minimum of 40 or so hours of gameplay from an RPG. Consoles are a bit lower, usually 20 to 40. This formula seems to be somewhat fixed in the minds of game players (a strange mix of the approximate amount of time a game can keep a player’s interest, and marketing education about how much gameplay a buyer can expect for their money), but there are exceptions, like Baldur’s Gate for the PC having 100+ hours of play. Because of these hefty gameplay quantity demands, your game needs a variety of gameplay types (such as puzzles, combat, crafting, different types of travel, etc.) or your primary combat system had better be very fun and addicting. The Diablo games fall into the latter category. The gameplay is very repetitive, but also very addictive. Some have theorized that the game somehow awakens our inherent “hunter-gatherer” lineage, and we just can’t stop clicking the mouse.
C OM MON AI E LEM ENTS RPGs contain a number of commonly AI-controlled elements. These include both antagonistic characters (enemies, bosses, and non-player characters), as well as good or neutral characters (shopkeepers, and other party members). Since RPGs’ main gameplay revolve in many ways around character interaction, either combat or otherwise, each of these elements can be quite complex. ENEMIES The majority of the population of most RPG worlds is enemies. An almost endless supply of enemies is needed to provide the player with something to dispatch and get experience points, money, and powerful new items. RPGs in the past used almost exclusively what can be described as statistical AI, in that the attributes (strength, size, hit points, etc.) of the monsters determined everything about them: the attacks they use, the way they fight, how tough they are in general, what treasure they drop when they die, and so on. Today’s games go a bit further and have enemies that are more hand-tailored. These modern enemies also use more complex behavior patterns, including running away, healing themselves, fighting in groups by surrounding a player and using complementary attack methods, and so forth.
Chapter 4
Role-Playing Games (RPGs)
75
Since enemies in RPGs usually come in such numbers during a game, the AI is specifically set up to be more A and not so much I. Turn-based RPGs of the past (Bard’s Tale, Phantasy Star, Chrono Trigger), the so-called real-time combat RPG (The Legend of Zelda, the later Ultima™ games, Diablo, Terranigma), and the fusion variants brought about recently (Baldur’s Gate or Icewind Dale, which are real-time games that can be paused and, thus, made to act turn-based) all pretty much boil down the enemies to be combination containers (of wealth and experience points) and obstacles (by being “walls” of a certain number of hit points that the hero must destroy to get by). Very few games go beyond this kind of simple-style enemy to create anything with personality, ingenuity, or shifting strategy. This is done by design, of course. When a player who has spent 60 or more hours playing your game goes into a room and sees a monster approach that looks like an enemy character he has seen before, he should feel one of three ways: 1. I can beat this guy. I know what attacks he uses, approximately how many hit points he has, and that I have a weapon that affects this enemy. 2. I think I can defeat this guy. He looks a lot like an enemy I’ve already fought, but is a different color, or a special name, that makes him unusual and possibly more advanced. In effect, I believe he belongs to an enemy “type,” but I’m not sure about his toughness. 3. I cannot beat this guy. He’s too tough, or I don’t have the weapon necessary to get through his armor. I know because I’ve tried before, and failed, or somebody in the game has warned me. This is another way of immersing the player in the game and making him feel a part of the world, in that he “knows” the enemies by experience. If a lowly Orc suddenly pulls out a grenade (after futilely running up and using a rusty dagger in the last fifty encounters) and nukes the player, the player is going to feel somewhat cheated. However, this basic guideline can be occasionally sidestepped, if the player is allowed to save the game whenever he wants, or the game actually autosaves quite frequently. In this way, a highly unusual encounter with a special enemy might kill the player, but he won’t have lost much playing time if he has a save. Yes, this leads to more “save, then round the corner, kill one monster, then save” behavior from the player, but it also gives you more freedom to put elements of surprise into your random encounters. BOSSES Bosses are larger, more complex game characters, either humanoid or creature, found at the end of each level (or game world, or subsection) after defeating a horde of lesser enemies. They are usually equivalent to monster leaders, the Kings of the Monsters. These are specific, usually unique enemies that can break all the
76
AI Game Engine Programming
previous rules. Players expect to be surprised by the power, skills, weapons, and so forth used by these characters. Bosses are even thought of as treats in the RPG world, and a good boss creature can make up for a lot of game shortcomings, either in the areas of average gameplay, or merely a period of tedious leveling-up necessary to continue on in the game world. As such, Boss monsters are usually heavily scripted, with specialty attacks and behaviors that only they perform. Boss monsters also usually communicate with the player, in the form of plot advancing information, or pure invectives. So the AI for these creatures needs to include use of the dialogue system for the game. The Final Fantasy series’ Boss monsters are a wonder of specialized coding, with encounters that might take hours of real time, complete with various stages of battle and conversation. These encounters are strictly paced by the developers, with planned volleys of the player’s advantage, followed by the enemy’s advantage, scripted interruptions with other enemies or special game events, and whatever else the designers can think up. Another tried-and-true Boss tactic involves the “can’t be killed . . . yet Boss.” This involves a Boss that the players can bring to near death, only to miraculously escape, shouting “I’ll be back!” and promising to be bigger and badder next time. Although somewhat trite, this is the gaming equivalent of simple character development, with the Bad Guy developing over the course of the game as much as you are. Some games use the designation of “sub-boss” to further stratify the monsters in the game, although they are usually just very tough versions of regular creatures, like the “unique” creatures that heavily populate the Diablo series. But even Diablo, which many considered an “RPG-lite” click fest, also uses much more specialized Boss creatures that employ additional dialogue, animations, spell and weapon effects, and special powers. The Boss designation also includes the final creature (wizard/god/evil doer) that the player will need to defeat to win the game, also called the End Boss. This character is very important indeed, and many a good game has received bad marks for having a disappointing or anticlimatic End Boss. The player should have to perform every trick he or she has learned during the game, and stretch the acquired skills to the limit to destroy this character, and the End Boss itself should be able to do things that the player has never seen before in the game. The End Boss should be tough from a statistics point of view, of course (with lots of hit points and immunities to weapons or spells), but the End Boss should also be capable of behaviors beyond the typical. That’s why the character is the End Boss in the first place. NONPLAYER CHARACTERS (NPCS) NPCs are defined as anybody in the game that is not a human player. Usually, however, the term NPC refers to characters in the game that the player can interact with in ways other than combat. NPCs are the characters who inhabit the towns,
Chapter 4
Role-Playing Games (RPGs)
77
the half-dead soldiers on the trail who give the player valuable clues to the danger ahead, and the occasional old man who offers the player’s character money to rescue the old man’s daughter. Typically, NPCs can be grouped into one of two types: 1. One-shot characters (meaning they have something for the player once during the course of the game, but afterwards will only greet the player with gratitude), like the people that are involved in a side quest. 2. Information-dumping characters, that a player can keep conversing with at different points during the game. These characters might know something additional about whatever is currently “new” in the game flow. NPCs are generally not very intelligent; they usually don’t have to be. Anything they add beyond information or story advancement is just flavor for the game. However, they also represent one of the largest sources of information the player has about the flow of the storyline. NPCs can also serve as in-game help that can bring a stuck or lost player back into alignment with the objectives of the game. As such, many games have experimented with differing ways of doing NPC conversation. Some games give the player keywords that represent questions the player is posing to the NPC (as in the Ultima games), others give the player a choice between a number of complete sentences that represent the different attitudes the player can take with the NPC. The evolution of these systems will continue as grammar systems become better, faster, and more generally accepted. Some day, players may converse directly with a general AI NPC who can give wide-ranging responses by indexing the character’s knowledge base and forming sentences on the fly. Until then, we do what we can. SHOPKEEPERS Shopkeepers are special NPCs that do business with the player; buying and selling gear, teaching the player new skills, and so on. Shopkeepers usually aren’t much smarter than regular NPCs, but they get special mention because they usually have extended interfaces, which, in turn, require special code so they seem intelligent and usable. Sometimes shopkeepers might be part of a scripted quest or game sequence, in that they only become shopkeepers later in the game, or after a task has been completed. A shopkeeper thus might have a notion about whether or not he likes the player, which would then affect his attitude, and prices, when dealing with that player. Some games have a general charisma attribute for characters within the game (or some derivative; the meaning is “How well other people perceive you naturally,” considering first impressions, the player’s looks, and the player’s speaking ability), as well as some form of a reputation system that represents a sort of
78
AI Game Engine Programming
“rating” depicting the amount of good versus evil deeds a player has, as well as flags representing specific things the player has done that NPCs can notice and respond to. There is a natural human tendency to give inanimate things human qualities, and this tendency is tied directly to the amount of time we have to spend dealing with something. There is also a correlation with how much that object has cost us. Very few people would attribute human qualities to their shoes, but many people name their cars, know its gender, know how to identify if it’s having a bad day, and will even plead with it if it isn’t running well. Both objects (shoes and cars) do roughly the same thing: help protect our bodies from the rigors of traveling, so why the disparity? The answer is obvious. With no moving parts, and a simple procedure that we learned when we were three years old, we put on our shoes in the morning, and forget about them. Buying a new pair doesn’t require a credit check. Our cars are exactly the opposite. The same is true with Shopkeeper AI. If you have a one-shot NPC within your game, you can pretty much do whatever you want with his behavior, dialogue, and interactions with the player. The player isn’t expecting much and will take most things at face value. But with a shopkeeper, especially one that the player will have to keep coming back to for a large part of the game, every nuance, reply, and animation frame will be carefully watched, memorized, and humanized. Do you have a bartering system (which in reality takes the player’s charisma score, adds in a random factor, and determines a small discount that a player can bargain for) within your game? Over time, a human player will start to imagine intricate rules involving the order of the items he does business with, the time of day, the shopkeeper’s moods, and a host of other factors that may not actually exist. It is precisely this humanizing tendency that allows game makers to get away with so little detail in their games because the human player will fill in all the complexity where there is none. The lesson is that shopkeepers do more than provide your players with an economy interface; they also give richness to the world and provide the player with other facets of the game to consider. PARTY MEMBERS Members of a player’s adventuring party are also special NPCs, except that they travel with the player, and are either completely player-controlled (in turn-based RPGs, or in later games that allow players to pause the action so they have time to give detailed commands) or have AI code associated with them. These AI-based party members need careful coding because stupid party members will drive potential players away quickly. Many of the real-time combat games use simple party AI, so that the player can predict (and rely on) what each party member is going to do during a fight.
Chapter 4
Role-Playing Games (RPGs)
79
A large factor to remember with real-time combat RPGs is pathfinding. In turnbased combat systems, a player’s party members are just attached to the player, or follow the player around directly (like the Final Fantasy games, or even the early Bard’s Tale), but in real-time games, they actually have to pathfind to follow the player. In a semi-enclosed space (such as an underground dungeon, for instance) with no room to manuever, one or more party members might go running off to take some extra-long scenic route that the pathfinder managed to find. Blind pathing can be supremely frustrating to the player, as it can cause these confused party members to run through packs of monsters in other parts of the map, even bringing unfriendlies running into the room behind the “helpful” friends to join in the fight. Here’s a place where an intelligent party member might say, “Hmm, I can’t get around that guy directly to use my sword. But I do have a bow and arrow in my pack, and I’m decent at archery, maybe I’ll try a ranged attack.” A simpler solution might be “Can’t get around directly, so I can’t attack. Maybe I should tap my weaker buddy on the shoulder, who’s being mauled by a creature, and replace him on the front line.” These kinds of “smarts” (rather than ignorant pathfinding and script following) are the difference between useful party members, and ineffective accomplices that the player needs to babysit. If the characters a player adventures with frequently screw up, do the right thing in the wrong way, or are constantly getting themselves (or worse, the player) killed, the player is not going to want to continue playing with them. Baldur’s Gate (and its descendents) even allows users to edit the scripts that govern the party members’ AI, so that users have even more control over this crucial game element. Some users in the community have created very advanced AI scripts and put them up on fan websites for all to use. See the section on “Scripting” that follows. Adding a scripting system to edit a party AI is a careful balance. If you make it too easy to use and don’t provide enough complexity and functionality, it’s worthless. But if the system is too powerful, then it can overwhelm the casual gamer, and again becomes worthless to a large part of your audience. A technique that many sports games use to allow players to adjust the AI in their games is to expose specific tendencies of behavior as “sliders” (scroll bars that tie to a variable) that the player can set. For sports games, this means that the players could set up a basketball game where the AI never tries to steal the ball, doesn’t guard as well, and is better at three point shots all by setting sliders to certain points. A similar system could be used to give more casual gamers access to AI editing without having to write script code. Even some of the more complex uses of a scripting system, like setting up when specific spells would be cast by an AI mage character, could be represented as sliders that are specific to that spell. This does translate to many potential sliders, but again, it’s definitely more accessible to a larger audience than script files are.
80
AI Game Engine Programming
U SEFU L AI T ECH N IQU ES Along with the many types of AI-controlled entities within RPGs come the many AI techniques that are useful when constructing RPG-style games. These include scripting (because of the heavy story-based element in the genre), finite-state machines (for their general usefulness), and messaging (since so many RPG tasks are flag-based events). SCRIPTING Most RPGs are heavily scripted because these games tend to follow a very specific storyline. Scripts are used for a variety of game constructs, including dialogue, game event flags, specific enemy or NPC behavior, environmental interaction, and many others. Scripting is used because most RPGs are linear, or at most branching linear, and so work well with the scripted interface. You can design parts of the game to play out almost exactly as specified, with choke points and flags embedded into the scripts so that the players are forced to follow the game flow from point A to point B, even if they first wandered over to points C, D, E, and F in the meantime. Plus, the conversational nature of many RPGs also lends itself to this technique. You can think of scripts as a data-based way of hardcoding the assorted events that come up during the overall story. See Listing 4.2 for an example of a short script from the Black Isle game, Baldur’s Gate. Here you can see a very basic attack script, which determines whether to attack an enemy based on the enemy’s distance to the character, and then also determines whether to use a ranged or melee weapon. It does perception checking (the range calculations) as well as perception scheduling (by saying how often the script should be run). It also has some randomness, in that the determination for ranged or close combat is determined by a random number (33 percent of the time, it chooses melee, the rest of the time, it chooses ranged). LISTING 4.2
Sample Warrior AI user-defined script from Baldur’s Gate.
IF // If my nearest enemy is not within 3 !Range(NearestEnemyOf(Myself),3) // and is within 8 Range(NearestEnemyOf(Myself),8)
Chapter 4
Role-Playing Games (RPGs)
81
THEN // 1/3 of the time RESPONSE #40 // Equip my best melee weapon EquipMostDamagingMelee() // and attack my nearest enemy, checking every 60 ticks // to make sure he is still the nearest AttackReevalutate(NearestEnemyOf(Myself),60) // 2/3 of the time RESPONSE #80 // Equip a ranged weapon EquipRanged() // and attack my nearest enemy, checking every 30 ticks // to make sure he is still the nearest AttackReevalutate(NearestEnemyOf(Myself),30) END
FINITE-STATE MACHINES (FSMS) The staple of game development, FSMs are useful in RPGs, just as they are useful in any game—they allow the developer to split the game into explicit states. In each state, specific characters can perform different behaviors, and manage these with discrete code blocks. Thus, you could have an NPC who first meets a player and gives the player a quest (for example, state before meeting the player is state_intro, changing to state_quest after giving the player information about a quest). Then, after the player finishes the quest, the NPC becomes a shopkeeper and sells the player things at a discount as a reward (state_shopkeep). Note how earlier the script from Baldur’s Gate is only applicable if an enemy is close by. Any other game state would require additional scripting, or it could fall back on some default script, which would most likely do some idle behavior. By having a state-based system, but scripting the entry and exit to those states, many RPGs hide the “hard” state transitions (meaning, it’s difficult to notice the difference in game state, because the transition was a seamless scene that moves us from one state to another). Other games do not, like Nintendo’s classic The Legend of Zelda, in which the game was split into two globally distinct states: the
82
AI Game Engine Programming
overworld and the dungeons of the underworld. The game’s music would change, the character itself would look a little different (because of the “lighting”), and if the player died, the game acted a little differently (by allowing the player to continue in the same dungeon, if the player wanted), all because of this basic state change. MESSAGING With so many elements in an RPG world, the need to communicate between entities is high, so a messaging system is useful in this genre. Information can be passed between party members quickly and easily, facilitating group combat or dialogue. Door keys (or whatever your game is using) can message locks to open, and outof-place wall stones could cause entire sequences of events to occur when pushed. Because of the sheer number of uses within an RPG, messaging systems can really give you a lot of flexibility and ease of implementation. One thing that should be watched for, because it breaks the illusion of reality, is for instant messaging being used by the game. If a party kills some creature on the far side of the world, they then teleport back to town (because of a special magic item), and everyone back in town already knows about the battle, that the party won, and that the player is the hero. The townspeople obviously got the message and have switched on the game state-specific behavior for it. Wouldn’t a better reaction be that the first character the player talks with doesn’t know (unless the player took the long way home, and gave everybody time to find out on their own), and the player has to tell him? Then, that character runs into the streets and spreads the good news? Build messaging into the game, and use it to set game flags that change game behavior, but don’t overuse it, or abuse the system by allowing game states to change instantaneously in ways that couldn’t possibly have occurred. If the mayor of the town has his own wizard who saw everything happen through his crystal ball, that’s a different story, but it should be portrayed as such.
E XAM PLES Classic games like Wizardy, the early Ultimas, Phantasy Star, Might and Magic, and the Bard’s Tale had mostly statistic-based enemies, with little special case code. They all used a simple “key and lock” puzzle system (using some sort of key or jewel or Skull of Muldark or what have you) that had to be found and used in the right place at the right time. This was most likely coded as a system of flags that the elements of the game would access to determine the particulars of the game progression.
Chapter 4
Role-Playing Games (RPGs)
83
Usually, the gameplay diagram for these games would include a town state, a “travel” state, and a combat state. The differences between these games were pretty much the overall game’s graphic quality, how the player conversed with NPCs, and the combat interface. Strangely enough, some massive multiplayer online RPGs (MMORPGs) are using this exact game style to create huge worlds in which people can play. The only real gameplay addition has, of course, been the vast number of people who are also playing the game at the same time, leading to more human-to-human interactions. Modern RPGs such as the later Final Fantasy games, Neverwinter Nights, Baldur’s Gate, and System Shock are much more scripted affairs, with some of the attribute-based enemies of these games, but with a large portion of hand-tailored encounters and environments along the way to provide the player with a more crafted gameplay experience. Only recently have the online RPGs tried this tactic (such as the Final Fantasy online game) because of the enormous amount of work associated with creating custom quests and encounters for a world that may be inhabited by thousands of people at all hours of the day. But, the demand is there for higher quality content, so game companies will provide it.
E XCEPTIONS Bethesda Softworks makes the excellent Elder Scrolls series of RPGs (see Figure 4.1 for a screenshot from Elder Scrolls: Arena, the first in the series), which it touts as being open ended, meaning that you can solve the game and perform the various quests in a nonlinear fashion. The games do deliver this promise to a much larger degree than any other RPG. A large amount of freedom is granted through the lack of time limits on the quests you receive, so you can collect quests, and do them in any order. The quests are still mostly scripted (a number of quest types are used as templates, with different characters and locations) and usually simple in nature to facilitate this (although the newer games in the series have vastly improved the variety and complexity of quests). The main quest is still linear, facilitated by scripted encounters with unique NPCs, but it allows the player to take time completing many other side quests as well. Neverwinter Nights is another recent game that was supposed to change everything. By allowing players to control a character in the game and actually be in the Dungeon Master role (as borrowed from the pen and paper world), the game was supposed to be Dungeons and Dragons (D&D) fully brought to the computer. To some degree it succeeded, but in many ways, all it really showed was that the average person is pretty bad at coming up with good game content. Patches have fixed some of the problems, and the title is nothing if not created
84
AI Game Engine Programming
FIGURE 4.1
Elder Scrolls: Arena screenshot. © 1993. Bethesda Softworks LLC, a ZeniMax Media company.
for longevity, so this will surely change, and good modules will make their appearance on the Net.
S PECI FIC G AM E E LEM ENTS T HAT N EED I M PROVEM ENT Any established genre can use some improvements pushing forward through the sea of established storylines and gameplay mechanics. RPGs have their share of issues when it comes to perennial issues. Some specific issues that could use some fresh insight include making role playing more then just endless combat, grammar machines, quest generators, better enemy and party member AI, and fully realized towns. A game with all these elements would truly be an epic adventure, with something new behind every door. ROLE PLAYING DOES NOT EQUAL COMBAT The definition of “role playing” is typically “acting like someone else in an escapist fantasy.” There is a vast array of possible behaviors that you could
Chapter 4
Role-Playing Games (RPGs)
85
engage in. Acting means a lot of things; everything from behaving like another person to using their manner of speaking. It can also mean subtle (yet very important) distinctions like taking on the other identity’s core beliefs (maybe the character being role played is whole-heartedly evil, whereas the person doing the role playing might be a Girl Scout), or holding grudges against others that have done the character wrong within the role playing universe. All of these things give role playing a rich, usually dramatic, and freeing sense of open-endedness that make it an activity with nearly limitless potential. However, in most RPGs, right from the start, most of the time spent role-playing is actually time spent killing, mainly because of some seminal influences: two really old pen-and-paper RPGs (Dungeons and Dragons and, earlier than that, Chainmail) centered their gameplay systems on fighting against fantastical creatures. The rulebooks were filled with combat statistics, magical spell lists, and weapon descriptions. There really wasn’t a single chapter anywhere in the rulebooks about creating realistic stories, locales, and people to inhabit them. Novel combat scenarios are much easier to model and invent than an actual story with plot, characters, drama, and so on. Consider this: nonkiller classes in most RPGs are only useful for the small set of contrived circumstances that the designers have included to justify these classes. Thieves are one of the more classic types with problems, even in paper D&D. If you allow thieves to really do what they do, they’re too powerful because they don’t have to follow the rules like everybody else does (just like in real life; the Mafia is more powerful than a police officer). So games hobble them. Thieves can disarm traps, and pickpocket. But, if they disarm incorrectly, they generally die, and if they pickpocket unsuccessfully, they are generally always caught. Fun is nowhere to be seen. Think of the myriad wonderful professions that players can choose from in the average Massive Multiplayer Online Role Playing Game (MMORPG). In Ultima Online, a player could be a baker. Unfortunately, the player could spend months playing the game, become a Master Baker, a true King of baking, and then be almost instantly killed the second the player stepped outside of town by an extremely low-level fighter with a rusty spoon. In today’s MMORPGs, people tend to be tanks (meaning fighter types with huge amounts of health and armor; human walls that absorb damage), or casters (someone who stands behind a tank and can either damage creatures with spells, or heal the tank so he can continue to bash and be bashed). Specialty classes have somewhat dissolved into these two basic groups. Huge areas of compelling potential gameplay are hidden within RPG worlds, but that involves thinking about ways of creating content that doesn’t involve killing and that takes advantage of nonlethal skills in a meaningful way, not just to
86
AI Game Engine Programming
affect your prices for new swords. The task involved here is not an easy one, and writing AIs to support these new quest types will also be hard. But our RPGs will definitely be better for it.
G RAM MAR M ACH I N ES Grammar machines (GMs) make for better conversations. A lot of the interaction with other characters in RPGs is through conversation, usually in the form of choosing from a list of responses, and then reading the character’s scripted response. Ultima used a keyword system, so a player would say “thieves,” and the other character would tell the player about the local thieves, mentioning toward the end that someone named Blue is their boss. A new keyword, “Blue,” would show up in the player’s list, and the player could ask for additional information in this way. Old text-adventure games actually had rudimentary grammar engines that could handle semicomplex sentences. A fully functional grammar system used to converse with NPCs in a modern RPG has yet been implemented. This might change because of the advent of better and better speech recognition software. Eventually, RPGs might use this system instead of a slow, clumsy text interface to allow the user to really ask questions. Our job as AI programmers will then be to fully flesh out a grammar engine, and fill a text database with enough knowledge to dutifully answer those questions.
Q U EST G EN ERATORS The real quest (for game developers) is quest generators that don’t churn out derivative or repetitive content. Sort of the Holy Grail of large-scale RPGs, an advanced quest generator could make up new quests that the player could tackle without having to be explicitly set up and scripted by a game designer. Games like World of Warcraft, which are played around the clock online, could benefit greatly from a system that could come up with novel challenges for any number of party members, and of any skill level. As of now, only a few games have “random” quests, and they usually fall into the “Fed Ex” quest realm. That is, go somewhere, get something, and bring it back to me. An improvement might be a system set up ad-lib style; using templates to create custom quests (or strings of connected quests) that included multiple characters, locations, rewards, and different actions to be done. These templates, connected to a database of potential ad-lib names and locations, as well as some way of scoring quests for skill level and such, could make RPG games truly unique experiences (at least for side quest interactions). The game could even keep track of which quests
Chapter 4
Role-Playing Games (RPGs)
87
the player liked (by keeping records of quests turned down or never finished versus successful and repeated types) and adjust the kinds of quests given to a specific player. Also, by making the ad-lib machine extensible, you could add content continually (through mods, patches, or expansion packs to individual products), and the ad-lib system would just incorporate it into the mix.
B ETTER P ARTY M EM BER AI Party AI that can be extended and modified, both implicitly and explicitly, is another big area in need of concern. Early real-time RPGs (like Ultima 7, pictured in Figure 4.2) had simple party AI that mainly just followed a player around the map and tried to help during combat. Baldur’s Gate has contributed heavily to real-time RPG party AI becoming a greater priority. The level of adjustment that can be accomplished within their simple script form is pretty
FIGURE 4.2 Ultima™ 7 screenshot.
88
AI Game Engine Programming
astounding, but it could be better. The character could keep track of the sorts of actions the player has the character do, and could incorporate them into automatic behavior. Think of this as simple learning by imitation. Does the player always retreat from a certain character (like a weak mage, perhaps)? After two or three times of doing this manually, the mage could retreat automatically. Does the player drink a health potion whenever the player gets to one-third health, but only after the battle is over or after running away from immediate danger? The characters should perceive this and parrot these simple behaviors. Imagine how the player’s game experience is going to evolve and change as the game progresses, instead of micromanaging very tedious actions again and again during hours of gameplay. It might even be possible to show the player this learned behavior list and allow the player to edit it by deleting things, or changing the priorities of these behaviors.
B ETTER E N EM I ES Instead of just mobs (groups of monsters that turn toward the player, advance until in range, and attack), enemies should work together from multiple fronts, using plans and the environment to their advantage. They should set ambushes, make traps, find your weakness and try to exploit it, and do everything else that a human player would do. This is, of course, a universal problem. As stated earlier, most RPG enemies are supposed to be relatively mindless, so the player can quickly kill enough of them to rise in rank at a rate that feels good. The problem is that this need creates very monotonous battles, one after another, with exceedingly stupid monsters. One popular answer to this is sub-bosses or mildly scripted and slightly more strenuous enemies that will make the player feel like the whole of creation is not filled with senseless drones, all attacking in the same manner as the last. Dungeon Siege (Figure 4.3) and the Diablo games used this technique relatively successfully, as areas of the map would always have a native type of creature, and some larger, stronger version of that creature type would be leading them. This unique creature would not be tied to any quest (although some were) but, rather provided a bit of variety to the constant stream of cannon fodder. These sub-bosses could be developed as more than just tougher versions of regular monsters, to a level where they are truly small boss monsters that rule that part of the game world. Sub-bosses could be little generals, giving sophisticated orders to their armies, and doing things that a leader would do. By killing this creature, the player would weaken the attack of all the creatures the sub-boss led, until another leader is promoted.
Chapter 4
Role-Playing Games (RPGs)
89
FIGURE 4.3 Dungeon Siege screenshot. © 2002 Gas Powered Games Corp. All rights reserved. Gas Powered Games and Dungeon Siege are the exclusive trademarks of Gas Powered Games Corp. Reprinted with permission.
An aside about Dungeon Siege, however, is that the game did too many things automatically for the player. At times, the game seemed to be playing itself, with hardly any input from the user. If this automatic behavior could have been modified or tweaked (maybe even just a slider so that the player could set the level of automation he liked), the game might have felt better to a larger audience.
F U LLY -R EALIZED T OWNS The towns that constitute the trade and information centers of these games are usually pretty dull, filled with people either standing around, or moving between two locations. These townsfolk usually say the same thing over and over and don’t appear to have a “life” at all. Obviously, this is not reality. By using simple rules, and a data-driven approach to town creation, even large villages could be populated
90
AI Game Engine Programming
with characters who have jobs, go to school, shop for groceries, or whatever it is that people do in your RPG world. If you employ a system like this, you would also have to make it easier for the human player to find people in the town (this is why most games have people standing in one place, so that the user knows where to find them). But this is a problem that can be solved (perhaps you have certain important NPCs that can be found in one of three different places, based on time of day). The overall effect of a living, breathing town would make the game world much more interesting and immersive. Implementing this kind of town could be done a few different ways. You could use a need-based system (like The Sims), in which each NPC would have a number of needs and would autonomously determine how to fulfill those needs. As an arbitrary example, let’s say that a certain part of town contains 100 NPCs. Each NPC has three needs: hunger, business, and family. Each need is satisfied when the NPC performs tasks that are suited to the particular need (eating to hunger; trading, training, talking, and so forth to business; and parenting, providing, and so on to family). The game could then use a “need pathfinding” system to give information on how to fulfill its needs to each NPC. The streets would be busy with people, going to and fro, buying bread, painting fences, or looking for their kids. The given action of each townsperson is defined by what need is the highest. Another way to write this system would be to write a number of different scripts, each of which would define a chain of actions, and just assign these little scripts to each NPC in the map. The second method saves a lot of computation (because you don’t have to do any sort of planning, or need tracking), but isn’t as general (you could implement a hundred different places for a need-based NPC to satisfy his hunger and the AI would use them all, whereas you’d need to write a hundred different scripts in addition to creating the hundred different places in the scripted system).
S U M MARY As a game genre, RPGs have been around a long time and people still love them; they show no sign of falling out of favor. They provide people with an escape from their ordinary lives by allowing users to take on another persona. The AI systems in this genre are quite complex, with many different AI needs across the entire game. Enemies and Boss Enemies are necessary to give the player something to fight, and to provide story motivation. NPCs and Shopkeepers provide the player with more personal interactions (other than combat), and give the world a living feel, complete with an economy.
Chapter 4
Role-Playing Games (RPGs)
91
Party-member AI needs special attention, especially in real-time combat-based RPGs. AI Scripting is a prime weapon to use in developing RPGs, but FSMs, and messaging systems are also staples for this genre. Some areas in which RPGs need improvement include grammar machines for better conversations, quest generators for more varied and long-lasting gameplay situations, better enemy and party member AI, and fully-realized towns to give the player a greater sense of immersion in the world.
This page intentionally left blank
5
Adventure Games
In This Chapter Common AI Elements Useful AI Techniques Areas That Need Improvement Summary
A
dventure games and early personal computers were made for each other. The spectacularly limited abilities of early PCs required a truly creative game to give the player a rich experience. This was challenging given the fact that the game could only give the player feedback by spelling things out in black and white text on the screen, or showing a few blocky shapes in limited colors. What was needed was a great story and some way of interacting with that story, letting the player’s own imagination create the striking visuals. Plus, PCs gave the game industry something they’d never really had before: a full keyboard interface. In the late 1970s and early 1980s, adventure games were some of the first games to make entertainment use of the clunky PCs that were just starting to become popular. The so-called text-based adventure games (the original being Collosal Cave Adventure, another being the famous Zork series) were our first taste of the genre. These games got their names because they had no graphics whatsoever—a text description of the room you were in and your imagination were all that you had to utilize. The player would type commands into a parser, and the game would either respond in kind with the result of the action the user had entered or inform the user that it didn’t know what he or she was talking about (if the user typed something in that wasn’t in the game’s command language). The player traveled from room to room collecting elements used to unlock puzzles, which would in turn allow the user access to other areas and further the story. Eventually, people started attaching pictures to these puzzle-filled stories, including games like the King’s Quest series, LucasArts’® seminal Day of the Tentacle and Monkey Island games, and the Leisure Suit Larry games. LucasArts also did away with full-text parsers, instead relying on a highly simplified keyword and iconic interface. 93
94
AI Game Engine Programming
In 1993, a small company called Cyan released a game called Myst. Myst took the adventure game and removed most of the story, leaving a very pretty world (it was one of the first CD-ROM games and used prerendered backdrops, which looked amazing compared with the simplistic real-time 3D worlds that people were used to seeing in other games at the time) and a large number of puzzles to solve. A player couldn’t die, but there was also no help to guide the player through the game; it was pure exploration mixed with trial and error. Although this sounds like a simple premise, Myst was the runaway hit of its time and is still widely credited as one of the best-selling computer games of all time. It spawned five sequels (the entire series has sold more than 12 million copies worldwide) and countless similar games tried to follow its formula. Today, the classic adventure game has all but disappeared. Nobody seems to know why. The Myst games may have given the genre sales numbers (adventure games had never been very big sellers), but they also may have been the reason for the dearth of new titles. People started to associate the adventure game title with slow, casual gaming that was merely a collection of puzzles and forgot (or had never heard) about the well-written, rich storylines of the earlier titles. Players have instead headed for the instant gratification of the more action-oriented adventuregame variants that have begun to take over the genre today. This book will not concentrate on the classic style of adventure game, which has also been called interactive fiction. We mention them for historic note only, since the level of AI elements inherent in these games is usually so low that they don’t require even moderate levels of decision-making potential. They are usually coded with state-based characters; most have only static elements, and only certain games even have actors that can move from room to room. Also, because the human could solve the puzzles in many of these games in any order, the AI for the characters is something more akin to a database of flags then to an actual decision structure. That being said, creating a classic-style game would require a parsing system, which is very akin to the scripting engine described in Chapter 18. Instead, this book will focus on the modern alternatives that have all but taken over the genre. These new takes on the adventure game (sometimes called action adventure) are usually variations of the first-person shooters/third-person shooters (FTPS) genre that focuses on noncombat-based gameplay situations: a mostly exploratory game (like Tomb Raider), or the more recent stealth games. The stealth game involves a main hero who cannot shoot his way out of the primary situations in the game but instead must use elements of stealth and guile to slip past the guards (such as the recent Metal Gear games, or the Thief series). Stealth games have proven hugely popular because of the varying gameplay elements, and the heightened sense of tension that comes from having to come up with alternative means of traversing the level and solving problems other than “pull the trigger.”
Chapter 5
Adventure Games
95
This transcends the FTPS roots of the games, bringing players back to the feeling of constant puzzle solving and a great storyline, but in a real-time game environment, so these are now considered adventure titles. Another variation, which does contain some combat elements, is called the survival horror game. Titles such as Resident Evil still have a lot of combat, mostly projectile attacks, but these are mostly three-dimensional exploration titles with lots of puzzle-elements to drive the player around the map.
C OM MON AI E LEM ENTS Adventure games are in somewhat the same realm as role-playing games. They also have enemies, non-player characters, and cooperative elements. But the modern adventure game also tends to sport advanced perception systems and specialized cameras that require AI programming effort. ENEMY AI Enemies in stealth games tend to be implemented with scripted movement sequences or very simple rules. The player needs to sneak by guards and other enemies and has to be able to identify patterns of movement to determine ways of exploiting these patterns. Once alerted to the player’s presence, however, the enemy’s behavior can get a whole lot smarter, and enemies can become quite involved. Guard characters usually employ multiple stages of attention, from “Did I hear something?” to a guard pretending he didn’t hear the player’s character as the guard slowly patrols in the player’s direction while taking the safety off his gun. Guards also perform basic behaviors like calling for backup, hunting the player down, and so forth. Remember that as an AI designer, you don’t want the enemies to be too diligent, or a player’s character would wake up the whole complex by setting off one guard, which would be frustrating to the human player. For other types of adventure games, pretty much anything goes. Some games use somewhat mindless hunter-style enemies, as in the simpler FTPS games. Other games have smart enemies that are constrained to zones (as in the Thief games), so a player might find himself being tracked down by an alerted guard, but the player won’t set off the whole world if he can escape his territory within a reasonable time. The survivor horror titles use very simple enemy AI, usually because the monsters involved are zombies, or something similar. The combat interface is mostly secondary to the exploration and puzzle interaction, so the enemies are slow, and the action isn’t as twitch-oriented (reliant on fast reflexes).
96
AI Game Engine Programming
NONPLAYER CHARACTERS (NPCS) Just as in RPGs, NPC characters are noncombatant inhabitants of the game world. They are placed there to give the player information, or to bring the world to life for visual support. The AI used for these characters is quite varied, from both an ability level and an implementation level, and can be anything from a static dialogue and actions to a much more complex system involving paths, goals, and a conversation engine with which to engage the player. This is all determined by the design goals of your game. COOPERATIVE ELEMENTS Cooperative characters go beyond the realm of NPCs. These characters assist the player directly, by showing the player new items, locations, or quests. In the case of action-oriented adventure games, cooperative characters will sometimes assist by helping players fight against the enemy creatures in the game. They can even be secondary main characters. Other games involve the player constantly switching primary control back and forth, in episodic or mission-based chunks of time, between different game characters. Switching control like this is a great way to decrease the perceived linearity of your game and to break the action into manageable chunks for the player. The state of the guards in a stealth-based game is the game, so to speak. The player is essentially balancing his exploration and discovery goals with trying to sneak around unseen and unheard, so as to slip past all the guards without “setting off the system” (meaning, causing the guards to become alerted to his presence), and bringing ruin upon himself. In order to be challenging at all, many of these games use smart chains of guards. This refers to guards that talk to one another, overlap each other’s territory, and generally share in patrolling an area. Connected guards lead to what can be thought of as a tightly coupled system. Each guard is in many ways coupled to other guards. The player cannot just get past one guard at a time, but must contend with systems of guards that are working together. Because of this touchy nature of stealth games, the programmer must make sure that an AI helper in that specific genre isn’t going to do anything that would set off the guards, or else we’re back to player frustration. PERCEPTION SYSTEMS For stealth games, most of the complexity of the AI model is contained within the perception system. Different techniques have been developed for each of the senses—to model each sense such that it translates well to the videogame world. Thief, from LookingGlass™ Studios, took the stealth game to an entirely new level, with the main thrust of the gameplay being constant sneaking,
Chapter 5
Adventure Games
97
hiding in shadows, pickpocketing specific characters when they’re not looking, and so on. A good breakdown of the perception system of Thief was given by one of the programmers who worked on the game at the 2002 Game Developer’s Conference; the paper can be found online at the following site: http://www. gamasutra.com/gdc2003/features/20030307/ leonard_01.htm under the heading Building an AI Sensory System. This is highly suggested reading if you plan to do a system of this complexity. Also, see the CD-ROM for additional links and materials. CAMERA Most adventure games are three-dimensional (a notable exception is the twodimensional Commandos series) and third person, so again the problems associated with bad camera placement are inherent. However, because of the much slower pace of these types of games, this is usually an easier problem to fix, and cinematic-style camera cuts with precise camera placement are usually the norm. Certain sections of the game may require a free-form camera system, and thus need programmer attention. Stealth games also frequently require an around the corner camera angle for hiding behind cover and watching a guard walk by. This can be an algorithmic camera that comes up when the player crouches next to a corner, or specific camera parameters can be set up in the level editor for particular cover positions.
U SEFU L AI T ECH N IQU ES The various AI elements used in adventure games once again give rise to the need for a varied AI toolset in order to solve all the required logic problems. The techniques that work well in adventure games include: finite-state machines, scripting and messaging systems, and fuzzy logic systems. FINITE-STATE MACHINES (FSMS) Many elements of stealth and exploration adventure games lend themselves well to FSM-based AI systems. If the game is digitally triggered, such as guards having an alerted state of yes or no, or if the game has an enumeration of states (like neutral, annoyed, alert, mad, berserk), then state machines provide the best bang for the buck. Because of the nature of state machines, you can make parts of your AI fairly simple, with other parts having many more states and thus much more complexity. For games with limited AI complexity and a large number of very straightforward AI tasks, you might want to stay with a state-based system.
98
AI Game Engine Programming
SCRIPTING SYSTEMS Some adventure games use very cinematic camera placement, lots of in-game dialogue, and sequences that show the results of solving a particular puzzle somewhere else in the level. Scripting systems allow the programmers (and designers) to easily put extra tailoring into specific parts of the game, and this technique is readily used for the linear story that these games employ. The combination of triggered events setting off scripted sequences, and having the trustworthy game mechanic of having to “unlock” later parts of the game by accomplishing tasks (which is essentially changing certain game-state flags) gives the best of both worlds; it allows game designers to have many places within a game in which to get specific things to happen, while still giving the player some feeling of being able to roam around uncontrolled. MESSAGING SYSTEMS The event-driven nature of typical adventure-game puzzles (push lever A, door goes up; move three stones into certain pattern, hidden chamber opens; and so forth) lends well to the use of messaging systems. Passing messages means that the disparate elements in the game don’t require direct code access to each other to communicate. The advanced perception systems of stealth games can use messages for determining perceived sounds and the like, as well as providing enemy guards an easy method for alerting others or calling for help. FUZZY LOGIC The perception systems used by stealth games can be quite complex. In the face of numerous, sometimes conflicting, sensory inputs, AI opponents need to incorporate fuzzy decision making to make full use of the rich information. Many of the challenges in stealth titles involve getting past guardians, and using a fuzzystate-based system can help make guard states feel forgiving to the player (the player can sneak by if the player doesn’t push the boundaries too much—like being able to push on a pinball table: some movement is legal, but if you overdo it, you tilt). Frequently, part of the gameplay is having the guards deal with situations such as player-initiated distractions, diversions, ambushes, and other kinds of slighting. These sorts of interactions are often scripted. Another implementation could use fuzzy logic to allow the guards a fuller and more flexible model of the world, in order to deal with the kind of imperfect information that a diversion might provide. The guard’s notion of his territory might be fairly clear—he hasn’t seen or heard anything suspicious in a while. Then, the player throws a rock into a dark
Chapter 5
Adventure Games
99
corner. The guard hears it, his suspicion level goes up a bit, he adds a suspicion target to his internal list, and he focuses most of his attention on it because it’s his only area of concern right now. The player tosses another rock; the guard reacts by getting more suspicious, adds another target to his list of things to investigate. He yells, “Who’s there?” and cocks his weapon, moving slowly toward the corner. You get the picture. The ebb and flow of suspicion, directed toward however many targets, is determined by the guard’s very unclear, sparse picture of the world, which is determined by his perceptions. Note however, that this kind of system is typically much harder for the player to figure out. Scripted systems are usually quite telegraphed: the smart player can watch the guard for a bit, and notice that every two minutes he gets up and goes to the balcony to look outside, giving the player a window of time to make his or her move. A fuzzy system would instead be blending many different inputs into a final behavior; the player might not pick up on all the elements that are giving the guard his final behavior, and as such have difficulty determining what he or she needs to do in order to affect changes in the guard’s actions. In practice, most of this fuzziness would be better used within the perception system itself, rather than in the decision structure. An FSM with fuzzy transition logic is much easier to program then a full fuzzy logic system is. Examples
After the classic adventure games began to wane in popularity, crossover genres started to appear. Tomb Raider was the early hit that started us off on the crossover from shooter to adventure game. Other earlier games included Alone in the Dark, and Shadow Man, which added horror elements, and eventually gave us Resident Evil. Resident Evil in turn spawned a slew of more fully horror-based exploration titles like Silent Hill, American McGee’s Alice in Wonderland, and Nightmare Creatures. These action-adventure games still had lots of combat involved, because the AI systems were still borrowing heavily from their FTPS brothers. The designers just increased the exploration and item-gathering challenges to round out the overall experience. As the AI engines got better, and perception systems became complex and had gameplay depth, the stealth games came out, with Thief, Deus Ex, and Metal Gear Solid initially leading the pack. These games made it fun to not kill your enemies but, rather, to never even let them see you. Commandos was an overhead twodimensional stealth game: the gamer’s job was to accomplish missions by infiltrating increasingly complex enemy bases and sneaking from spot to spot unseen. The game was spectacularly hard, but very well done. The line of sight of all the guards was actually shown as moving cones on the ground, so players could much more intimately time their movements to ensure their secrecy. This is a great
100
AI Game Engine Programming
example of giving the human player more information in order to deepen the game mechanic. Another notable hybrid adventure game was Blade Runner, which touted real multiple endings and storylines, and a somewhat alive world. The NPCs in the game were engaged in semi-autonomous behavior, moving through the city to get to stores, jobs, and so forth. The overall effect was mostly cosmetic, though, as interactions with the NPCs were still very state- and/or event-based. Although a new classic-style adventure game is rare, it is not fully extinct. Some great examples of these games in recent years include Full Throttle, Grim Fandango, and Circle of Blood. These games have expanded the old formula, with better (and more involved) puzzles, great graphics, and much more varied gameplay elements (Full Throttle even included a motorcycle combat stage). The interaction system that these games use has gone up and down in complexity over the years. With the initial text adventures, the player could type pretty much anything, and the game’s parser would either recognize the command or say otherwise. Players would eventually learn the commands that the parser knew. Later, with LucasArts’ SCUMM system (which stands for Script Creation Utility for Maniac Mansion, a great example of a tool being built for a specific game becoming the cornerstone of an entire suite of games, as the SCUMM engine was eventually used in no less than eighteen games. SCUMM still has a rabid fan base online, with new games created by fans still coming out. Visit http://www. scummvm.org/ for more details), the possible commands were given to the player as buttons on the graphical interface, and the player could apply these commands to various elements on screen. Full Throttle went even more abstract, with icons depicting the player’s eye, mouth, or hand being used as context-sensitive commands to apply to game objects. So, if a player used his mouth with an NPC, the player would talk, whereas if the player used his mouth with a beer, the player would drink it. The simplification of possible inputs from the human to facilitate ease of interfacing with the game led the NPCs to become much more simplistic as well. The level of communication with the player is inherently limited, simply because the player no longer has any means by which to respond intelligently. If an NPC asks a player for the time, does the player click on the character with the mouth icon to talk, or with the hand icon to check the character’s watch? If the player chooses the wrong response, and the NPC asks what’s wrong, then what? This limited interface may streamline the game somewhat, but it definitely takes away from the feeling of living in an organic, much more interactive environment like Zork. Sure, most of the nonsense things you typed in Zork were ignored by the response “I don’t know what that means” but you were still allowed to type them. In the games with the simpler interface, you were left to just shout at the screen.
Chapter 5
Adventure Games
101
A REAS T HAT N EED I M PROVEM ENT As with any game genre, there are always areas within the family of released games for improvements in the AI realm. In adventure games, these include: additional types of steal goals, returning to traditional adventure game roots, better NPC communication, and user interface designs. ADDITIONAL TYPES
OF
STEALTH GOALS
In addition to the classic stealth mechanic of patterned movement that has to be circumvented, Deus Ex gave players many different ways to accomplish key story goals. For example, to get through a particular door, the player could shoot the guard and take his key, and then fight the other four guards that would come when they heard the shot. The player could also cause some kind of diversion, and then use a hacking skill to open the unguarded lock. Or, the player could climb through a ventilation shaft and find a different way in. The player could even find a guard uniform and use it to walk right by the guard. By doing this, the game designers made each encounter and area of the world into a puzzle. The player had to really experiment with the situation to uncover the hidden gameplay gems. The player didn’t have to sneak down one particular hallway and open one particular door. This forced Deus Ex’s guard AI to be more open ended, instead of being heavily scripted, because there were potentially so many ways to get around them. A RETURN
TO
TRADITIONAL ADVENTURE ROOTS
Traditional interactive fiction provided computer gamers with some of the most popular games released in the 80s and 90s. Many of the classic LucasArts and Sierra games have loyal followings. Today’s exploratory and more action-oriented games must meld with classic roots of the genre to bring adventure games alive again. In many ways, the genre has become too action oriented. There is still a place for complex logic and exploration puzzles, as well as deep storylines with interesting NPC characters that have full personalities. Today’s “run and gun” adventure games sometimes suffer from not having the time necessary to build up the intricate stories of yesterday’s game titles. BETTER NPC COMMUNICATION The inherent noncombat nature of modern stealth adventure games lends itself well to having additional story-driven elements included as part of the experience. By giving NPCs in adventure games real grammar systems, or even allowing branching storylines within the full umbrella of the greater game story, the world in which the adventure is occurring could become more real, and much more personal to the
102
AI Game Engine Programming
player. This, of course, would require an immense amount of additional work in story design to make up for branching and consistency problems. USER INTERFACE When we lost the full-text parsers of the original text adventures, we also lost the ability to have rich interactions with in-game characters. After going to a graphical interface, the complexity was gradually degraded until eventually some adventure games had as few as three or four basic commands that could be used with elements in the world. Today, with the more action-oriented variants, little interaction occurs other than a player positioning his or her character well and using quiet weapons or tools when necessary. Imagine Sam and Max with a full-voice interface, or some other kind of general interface where the player could get a much richer kind of connection to the game if he or she spent the time to explore the capabilities of the parser. Eventually, a new interface could help adventure games regain some of their traditional depth, without having to resort to typing long sentences into a computer.
S U M MARY Adventure games are continuing to evolve from their initial roots, which was a string of puzzles wrapped into a story, and were definitely not played in real time. The modern stealth games and the more action-oriented exploration games are modern variants of the classic adventure formula that will continue to give game players challenges and new worlds to explore. The first adventure games were text-based and required the user to type commands to a parser. These eventually gave way to the graphical adventure game, which added a graphical user interface to save the user from typing. Modern adventure games are variants on the FTPS genre, and emphasize noncombat situations such as exploration and stealth. Enemy AI in stealth games can be somewhat pattern-based because the object of the game is to note patterns and circumvent confrontations. In the more exploratory combat-style games, enemy AI can be much more varied. Most adventure games have a number of NPCs, as well as cooperative characters, that give the player information or new gear. The AI level of these agents varies greatly. Perception systems are paramount for stealth games because overcoming the guards’ perceptions is the goal of the game. Camera AI is usually necessary for these adventure games because they usually are done in 3D.
Chapter 5
Adventure Games
103
FSMs, scripting, fuzzy logic, and messaging AI systems are commonly used within the adventure genre. New stealth challenges (possibly by infusing the current game schemes with more intelligent enemies) is an area of improvement for the adventure genre. A return to the classic adventure game roots is needed to help revive the lineage of the genre. Increased NPC communication and story branching might give adventure games additional personal connections to the player. An advanced user interface could help give back the richer interaction level of more traditional adventures to modern games.
This page intentionally left blank
6
Real-Time Strategy (RTS) Games In This Chapter Common AI Elements Useful AI Techniques Examples Areas That Need Improvement Summary
T
he AI systems used in RTS games are some of the most computationally intensive of all videogames. They usually involve large armies that must coordinate their behavior and technology trees that must be navigated to perform goals. They must also share CPU time with the rest of the game technology, like collision detection and drawing routines, which also contend with numerous units. Although RTS games have been around for years (the 1990 game Herzog Zwei for the Sega® Genesis™ console is usually considered the first), AI performance has been nowhere near the level of good human players. The AI in RTS games has to fight against many factors: huge numbers of characters to give orders to, very incomplete information about the game world (the fog of war is the most obvious example), heavy emphasis on micro actions (meaning that actions have limited effect on the overall game), and having to run in real time. By contrast, consider the types of games in which AI has achieved expert (or at least very good) level: turn-based games, with perfect information, in which most moves have global consequences and in which limited human-planning abilities can be outsmarted by mere brute force enumeration. This type of game includes chess and the like. Thus, almost every aspect of RTS games is considered non-optimal for AI performance. The burden lies on game designers to overcome these problems in a believable fashion.
C OM MON AI E LEM ENTS RTS games are some of the largest consumers of AI programmer time. There are many differring elements within RTSs that require AI logic, which include: individual 105
106
AI Game Engine Programming
units, economic units, high-level strategic AI, commanders and other medium-level strategic units, town building, indigenous life, pathfinding, and tactical/strategic support systems. INDIVIDUAL UNITS The real player in RTS games is the “overseeing general” of the “army” (or whatever name you wish to give to the forces; military names are being used because the vast majority of these games involve military based setups), either the CPU or the human user. The goals each player is fighting for can involve the entirety of their society. However, this doesn’t mean that individual units are worry-free. Individual behaviors in RTS games are usually considered secondary, by temporarily overriding the primary order given by a user. Most of this local intelligence falls into the categories of pathfinding, obstacle avoidance, concentrating attacks, and falling back when the player cannot win. The question of how much intelligence to put at this secondary tactical level is tricky. The amount of micromanagement your RTS is trying to achieve should determine this. The more individual intelligence a unit has, the less often a player has to check every unit in his or her army. However, for games with low-level tactical AI, if the CPU opponent micromanages its individual-unit AI too much (giving it the appearance of better individual AI), it will be seen as cheap AI trick because it isn’t possible for the human to replicate the computer’s efforts as fast or easily. One simple example of this is the archer behavior in the Age of Empires games. The computer will send in many weak projectile units, which then shoot, retreat, shoot, retreat. This very simple behavioral micromanagement makes these weak units become much more powerful because they will string out and separate guards in all directions, a behavior that would be very difficult (or at least tedious) for a human to do. Reliance on the power of this simple individual behavior has also made the Age of Empires games not attempt more common strategic techniques, such as setting up a wall of melee fighters and putting the archers (or other long-range attackers) behind them for support, which is something that almost all human players do. ECONOMIC INDIVIDUAL UNITS Sometimes called peons (the “builders” and “gatherers”), economic individual units are those that usually do not fight but are, instead, employed as the economy on which the player gains resources for creating his or her armies. Much like other individual units, the level of AI has to be carefully tuned to the level of micromanagement the game requires. Age of Empires recently addressed common dislikes about this area of the game’s AI by making peons automatically start gathering resources after building a resource-associated building, and also
Chapter 6
Real-Time Strategy (RTS) Games
107
making food gathering easier by the ability to “queue up” farms instead of having to check back and replant them manually. Other common peon management techniques include: Order queues. In most RTS games, the interface allows a player to tell a unit to perform multiple actions, one after another. This is a very powerful addition to the genre because it allows smart players to plan the behavior of their economic units ahead, so the player can then continue play, assured that their economic units will be busy during more battle-oriented points of the game. However, the interface still requires the player to set it up, so the AI of each individual unit doesn’t have to be bloated with special-case code designed to make the peons appear smart. Auto-retreating. Peon units can rarely fight (or aren’t skilled at fighting), so most RTS games have some sort of autoretreat AI for these units. Usually it’s just leaving the attack range of the enemy, however. This aspect could definitely be improved by getting to a building for protection, or running to the nearest military unit (while shouting “Help!”). Also, noticing when the danger is over and going back to work would be another welcome addition. HIGH-LEVEL STRATEGIC AI High-level strategic AI might be thought of like the general of a real army. This is the layer that most closely maps to trying to mimic the human player. Performing commands and plans from this level of direction might involve numerous units, or require whole sections of the economy to shift. High-level plans usually include actions at many different levels of AI to complete. The perceptions at this level are typically built on information from the lower levels to determine what the enemies are doing. Given all this feedback, the high-level AI makes plans to deal with threats exposed in the perception data. In this way, the strategic level affects everything from the individual soldier (as part of a larger group of soldiers who are told by a commander level to respond by moving) to the entire economic system for the AI player (when shifting the allocation of units that are retrieving resources to bias a particular type that will support the high-level plans). Frequently, the high-level AI is multifaceted, in that it is running resource allocation between several different aspects of the game (defense versus offense versus research versus economy), and thus represents most of a given RTS civilization’s personality. Race #1 might value offense and have a strong economy. Race #2 might be cautious and studious. Coupled with specialty units for a given AI type, and some tunable parameters, the system designer can differentiate different types of AI opponent races easily, just from this level of the AI.
108
AI Game Engine Programming
COMMANDERS
AND
MEDIUM-LEVEL STRATEGIC ELEMENTS
Some games directly use “commanders” to bolster groups of units (such as Total Annihilation, which used its commander unit as a primary builder in addition to a super unit). In other games, commanders are used internally by the AI system to group units into fighting elements and control them in a larger war sense. This can be considered a medium-level AI, because it requires much more than simple individual actions (such as shoot or go somewhere) and is not a fully high-level strategy (line taking command of a particular resource, or defending a base). A simple example is a commander choosing a new destination for a group of units (medium level), but the individual units decide how to stay in formation and use the terrain features to get there (low level). By dividing the labor in this way, it makes the system easier to write. You can write higher-level systems to cover large troop movements, and lower-level code to get over and around the map. The part of the system that’s trying to get troops into position doesn’t have to worry about keeping the long-range units behind the short, or figuring out the quickest way through a maze-like canyon. A more complex example: the general decides that attacking player #3 is the best course of action (high level). The commander (medium level) would then direct twenty infantry to attack from the west, followed by a group of ranged weapon units, and some tanks in from the south to take out towers that could harm the infantry along the way. As always, the low-level pathfinding and avoidance AI would get all those units around the map in the best way possible given the lay of the land. This middle level of strategic RTS game AI is usually sorely lacking, by and large because it is the most complex to create and tune. High-level goals can be somewhat direct, almost simple. Think of the high-level goal “Take command of Hill #3.” Stripped of all the details necessary to actually accomplish the goal, the entire plan is only five words. Low-level goals are also straightforward, involving very atomic behaviors and local, small-scale perceptions. In contrast, the commander level requires large collections of feedback information from many sources. It has to combine all these perceptions into short- and medium-range plans that coordinate group movements, resource allocation, and in some games, form secondary goals involving diplomacy and trade. TOWN BUILDING Most RTS games involve collecting resources in order to build a town (base, settlement, colony, etc.) that will then provide the player with the tools and technology to create larger and better-equipped armies. Laying out the initial headquarters, as well as planning the advanced AI bases, is a difficult problem in its own right. A player will want to place structures somewhat close together, for
Chapter 6
Real-Time Strategy (RTS) Games
109
ease of protection (by surrounding walls, or force fields, etc.). But the player will also want to spread them out a bit, to get better visibility and guard against areaeffect weapons. Finding this balance, while keeping a fluid economy running, can be quite challenging. Many games use hard rules for town building (which are broken up into difficulty levels) that start out fine, but may or may not be able to cope with changing world conditions, and as such can look silly by the end of the game. The decisions about where to place key structures need to account for many different elements. Economic structures need to be placed next to the resource they are going to store; military structures need clear exit lanes and proximity to the front line (if possible). Guard structures need to maximize visibility effects and be able to back each other up and watch over the largest possible number of other units. INDIGENOUS LIFE Most RTS games have some kind of native inhabitants within their game worlds. Games like Warcraft have sheep walking around in them, and Age of Empires actually uses the indigenous fauna as a resource that can be gathered. Other games treat the locals as a hazard, or even a source of powerups. AI for these entities is usually minimal, but some games give them a certain degree of intelligence. Depending on the nature of these elements within your game (be it resource or hazard), you might need to balance the distribution of these elements, otherwise your players may not have fun. Age of Empires games using random maps can sometimes be thrown off by having a wolf too close to a player’s initial town, and this random element can diminish the starting capabilities of that player tremendously if the wolf inadvertently kills one or more of that player’s initial peons. PATHFINDING Pathfinding is one of the biggest CPU concerns for RTS games. In the worst-case scenario, a huge number of units could be simultaneously ordered to go to wildly different faraway locations across the map. The pathfinding system must correctly find quality paths for everyone, load balance the CPU cycles necessary to find these paths, and use other optimizations to make pathfinding feasible for so many separate entities. Other types of movement elements such as formations, flocking techniques, and follow-the-leader-type systems will vastly improve the speed of per-unit pathfinding. Other pathfinding concerns include handling friendly units blocking paths, dealing with special case choke points like bridges, and dynamic path elements such as user-constructed walls or level debris.
110
AI Game Engine Programming
TACTICAL
AND
STRATEGIC SUPPORT SYSTEMS
Many RTS games are increasingly using extended AI techniques to make the actions taken by their games smarter. These advanced support systems include the following: Terrain analysis. By dividing the terrain into manageable chunks and then breaking down various characteristics of each piece, the AI can glean huge amounts of data that can be useful for strategic decision making. Terrain bottlenecks and odd landscape features can be identified and recorded for the pathfinding system, so that the pathfinder can more easily and quickly develop intelligent paths. The system can keep track of enemy base locations and resources, and also find holes in the player’s (or other player’s) defenses. Most of this can be done by using an influence map, which is really just a fancy name for grid-based map attributes. The AI divides the game world up into an even grid, and then associates each location with data specifically describing certain features of each grid square. Terrain analysis data can be created offline during level creation, but the system becomes much more powerful when the game’s AI dynamically updates it during the course of the game, as scouting information comes in or allies offer up counsel. Some RTS games have a special multiplayer mode in which a certain resource is located all in one spot on the map, leading to a vicious fight over this precious supply point by all the players. Human players can see quite easily that control of the scarce resource is the only way to win in this style of map. AI opponents, unless specifically analyzing the terrain for features like this, are usually ineffective at seeing the long-term problem with this type of map. Typical RTS AI will only head for far-off resources when local ones are depleted and will usually be overrun by human players who have already taken control. The same sort of situation can arise in game maps that have strong movement choke points, like a river crossing or a bridge across a deep canyon. A human player can seek out terrain elements like these and set up strong defenses on one side, and then wait for the computer opponents to waste a lot of resources trying to get through. Opponent modeling. In games with imperfect information, like RTS games (or poker, for another example), a player cannot use standard AI opponent assumptions. AI systems for games like chess routinely are built around the premise “My opponent will make roughly the same decisions as I do, because we both use the same optimal search algorithms for the state space of this game.” In RTS games, the AI might not know the abilities of the other players (since it can only guess by observation as to what units and technology players have researched, as well as where players have located all their forces), and thus has no basis on which to make predictions about the other players.
Chapter 6
Real-Time Strategy (RTS) Games
111
By observing and noting both physical abilities of the opponents (like seeing a Dread Mage, or hearing a dragon scream), as well as opponent behaviors (the opponent has always attacked the base from the right, or has always built a tower near the opponent’s own gold mines), the AI can build a model of its opponents. Keeping this model as up-to-date as possible is very important, so the AI can use the model to make much more appropriate decisions in dealing with its opponents. By noting which players have specialty units in their army, the AI can build a fairly accurate tech tree for its opponents and know what other technologies or units each opponent has access to, and can plan for future attacks that might use these. By recording player behavioral tendencies (which types of units the player favors, the time between player attacks, the usual kinds of defenses the player uses, etc.), the AI can better assign defenses and build the correct units to answer upcoming challenges from its opponents. In essence, this is what human military generals do, as well as the meaning of the age-old saying, “know your enemy.” Resource management. Most RTS games (Myth was a notable exception) have an economy that must be tended to as much, if not more, than the battles. Raw resource requirements such as gold or wood and the need for secondary resources like combat units and research structures must be balanced during the course of the game. Most games’ AI handle this complex task by starting the AI off with a build order (a string of things to build, one after another, that will jump-start a thriving economy), which is a technique that even human players use. This leads to very predictable AI behavior, however, because experienced human players are quick to discover this build order and, from it, learn the approximate times for attacks and when AI defenses will come online so they can exploit defensive holes. A better arrangement might involve resource allocation systems that recognize supply deficiencies and rectify them by using a planner to organize goals necessary to fill these needs. By using a need-based system, AI opponents could be implemented that bias heavily toward certain units or resources and would rely much more on map type and personality, rather than blindly following a build order and then reacting to the outcome of the initial first large battle. Even humans who use a build order are quick to adapt the build order to specific things that they see (either in the form of map resources or enemy activity, through their scouts) so that they are not blind-sided. An early RTS game, Enemy Nations, used this exact approach with excellent results. Reconnaissance. Most of these games have some form of “fog of war,” which is a mechanism for visually representing two things: unexplored terrain and line of sight. To combat these perception deficiencies, players must use units to explore the map, to uncover map features, such as borders or resources, and to find the enemy and its forces. This is a difficult assignment.
112
AI Game Engine Programming
Most AI opponents in RTS games do a good job of exploring the map, simply because they can micromanage a scout unit much more effectively than most humans, but the concept of keeping tabs on enemy movements and encampments through additional recon is uncommon. Humans have to use continual scans to see what kinds of threats the AI (or other human players) are building up against them, as well as noticing any changes to the area that have occurred since the last time a scout went through (like the creation of guarding structures, or the depletion of resources by other players). One way that some games have tackled this problem is to have the AIcontrolled player use a scattered methodology when building its structures. The AI player doesn’t have to remember where anything is, so it can create very random and scattered towns that give the AI system the greatest amount of line of sight possible. Then, advancing armies from other players are sure to enter the line of sight of one of these forward buildings, thus alerting the system to invasion early on. This does lead to somewhat greater building loss by the AI, though, because the human will make sure that these forward buildings are taken down as they are passed. A better system would be the more complex wall building and guard-post placement that most humans use. Diplomacy systems. One of the underused places for AI in today’s RTS games is in the area of diplomacy, which is defined as different players working together toward a victory. Age of Empires takes AI diplomacy to mean “we won’t kill each other,” and that players also share map visibility information. It doesn’t go into such areas as supporting an ally’s troop movements, specialization (“my opponent will develop many units; I’ll mine gold and build towers”), or even simply timing attacks to coincide more readily with allies. Human players manage all these diplomatic tasks very well, and AI systems should develop these tasks further. Of course, this involves additional AI work and additional user interface work because the human would need ways to communicate to the AI ally that he’s planning an attack from the south in sixteen minutes, or that he needs help in sector six.
U SEFU L AI T ECH N IQU ES All those specialized game elements requiring AI call for one of the largest required tool sets of any AI game engine. Some of the techniques that work well with RTS games include messaging, finite-state machines, fuzzy-state machines, hierarchical AI, planning, scripting, and data-driven systems. MESSAGING With such a huge number of potential units in the game, polling for game state changes or enemy events would be computationally wasteful. Instead, messaging
Chapter 6
Real-Time Strategy (RTS) Games
113
systems can be used for broadcasting events and game flags to a large number of registered units quickly and easily. FINITE-STATE MACHINES (FSMS) Never to be left out, FSMs can always be useful somewhere within the numerous AI tasks that are part of the RTS world. Individual-unit AI (most likely implemented as stack-based FSMs, so that they can be temporarily interrupted, then restored easily), systems within the strategy level (a city builder AI could be constructed as an FSM making use of an offline-created build-order script that has been proven to work), and many other game elements can take advantage of the loyal FSM. Small-scale modules are a great fit for FSMs, because they are easy to create and their primary disadvantage, that of not scaling well to large problems, isn’t an issue if used in this way. FUZZY-STATE MACHINES (FUSM) RTS games’ higher-level strategic requirements are some of the few game genre problems that don’t lend themselves well to regular state-machine-based solutions. The preponderance of imperfect information about the opponents and the world, combined with the number of micro decisions that need to be made, make for a game in which the AI opponent usually has multiple directions to play toward, all of which are winning decisions. A better system is fuzzy-state machines (FuSM), which provide the structure and reproducibility of state machines, while accounting for the somewhat “flying blind” nature of RTS decision making. The AI might not know how many tanks the enemy has, or how much gold the opponent has in reserve to purchase additional reserve troops, but must still try to thrust forward toward victory. FuSMs allow this type of gameplay decision, without using the more straightforward method of just cheating and giving the AI knowledge of its opponent’s positions and army makeup (which it then uses to make “intelligent” decisions based on some randomness and the difficulty level of the game). The parallel nature of FuSMs allows an AI system to determine, separately, how much effort to spend on each facet of command that might require attention at any given time. Thus, the complete blend of behavior that the AI is exhibiting is going to be much more varied and contextual, and will not rely on omniscient cheating to help the AI. HIERARCHICAL AI RTS games have multiple, sometimes conflicting AI requirements. A computer opponent needs to move an army from point A to point B, but along the way, a small
114
AI Game Engine Programming
ambush happens and its units are being attacked. Do the endangered units break off and return fire, does the entire army stop and make sure the problem is quelled, or do all the troops ignore the threat and march on? The answer is determined by the amount of individual versus commander (or strategic versus tactical) AI, but also the interface between these differing layers and how one can influence the other. Hierarchical systems provide a means for RTS games to form high-level goals but also appear smart at a unit level, without choking the primary AI system for resources. PLANNING Goal planning is a large part of the RTS AI world. To accomplish higher-level tasks (for example, to guard the left side of a player’s camp against air attack) any prerequisite tasks must also be added to the AI’s current plan. Thus, for the just-mentioned task, the AI would have to also (1) gain any foundation technologies in the tech tree (for example, a player might need to make guard towers before he can build antiaircraft towers, or the game could require a communications building so that a player’s weapons could use radar to detect incoming planes), and (2) determine the necessary resource units to spend (which, if deficient, might spawn a secondary goal to gain more of the needed resources). Tech-tree navigation is only one area of planning, however. Specific offensive or defensive goals require planning to appear intelligent as well. It has even been researched that to look truly intelligent, even simple tasks like running away from a threat need some level of forward thinking (beyond just pathfinding). So large troop attacks could use planning to coordinate smaller groups to work in concert. A diplomatic planner could determine how to “save up” the resources that an ally has requested in order to trade for a much-needed technology. SCRIPTING Although RTS games usually don’t use scripting to the same extent as other genres, it is still used to extend the story elements of certain games, or to more rigidly describe the behavior of certain units under certain conditions. Some titles seem to be concentrating on fewer units and more scripted and rich interactions between these units (such as Warcraft III ). This emphasis on so-called superunits has led to scripting being used more heavily in this style of game, in much the same way that Half-Life led to more scripting in FPS games. Another place that scripting is useful within RTSs is the aforementioned buildorder scripts that most RTS games employ. Some of these scripts can become quite complex, and even include options for building based on early enemy attacks or proximity to certain resources.
Chapter 6
Real-Time Strategy (RTS) Games
115
DATA-DRIVEN AI Many of the larger RTS games are putting large portions of the AI decision making into non-code form, be it simplistic parameter setting (like the early Command and Conquer games) to actual rule definitions (such as the Age of Empires scripts). This allows two things: Designers working on the games gain easier access to the game so they can tune the AI, and people who buy the game can tweak the AI settings themselves. Age of Empires especially needed a system like this, with upwards of a dozen civilizations. See Listing 6.1 for an example of a user-defined Age of Empires script. LISTING 6.1 A sample Age of Empires AI user-defined script showing simple rule definitions. ; attack (defrule (or (goal GOAL-PROTECT-KNIGHT 1) (goal GOAL-START-THE-IMPERIAL-ARMY 1)) (or (unit-type-count-total knight-line >= 25) (soldier-count >= 30)) => (set-goal GOAL-FAST-ATTACK 1) (set-strategic-number sn-minimum-attack-group-size 8) (set-strategic-number sn-maximum-attack-group-size 30) (set-strategic-number sn-percent-attack-soldiers 100) (attack-now) (disable-timer TIMER-ATTACK) (enable-timer TIMER-ATTACK 30) (set-strategic-number sn-number-defend-groups 0) (disable-self) )
(defrule (current-age == feudal-age) (soldier-count > 30 ) (goal GOAL-FAST-ATTACK 1) => (set-strategic-number sn-number-explore-groups 1) (set-strategic-number sn-percent-attack-soldiers 100) (attack-now) (set-goal GOAL-FIRST-RUCH 0) (disable-timer TIMER-ATTACK)
116
AI Game Engine Programming
(enable-timer TIMER-ATTACK 30) (disable-self) ) (defrule (current-age == feudal-age) (soldier-count > 20 ) (or (players-current-age any-enemy >= castle-age) (players-population any-enemy >= 20)) => (set-goal GOAL-FAST-ATTACK 0) ) (defrule (current-age >= feudal-age) (soldier-count > 20 ) => (set-goal GOAL-FAST-ATTACK 1) ) (defrule (current-age == feudal-age) (goal GOAL-FAST-ATTACK 1) (timer-triggered TIMER-ATTACK) (soldier-count > 20 ) => (set-strategic-number sn-percent-attack-soldiers 100) (attack-now) (set-strategic-number sn-number-defend-groups 0) (disable-timer TIMER-ATTACK) (enable-timer TIMER-ATTACK 30) )
E XAM PLES Herzog Zwei, the granddaddy of RTS games, was really more an action game with the added twist that players had to acquire money to get more equipment. With no real pathfinding, enemies constantly got stuck. A player could trick the AI builder unit so that it was impossible for it to fight back. For the most part, Herzog was probably coded using a very simple state machine, with the states defined as get money, attack, and defend. Westwood Studio’s® Dune: The Building of a Dynasty came out two years later and started the standard RTS formula that mostly continues today, in which players build
Chapter 6
Real-Time Strategy (RTS) Games
117
a town, mine resources, span a tech tree, and fight enemies. The game didn’t have the best AI, but understandably so, given the minimal system requirements of the game. Dune used an initial defense build order, followed by a phase of finding the opponent’s base, and then attacking. It wouldn’t really rebuild its defenses (because they were only built during the opening phase), it wouldn’t attack anywhere but the side of its opponent’s base facing its base (no real flanking or trying to find weaknesses), and it cheated extensively (the AI never seemed to run out of money, and it could build its structures unconnected from each other, whereas the human could not). The golden age of RTS games included the Command and Conquer series, Warcraft, Starcraft, and many spin-offs and imitations. During this time, the AI continued to push forward, the biggest improvement being pathfinding. But the games were still plagued by AI exploits that human players would find very quickly. This was mainly because the AI didn’t have the processing power or memory space necessary to use things like influence maps for full terrain analysis or better planning algorithms. More modern games—such as the Age of Empires series, Empire Earth, Cossacks, and the like—have built on these modest foundations and created full-featured games with plenty of challenge and fairly good AI opponents. Although some problems are perennial (such as formations interfering with pathfinding, and diplomacy AI being all but absent), these games can, and will, give human players a challenge without cheating (for the most part) and without exploits. Most of these titles use some form of advanced terrain costing to further their pathfinding. Most do some planning to determine goals and subgoals. Starting build orders are still quite popular, simply because of their ease of implementation and the tunable way that they affect difficulty level. Some modern RTS games have changed direction a bit, with Warcraft III, Command and Conquer: Generals, and Age of Mythology being notable examples. These games have started emphasizing the use of superunits, or champions, instead of throngs of mindless units. These champion units are tougher, more capable, and more expensive to build and to lose. They also employ a much higher amount of mission scripting, so that the game has a much more crafted feel, instead of many of the missions of earlier RTS games where players were just pitted against larger and larger opposition forces.
A REAS T HAT N EED I M PROVEM ENT RTS games, like all genres, could use some fresh perspective and new direction in gameplay. Many things were done unintelligently in the past due to CPU constraints, and have remained unintelligent due more to convention than anything else. Some of the areas in the RTS world that could use improvement include: learning, determining
118
AI Game Engine Programming
when an element is stuck, helper AI, opponent personality, and using more strategy with less tactics. LEARNING RTS AI too often gets caught in the same trap repeatedly. A simple example is readily seen in most RTS titles, in which the computer will march one or two units past a tower (which will kill them) over and over. The AI should definitely take into account successful travel information about map locations (using the influence mapping techniques described earlier) so that it can stop being kill-zoned by smart players who notice lines of migration. Other learning opportunities for RTS games could include opponent modeling opportunities like keeping track of the direction of player attack, noting which types of units the player favors, or even keeping track of game strategies across multiple games against a particular player. Does the player use early rushes? Does the player rely on units that require a lot of a certain resource? Does the player frequently build a number of critical structures in a poorly defended place? Are the player’s attacks balanced, or does the player build many rocks, many paper, but never any scissors? When you start attacking a remote base, how long does it take the player to respond? The answers to these kinds of questions could be stored along with statistics that would allow a smart AI system to adapt to these kinds of issues and more. Using this kind of information doesn’t mean that the AI slowly becomes unbeatable; it just means that the human has to switch tactics to win, somewhat forcing the player to investigate other areas of the game’s complexity. An AI opponent that is shutting down specific player offensive maneuvers doesn’t necessarily mean that the AI itself has to be aggressive, unless the player has set the difficulty very high. DETERMINING WHEN
AN
AI ELEMENT IS STUCK
At some point, in almost every game, an AI element (from the lowliest economic peon, to an entire group of tanks) might get into a situation where it doesn’t know what to do at all. Maybe all the resource-gathering centers are gone, there’s not enough money to build another one, and a peon has an armload of coal but doesn’t know what to do with it. Or a group of tanks is being hounded by an aerial unit (and cannot fight back), but is also trapped in a close-quarters area, and stuck in a pathfinding/fleeing cycle that keeps the tanks going in circles as they try to get away, but trip each other up, over and over again. This type of nasty feedback loop can make an AI element look extremely stupid, but it is precisely the kind of behavior that almost every RTS game has in some form. Detecting this kind of “stalling” and either having a contingency plan, or some kind of bailout behavior, is essential to help the intelligence of these games.
Chapter 6
Real-Time Strategy (RTS) Games
119
Another case of this is the classic problem in which a player has to kill all the units in the enemy’s army to win, and the AI has one peon unit, hidden behind a tree, somewhere on the huge world map. This leads to the player scouring the map, for an hour and a half, until the player happens upon the peon, who was just sitting there frozen with nothing to do. The AI in RTS games should be able to recognize when it’s been beaten (most do, but even the best get confused sometimes) and offer surrender. If the player wants to hunt down the last peon, the player can; but the designer should also give the player the chance to see his hard-won “Victory!” screen without spending all day hunting for some foolish unit. HELPER AI To alleviate micromanagement tasks that a human player performs repeatedly during the game, helper AI is an area that screams for exploration by developers. Also mentioned in Chapter 4 during the discussion of RPG party members, “automatic” behavior that units perform on their own could be improved. A flexible system could add new behaviors (if the game recognizes that the player is always doing a specific small behavior), exhaust unwanted behaviors, and perform with mild intelligence. It would make playing RTS games much more flavorful than the current “build up, attack, build up, attack” click-fest, in which the person who knows the best build order and can get things done the fastest wins. Sometimes, yes, that is exactly the game some people want to play. But right now we don’t have much of a choice, as it seems to be the way most RTS games are set up. In effect, this system would recognize small behavior macros (groups of behaviors that the human is repeatedly doing) and then either ask the player if he needs help in doing that or just take over the task (possibly with some sort of “It’s taken care of ” message communicated to the player). The player could select the level of macro help he’d like, with level 0 being no help, level 5 would find things repeated more than five times and would extinguish these behaviors if the player cancelled out of them more than once, and at level 10 it would discern anything the player repeated more than twice; the macro would never extinguish these rules. At any rate, you would probably also want little macro “flags” to appear somewhere onscreen (or in some quick menu), so that the player could cancel any that the player wanted to at any time. OPPONENT PERSONALITY One of the earliest RTS games, Herzog Zwei, had two opposing AI personalities (heavily offense-based and heavily defense-based). Each offered a very different playing experience. A player had lots of time to build forces against the defensive opponent, whereas the player had almost no time at all before the more offensebased AI would be at the player’s main base with invaders.
120
AI Game Engine Programming
Imagine getting variation not just in difficulty level of the AI, but in other attributes as well. We do this in sports games or fighting games, why not in RTS games? By using resource allocation systems to describe bias toward specific units, or specialization in different branches of the tech tree, we could generate opponents with much more flavor. In the development phase, different stable personalities could be tuned and played against each other, to find the combinations that lead to victory. These personalities could even be replaced by a singular AI opponent over time, so the AI opponent would start play with a very balanced game, but after a brutal combat loss might get “mad” and use a much more aggressive resource allocation table to force out more units, for retribution. This would not only flavor the AI battle, but could carry over into the diplomacy game. A player might reconsider allying with an AI character that the player knows has a tendency to turn on its allies, or is a hothead and will become angered by the smallest incursion, turning the supposed ally into a liability if the AI character is off hunting a perceived enemy instead of sticking to a larger agreed-upon battle plan. MORE STRATEGY, LESS TACTICS AI micromanagement leads to better per-unit behavior. To be considered humanlike, however, RTS games need better strategic team leadership, not individual-unit intelligence that outdoes the human in speed or tedium. Instead of better planning algorithms and squad (or commander)-level AI, which is more analogous to the way a human plays, most games rely on the computer’s ability to quickly micromanage attacking units on an individual basis. Another commonly used technique is to have unit AI that is not present when a human player is under control, which makes it feel like micromanagement. This leaves the AI able to do things that are near impossible for a human, which leads to frustration, and a feeling that the AI is cheating. Perhaps the AI could be given limits on the amount of micromanaging it can do in a given timeframe, to simulate the time it takes a human to scroll around, clicking the mouse and hitting hotkeys. In any case, better strategic sy