AI Decision Tree

Question

I created little decision tree, what do you think about it, what I can correct? I wanted to create a code for tree that looks in that way:

enter image description here

My implementation:

using System;
using System.Collections.Generic;
using System.Text;
public interface TreeNode
{
 bool nodeState { get; }
 bool Evaluate();
}
/// <summary>
/// Returns true when one of childs returns true
/// </summary>
public class Selector : TreeNode
{
 private List<TreeNode> childNodes;
 public bool nodeState { get; private set; } = false;
 public Selector(List<TreeNode> childNodes) { this.childNodes = childNodes; }
 public bool Evaluate()
 {
 foreach (TreeNode node in childNodes)
 if (node.Evaluate())
 {
 nodeState = true;
 return true;
 }
 nodeState = false;
 return false;
 }
}
/// <summary>
/// Returns true when all childs return true
/// </summary>
public class Sequence : TreeNode
{
 private List<TreeNode> childNodes;
 public bool nodeState { get; private set; } = false;
 public Sequence(List<TreeNode> childNodes) { this.childNodes = childNodes; }
 public bool Evaluate()
 {
 foreach (TreeNode node in childNodes)
 if (!node.Evaluate())
 {
 nodeState = false;
 return false;
 }
 nodeState = true;
 return true;
 }
}
/// <summary>
/// Has only one child, negate it
/// </summary>
public class Inverter : TreeNode
{
 private TreeNode nodeToInvert;
 public bool nodeState { get; private set; } = false;
 public Inverter(TreeNode nodeToInvert) { this.nodeToInvert = nodeToInvert; }
 public bool Evaluate()
 {
 nodeState = !nodeToInvert.Evaluate();
 return !nodeToInvert.Evaluate();
 }
}
/// <summary>
/// Leaf of tree, returns delegate of bool function that is setted in it's constuctor
/// </summary>
public class ActionNode : TreeNode
{
 public delegate bool ActionNodeDelegate();
 private ActionNodeDelegate action;
 public bool nodeState { get; private set; } = false;
 public ActionNode(ActionNodeDelegate action)
 {
 this.action = action;
 }
 public bool Evaluate()
 {
 nodeState = action();
 return action();
 }
}
public static class DecisionTree
{
 public static void Test()
 {
 while (true)
 {
 AITree tree = new AITree();
 Console.ReadKey();
 Console.Clear();
 }
 }
}
public class AITree
{
 private float playerDistanceFromEnemy;
 private int playerPower;
 private ActionNode IsInAttackRange;
 private ActionNode IsVisible;
 private ActionNode EstimatePlayerPower;
 private Sequence Attack;
 private Inverter Patrol;
 private Sequence Escape;
 private Selector Root;
 bool PlayerIsInAttackRange() => playerDistanceFromEnemy < 5;
 bool PlayerIsVisible() => playerDistanceFromEnemy < 8;
 bool PlayerIsTooPowerful() => playerPower > 3;
 public AITree()
 {
 Random rnd = new Random();
 playerDistanceFromEnemy = (float)rnd.Next(10, 100) / 10;
 playerPower = rnd.Next(1, 6);
 IsInAttackRange = new ActionNode(PlayerIsInAttackRange);
 IsVisible = new ActionNode(PlayerIsVisible);
 EstimatePlayerPower = new ActionNode(PlayerIsTooPowerful);
 Attack = new Sequence(new List<TreeNode> { IsInAttackRange, IsVisible }); // Attack only when player is visible and is in attack range
 Patrol = new Inverter(Attack); // Patrol only when not attacking
 Escape = new Sequence(new List<TreeNode> { IsVisible, EstimatePlayerPower }); // Escape when player is visible and player is too powerful 
 Root = new Selector(new List<TreeNode> { Escape, Patrol, Attack }); // Escape has the biggest priority
 Root.Evaluate();
 ShowCommunicats();
 }
 private void ShowCommunicats()
 {
 StringBuilder sb = new StringBuilder();
 Console.WriteLine($"Player distance: {playerDistanceFromEnemy}, Player power: {playerPower}");
 sb.AppendLine();
 Console.WriteLine(Patrol.nodeState ? "enemy will patrol" : "enemy will not patrol");
 Console.WriteLine(Escape.nodeState ? "enemy escapes" : "enemy will not escape");
 Console.WriteLine(IsVisible.nodeState ? "enemy see player" : "enemy dont see player");
 Console.WriteLine(IsInAttackRange.nodeState ? "player is in the enemy attack distance" : "player is too far to hit");
 Console.WriteLine(Attack.nodeState ? "enemy attacks" : "enemy will not attack");
 }
}

