Since I had no previous experience of coding a computer player I turned to our friend google for advice. I found a number of threads on the subject, some talked about AI, but most of them talked about reaction based solutions, but since I’m not interested in AI and rather want to mimic the feeling found in old-school fighting games I decided to go for the reaction based solution. And when I use the phrase “reaction based”, I’m referring to an implementation that selects action-based on one or several conditions e.g. if the opponent hit then block. 

Feeling a bit over-confident, I stopped reading and headed over to Visual Studio just to realize that this was not as easy as I had thought. Soon I had a bunch of if-statement and a code hard to follow. I refactored the code, but still I wasn’t pleased

Along came Halloween and at my workplace, we had an amazing party (I was dressed as the Invisible Man). After dinner, I chatted with a colleague and talking about the computer player he asked if I was using a decision-tree for action selection. Decision trees? What’s this, yet another gap of knowledge.

The name itself told me that this was something I had to read up on. So, the day after, still recovering from the party, I started reading. And oh yes, this was what I’ve been looking for. (Thanks Mikael for the suggestion)

Decision trees

The full definition is somewhat longer, but simplified, a decision tree is a tree structure describing conditions and results. Every node is a condition deciding upon which branch to follow until reaching the leaf and the result of the path taken. This was exactly the kind of data structure I needed to find a structure around the computer player logic Using a fluent builder I could put all conditions in a tree and let the leaves contain what actions to perform.

Decision tree for the computer player.

DecisionTreeNode

My implementation of the decision tree is very basic, it consists of a DecisionTreeNode-class that I use for the tree as well as for the nodes and the leaves. 

The Condition-property is only applicable to condition nodes. It’s a delegate that when called will evaluate what child node to step into. It returns the name of the child to step into.

The Result-property is only applicable to leaves. It’s a delegate with actions associated to the leaf.

The GamePlayState-class contains all data needed when deciding computer action.

DecisionTreeBuilder

I’m quite fond of fluent coding so when building the DecisionTreeBuilder it was a natural pattern to choose. Using this pattern makes classes easy to use and code easy to read.
 
This is how I build the decision tree

var decisionTree =
    DecisionTreeBuilder
        .Begin(
            "Reacting",
            state =>
                state.Player.IsReacting()
                    ? "Elapsed"
                    : "Opp new action")
        .AddNode(
            "Elapsed",
            state =>
                state.Player.IsTimeToReact(state.GameTime.TotalGameTime)
                    ? "Facing"
                    : "Done 1")
        .AddNode(
            "Facing",
            state =>
            {
                return
                    state.Player.IsFacingOpponent()
                        ? "Reachable 1"
                        : "Reachable 2";
            })
        .AddNode(
            "Reachable 1",
            state =>
                state.Player.IsWithinReach(state.Opponent)
                    ? "Opp attacking"
                    : "Opp approaching")
        .AddNode(
            "Opp attacking",
            state =>
                state.Player.ActionToReactUpon is AttackAction
                    ? "Defend"
                    : "Attack 1")
        .AddLeaf(
            "Defend",
            state =>
            {
                state.Player.ResetReaction();
                state.Player.ParryHeadCut();
            })
        .AddLeaf(
            "Attack 1",
            state =>
            {
                state.Player.ResetReaction();
                state.Player.HeadCut();
            })
        .Parent()
        .AddNode(
            "Opp approaching",
            state =>
                state.Opponent.IsAdvancing() &&
                state.Opponent.IsFacingOpponent()
                    ? "Idle 1"
                    : "Advance 1")
        .
        .
        .
        .Build();

AddNode will create and append a new node to the current nodes’ children and then go into the newly created node and make it current. AddLeaf will create and append a new leaf, but not go into it. Parent will go to the parent node and make it current. Build will return the newly composed tree. 

The choice to use strings for names makes it easy to follow the code but also makes it easy switching between the diagram and the code. The Parent-, and Name-properties together with the GetFullName method make nice tools while debugging.

Player

In my game I have a HumanPlayer-class and a ComputerPlayer-class, both implementing an abstract class Player. The main difference between the Human- and the ComputerPlayer-class is how the Update-method is implemented. The HumanPlayer-class is using input from keyboard and gamepad to control the player character while the ComputerPlayer is using the decision tree. 

The code for using the tree looks like this:

    var leaf = _decisionTree.Evaluate(state);
    leaf.Action(state);

Nice, isn’t it?

Happy coding!
jan.