In a sentence: A Tree Machine is a state machine where the individual states are behaviour trees.
The goal of this project is to combine behaviour trees and state machines in order to mitigate the negative effects of both. A custom language allows for fully data-driven development, so that you can adjust your Tree Machine while the program is still running.
State machines allow for objects to be in a particular state, and within each state they would act in a particular manner. When some condition is met, the machine would set another state as active. The disadvantage with these is called 'state explosion', where you end up with too many states and a graph that looks like it belongs in a ramen bowl. Therefore, state machines are good at transitions, but not very good at creating complex behaviours.
Each behaviour tree tick starts from the head of the tree and traverses the tree. Each node then calls subtrees, and then they recursively return the state of the tree. The state is usually SUCCESS, FAILURE or RUNNING. A programmer can create different types of nodes, whereas a product designer can then combine these to create complex behaviours. Behaviour trees can end up being too big for entities which have many capabilities. Therefore, behaviour trees are good for complex individual behaviours, but bad at transitioning between different states.
The point of tree machine is to retian all the positive attributes of state machines and behaviour trees, and combine them together to remove their disadvantages.
I havent given it a name yet, but it is a language within YAML or JSON. Here is an example:
trees:
move_randomly:
"set_position(new_v2(randf(0, 1),randf(100, 200)))"
states:
move_randomly:
tree: move_randomly # Optional since it is called the same as the state name
transitions:
"done()":
- 1: move_randomlyFirst define the trees. In this case there is only one tree called move_randomly. Then define the states. In this case there is only one state which is also called move_randomly, which references the move_randomly tree. Since the state and tree are the same, you can opt out of the tree key in the state. The move_randoly tree has a single node, which sets the position to a random position. A state also has a list of transitions, and in this case, when the tree is done(), the tree is reset, and a loop happens, ie the machine goes back to the move_randomly state, with probability 1.
There are 2 different types of customizable items:
- Functions: These take some parameters, perform some logic, and return a literal
- Behaviours: These take some parameters, perform some logic, and return
SUCCESS,FAILUREorRUNNING.
The actual program reads JSON, but I prefer to write out the tree machines themselves as YAML and then convert to json. For this, a helper script exists in the codegen folder to convert a folder of YAML files to JSON. Feel free to extend this as you see fit for your project.
The codegen project in this repository can read a set of files such as those specified in TreeMachine.Tests/functions.yaml and TreeMachine.Tests/behaviours.yaml and generate the contents in the folders TreeMachine.Tests/src/Functions/ and TreeMachine.Tests/src/Behaviours/ respectively. If you take any file in this folder, any code which is between // <TAG> and // END_<TAG> is generated, and the rest is filled in by the user. This avoids the user needing to create boilerplate and instead really focus on just the logic for creating the functions and behaviour for the language.
The idea is to create a TreeMachine.Manager class, add your custom functions and behaviours to it, parse the tree machines, then create a tree machine from the ones you just parsed, initialise it with the entity and global blackboard of your choice, then start ticking it. The behaviours will affect the properties of your entity. You can have behaviours and functions in different folders. Some for all types of entities (such as add functions and sequence behaviours), and some for specific entities. Then the codegen script can be run multiple times.
- Clone the repo
# Clone the repository
git clone https://github.com/anomalyco/tree-machine-csharp.git
cd tree-machine-csharp- Install dependencies (optional but recommended)
I use mise-en-place (or just mise) to manage dependencies in the project. To install mise, follow the instructions here: https://mise.jdx.dev/installing-mise.html (remember to both install and source it).
After installing mise, you can run the following to install the dependencies in mise.toml
mise install- Run the tests
task testIf you want great examples, look no further than the taskfile.yml and the TreeMachine.Tests package, especially TreeMachineTest.cs.
Literals contain individual values. A literal can be any of these types:
- int32: A signed integer of size 32 bits
- int64: A signed integer of size 64 bits
- uint32: An unsigned integer of size 32 bits
- uint64: An unsigned integer of size 64 bits
- float: A floating point value
- double: A floating point value of double precision
- vector2: A tuple of 2 floats
- vector3: A tuple of 3 floats
- blackboard: A blackboard is effectively a dictionary. It is a concept used in behaviour trees to store state over the course of time. A tree machine generally has 2 blackboards available to it. A local blackboard is only available to that tree machine, whereas a global blackboard is shared among many tree machines and can be used as a means of communications between entities.
A function is one type of expression. An expression is a concept which, given some input, performs some logic and produces an output. In the case of functions, the output is a typed literal. All items in this project are typed, so to perform type conversion, the objects must go through a function. For example, one does not simply add an int32 and a float, one must first convert the int32 to a float and then add that value to the original float, or vice versa if the intended result is an int32.
Example function definition is as follows:
"float:add_f(list<float>:values)":
description: "Add a list of `int64`s"
can_be_constant: true
"float:index_list_f(list<float>:values,uint32:index)":
description: "Get element from `values` at index `index`. Example: `index_v2(v2,0)` = v2[0] "
can_be_constant: false
"blackboard:get_global_blackboard()":
description: "Returns the global blackboard"
can_be_constant: falseThe format of a function definition is a follows: <return_type>:<name>([<parameter_type>:<parameter_name>,...]). The description key is also necessary and will be placed as a docstring for the class. can_be_constant is a special field used for optimization. If in doubt, set to false. This field is used to optimize a TreeMachine when parsing it, to remove unecessary nodes. For example, given add_f(1,3), this can be simply reduced to 4. However, if there are children of add_f which are not constant, for example addf(randf(), 2), where randf generates a random float between 0 and 1, then this node will not be pruned.
Behaviours on the other hand return a BehaviourStatus. This can be either SUCCESS, FAILURE or RUNNING. Some example behaviours are the following:
"sequence()":
description: "Runs its children in sequence. Will return RUNNING if any of its children returns RUNNING. Will continue executing from the last child that returned RUNNING before, unless reset. If one of its children returns FAILURE, it will return FAILURE and will reset. If it's last child returns SUCCESS, it will return SUCCESS and reset"
is_leaf: False
"fallback()":
description: "Runs its children in sequence. Will return RUNNING if any of its children returns RUNNING. Will continue executing from the last child that returned RUNNING before, unless reset. If one of its children returns SUCCESS, it will return SUCCESS and will reset. If it's last child returns FAILURE, it will return FAILURE and reset"
is_leaf: False
"invert()":
description: "If the child returns RUNNING, it returns RUNNING. Otherwise it returns the opposite between SUCCESS and FAILURE"
is_leaf: False
"expression_to_behaviour(bool:value)":
description: "Converts a given boolean expression to a behaviour, for usage in behaviour trees. If the expression returns `true`, it will return `success`, or `failure` otherwise"
is_leaf: True
"set_f(blackboard:b,string:name,float:value)":
description: "Put a float with the given name on the local blackboard to the given value"
is_leaf: TrueThe format of a behaviour definition is a follows: <name>([<parameter_type>:<parameter_name>,...]). The description key is also necessary and will be placed as a docstring for the class. In the Init function of certain behaviours, we can manually put some asserts. For example, the sequence() and fallback() behaviours must have at least one subbehaviour, whereas the invert() subbehaviour must only have one subbehaviour. Leaf nodes on the other hand do not have subbehaviours and will not reset or initialise their children (children = child subbehaviours) because they should not have any. An automatic assert that leaves have no children is put into leaf classes.
Tree machine definitions consist of multiple parts. I will discuss these for the YAML, but you can do the equivalent in JSON. My preferred workflow is to crete the tree machine in YAML, because it is nicer to look at and not as visually straining as JSON, then use codegen to convert to JSON.
- comma to separate parameters, vs semicolon to separate vector elements, vs '/' for expressions
Behaviours and Functions are expressed as Expressions. Expressions contain of literals and subexpressions. For example:
1. set_position(new_v2(randf(0, 1),randf(100, 200)))
2. set_position(0/0)
3. add_f(2;3;5)
4. add_f(GLOBAL_X;add_f(2;3;5))
Note that in 1, we have new_v2 as a parameter which is a subexpression, and then subexpressions for that subexpression. Separate parameters are separated by ,. Then we have randf(0, 1), where 0 and 1 are literals. With regards to literals for vector2 and vector3 types, we separate these by /, as seen in the second example. Example 3 shows that list elements are separated by ;. Example 4 shows an example of a macro being used. Macros are discussed next.
The first key which is considered is the macros field. This is a field of key-value pairs, where, for the rest of the tree, any string which looks like the key, will be replaced by the value. Therefore, my preferred workflow is to define macro keys in ALLCAPS, and use lowercase letters for everything else. Example macros:
macros:
LOCAL_X: get_f(get_local_blackboard(),x)
GLOBAL_X: get_f(get_global_blackboard(),x)
TEN: add_f(2;3;5)
POS_X: index_v2(get_position(),0)
POS_Y: index_v2(get_position(),1)Later macros can also use previous macros.
A tree starts with a behaviour and then iterates over that and its subbehaviours. The iteration is dependent on the behaviours. Leaf nodes of behaviours usually affect the entity that the tree machine is a component of. Subbehaviours can also be other trees, which are unrolled within that tree.
trees:
reset_x_local:
set_f(get_local_blackboard(),x,0)
init_x:
sequence():
- reset_x_local
- set_f(get_global_blackboard(),x,0)
increase_x:
sequence():
- set_f(get_local_blackboard(),x, add_f(LOCAL_X;TEN))
- set_f(get_global_blackboard(),x, add_f(GLOBAL_X;TEN))In the above example, we can see reset_x_local which resets the variable x in the local blackboard to 0. This tree is then used in init_x, which is a sequence that in the first tick resets local x, and in the second tick resets the global x. In a real scenario, we could replace sequence() with a parallel() node, which might execute both in a single tick. increase_x then increases each of local and global x by 10.
A state contains a tree, and it will tick that tree and only that tree. Before a tick, it will evaluate a set of conditions. The first condition that returns true, it will evaluate the transitions that the condition leads to, chooses one of them at random, and then switch state and tick the tree of the new state. If no condition returns true, it will instead continue ticking its own tree. Example:
states:
init_x:
transitions:
"done()":
- 1: increase_x
- randf(0, 1): reset_x
increase_x:
inherits: [before_and_after]
reset_x:
tree: reset_x_local
inherits: [before_and_after]You will notice that reset_x state has a tree key. The others do not have this key because they are named the same as their corresponding tree, so the tree key is implicitly the name of the state by default. The init_x state is the initial state because it is declared first. In this example, init_x is the only one with explicit transitions. Here, if the state is done, the state will transitions with weight 1 to the increase_x state, or with weight some random value between 0 and 1, to state reset_x. The other states inherit from the before_and_after abstract state, which are discussed next.
In order to avoid the same transitions being copy pasted over and over, we have abstract states. Here is an example:
abstract_states:
before_and_after:
before:
"le_f(30, LOCAL_X)":
- 1: reset_x
after:
"done()":
- 1: increase_xHere we have a single abstract state called before_and_after, with a single before transition and a single after transition. When states inherit these abstract states, the before transitions are placed before the state's own transitions, whereas the after states are placed after the state's own transitions. For example, these 2 states are equivalent:
states:
state1:
tree: tree_x
inherits:
- before_and_after
transitions:
"condition1()":
- 1: tree_y
state2:
tree: tree_x
transitions:
"le_f(30, LOCAL_X)":
- 1: reset_x
"condition1()":
- 1: tree_y
"done()":
- 1: increase_xAn abstract state can have either before, after or both keys.
- The first state in the tree machine is the initial state.
- When a
Tick()happens on the tree, the machine first evaluates the transition conditions in order. If one of them is true, it samples from the given weights and choose the next state to go to and tick that state's tree. If none of the conditions are true, the machine simply tick the current state's tree.
Whenever I refer to "codegen parameter" in this section, you may look at TreeMAchine.Tests/conf/default.yaml as reference. These are the inputs to the codegen program.
- Create the tree machine yaml
- Convert to json using
codegen, using theyaml_folderand thejson_folderparameters - Create
functions.yamlandbehaviours.yaml, and set the path of these files tofunctions_fileandbehaviour_fileparameters for codegen. - Use codegen to generate the classes, in the
functions_destination_folderandbehaviours_destination_folder. - Fill in
Execute()andTick()for each generated function and behaviour class respectively, as well as any other possible functions and locations.Execute()andTick()are the only mandatory ones, and the program will not compile without them. If you add a new member, you must reset it in theReset()function, otherwisecodegenwill crash as a warning. - Use
TreeMachine.Managerin your program as follows:
Random r = new Random(666); // Random to pass to manager
Manager<Entity> manager = new Manager<Entity>(r); // The manager
// This block is generated with codegen, simply by including the commented lines in your program, and adding this file to the `additional_files_to_fill` section for the codegen parameters
// GENERATED_ADD_FUNCTIONS
manager.AddFunction("or", FunctionOr.Construct);
manager.AddFunction("randf", FunctionRandf.Construct);
// END_GENERATED_ADD_FUNCTIONS
// GENERATED_ADD_BEHAVIOURS
manager.AddBehaviour("expression_to_behaviour", BehaviourExpressionToBehaviour.Construct);
// END_GENERATED_ADD_BEHAVIOURS
manager.ParseFolder("/trees/jsons/"); // Will read all trees in the folder
Entity entity = new Entity(); // The entity (subject of the tree machines) is called `Entity`
Blackboard globalBlackboard = new Blackboard(); // Global Blackboard
TreeMachine<Entity> tm = manager.GetTreeMachineClone(treeMachineName); // Instantiating a tree machine
tm.Init(entity, globalBlackboard); // Initializing the tree machine
tm.Tick(); // Ticking the tree machine- You can adjust the trees in real-time, keep track of which entity has which tree machine, then re-parse with a new manager, and replace the tree machine of each entity with the new tree machines, so that you do not need to recompile or restart the project.
- A behaviour of a tree machine could be to switch the entity's tree machine to another one. This could be used for example for a robot going from indoors to outdoors, or changing forms from walking to driving.
- Tree Reference Order – If a tree references another tree, the referenced tree must be declared first. This ensures consistent ordering and reduces potential runtime errors. Internally, the trees are 'unrolled', which means that this also prevents infinite recursion during parse time.