Answer 1

Code style

Naming

• The interface naming convention has a capital I at the beginning of your name so your TreeNode should be called ITreeNode.

• Public members should follow the Pascal Case typing e.g instead of bool nodeState { get; } the name should be bool NodeState { get; }

• Private variables should follow the camel Case typing e.g instead of Sequence Attack the name should be Sequence attack.

• Boolean members should have a prefix like is, can, or something that will look like a question when you put it into an if statement take the following example in consideration:

  if (KillMonster)
  {
   //...
  }
  if (CanKillMonster)
  {
   //...
  }
  

The second one looks and reads a lot more clearer to me.

Do not omit curly braces, especially around a foreach loop

Func<T> vs custom delegate

The difference between these 2 isn't that big, so if your needs don't match one of the following cases you can just use the generic functor:

1. You can have a specific name for your custom delegate, if you find it necessary, but not for a Func<T>.

2. You can have ref / out parameters in a custom delegate but no in a Func<T>.

That's pretty much it, they can both hold methods with the same signature, in your case I don't find a need for a custom delegate so you can just swap this line:

private ActionNodeDelegate action;

To this:

private Func<bool> action;

You can now delete your old delegate and replace the types everywhere needed.

Applying LINQ to make the code shorter and more readable

You have only 2 foreach loops in total and we can transform them into LINQ syntax:

foreach (ITreeNode node in childNodes)
{
 if (node.Evaluate())
 {
 NodeState = true;
 return true;
 }
}
foreach (ITreeNode node in childNodes)
{
 if (!node.Evaluate())
 {
 NodeState = false;
 return false;
 }
}

Can become:

if (childNodes.Any(node => node.Evaluate()))
{
 NodeState = true;
 return true;
}
if (childNodes.Any(node => !node.Evaluate()))
{
 NodeState = false;
 return false;
}

Avoiding multiple unnecessary calls

Why would you call a method twice, when you already have the return value saved?

NodeState = !nodeToInvert.Evaluate();
return !nodeToInvert.Evaluate();
NodeState = action();
return action();

Can become:

NodeState = !nodeToInvert.Evaluate();
return NodeState;
NodeState = action();
return NodeState;

It doesn't seems like a big improvement but it's basically making your code twice faster in this specific method. Imagine if Evaluate and action take long time, would you like to wait 20 seconds instead of just 10? The methods that will be executed and will control your AI decisions will be called probably each frame in a normal game, you want to make those as fast as possible.

Adding more modifiers to your variables

Access modifiers

You're being a little bit inconsistent with where you put access modifiers. Most of your variables in AITree have the explicit private access modifier but some of them don't I don't see a reason for that, they should all have it. Namely:

bool PlayerIsInAttackRange() => playerDistanceFromEnemy < 5;
bool PlayerIsVisible() => playerDistanceFromEnemy < 8;
bool PlayerIsTooPowerful() => playerPower > 3;

Modifiers

A common modifier is readonly. This modifier allows you to give value to your variable only at initialization or in the constructor, this is pretty useful as it can guarantee that your variable wont mutate during it's lifetime.

Most of your variables can have readonly added:

private float playerDistanceFromEnemy;
private int playerPower;
private ActionNode IsInAttackRange;
private ActionNode IsVisible;
private Sequence Attack;
private Inverter Patrol;
private Sequence Escape;
private ITreeNode nodeToInvert;
private Func<bool> action;
private List<ITreeNode> childNodes;

Redundancy

You have some redundant variables in your AITree

