Artificial Intelligence in Games: Choosing the Right Decision Model

???????????Different models exist to make intelligent non-player characters (NPCs) in games. Which model is the best? Is there a one-size-fits-all model? What are the merits and weaknesses of each decision model? This article provides insight into making rational trade-offs when choosing between game artificial intelligence (AI) decision models.

???????????Decision models in the context of game AI are capabilities that enable game agents to make introspective choices like when to run and when to walk; when to attack and when to retreat; how best to defeat an opponent; an optimal difficulty level for the player; or even how to proceed as part of a crowd or battalion. Notice that while some of these scenarios are Boolean in nature, that is, they have only one of two outcomes - true or false, others are not. For instance, choosing when to run or walk might be based on the presence of an enemy that can be easily scripted, whereas choosing an optimal level for the player would require adaptability and consideration of external factors.

???????????This tussle between scripting and adaptability is better defined in the game world as authorial control and autonomy. Decision models with higher authorial control have well-defined and predictable outcomes that the developers can easily tweak, as opposed to more autonomous models that consider various external factors and are more unpredictable. Fig 1.0 shows these models on a spectrum from authorial control to autonomy.

Comparing Game AI Decision Models

???????????Good old finite state machines (FSMs) have proven to be highly dependable in the industry. This is because of its simplicity. FSMs have well-defined states and transitions that enable NPCs to behave intelligently hence the reason why it is on the authorial control end of the spectrum in Fig 1.0. Sadly, though, FSMs do not scale well. Over the course of a game's development, the number of FSMs can explode exponentially, making maintenance cumbersome and error-prone. Also, FSMs are ill-equipped to handle reuse because they always start in an initial state.

???????????Hierarchical FSMs (HFSMs) build upon FSMs by providing more structural control. For example, they allow nested state management which can be used to create “history states” through hysteresis thus facilitating reusability.

???????????Similar to FSMs behavior trees (BTs), are simple, tree-like decision models that rank high on authorial control. However, they scale better than FSMs because they do not have states and consequently do not need to remember previous actions before embarking on the next actions. Rather BTs run every root in their trees until a tree node meets the stipulated precondition, then only that tree node is executed as shown in Fig 2.0. BTs should not be considered a silver bullet because although they scale better than FSMs, they can be computationally expensive since they must recurse from the tree's root each time a behavior is selected. On mobile devices, this poses a big challenge due to limited resources. Furthermore, they should not be used for behaviors that inherently rely on other behaviors as this can lead to an endless loop.

???????????Conversely, utility AI models apply utility theory to decision-making. This theory is based on the idea that in a pool of options, there is no one right choice, instead, choices are chosen based on relative suitability, considering all factors, internal and external. For instance, in The Sims game, where utility AI is used for decision-making, the NPCs consider external and internal factors like, “very hungry”, “poor food”; and “little hungry”, “spectacular food” to calculate a floating-point preferability score that informs its autonomous choice, “eat”. While using utility AI models can achieve dynamism that appears to “make sense” instead of being entirely random, it is pertinent to bear in mind that what might “make sense” to the computer might not make sense to a player and would end up ruining their gaming experience. Hence, for certain behaviors requiring more predictable outcomes, Utility AI model should be combined with models with more authorial control like BTs.

???????????Finally, planners, unlike the previously discussed decision models are models that allow game designers to be expressive. Rather than detailing how a behavior is to be accomplished, two things are described. First, the goal. This could be transporting the NPC from point A to point B. The second is a description of the game world. “Bicycle game objects can move along paths”, and “cars can also move along paths”. Using these, planners can perform forward or backward chaining searches to accomplish behaviors like navigation. Backward chain search planners have the benefit of discovering approaches that might not have been envisioned by the game designer but can also detract from the overall game storyline because of the combination of character-centric decision-making and autonomy.

Reactivity vs Deliberation

???????????Reactivity is the ability of an NPC to respond to changes in its environment within a short time frame, while deliberation is the behavior of an NPC that is pre-conceived and sustained over a period.

??????????? Reactivity and Deliberation are two different concepts that require different decision models. When choosing the right decision model for an in-game behavior, it is necessary to determine whether that behavior is reactive or deliberate. More reactive behaviors should use more autonomous models. On the other hand, more deliberate behaviors require some form of authorial control.

Crowd Movement

???????????Crowd movement follows the flocking algorithm defined by Craig Reynolds. It is based on three key components: separation, alignment, and cohesion. ???????????

???????????Controlling a group of game objects might seem cumbersome at first thought, but with the help of a flocking algorithm, a decision model with high authorial control like scripting can be used to implement crowd movement. All the script needs to do is to avoid collision between flock members, set a minimum distance for each flock member, and move each member as an entity of the flock by aligning them towards the average position of each flock member.

Conclusion

???????????What is the best decision model for game AI? As with all things in programming, the correct answer is, you guessed it, it depends. Is there a one-size-fits-all model? No, models exist on a spectrum from authorial control to autonomy. What works for one behavior might not work for the other. What are the merits and weaknesses of each decision model? FSMs and BTs are simple, intuitive, and predictable with the former being hard to scale and the latter being more computationally expensive. On the other hand, while Utility AI and Planners have more autonomy and can offer adaptability and realistic dynamism they are also less predictable and can defeat the purpose of an immersive and engaging gameplay experience.