How do I structure this Decision tree?

Questions & Answers
1

I’ve slowly started to learn AI programming using C#/Unity.

I just finished my first FSM and want to move to decison trees now. I want it to be faily simple. Im just playing around to understand the concept before trying to advance it in any way.

I bought an AI-Unity Book with an outline of a code example in it. I dont feel like I have enough information from the book to continue with it.

This is whats in it:

A parent class DecisionTreeNode, from which Ill derive the other ones.

public class DecisionTreeNode : MonoBehaviour
{
   public virtual DecisionTreeNode MakeDecision()
   {
      return null;
   }
}

A pseudo-abstract class Decision

public class Decision : DecisionTreeNode
{
   public Action nodeTrue;
   public Action nodeFalse;
   public virtual Action GetBranch()
   {
      return null;
   }
}

A Pseudo-abstract class Action

public class Action : DecisionTreeNode
{
   public bool activated = false;
   public override DecisionTreeNode MakeDecision()
   {
      return this;
   }
}

public virtual void LateUpdate()
{
   if (!activated)
   return;
   // Implement your behaviors here
}

A final class DecisionTree

public class DecisionTree : DecisionTreeNode
{
   public DecisionTreeNode root;
   private Action actionNew;
   private Action actionOld;
}

public override DecisionTreeNode MakeDecision()
{
   return root.MakeDecision();
}

void Update()
{
   actionNew.activated = false;
   actionOld = actionNew;
   actionNew = root.MakeDecision() as Action;
   if (actionNew == null)
     actionNew = actionOld;
   actionNew.activated = true;
}

So lets say I want a simple game with an NPC with 4 parameters: Hungry, Thirsty, Sleepy and Bored. These parameters can be answered by True or false (yes or no).

If it checks out to be hungry, the npc will walk to an Apple and eat it. If its instead are Sleepy, it will walk to the bed, the water if its thirsty or the ball if its bored.

How Should the Decisions be implemented?

What I understand, the decisions could be implemented as seperate classes, all derieved from DecisionTreeNode. Like this:

public class FoodClass : DecisionTreeNode {} 

public void GotoApple()
{
 // Walk to the apple
}

Now From here I cant see how to continue.

In the Action-class’s LateUpdate() It sais //Implement your behaviours here. Should I in this function implement if/else-statements, which checks some booleans like

If(isHungry)
{
  foodclass.GoToApple();
}
else if(IsSleepy)

… and so on with all the different booleans? It seams kinda like it defeats the purpose of a DT with all these if/else-statements?

or should these node-classes all have a LateUpdate() where the classes themself here checks if the NPC is Hungry or not?
And what do you see as the purple of the class Action respective to Decision?

I really hope some of you can see how they mean to connect all of these classes with their functions to eachother. Thank you for even reading this far!

2

Hi @Growlithsama, with the actions you describe, I think what you really want is a state machine to handle the decisions of what actions your NPC should take (and yes those are handled with logical comparison statements - either if else or switch-case) and not a decision tree. A decision tree is useful where you have a number of factors that influence an outcome.

For example, say you want base your NPCs aggressive behavior - whether or not it will fight - based on how hungry, thirsty, sleepy, or bored it is. So, if it is not hungry and not thirsty and not sleepy but bored it will fight. If it is hungry, not thirsty, not sleepy and not bored, it will not fight. and so on with every permutation of those factors that will determine whether or not it will fight.

Usually it will be more nuanced with variations of each factor in the mix - a little hungry, hungry, very hungry; a little sleepy, sleepy, very sleepy. So you have a lot of different states each variable could be in.

The decision tree structure helps your code navigate those input factors to arrive at the output behavior.

State machines do not “make decisions” in the same way and are never actually a kind of tree, but rather just a routing from one state to the next based on the current state and input conditions and other conditions.

So it is similar to a state machine in that it deals with the states of each of those factors, and it uses logical comparison statements to arrive at the output. The difference is that each factor in the state machine is a separate behavioral state, whereas in the decision tree each factor contributes to the output behavioral state.

It just depends what you are after, but if all you want is one behavior it the NPC is hungry, and another if if it is sleepy, then you don’t need a decision tree.