These 2 for example:

private readonly ActionNode EstimatePlayerPower;
private readonly Selector Root;

You are using those only in your constructor as helper variables, but they have no other use in the class, you should either make them local variables to the constructor or just remove them.

Also in your ShowCommunicats method, the StringBuilder sb = new StringBuilder(); is absolutely redundant.

Overall design

• A better way of saving the current state/action of your AI would be handy.

• You should consider using the Strategy pattern as it's pretty good design pattern when it comes to making decisions.

  Update

  As requested I will put some guidance here on how to implement the Strategy pattern, but I cant provide a working example as your code currently isn't in that state yet, as it will require you to have actual actions to happen such as Attack, Patrol, etc.

  You will need 2 things to implement the Strategy pattern:

  1. Common base interface/abstract class which has the core signature / functionality.

  2. Some enum which has all the possible actions (Attack, Patrol, etc), as you will use that in a switch case.

  Once that's done you will need an extra variable to save the state of your AI (this will fix point 1), and just switch that variable in your switch case, you will want to order the switch cases in specific order depending on the priority, this can be done with collection as well which you will sort by priority of each action, and just do a quick iteration over it with a simple if statement checking if the current action is available.

  Another option would be to go with some collection which you will filter out to get the best element.

• Your classes look a bit weird to me, Inverter doesn't quite fit the whole picture.

• I feel like ITreeNode is being overly-inherited. Inverter doesn't looks like a node + it doesn't really benefits from the inheritance of ITreeNode as far as I can tell. It's just adding more code to the class and if you don't have to implement the interface the class will be a single method, which is one more reason why Inverter is bad.

• Michael: Could you show me an example about how strategy design pattern can help me in this case?
• Denis: Added some more info on it @Michael
• Mathieu Guindon: Private variables should follow the Pascal Case - that's camelCase ;-) also, given the existence of actual Action delegates for void methods, "action" seems a rather odd name for a Func<T>.
• Denis: I'm bad at editing copy pasted lines @Mat'sMug, thanks for the note.
• Michael: @denis So what in what way in your opinion, I might write inverter?

Answer 2

Bugs

• The Evaluate() method of Selector/Sequence do not call Evaluate() on all child nodes. Therefore, you can not be sure, that the noteState is correct for all nodes. But your example code uses the Node state of all nodes after running Root.Evaluate().

---

Selector/Sequence.Ctor

• Check if argument is null (otherwise you may get a NRE in method Evaluate)
• You could use IEnumerable<TreeNode> as argument type to be more flexible.
• The childNodes collection could be readonly.

Selector/Sequence.Evaluate

You could use LINQ for that:

public bool Evaluate() => nodeState = childNodes.Any(n => n.Evaluate());
public bool Evaluate() => nodeState = childNodes.All(n => n.Evaluate());

However, as mentioned above, you should call Evaluate() for all child nodes.

public bool Evaluate()
{
 childNodes.ForEach(n => nodeState |= n.Evaluate());
 return nodeState;
}
public bool Evaluate()
{
 nodeState = true;
 childNodes.ForEach(n => nodeState &= n.Evaluate());
 return nodeState;
}

Naming Conventions

There are naming conventions in C#

• Interfaces should start with 'I'
• Property should start with capital letters
• ....

---

Your requirement reminds me of the framework Countable and uncountable sets from @Dmitry Nogin.

• Denis: Nice usage of the expression body function, I didn't know you can assign value and return it at the same time.
• Michael: I though that Selector and Sequence checks childs and if they find node that is interesting, they break searching. Isn't that?
• JanDotNet: @Michael: Yes, it is. And the nodeState of the Selector/Sequence is correct. But the Evaluate method of the children is used to set the nodeState of the child nodes. If searching was broken, Evaluate was not called for some of the child nodes and the nodeState may not be correct in turn...
• Michael: Ok, can you tell me what this operators: "|=", "&=" do in the code? Are they some binary operators?
• JanDotNet: It is the short version of nodeState = nodeState | n.Evaluate() / nodeState = nodeState & n.Evaluate().