Game AI Pro 360: Guide to Architecture

Steve Rabin

• Publisher: CRC Press
• Year: 2019
• ISBN:
  9780429619717
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

Steve Rabin's Game AI Pro 360: Guide to Architecture gathers all the cutting-edge information from his previous three Game AI Pro volumes into a convenient single source anthology covering game AI architecture. This volume is complete with articles by leading game AI programmers that further explore modern architecture such as behavior trees and share architectures used in top games such as Final Fantasy XV, the Call of Duty series and the Guild War series.

Key Features

• Provides real-life case studies of game AI in published commercial games

• 
  
  

• Material by top developers and researchers in Game AI

• 
  
  

• Downloadable demos and/or source code available online

• 
  
  

1

Behavior Selection Algorithms

An Overview

Michael Dawe, Steve Gargolinski, Luke Dicken, Troy Humphreys, and Dave Mark

1.1Introduction

1.2Finite-State Machines

1.3Hierarchical Finite-State Machines

1.4Behavior Trees

1.5Utility Systems

1.6Goal-Oriented Action Planners

1.7Hierarchical Task Networks

1.8Conclusion

References

1.1 Introduction

Writing artificial intelligence systems for games has become increasingly complicated as console gamers demand more from their purchases. At the same time, smaller games for mobile platforms have burst onto the scene, making it important for an AI programmer to know how to get the best behavior out of a short frame time.

Even on complicated games running on powerful machines, NPCs can range from simple animals the player might run past or hunt to full-fledged companion characters that need to stand up to hours of player interaction. While each of these example AIs may follow the Sense–Think–Act cycle, the “think” part of that cycle is ill-defined. There are a variety of algorithms to choose from, and each is appropriate for different uses. What might be the best choice to implement a human character on the latest consoles might not be suitable for creating an adversarial player for a web-based board game.

This article will present some of the most popular and proven decision-making algorithms in the industry, providing an overview of these choices and showing when each might be the best selection to use. While it is not a comprehensive resource, hopefully it will prove a good introduction to the variety of algorithmic choices available to the AI programmer.

1.2 Finite-State Machines

Finite-state machines (FSMs) are the most common behavioral modeling algorithm used in game AI programming today. FSMs are conceptually simple and quick to code, resulting in a powerful and flexible AI structure with little overhead. They are intuitive and easy to visualize, which facilitates communication with less-technical team members. Every game AI programmer should be comfortable working with FSMs and be aware of their strengths and weaknesses.

An FSM breaks down an NPC’s overall AI into smaller, discrete pieces known as states. Each state represents a specific behavior or internal configuration, and only one state is considered “active” at a time. States are connected by transitions, directed links responsible for switching to a new active state whenever certain conditions are met.

One compelling feature of FSMs is that they are easy to sketch out and visualize. A rounded box represents each state, and an arrow connecting two boxes signifies a transition between states. The labels on the transition arrows are the conditions necessary for that transition to fire. The solid circle indicates the initial state, the state to be entered when the FSM is first run. As an example, suppose we are designing an FSM for an NPC to guard a castle, as in Figure 1.1.

Our guard NPC starts out in the Patrol state, where he follows his route and keeps an eye on his part of the castle. If he hears a noise, then he leaves Patrol and moves to Investigate the noise for a bit before returning to Patrol. If at any point he sees an enemy, he will move into Attack to confront the threat. While attacking, if his health drops too low, he’ll Flee to hopefully live another day. If he defeats the enemy, he’ll return to Patrol.

While there are many possible FSM implementations, it is helpful to look at an example implementation of the algorithm. First is the FSMState class, which each of our concrete states (Attack, Patrol, etc.) will extend:

Figure 1.1

This FSM diagram represents the behavior of a guard NPC.

 class FSMState { virtual void onEnter(); virtual void onUpdate(); virtual void onExit(); list<FSMTransition> transitions; };

