Cover image for AI for Games, Third Edition, 3rd Edition

AI for Games, Third Edition, 3rd Edition

Author Ian Millington
Release Date: 2019/03/01
ISBN: 9781351053280
Topic:
0%
29
Chapters
0-1
Hours read
0k
Total Words
    Start Reading Now    
       Add to Wishlist       
View table of contents

AI is an integral part of every video game. This book helps professionals keep up with the constantly evolving technological advances in the fast growing game industry and equips students with up-to-date information they need to jumpstart their careers. This revised and updated Third Edition includes new techniques, algorithms, data structures and representations needed to create powerful AI in games.

Key Features

  • A comprehensive professional tutorial and reference to implement true AI in games
  • Includes new exercises so readers can test their comprehension and understanding of the concepts and practices presented
  • Revised and updated to cover new techniques and advances in AI
  • Walks the reader through the entire game AI development process

  • Table of Contents

    1. Cover
    2. Half Title
    3. Title Page
    4. Copyright Page
    5. Dedication
    6. Table of Contents
    7. PART I AI and Games
      1. CHAPTER 1 INTRODUCTION
      2. 1.1 What Is AI?
      3. 1.1.1 Academic AI
      4. 1.1.2 Game AI
      5. 1.2 Model of Game AI
      6. 1.2.1 Movement
      7. 1.2.2 Decision Making
      8. 1.2.3 Strategy
      9. 1.2.4 Infrastructure
      10. 1.2.5 Agent-Based AI
      11. 1.2.6 In the Book
      12. 1.3 Algorithms and Data Structures
      13. 1.3.1 Algorithms
      14. 1.3.2 Representations
      15. 1.3.3 Implementation
      16. 1.4 Layout of the Book
      17. CHAPTER 2 GAME AI
      18. 2.1 The Complexity Fallacy
      19. 2.1.1 When Simple Things Look Good
      20. 2.1.2 When Complex Things Look Bad
      21. 2.1.3 The Perception Window
      22. 2.1.4 Changes of Behavior
      23. 2.2 The Kind of AI in Games
      24. 2.2.1 Hacks
      25. 2.2.2 Heuristics
      26. 2.2.3 Algorithms
      27. 2.3 Speed and Memory Constraints
      28. 2.3.1 Processor Issues
      29. 2.3.2 Memory Concerns
      30. 2.3.3 Platforms
      31. 2.4 The AI Engine
      32. 2.4.1 Structure of an AI Engine
      33. 2.4.2 Tool Concerns
      34. 2.4.3 Putting It All Together
    8. PART II Techniques
      1. CHAPTER 3 MOVEMENT
      2. 3.1 The Basics of Movement Algorithms
      3. 3.1.1 Two-Dimensional Movement
      4. 3.1.2 Statics
      5. 3.1.3 Kinematics
      6. 3.2 Kinematic Movement Algorithms
      7. 3.2.1 Seek
      8. 3.2.2 Wandering
      9. 3.3 Steering Behaviors
      10. 3.3.1 Steering Basics
      11. 3.3.2 Variable Matching
      12. 3.3.3 Seek and Flee
      13. 3.3.4 Arrive
      14. 3.3.5 Align
      15. 3.3.6 Velocity Matching
      16. 3.3.7 Delegated Behaviors
      17. 3.3.8 Pursue and Evade
      18. 3.3.9 Face
      19. 3.3.10 Looking Where You’re Going
      20. 3.3.11 Wander
      21. 3.3.12 Path Following
      22. 3.3.13 Separation
      23. 3.3.14 Collision Avoidance
      24. 3.3.15 Obstacle and Wall Avoidance
      25. 3.3.16 Summary
      26. 3.4 Combining Steering Behaviors
      27. 3.4.1 Blending and Arbitration
      28. 3.4.2 Weighted Blending
      29. 3.4.3 Priorities
      30. 3.4.4 Cooperative Arbitration
      31. 3.4.5 Steering Pipeline
      32. 3.5 Predicting Physics
      33. 3.5.1 Aiming and Shooting
      34. 3.5.2 Projectile Trajectory
      35. 3.5.3 The Firing Solution
      36. 3.5.4 Projectiles with Drag
      37. 3.5.5 Iterative Targeting
      38. 3.6 Jumping
      39. 3.6.1 Jump Points
      40. 3.6.2 Landing Pads
      41. 3.6.3 Hole Fillers
      42. 3.7 Coordinated Movement
      43. 3.7.1 Fixed Formations
      44. 3.7.2 Scalable Formations
      45. 3.7.3 Emergent Formations
      46. 3.7.4 Two-Level Formation Steering
      47. 3.7.5 Implementation
      48. 3.7.6 Extending to More Than Two Levels
      49. 3.7.7 Slot Roles and Better Assignment
      50. 3.7.8 Slot Assignment
      51. 3.7.9 Dynamic Slots and Plays
      52. 3.7.10 Tactical Movement
      53. 3.8 Motor Control
      54. 3.8.1 Output Filtering
      55. 3.8.2 Capability-Sensitive Steering
      56. 3.8.3 Common Actuation Properties
      57. 3.9 Movement in the Third Dimension
      58. 3.9.1 Rotation in Three Dimensions
      59. 3.9.2 Converting Steering Behaviors to Three Dimensions
      60. 3.9.3 Align
      61. 3.9.4 Align to Vector
      62. 3.9.5 Face
      63. 3.9.6 Look Where You’re Going
      64. 3.9.7 Wander
      65. 3.9.8 Faking Rotation Axes
      66. CHAPTER 4 PATHFINDING
      67. 4.1 The Pathfinding Graph
      68. 4.1.1 Graphs
      69. 4.1.2 Weighted Graphs
      70. 4.1.3 Directed Weighted Graphs
      71. 4.1.4 Terminology
      72. 4.1.5 Representation
      73. 4.2 Dijkstra
      74. 4.2.1 The Problem
      75. 4.2.2 The Algorithm
      76. 4.2.3 Pseudo-Code
      77. 4.2.4 Data Structures and Interfaces
      78. 4.2.5 Performance of Dijkstra
      79. 4.2.6 Weaknesses
      80. 4.3 A*
      81. 4.3.1 The Problem
      82. 4.3.2 The Algorithm
      83. 4.3.3 Pseudo-Code
      84. 4.3.4 Data Structures and Interfaces
      85. 4.3.5 Implementation Notes
      86. 4.3.6 Algorithm Performance
      87. 4.3.7 Node Array A*
      88. 4.3.8 Choosing a Heuristic
      89. 4.4 World Representations
      90. 4.4.1 Tile Graphs
      91. 4.4.2 Dirichlet Domains
      92. 4.4.3 Points of Visibility
      93. 4.4.4 Navigation Meshes
      94. 4.4.5 Non-Translational Problems
      95. 4.4.6 Cost Functions
      96. 4.4.7 Path Smoothing
      97. 4.5 Improving on A*
      98. 4.6 Hierarchical Pathfinding
      99. 4.6.1 The Hierarchical Pathfinding Graph
      100. 4.6.2 Pathfinding on the Hierarchical Graph
      101. 4.6.3 Hierarchical Pathfinding on Exclusions
      102. 4.6.4 Strange Effects of Hierarchies on Pathfinding
      103. 4.6.5 Instanced Geometry
      104. 4.7 Other Ideas in Pathfinding
      105. 4.7.1 Open Goal Pathfinding
      106. 4.7.2 Dynamic Pathfinding
      107. 4.7.3 Other Kinds of Information Reuse
      108. 4.7.4 Low Memory Algorithms
      109. 4.7.5 Interruptible Pathfinding
      110. 4.7.6 Pooling Planners
      111. 4.8 Continuous Time Pathfinding
      112. 4.8.1 The Problem
      113. 4.8.2 The Algorithm
      114. 4.8.3 Implementation Notes
      115. 4.8.4 Performance
      116. 4.8.5 Weaknesses
      117. 4.9 Movement Planning
      118. 4.9.1 Animations
      119. 4.9.2 Movement Planning
      120. 4.9.3 Example
      121. 4.9.4 Footfalls
      122. CHAPTER 5 DECISION MAKING
      123. 5.1 Overview of Decision Making
      124. 5.2 Decision Trees
      125. 5.2.1 The Problem
      126. 5.2.2 The Algorithm
      127. 5.2.3 Pseudo-Code
      128. 5.2.4 Knowledge Representation
      129. 5.2.5 Implementation Notes
      130. 5.2.6 Performance of Decision Trees
      131. 5.2.7 Balancing the Tree
      132. 5.2.8 Beyond the Tree
      133. 5.2.9 Random Decision Trees
      134. 5.3 State Machines
      135. 5.3.1 The Problem
      136. 5.3.2 The Algorithm
      137. 5.3.3 Pseudo-Code
      138. 5.3.4 Data Structures and Interfaces
      139. 5.3.5 Performance
      140. 5.3.6 Implementation Notes
      141. 5.3.7 Hard-Coded FSM
      142. 5.3.8 Hierarchical State Machines
      143. 5.3.9 Combining Decision Trees and State Machines
      144. 5.4 Behavior Trees
      145. 5.4.1 Implementing Behavior Trees
      146. 5.4.2 Pseudo-Code
      147. 5.4.3 Decorators
      148. 5.4.4 Concurrency and Timing
      149. 5.4.5 Adding Data to Behavior Trees
      150. 5.4.6 Reusing Trees
      151. 5.4.7 Limitations of Behavior Trees
      152. 5.5 Fuzzy Logic
      153. 5.5.1 A Warning
      154. 5.5.2 Introduction to Fuzzy Logic
      155. 5.5.3 Fuzzy Logic Decision Making
      156. 5.5.4 Fuzzy State Machines
      157. 5.6 Markov Systems
      158. 5.6.1 Markov Processes
      159. 5.6.2 Markov State Machine
      160. 5.7 Goal-Oriented Behavior
      161. 5.7.1 Goal-Oriented Behavior
      162. 5.7.2 Simple Selection
      163. 5.7.3 Overall Utility
      164. 5.7.4 Timing
      165. 5.7.5 Overall Utility GOAP
      166. 5.7.6 GOAP with IDA*
      167. 5.7.7 Smelly GOB
      168. 5.8 Rule-Based Systems
      169. 5.8.1 The Problem
      170. 5.8.2 The Algorithm
      171. 5.8.3 Pseudo-Code
      172. 5.8.4 Data Structures and Interfaces
      173. 5.8.5 Rule Arbitration
      174. 5.8.6 Unification
      175. 5.8.7 Rete
      176. 5.8.8 Extensions
      177. 5.8.9 Where Next
      178. 5.9 Blackboard Architectures
      179. 5.9.1 The Problem
      180. 5.9.2 The Algorithm
      181. 5.9.3 Pseudo-Code
      182. 5.9.4 Data Structures and Interfaces
      183. 5.9.5 Performance
      184. 5.9.6 Other Things Are Blackboard Systems
      185. 5.10 Action Execution
      186. 5.10.1 Types of Action
      187. 5.10.2 The Algorithm
      188. 5.10.3 Pseudo-Code
      189. 5.10.4 Data Structures and Interfaces
      190. 5.10.5 Implementation Notes
      191. 5.10.6 Performance
      192. 5.10.7 Putting It All Together
      193. CHAPTER 6 TACTICAL AND STRATEGIC AI
      194. 6.1 Waypoint Tactics
      195. 6.1.1 Tactical Locations
      196. 6.1.2 Using Tactical Locations
      197. 6.1.3 Generating the Tactical Properties of a Waypoint
      198. 6.1.4 Automatically Generating the Waypoints
      199. 6.1.5 The Condensation Algorithm
      200. 6.2 Tactical Analyses
      201. 6.2.1 Representing the Game Level
      202. 6.2.2 Simple Influence Maps
      203. 6.2.3 Terrain Analysis
      204. 6.2.4 Learning with Tactical Analyses
      205. 6.2.5 A Structure for Tactical Analyses
      206. 6.2.6 Map Flooding
      207. 6.2.7 Convolution Filters
      208. 6.2.8 Cellular Automata
      209. 6.3 Tactical Pathfinding
      210. 6.3.1 The Cost Function
      211. 6.3.2 Tactic Weights and Concern Blending
      212. 6.3.3 Modifying the Pathfinding Heuristic
      213. 6.3.4 Tactical Graphs for Pathfinding
      214. 6.3.5 Using Tactical Waypoints
      215. 6.4 Coordinated Action
      216. 6.4.1 Multi-Tier AI
      217. 6.4.2 Emergent Cooperation
      218. 6.4.3 Scripting Group Actions
      219. 6.4.4 Military Tactics
      220. CHAPTER 7 LEARNING
      221. 7.1 Learning Basics
      222. 7.1.1 Online or Offline Learning
      223. 7.1.2 Intra-Behavior Learning
      224. 7.1.3 Inter-Behavior Learning
      225. 7.1.4 A Warning
      226. 7.1.5 Over-Learning
      227. 7.1.6 The Zoo of Learning Algorithms
      228. 7.1.7 The Balance of Effort
      229. 7.2 Parameter Modification
      230. 7.2.1 The Parameter Landscape
      231. 7.2.2 Hill Climbing
      232. 7.2.3 Extensions to Basic Hill Climbing
      233. 7.2.4 Annealing
      234. 7.3 Action Prediction
      235. 7.3.1 Left or Right
      236. 7.3.2 Raw Probability
      237. 7.3.3 String Matching
      238. 7.3.4 N-Grams
      239. 7.3.5 Window Size
      240. 7.3.6 Hierarchical N-Grams
      241. 7.3.7 Application in Combat
      242. 7.4 Decision Learning
      243. 7.4.1 The Structure of Decision Learning
      244. 7.4.2 What Should You Learn?
      245. 7.4.3 Four Techniques
      246. 7.5 Naive Bayes Classifiers
      247. 7.5.1 Pseudo-Code
      248. 7.5.2 Implementation Notes
      249. 7.6 Decision Tree Learning
      250. 7.6.1 ID3
      251. 7.6.2 ID3 with Continuous Attributes
      252. 7.6.3 Incremental Decision Tree Learning
      253. 7.7 Reinforcement Learning
      254. 7.7.1 The Problem
      255. 7.7.2 The Algorithm
      256. 7.7.3 Pseudo-Code
      257. 7.7.4 Data Structures and Interfaces
      258. 7.7.5 Implementation Notes
      259. 7.7.6 Performance
      260. 7.7.7 Tailoring Parameters
      261. 7.7.8 Weaknesses and Realistic Applications
      262. 7.7.9 Other Ideas in Reinforcement Learning
      263. 7.8 Artificial Neural Networks
      264. 7.8.1 Overview
      265. 7.8.2 The Problem
      266. 7.8.3 The Algorithm
      267. 7.8.4 Pseudo-Code
      268. 7.8.5 Data Structures and Interfaces
      269. 7.8.6 Implementation Caveats
      270. 7.8.7 Performance
      271. 7.8.8 Other Approaches
      272. 7.9 Deep Learning
      273. 7.9.1 What is Deep Learning?
      274. 7.9.2 Data
      275. CHAPTER 8 PROCEDURAL CONTENT GENERATION
      276. 8.1 Pseudorandom Numbers
      277. 8.1.1 Numeric Mixing and Game Seeds
      278. 8.1.2 Halton Sequence
      279. 8.1.3 Phyllotaxic Angles
      280. 8.1.4 Poisson Disk
      281. 8.2 Lindenmayer Systems
      282. 8.2.1 Simple L-systems
      283. 8.2.2 Adding Randomness to L-systems
      284. 8.2.3 Stage-Specific Rules
      285. 8.3 Landscape Generation
      286. 8.3.1 Modifiers and Height-Maps
      287. 8.3.2 Noise
      288. 8.3.3 Perlin Noise
      289. 8.3.4 Faults
      290. 8.3.5 Thermal Erosion
      291. 8.3.6 Hydraulic Erosion
      292. 8.3.7 Altitude Filtering
      293. 8.4 Dungeons and Maze Generation
      294. 8.4.1 Mazes by Depth First Backtracking
      295. 8.4.2 Minimum Spanning Tree Algorithms
      296. 8.4.3 Recursive Subdivision
      297. 8.4.4 Generate and Test
      298. 8.5 Shape Grammars
      299. 8.5.1 Running the Grammar
      300. 8.5.2 Planning
      301. CHAPTER 9 BOARD GAMES
      302. 9.1 Game Theory
      303. 9.1.1 Types of Games
      304. 9.1.2 The Game Tree
      305. 9.2 Minimaxing
      306. 9.2.1 The Static Evaluation Function
      307. 9.2.2 Minimaxing
      308. 9.2.3 The Minimaxing Algorithm
      309. 9.2.4 Negamaxing
      310. 9.2.5 AB Pruning
      311. 9.2.6 The AB Search Window
      312. 9.2.7 Negascout
      313. 9.3 Transposition Tables and Memory
      314. 9.3.1 Hashing Game States
      315. 9.3.2 What to Store in the Table
      316. 9.3.3 Hash Table Implementation
      317. 9.3.4 Replacement Strategies
      318. 9.3.5 A Complete Transposition Table
      319. 9.3.6 Transposition Table Issues
      320. 9.3.7 Using Opponent’s Thinking Time
      321. 9.4 Memory-Enhanced Test Algorithms
      322. 9.4.1 Implementing Test
      323. 9.4.2 The MTD Algorithm
      324. 9.4.3 Pseudo-Code
      325. 9.5 Monte Carlo Tree Search (MCTS)
      326. 9.5.1 Pure Monte Carlo Tree Search
      327. 9.5.2 Adding Knowledge
      328. 9.6 Opening Books and Other Set Plays
      329. 9.6.1 Implementing an Opening Book
      330. 9.6.2 Learning for Opening Books
      331. 9.6.3 Set Play Books
      332. 9.7 Further Optimizations
      333. 9.7.1 Iterative Deepening
      334. 9.7.2 Variable Depth Approaches
      335. 9.8 Game Knowledge
      336. 9.8.1 Creating a Static Evaluation Function
      337. 9.8.2 Learning the Static Evaluation Function
      338. 9.9 Turn-Based Strategy Games
      339. 9.9.1 Impossible Tree Size
      340. 9.9.2 Real-Time AI in a Turn-Based Game
    9. PART III Supporting Technologies
      1. CHAPTER 10 EXECUTION MANAGEMENT
      2. 10.1 Scheduling
      3. 10.1.1 The Scheduler
      4. 10.1.2 Interruptible Processes
      5. 10.1.3 Load-Balancing Scheduler
      6. 10.1.4 Hierarchical Scheduling
      7. 10.1.5 Priority Scheduling
      8. 10.2 Anytime Algorithms
      9. 10.3 Level of Detail
      10. 10.3.1 Graphics Level of Detail
      11. 10.3.2 AI LOD
      12. 10.3.3 Scheduling LOD
      13. 10.3.4 Behavioral LOD
      14. 10.3.5 Group LOD
      15. 10.3.6 In Summary
      16. CHAPTER 11 WORLD INTERFACING
      17. 11.1 Communication
      18. 11.1.1 Polling
      19. 11.1.2 Events
      20. 11.1.3 Determining Which Approach to Use
      21. 11.2 Event Managers
      22. 11.2.1 Implementation
      23. 11.2.2 Event Casting
      24. 11.2.3 Inter-Agent Communication
      25. 11.3 Polling Stations
      26. 11.3.1 Pseudo-Code
      27. 11.3.2 Performance
      28. 11.3.3 Implementation Notes
      29. 11.3.4 Abstract Polling
      30. 11.4 Sense Management
      31. 11.4.1 Faking It
      32. 11.4.2 What Do We Know?
      33. 11.4.3 Sensory Modalities
      34. 11.4.4 Region Sense Manager
      35. 11.4.5 Finite Element Model Sense Manager
      36. CHAPTER 12 TOOLS AND CONTENT CREATION
      37. 12.0.1 Toolchains Limit AI
      38. 12.0.2 Where AI Knowledge Comes From
      39. 12.1 Knowledge for Pathfinding and Waypoints
      40. 12.1.1 Manually Creating Region Data
      41. 12.1.2 Automatic Graph Creation
      42. 12.1.3 Geometric Analysis
      43. 12.1.4 Data Mining
      44. 12.2 Knowledge for Movement
      45. 12.2.1 Obstacles
      46. 12.2.2 High-Level Staging
      47. 12.3 Knowledge for Decision Making
      48. 12.3.1 Object Types
      49. 12.3.2 Concrete Actions
      50. 12.4 The Toolchain
      51. 12.4.1 Integrated Game Engines
      52. 12.4.2 Custom Data-Driven Editors
      53. 12.4.3 AI Design Tools
      54. 12.4.4 Remote Debugging
      55. 12.4.5 Plug-Ins
      56. CHAPTER 13 PROGRAMMING GAME AI
      57. 13.1 Implementation Language
      58. 13.1.1 C++
      59. 13.1.2 C#
      60. 13.1.3 Swift
      61. 13.1.4 Java
      62. 13.1.5 JavaScript
      63. 13.2 Scripted AI
      64. 13.2.1 What Is Scripted AI?
      65. 13.2.2 What Makes a Good Scripting Language?
      66. 13.2.3 Embedding
      67. 13.2.4 Choosing an Open Source Language
      68. 13.2.5 A Language Selection
      69. 13.3 Creating a Language
      70. 13.3.1 Rolling Your Own
    10. PART IV Designing Game AI
      1. CHAPTER 14 DESIGNING GAME AI
      2. 14.1 The Design
      3. 14.1.1 Example
      4. 14.1.2 Evaluating the Behaviors
      5. 14.1.3 Selecting Techniques
      6. 14.1.4 The Scope of One Game
      7. 14.2 Shooters
      8. 14.2.1 Movement and Firing
      9. 14.2.2 Decision Making
      10. 14.2.3 Perception
      11. 14.2.4 Pathfinding and Tactical AI
      12. 14.2.5 Shooter-Like Games
      13. 14.2.6 Melee Combat
      14. 14.3 Driving
      15. 14.3.1 Movement
      16. 14.3.2 Pathfinding and Tactical AI
      17. 14.3.3 Driving-Like Games
      18. 14.4 Real-Time Strategy
      19. 14.4.1 Pathfinding
      20. 14.4.2 Group Movement
      21. 14.4.3 Tactical and Strategic AI
      22. 14.4.4 Decision Making
      23. 14.4.5 MOBAs
      24. 14.5 Sports
      25. 14.5.1 Physics Prediction
      26. 14.5.2 Playbooks and Content Creation
      27. 14.6 Turn-Based Strategy Games
      28. 14.6.1 Timing
      29. 14.6.2 Helping the Player
      30. CHAPTER 15 AI-BASED GAME GENRES
      31. 15.1 Teaching Characters
      32. 15.1.1 Representing Actions
      33. 15.1.2 Representing the World
      34. 15.1.3 Learning Mechanism
      35. 15.1.4 Predictable Mental Models
      36. 15.2 Flocking and Herding Games
      37. 15.2.1 Making the Creatures
      38. 15.2.2 Tuning Steering for Interactivity
      39. 15.2.3 Steering Behavior Stability
      40. 15.2.4 Ecosystem Design
    11. REFERENCES
      1. Books, Periodicals, Papers and Websites
      2. Games
    12. INDEX
    3.145.38.117