How to handle Multiple Trees

renatopp commented 9 years ago

This thread discuss how to handle multiple trees in the editor and the client libraries.

Motivation

You can use multiple trees in some different ways:

You may use one or more independent trees (they don't have tree nodes).
You may want to create a main tree which calls other trees as util functions. For example, a SoldierTree that uses CombatUtilTree, HealingUtilTree and CoverUtilTree.
You also may want to create several "main" tress that calls other trees as util functions. For example, CommanderTree and SoldierTree using the same utility subtrees.
In a worse scenario, you may want to use two trees recursively. For example, tree A calls B and tree B calls A (I don't know any case where this would be useful, but I don't see why and how to avoid it).
Worse yet, you may use the same tree recursively, e.g., tree A calls tree A.

Given that you may use the same subtree several times and the case where you use the trees recursively, I want to create a single object instance for each tree.

So, I'm thinking in something like that:

var behaviorCollection = b3.load(behavior3_data);

var soldierTree = behaviorCollection['SoldierTree'];
var commanderTree = behaviorCollection['CommanderTree'];

and then you use the trees as usual.

Editor

If we follow this behavior collection thing we:

can't allow trees with the same name.
could change the JSON format to make easier to read these trees (maybe similar to how nodes work). This also would help with #5.
Client

In the client libraries we can create an empty BehaviorTree for each tree in the JSON, and then create their nodes (we can't create nodes together with the trees because nodes can have reference some tree).

Moreover, we need to update how BehaviorTree.tick method works, maybe breaking it in several internal methods. To understand that, consider the following situation:

a SoldierTree have two differences references to CombatTree (let's say C1 and C2);
in the client we only have two objects, one for SoldierTree and other for the CombatTree (for both C1 and C2);
if the SoldierTree calls C1 and then C2, everything will explode right away because both C1 and C2 are the same object, thus sharing the same IDs, nodes and node IDs (i.e., blackboards uses trees and nodes IDS to store information).

The same would occur if the CombatTree were referred by SoldierTree and CommanderTree.

So, before calling the subtree, we need to change temporarily its ID.

I'm not sure if this issue is barely understandable by anyone but me. I've been thinking a lot about this feature lately, so the description may lack some more contextualization.

--- Want to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/27127836-how-to-handle-multiple-trees?utm_campaign=plugin&utm_content=tracker%2F18331319&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F18331319&utm_medium=issues&utm_source=github).

Talisca commented 8 years ago

For one of our projects we had to modify behavior3js and behavior3editor just slightly to achieve this. In fact, your editor is already able to handle the usage of subtrees. There is just the missing routine to import such a project, which was more or less straightforward. I implemented the counterpart for behavior3js to import behavior3editor-projects and had to split up the tick-method into tick() and _execute() (I think?). So that a tree can execute its subtree's and provide its subtree's with its own blackboard.

If you're interested I'll provide you with the modified projects. I just don't know if the modifications still work with the latest versions.

renatopp commented 8 years ago

@Talisca, thanks for the reply.

Did you use something like that BehaviorCollection? Sure, I would like to see these modifications.

Talisca commented 8 years ago

First of all, sorry for my late response. I pushed my modifications long ago, but never got to the point to write a text. The repositories can be found in my profile.

@renatopp In general yes. b3.LoadProject (thats what I've called the method to load the behavior3editor-projects) returns a collection of all the unique tree's. Each subtree refers to one of the trees of this collection. I just didn't use the name of the tree's but the id (doesn't matter in our case).

Your mentioned problem of damaging states in the blackboard caused by multiple usage of trees is not handled in my pushed modification. I use the following solution in our project:

Create all main-tree's.
Go through each node of the tree's in the project-data and determine if the node is a tree
If the node is a tree, create a new BehaviorTree-instance for this node and save it in a subTree-collection.
At the end, connect the same root-nodes for the subtree's as for their main-tree's.

In our case we won't have a recursion anywhere (I just can't think of a case where this would be helpful). We use some tree's more then once in another tree. Here the saved states could be easily damaged without my modification above.

Another solution...

...I could think of, is the usage of an id-stack which is used to get the actual id for a tree/node. In _execute, I would push the tree-id to this stack with an incremental number indicating the current iteration step, e. g. this.idStack.push(this.id + iteration); Where iteration begins with 1 and is incremented for each new call of _execute(). This solves the same problem as above and I won't need to use more instances of the same tree.

tick.blackboard.get('isOpen', tick.tree.id, this.id); could then become something like tick.blackboard.get('isOpen', tick.tree.idStack.last(), this.id);

Somewhere at the end of each _execute-call, the id is removed and iteration is decremented. It's a fast implementation and does not increase the runtime that much.

Regarding recursions

I think there could be two favored behaviors.

A tree calls itself and expects that it is still open. Just to initialize some stuff in open().
A tree calls itself and expects that the sub-tree is closed.

The second part would be easily solved with the above idStack-solution. The first part expects the same id with every call. Could lead to an additional flag in the editor to determine which is desirable. I don't know.

Singleton tree's

There could be cases where we would like to use different properties for each sub-tree of the same kind. This essential information would be lost if we just use one instance of a tree. So this could come into play with the point above. I don't know. Currently we determine which creature should use which tree by using properties like creatureType, creatureFamily and so on. This happens in our LoadProject-method. If we would like to access the properties later in the nodes or somewhere else, they won't be there. I don't know if thats such a big problem.

behavior3 / behavior3editor