Each FSMState has the opportunity to execute logic at three different times: when the state is entered, when it is exited, and on each tick when the state is active and no transitions are firing. Each state is also responsible for storing a list of FSMTransition objects, which represent all potential transitions out of that state.

 class FSMTransition { virtual bool isValid(); virtual FSMState* getNextState(); virtual void onTransition(); }

Each transition in our graph extends from FSMTransition. The isValid() function evaluates to true when this transition’s conditions are met, and getNextState() returns which state to transition to when valid. The onTransition() function is an opportunity to execute any necessary behavioral logic when a transition fires, similar to onEnter() in FSMState.

Finally, the FiniteStateMachine class:

 class FiniteStateMachine { void update(); list<FSMState> states; FSMState* initialState; FSMState* activeState; }

The FiniteStateMachine class contains a list of all states in our FSM, as well as the initial state and the current active state. It also contains the central update() function, which is called each tick and is responsible for running our behavioral algorithm as follows:

• Call isValid() on each transition in activeState.transtitions until isValid() returns true or there are no more transitions.
• If a valid transition is found, then:
  • Call activeState.onExit()
  • Set activeState to validTransition.getNextState()
  • Call activeState.onEnter()
• If a valid transition is not found, then call activeState.onUpdate()

With this structure in place, it’s a matter of setting up transitions and filling out the onEnter(), onUpdate(), onExit(), and onTransition() functions to produce the desired AI behavior. These specific implementations are entirely design dependent. For example, say our Attack state triggers some dialogue, “There he is, get him!” in onEnter() and uses onUpdate() to periodically choose tactical positions, move to cover, fire on the enemy, and so on. The transition between Attack and Patrol can trigger some additional dialogue: “Threat eliminated!” in onTransition().

Before starting to code your FSM, it can be helpful to sketch a few diagrams like the one in Figure 1.1 to help define the logic of the behaviors and how they interconnect. Start writing the code once the different states and transitions are understood. FSMs are flexible and powerful, but they only work as well as the thought that goes into developing the underlying logic.

1.3 Hierarchical Finite-State Machines

FSMs are a useful tool, but they do have weaknesses. Adding the second, third, or fourth state to an NPC’s FSM is usually structurally trivial, as all that’s needed is to hook up transitions to the few existing required states. However, if you’re nearing the end of development and your FSM is already complicated with 10, 20, or 30 existing states, then fitting your new state into the existing structure can be extremely difficult and error-prone.

There are also some common patterns that FSMs are not well-equipped to handle, such as situational behavior reuse. To show an example of this, Figure 1.2 shows a night watchman NPC responsible for guarding a safe in a building.

This NPC will simply patrol between the front door and the safe forever. Suppose a new state called Conversation is to be added that allows our night watchman to respond to a cell phone call, pause to have a brief conversation, and return to his patrol. If the watchman is in Patrol to Door when the call comes in, then we want him to resume patrolling to the door when the conversation is complete. Likewise, if he is in Patrol to Safe when the phone rings, he should return to Patrol to Safe when transitioning out of Conversation.

Since we need to know which state to transition back to after the call, we’re forced to create a new Conversation state each time we want to reuse the behavior, as shown in Figure 1.3.

In this simple example we require two Conversation behaviors to achieve the desired result, and in a more complicated FSM we might require many more. Adding additional states in this manner every time we want to reuse a behavior is not ideal or elegant. It leads to an explosion of states and graph complexity, making the existing FSM harder to understand and new states ever more difficult and error-prone to add.

Thankfully, there is a technique that will alleviate some of these structural issues: the Hierarchical Finite-State Machine (HFSM). In an HFSM, each individual state can be an entire state machine itself. This technique effectively separates one state machine into multiple state machines arranged in a hierarchy.

Figure 1.2

This FSM diagram represents the behavior of a night watchman NPC.

Figure 1.3

Our night watchman FSM requires multiple instances of the Conversation state.

Figure 1.4

An HFSM solves the problem of duplicate Conversation states.

Returning to the night watchman example, if we nest our two Patrol states into a state machine called Watch Building, then we can get by with just one Conversation state, as shown in Figure 1.4.

