Behaviour Tree Design

2009-07-29

Behaviour Tree Design

Permalink 17:03:59, Categories: GSOC 2009  

Overview
The core components of a basic behaviour tree implementation are selectors, sequences, conditions and actions. With just these tools it is possible to recreate most finite state machines (FSMs) in a more intuitive manner. By then adding decorators the behaviour tree becomes a more powerful tool whilst maintaining its intuitiveness.

As conditions and actions can be created by making use of the refactored CEL triggers and rewards respectively the implementation of these core behaviour tree components will serve as a proof of concept of the usefulness of the recently completed Quest refactor.

More complex features of behaviour trees include memory management techniques and a scheduler controlled implementation. Both of these techniques could potentially be very useful within CEL but are beyond the scope of the proposed deliverables and would be unachievable in the remaining time frame of GSoC 2009. However, it is my intention to design the interface in a manner that will ease any future work on these features.

The remainder of this document outlines the tools I intend to develop and document in the coming weeks. Whilst I have provided a brief description here of their functionality, anybody interested in this tool is highly recommended to visit AiGameDev, specifically these freely available resources: A Brief Written Overview and A More Detailed Video Series. I was fortunate enough to sign on to the premium membership of this site with the initial payment from the GSoC project and I would have to say it has been crucial in the design of this tool.

Interface (iBTNode)
A behaviour tree is to be executed each time an entity needs to decide upon an action. The tree evaluates from the root evaluating each chosen child node. Each node returns a boolean to indicate the success or failure of that node. Therefore, the interface requires an execute method that returns a boolean. As it is intended that the behaviour tree may make use of the refactored celParameters class, this method must receive an argument of this type.

To connect nodes and leaves of type iBTNode, each node must maintain an array of children and provide methods for adding to this array.

To use a behaviour tree, the user must first create each node/leaf and connect them. Once constructed, an entity needing to choose an action will execute the root node which in turn, upon deciding the correct child, will execute the chosen child node and pass on the parameters. Eventually the root node will receive a boolean value indicating the success or failure of its child and, presuming its own execution is complete, will return its own success or failure to the user. The interpretation of this final return status will be implementation specific in so much that a return of false is not necessarily a negative result dependent on the design of the tree itself.

To summarise, the intended iBTNode interface is:
virtual bool execute (const celParams& params)
virtual bool addChild (iBTNode* child)

Selectors and Sequences (plgSelectors)
Selectors and Sequences, or collectively known as composites, are nodes in a tree with multiple children that control which children to execute. Selectors work through the children nodes until one child returns success, if a child returns success the selector stops executing children and itself returns success. However if no children succeed the selector also fails. They are often referred to as OR nodes, as one child or another is executed.

The logical opposite to selectors is sequences. Sequences execute children in order until one fails. If all children succeed the sequence succeeds but if any child fails the sequence immediately fails and stops to execute any further children. They are often referred to as AND nodes, as the first child and the second child and so on are executed.

Due to the name clash in CEL and CS with both the refactored CelSequences and the existing CSSequences, my current design decision is to instead name the sequences composite a SequentialSelector.

In addition, the selector composite by default selects children from left to right (dictated in code by the order they are added to the node) however this selection of one specific child can be implemented in numerous methods increasing the number of behaviours achievable. To demonstrate this capability I intend to implement both a standard selector and a random selector.

To summarise the following selectors are intended to be implemented during GSoC:
- DefaultSelector
- SequentialSelector
- RandomSelector

Decorators (plgDecorators)
Decorators, like selectors before, are nodes in the behaviour tree with the difference being that decorators tend to have one child. Their purpose is not to select a child to execute but to themselves perform some computation before passing execution to the child.

I intend to implement decorators for loops, limiting the number of times a child can execute, and negating the return value of a child (so that a sequence can continue UNLESS a condition has fired.) For a more complete list of example decorators please see http://aigamedev.com/hierarchical-logic/decorator/. If any are of particular interest to readers please let me know and I will try my best to implement them within the time frame.

To summarise the following decorators are intended to be implemented during GSoC:
- LoopDecorator
- ExecutionLimitDecorator
- NegateReturnDecorator

Conditions and Actions (plgBehaviourTree)
Finally, the leaves of a behaviour tree are made up of conditions and actions. In CEL we already have the concepts of triggers and rewards and as such the implementation of these leaf nodes is partially complete.

In essence actions are essentially rewards except actions must return a success or failure and rewards currently do not. I intend to modify slightly the interface to rewards to return this value and update the refactored rewards to implement this change. This should have no effect upon the quest implementation. All nodes of a behaviour tree will have to implement the interface iBTNode, I do not however intend to add this to the refactored rewards. Instead I will implement a wrapper BTAction the implements the iBTNode interface and executes an action.

Similarly triggers do not directly fit into the behaviour tree paradigm. Instead of waiting for a trigger to fire and choosing an actions based on this, behaviour trees check if a trigger has fired at the time of their evaluation and base their choice on if it has already occurred. Therefore another wrapper class is needed, TriggerFiredCondition. This condition will return false if checked before the trigger has fired and true after.

Conditions are not however limited to triggers firing. Instead conditions may include, for example, checking the health of an entity that the behaviour tree belongs to. A generic condition that can be implemented is checking the value of a parameter. The condition, ParameterCheckCondition, will be set up with the name of the parameter, the value and whether to check for equal to, less than or more than.

Other conditions will be application specific and cannot at this time be implemented. However, users of the behaviour tree can easily create their own conditions by implementing the iBTNode interface within their class and returning a boolean based upon the condition they desire to check.

To summarise the following leaf nodes are intended to be implemented during GSoC:
- BTAction
- TriggerFiredCondition
- ParameterCheckCondition

Please note: This document is a work in progress and will be updated with the projects progress including any updates brought to attention in the mail group discussion.

Trackback address for this post:

This is a captcha-picture. It is used to prevent mass-access by robots.
Please enter the characters from the image above. (case insensitive)

Comments, Trackbacks, Pingbacks:

Comment from: fiona [Visitor] Email · http://www.google.com
thank you
PermalinkPermalink 2010-03-16 @ 12:38

This post has 55 feedbacks awaiting moderation...

Comments are not allowed from anonymous visitors.

October 2014
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Search

Categories

Misc

XML Feeds

What is this?

powered by
b2evolution