Simple Decision Tree

Introduction:

Decision Trees are simple tree structures that are used to simplify and modularise logic (there are also decision trees in machine-learning. We aren’t covering those here).

Use Case:

Say we have a shop keeper. This shop keeper needs to respond to a customer but the response will differ depending on some criteria.

The criteria are:

  • If the customer has no money, tell him “Go away, you’re broke!”.
  • If the customer has money but it is LESS than 5000, and the customer is a “sphere”, tell him “Now now, we don’t want any trouble. Just leave us alone.”
  • If the customer has money but it is LESS than 5000, and the customer is NOT a “sphere”, tell him “We have some used car parts around back.”
  • If the customer has money and it is MORE than 5000, and the customer is a “cube”, tell him “Your highness, take a look at this exquisite ruby.”
  • If the customer has money and it is MORE than 5000, and the customer is NOT a “cube”, tell him “We have some caviar in the back, but it’ll cost ya!”

Now try imagine what an if-else block would look like given the conditions mentioned above. It is definitely possible but would quickly become a bit of a mess to manage.

And then what happens when a designer asks you to change some of the conditions to handle a few more cases later on?

Well unit tests would definitely come in handy and are usually a good idea anyway but in the interest of “Keeping It Simple Stupid”, we really should come up with a more manageable and scalable solution…and if we can design our solution in such a way that designers can create the logic structures via dragging, dropping and a bit of configuration, then even better!

Enter the Decision Tree:

Logic Design:

Decision Tree

The first step is to map out the logic flow that your decisions need to follow.

In the tree above, there are two types of nodes:
Decision Nodes: the diamonds.
Action Nodes: the rectangles with rounded edges.

Decision Nodes:

  • Evaluate a condition.
    • If the condition evaluates to true, execution follows down to the connected “Yes” node.
    • If the condition evaluates to false, execution follows down to the connected “No” node.

Action Nodes:

  • These nodes perform an action.
  • They are the leaves and execution stops when it reaches one of them as being a leaf means that they’re the end of the line.

Implementation:

For this example, we’re going to keep it simple and have the Action/Leaf nodes return a string value.

The “Nodes” will extend MonoBehaviours so they can be attached to empty Game Objects in Unity and linked up visually.

We’ll need:

  • Decision Node:

    • To evaluate the condition and choose whether to go to the “Yes” or “No” node.
    • This Node class will also have a “Condition” component. The Condition will do the evaluation and the Decision Node will then continue execution down the “_trueNode” if the Condition evaluates to True, or “_falseNode” if the condition evaluates to false.
    • fork node - Decision Tree Design.png
  • Condition Component:

    • As mentioned above.
    • These can be interchangeable so the Decision Node is generic and the Condition Component may be changed or extended.
  • Action or Result Node:

    • To return the string value.
    • result node - Decision Tree Design (2)
  • Base Node:

    • Using polymorphism we can connect either another Decision Node or Result Node to the “_trueNode” or “_falseNode” fields of the Decision Node.
    • node - Decision Tree Design.png
  • Decision Tree Container:

    • Used to encapsulate the inner workings of the decision tree (even though, in this example there isn’t too much going on).
    • Decision Tree - Design.png

Configuration:

In the Unity Editor, the structure we end up with, given the conditions above looks something like this:

Screen Shot 2016-05-08 at 18.00.24 copy.png

And below are some of the Nodes, linked up and configured.

1 - sdecision tree root.png

2 - decision node.png

The Decision Condition component’s extend a base Decision Condition component and add some conditional logic. In this example, there is one Condition component that checks the “Customer’s” money amount and another that checks the Customer’s “shape” (not displayed in the below images).

3 - decision node.png

4 - false node.png

And finally a “Result” node that will return a value back up the call hierarchy to the Decision Tree.

So to create a decision tree:

  1. Create a GameObject with a DecisionTree component.
    1. Create a child with a DecisionNode and connect it to the “_rootNode” field of the DecisionTree.
      1. Create the a DecisionNode or ResultNode to evaluate if the parent DecisionNode’s Condition evaluates to True. Connect it to it’s parent’s “_trueNode”.
        1. Continue with DecisionNodes and ResultNodes until this branch of your Decision Tree is complete!
      2. Create the a DecisionNode or ResultNode to evaluate if the parent DecisionNode’s Condition evaluates to False. Connect it to it’s parent’s “_falseNode”.
        1. Continue with DecisionNodes and ResultNodes until this branch of your Decision Tree is complete!

Demo Project:

A demo project can be found here.
It contains a simple scene with a “ShopKeeper” and a “Customer”.

Screen Shot 2016-05-08 at 18.13.14.png

Change the values of the Customer, Press Play and click the “respond to customer” button to get a response from the shop owner.

Then change the values on the customer. Try combinations of:

  • No money.
  • Some Money.
  • Maximum Money.
  • Cube Shape.
  • Sphere Shape.
  • Any other Shape.

and see if you get all the correct responses as dictated by the Decision Tree Graph at the top of this post.

Also take a look at how the nodes are connected in Unity and try add your own condition. Perhaps make a new branch that gives a different result if the Customer’s shape is a “Cylinder” (take a look at the other condition classes in the project for reference).

Considerations:

This decision tree implementation is constructed using components extending MonoBehaviours, and taking advantage of the MonoBehaviours’ serialisable nature.

Other techniques involve using:

  • Data driven approach:
    • XML
  • Scripting Languages:
    • Python
    • Lua, etc.
  • Or hard coded:
    • C#
    • Native,  etc.

A data driven and/or scripted approach would require some form of editor to design the tree so for the sake of simplicity these haven’t been addressed in this post, though there’s a good chance they will be in a later post (on either decision trees or behaviour trees).