The reason this works is that the HFSM structure adds additional hysteresis that isn’t present in an FSM. With a standard FSM, we can always assume that the state machine starts off in its initial state, but this is not the case with a nested state machine in an HFSM. Note the circled “H” in Figure 1.4, which points to the “history state.” The first time we enter the nested Watch Building state machine, the history state indicates the initial state, but from then on it indicates the most recent active state of that state machine.

Our example HFSM starts out in Watch Building (indicated by the solid circle and arrow as before), which chooses Patrol to Safe as the initial state. If our NPC reaches the safe and transitions into Patrol to Door, then the history state switches to Patrol to Door. If the NPC’s phone rings at this point, then our HFSM exits Patrol to Door and Watch Building, transitioning to the Conversation state. After Conversation ends, the HFSM will transition back to Watch Building which resumes in Patrol to Door (the history state), not Patrol to Safe (the initial state).

As you can see, this setup achieves our design goal without requiring duplication of any states. Generally, HFSMs provide much more structural control over the layout of states, allowing larger, complex behaviors to be broken down into smaller, simpler pieces.

The algorithm for updating an HFSM is similar to updating an FSM, with added recursive complexity due to the nested state machines. Pseudocode implementation is fairly complicated, and beyond the scope of this overview article. For a solid detailed implementation, check out Section 5.3.9 in the book Artificial Intelligence for Games by Ian Millington and John Funge [Millington and Funge 09].

FSMs and HFSMs are incredibly useful algorithms for solving a wide variety of problems that game AI programmers typically face. As discussed there are many pros to using an FSM, but there are also some cons. One of the major potential downsides of FSMs is that your desired behavior might not fit into the structure elegantly. HFSMs can help alleviate this pressure in some cases, but not all. For example, if an FSM suffers from “transition overload” and hooks up every state to every other state, and if an HFSM isn’t helping, other algorithms may be a better choice. Review the techniques in this article, think about your problem, and choose the best tool for the job.

1.4 Behavior Trees

A behavior tree describes a data structure starting from some root node and made up of behaviors, which are individual actions an NPC can perform. Each behavior can in turn have child behaviors, which gives the algorithm its tree-like qualities.

Every behavior defines a precondition, which specifies the conditions where the agent will execute this behavior, and an a...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• About the Editor
• About the Contributors
• Introduction
• 1 Behavior Selection Algorithms: An Overview
• 2 Structural Architecture—Common Tricks of the Trade
• 3 The Behavior Tree Starter Kit
• 4 Real-World Behavior Trees in Script
• 5 Simulating Behavior Trees: A Behavior Tree/Planner Hybrid Approach
• 6 An Introduction to Utility Theory
• 7 Building Utility Decisions into Your Existing Behavior Tree
• 8 Reactivity and Deliberation in Decision-Making Systems
• 9 Exploring HTN Planners through Example
• 10 Hierarchical Plan-Space Planning for Multi-unit Combat Maneuvers
• 11 Phenomenal AI Level-of-Detail Control with the LOD Trader
• 12 Runtime Compiled C++ for Rapid AI Development
• 13 Plumbing the Forbidden Depths: Scripting and AI
• 14 Possibility Maps for Opportunistic AI and Believable Worlds
• 15 Production Rules Implementation in 1849
• 16 Production Systems: New Techniques in AAA Games
• 17 Building a Risk-Free Environment to Enhance Prototyping: Hinted-Execution Behavior Trees
• 18 Smart Zones to Create the Ambience of Life
• 19 Separation of Concerns Architecture for AI and Animation
• 20 Optimizing Practical Planning for Game AI
• 21 Modular AI
• 22 Overcoming Pitfalls in Behavior Tree Design
• 23 From Behavior to Animation: A Reactive AI Architecture for Networked First-Person Shooter Games
• 24 A Character Decision-Making System for FINAL FANTASY XV by Combining Behavior Trees and State Machines
• 25 A Reusable, Light-Weight Finite-State Machine
• 26 Choosing Effective Utility-Based Considerations
• 27 Combining Scripted Behavior with Game Tree Search for Stronger, More Robust Game AI