Behaviour trees for better code structure

[jgs95 3]

Hi all,

Introduction

This post is about using the behaviour tree AI concept to improve the structure of your scripts.  When I started out writing scripts I used the binary tree approach but this resulted in quite a deep/nested structure which wasn't easy to maintain.  I found the binary tree approach wasn't suitable for sequences.  I.e. a linear sequence of N actions, as on each game loop the tree would need to be traversed, and context data would need to be evaluated to determine the next step in the sequence.

After looking around online I found this article: Behaviour trees for AI and how they work

This article provides a decent introduction to behaviour trees, what they are, what they do and how they are structured, so I'd recommend you read that before applying the behaviour tree approach.

API Design

I wrote my own framework a few weeks ago to implement this approach but it wasn't easy to modify once the script was finished, so I looked for an approach that has better maintainability and is easy to setup the structure and understand/read.  I found this github repository that provides a decent Fluent API for behaviour trees but needed to adapt it as it didn't implement the behaviour trees in the same way as the above article.  So I adapted the API and wrote a proof of concept script that simply chops Logs in Lumbridge.

Code - Main Class

Here is the main script class with comments providing an explanation.

@ScriptManifest(name = "Woodcutter", version = 1, author = "JGFighter95", category = Category.WOODCUTTING)
public class Woodcutter extends AbstractScript {
    private Node<WoodcutterData> tree;
    private WoodcutterData woodcutterData;

    @Override
    public int onLoop() {
        this.tree.tick(woodcutterData);
        return (int) Calculations.nextGaussianRandom(600, 100);
    }

    @Override
    public void onStart() {
        // WoodcutterData is accessible by the nodes in the tree. This class can be used
        // to provide a data context/information sharing object. It can also contain helper
        // methods to provide code reuse.
        this.woodcutterData = new WoodcutterData();

        // I have a context property of type MethodContext, so the nodes can use methods
        // such as getLocalPlayer()
        this.woodcutterData.context = this;

        // Set the generic property of TreeBuilder to WoodcutterData. This can be
        // any class you want and it doesn't need to extend any abstract class or
        // implement any interface.
        this.tree = new TreeBuilder<WoodcutterData>()
             // Repeat until fail has 1 child node and executes it until it returns
             // a status of Failure.
            .repeatUntilFail()
                // Selector is a composite node (meaning it has one or many child nodes).
                // As soon as one of its children return Success, the selector returns
                // Success back to its parent. If a chlid returns Failure it will keep
                // processing each child until they are all processed. If they are all
                // processed and none have returned Success, the selector will return
                // Failure. This is good for fallback scenarios, i.e. attempt action 1
                // and if it fails fall back to action 2, and so on.
                .selector()
                
                    // Insert is used to add a sub-tree to the tree. You could modularise
                    // functionality into trees, and reuse them in other scripts by inserting
                    // them. 
                    .insert(woodcuttingSubTree())
                    .insert(bankSubTree())
                .finish()
            .finish()
            .build();
    }

    // The woodcutting subtree performs the woodcutting section of the script: walk to
    // trees, find a tree, chop it down, wait for it to complete, then repeat until
    // the inventory is full.
    private Node<WoodcutterData> woodcuttingSubTree() {
        return new TreeBuilder<WoodcutterData>()
            // Like the selector described above, the sequence is also a composite. However,
            // for the sequence to return Success, each of its children must return Success.
            .sequence()
                // Condition is a type of leaf node. If it returns true, the sequence will
                // continue, otherwise it will end and return Failure to its parent.
                .condition(new HasEnoughInventorySpace())
                .sequence()
                    // An action is simply a leaf node (no children) which performs an 
                    // action.
                    .action(new WalkToTrees())
                
                    // Perform the woodcutting sequence until it returns Failure, which
                    // would happen when the HasEnoughInventorySpace returns Failure.
                    .repeatUntilFail()
                        .sequence()
                            .condition(new HasEnoughInventorySpace())
                            .action(new FindTree())
                            .action(new ChopDownTree())
                            .action(new WaitForLogs())
                        // After all the composite childs are done, you must call finish()
                        // to move the node pointer in the tree builder back until it
                        // gets to the root level. YOu don't really need to understand how
                        // it works, just that each composite child needs to be 'finished' once
                        // its children have been added, otherwise the tree won't be built
                        // properly.
                        .finish()
                    .finish()
                .finish()
            .finish()
            .build();
    }

    private Node<WoodcutterData> bankSubTree() {
        return new TreeBuilder<WoodcutterData>()
            .sequence()
                .action(new WalkToBank())
                .action(new OpenBank())
                .action(new DepositLogs())
                .action(new CloseBank())
            .finish()
            .build();
    }
}

Code - HasEnoughInventorySpace (Condition)

public class HasEnoughInventorySpace implements Function<WoodcutterData, Boolean> {
    @Override
    public Boolean apply(WoodcutterData woodcutterData) {
        MethodProvider.log("Condition: HasEnoughInventorySpace");
        return Inventory.emptySlotCount() >= 1;
    }
}

Code - FindTree (Action)

public class FindTree implements Function<WoodcutterData, State> {
    @Override
    public State apply(WoodcutterData woodcutterData) {
        MethodProvider.log("Action: FindTree");
        GameObject tree = GameObjects.closest(new Filter<GameObject>() {
            @Override
            public boolean match(GameObject treeCandidate) {
                if (!treeCandidate.getName().equals("Tree")) return false;
                if (!treeCandidate.hasAction("Chop down")) return false;
                List<Player> playersNextToTree = Players.all(new Filter<Player>() {
                    @Override
                    public boolean match(Player player) {
                        if (player.getName().equals(woodcutterData.context.getLocalPlayer().getName())) return false;
                        if (player.distance(treeCandidate) > 1) return false;
                        return true;
                    }
                });
                if (playersNextToTree.size() > 0) return false;
                return true;
            }
        });
        if (tree == null) return State.RUNNING;
        woodcutterData.tree = tree;
        return State.SUCCESS;
    }
}

BitBucket Repository

For the full script here is the bit bucket repository: jonathanstewart147 / db_behaviour_trees1 — Bitbucket

Conclusion

Hopefully this post made sense but please ask any questions and I will be happy to discuss them.

If you think about any improvements to this approach, or if there is something already out there, please let me know!

 

Happy scripting!

[flipjazz 13]

Nice examples! This will be fun to try out.

[BagelChef 17]

Nice write up! Switched to behavior trees as well from node based systems.

[Substratum 0]

@jgs95 Did you write your own framework for the learning experience or another reason? Could you not use the existing Java Behavior Trees framework mentioned in the article?