Chapter 3. Decision Making

In this chapter, we will cover the following recipes:

• Choosing through a decision tree

• Working a finite-state machine

• Improving FSMs: hierarchical finite-state machines

• Combining FSMs and decision trees

• Implementing behavior trees

• Working with fuzzy logic

• Representing states with numerical values: Markov system

• Making decisions with goal-oriented behaviors

Introduction

Making decisions or changing the game flow according to the game's state could get really messy if we rely only on simple control structures. That's why we will learn different decision-making techniques that are flexible enough to adapt to different types of games, and robust enough to let us build modular decision-making systems.

The techniques covered in the chapter are mostly related to trees, automata, and matrices. Also, some topics require a good understanding of how recursion, inheritance, and polymorphism work, so it is important that we review those topics if that is the case.

Choosing through a decision tree

One of the simplest mechanisms for tackling decision-making problems is decision trees, because they are fast and easy to grasp and implement. As a consequence, it's one of the most used techniques today; it is extensively used in other character-controlled scopes such as animations.

Getting ready

This recipe requires a good understanding of recursion and inheritance as we will constantly be implementing and calling virtual functions throughout the sections.

How to do it...

This recipe requires a lot of attention due to the number of files that we will need to handle. Overall, we will create a parent class DecisionTreeNode, from which we will derive the other ones. Finally, we will learn how to implement a couple of standard decision nodes:

1. First, create the parent class, DecisionTreeNode:

   using UnityEngine;
   using System.Collections;
   public class DecisionTreeNode : MonoBehaviour
   {
       public virtual DecisionTreeNode MakeDecision()
       {
           return null;
     ...

Working a finite-state machine

Another interesting yet easy-to-implement technique is finite-state machines (FSM). They move us to change the train of thought from what it was in the previous recipe. FSMs are great when our train of thought is more event-oriented, and we think in terms of holding behavior until a condition is met changing to another.

Getting ready

This is a technique mostly based on automata behavior, and will lay the grounds for the next recipe, which is an improved version of the current one.

How to do it...

This recipe breaks down into implementing three classes from the ground up, and everything will make sense by the final step:

1. Implement the Condition class:

   public class Condition
   {
       public virtual bool Test()
       {
           return false;
       }
   }

2. Define the Transition class:

   public class Transition
   {
       public Condition condition;
       public State target;    
   }

3. Define the State class:

   using UnityEngine;
   using System.Collections.Generic;
   
   public class State : MonoBehaviour...

Improving FSMs: hierarchical finite-state machines

Finite-state machines can be improved in terms of having different layers or hierarchies. The principles are the same, but states are able to have their own internal finite-state machine, making them more flexible and scalable.

Getting ready

This recipe is based on top of the previous recipe, so it is important that we grasp and understand how the finite-state machine recipe works.

How to do it...

We will create a state that is capable of holding internal states, in order to develop multi-level hierarchical state machines:

1. Create the StateHighLevel class deriving from State:

   using UnityEngine;
   using System.Collections;
   using System.Collections.Generic;
   
   public class StateHighLevel : State
   {
   }

2. Add the new member variables to control the internal states:

   public List<State> states;
   public State stateInitial;
   protected State stateCurrent;

3. Override the initialization function:

   public override void OnEnable()
   {
       if (stateCurrent == null)
        ...

Combining FSMs and decision trees

Given the previous recipes' ease of implementation and learning, we can combine them to develop a powerful decision-making system with benefits from both worlds, making it a very powerful technique in many different scenarios.

Getting ready

We will learn how to make modifications and develop child classes in order to create a finite-state machine that is capable of creating complex transitions based on decision trees.

How to do it...

This recipe relies on creating a couple of child classes from the one we already know and making a little modification:

1. Create a new action class that holds a reference to a state:

   using UnityEngine;
   using System.Collections;
   
   public class ActionState : DecisionTreeNode
   {
       public State state;
   
       public override DecisionTreeNode MakeDecision()
       {
           return this;
       }
   }

2. Implement a transition class that is able to hold a decision tree:

   using UnityEngine;
   using System.Collections;
   
   public class TransitionDecision : Transition...

Implementing behavior trees

Behavior trees can be seen as a synthesis of a number of other artificial intelligence techniques, such as finite-state machines, planning, and decision trees. In fact, they share some resemblance to FSMs, but instead of states, we think in terms of actions spanned across a tree structure.

Getting ready

This recipe requires us to understand Coroutines.

How to do it...

Just like decisions trees, we will create three pseudo-abstract classes for handling the process:

1. Create the base class, Task:

   using UnityEngine;
   using System.Collections;
   using System.Collections.Generic;
   
   public class Task : MonoBehaviour
   {
       public List<Task> children;
       protected bool result = false;
       protected bool isFinished = false;
   }

2. Implement the finalization function:

   public virtual void SetResult(bool r)
   {
       result = r;
       isFinished = true;
   }

3. Implement the function for creating behaviors:

   public virtual IEnumerator Run()
   {
       SetResult(true);
       yield break;
   }

4. Implement the general...

Working with fuzzy logic

There are times when we have to deal with gray areas, instead of binary-based values, to make decisions, and fuzzy logic is a set of mathematical techniques that help us with this task.

Imagine that we're developing an automated driver. A couple of available actions are steering and speed control, both of which have a range of degrees. Deciding how to take a turn, and at which speed, is what will make our driver different and possibly smarter. That's the type of gray area that fuzzy logic helps represent and handle.

Getting ready

This recipe requires a set of states indexed by continuous integer numbers. As this representation varies from game to game, we handle the raw input from such states, along with their fuzzification, in order to have a good general-purpose fuzzy decision maker. Finally, the decision maker returns a set of fuzzy values representing the degree of membership of each state.

How to do it...

We will create two base classes and our fuzzy decision maker...

Representing states with numerical values: Markov system

Having learned about fuzzy logic, it may do us well to mix some approaches and probably extend the functionality with finite-state machines. However, fuzzy logic doesn't work directly with values—they have to be defuzzified before they have a meaning within its scope. A Markov chain is a mathematical system that allows us to develop a decision-making system that can be seen as a fuzzy state machine.

Getting ready

This recipe uses the matrix and vector classes that come with Unity to illustrate the theoretical approach and make a working example, but it can be improved with our own matrix and vector classes with the proper implementation of the required member functions, such as vector-matrix multiplication.

How to do it...

1. Create the parent class for handling transitions:

   using UnityEngine;
   using System.Collections;
   
   public class MarkovTransition : MonoBehaviour
   {
       public Matrix4x4 matrix;
       public MonoBehaviour action;
   }

2. Implement...

Making decisions with goal-oriented behaviors

Goal-oriented behaviors are a set of techniques aimed at giving agents not only a sense of intelligence, but also a sense of free will, once a goal is defined, and given a set of rules to choose from.

Imagine that we're developing a trooper agent that needs to only reach the endpoint of capturing the flag (the main goal), while taking care of its life and ammo (the inner goals for reaching the first). One way of implementing it is by using a general-purpose algorithm for handling goals, so the agent develops something similar to free will.

Getting ready

We will learn how to create a goal-based action selector that chooses an action considering the main goal, avoids unintentional actions with disrupting effects, and takes an action's duration into account. Just like the previous recipe, this requires the modeling of goals in terms of numerical values.

How to do it...

Along with the action chooser, we will create base classes for actions and goals:

1. Create...