Discussing Behavior Trees

[davebaol]

I've opened this to discuss behavior trees API enhancements.

@implicit-invocation Resuming discussion https://github.com/libgdx/gdx-ai/pull/4#issuecomment-56509640 ... Not sure why you don't like the XML format, but I think that it has some advantages:

• comments are supported which can be really useful
• it's more powerful than json or any inline tab-based format.
• being it a standard format, external tools like editors (written in any language) can easily read/write a behavior tree.

So I'm playing with the XML format just to see what can be done. Currently I can successfully load a behavior tree from this file:

<BehaviorTree>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask" as="Bark"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask" as="Care"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.MarkTask" as="Mark"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask" as="Rest"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.WalkTask" as="Walk"/>
  <Root>
    <Selector>
      <Parallel>
        <com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask urgentProb="0.8"/>
        <AlwaysFail>
          <com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask/>
        </AlwaysFail>
      </Parallel>
      <Sequence>
        <Bark times="3"/>
        <Walk/>
        <Bark/> <!-- times defaults to 1, see BarkTask source code -->
        <com.badlogic.gdx.ai.tests.btree.dogtasks.MarkTask/>
      </Sequence>
    </Selector>
  </Root>
</BehaviorTree>

I added the "Import" tag to improve readability. It allows you to use the given alias in place of the fully qualified class name of the task. Actually Selector, Parallel, etc.. are predefined imports. Also, the "as" attribute is optional, meaning that the simple class name is used as the alias, i.e.

  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask"/>

creates the task alias "BarkTask". Also, I added task parameters, see urgentProb in CareTask and times in BarkTask. The attribute value is parsed according to the type of the corresponding field of the task class. For example, urgentProb is a float and times is an int. Supported types are: int, Integer, float, Float, boolean, Boolean, long, Long, double, Double, short, Short, char, Character, byte, Byte, and String.

Of course, we can maintain both formalisms as long as they have the same structural features. I mean, unlike task parameters, imports are just a syntactic sugar so they are not mandatory for the inline tab-based formalism.

I think we can use a "btree" branch in order to experiment with BT improvements while keeping the master branch clean.

[davebaol]

Wiki page updated, see Task Attributes and Constraints

[piotr-j]

Speaking of reflection, ability to serialize a tree would be useful probably. Due to circular references automatic serialization doesn't work at this point. I don't think a full serialization of a tree is needed, as they are created more often then not from tree files. Only ids and some state of currently running state would be required. There is no convenient way to get this info, or to restore it later. Maybe there is some clever way of doing this, but im too dumb to figure it out.

[implicit-invocation]

If we annotate the data fields, we can easily store the values of those fields, rebuild the tree from its definition and set those values back to nodes. Am I right?

[davebaol]

Yeah but we have also to save and restore the running task of each node and some other internal data for certain tasks. See this comment

[implicit-invocation]

It seems that kryo can save the tree into buffer and load the buffer into a tree just fine. I just have to ignore the blackboard field. For deterministic random, store the last seed and we will have the same sequence after reload.

Should we look into kryo source and borrow some logic? Will GWT backend be a problem?

[davebaol]

@implicit-invocation Interesting. I doubt kryo works for GWT though.

[implicit-invocation]

https://bitbucket.org/zbill/btree-serialization

My student set up a working example using kryo. Kryo doesn't seem to work with GWT. But we can borrow some of their reflection logic for our specific case.

[davebaol]

@implicit-invocation Cool, thanks. It's a nice proof of concept that we can add to the tests and simply exclude from GWT compilation set. This is enough IMO, no real need to overcomplicate the framework. What do you think?

BTW, sometimes I get this exception when loading the tree twice in a row:

Exception in thread "LWJGL Application" java.lang.IllegalArgumentException: Field "object" not found on class: com.badlogic.gdx.ai.btree.BehaviorTree
    at com.esotericsoftware.kryo.serializers.FieldSerializer.removeField(FieldSerializer.java:633)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.rebuildCachedFields(FieldSerializer.java:277)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.rebuildCachedFields(FieldSerializer.java:182)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.read(FieldSerializer.java:538)
    at com.esotericsoftware.kryo.Kryo.readObjectOrNull(Kryo.java:727)
    at com.dongbat.tree.utils.KryoTree.loadTree(KryoTree.java:47)
    at com.dongbat.tree.GameScene.load(GameScene.java:64)
    at com.dongbat.tree.GameScene$2.clicked(GameScene.java:112)
    at com.badlogic.gdx.scenes.scene2d.utils.ClickListener.touchUp(ClickListener.java:89)
    at com.badlogic.gdx.scenes.scene2d.InputListener.handle(InputListener.java:58)
    at com.badlogic.gdx.scenes.scene2d.Stage.touchUp(Stage.java:348)
    at com.badlogic.gdx.backends.lwjgl.LwjglInput.processEvents(LwjglInput.java:306)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication.mainLoop(LwjglApplication.java:207)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication$1.run(LwjglApplication.java:120)

[implicit-invocation]

Well, i got that exception on both saving and loading after the first load. It seems that FieldSerializer.removeField is called every time kryo.readObjectOrNull and kryo.writeObjectOrNull is called. Trying to find a way to fix but I'm not so familiar with kryo.

[davebaol]

Yeah, anyways I think Dog should have a (circular) reference to the tree and we should serialize the dog (usually in games entities like our dog have their own state that must be serialized too). Also, by doing this there's no need to remove the field object from the serializer, I guess. If I got it right Kryo can manage circular references properly.

[badlogic]

Reading that last message out of context is hilarious :) On Jul 22, 2015 9:01 PM, "davebaol" notifications@github.com wrote:

Yeah, anyways I think Dog should have a (circular) reference to the tree and we should serialize the dog (usually in games entities like our dog have their own state that must be serialized too). Also, by doing this there's no need to remove the field object from the serializer, I guess.

— Reply to this email directly or view it on GitHub https://github.com/libgdx/gdx-ai/issues/12#issuecomment-123828102.

[implicit-invocation]

But hey, finding a way to ignore the dog is easier than going deep into the dog and serializing everything, isn't it?

[davebaol]

Well, I got it working by serializing the dog, which makes the example a bit more realistic IMO. And you don't even have to register a FieldSerializer to remove the object field.

[implicit-invocation]

@davebaol It doesn't work like that. After deserializing, some tasks hold references to a different dog from the tree. The tree tries to pass the original object every run, but childFail childSuccess fail success still depends on this.object.

I think we should remove the blackboard reference from Task, only pass down reference of the tree. So every this.object will become tree.getObject()

I'm kind of busy lately, can you do it for me please?

[davebaol]

It doesn't work like that. After deserializing, some tasks hold references to a different dog from the tree. The tree tries to pass the original object every run, but childFail childSuccess fail success still depends on this.object.

For sure some tasks can have a null object, but how can it be a different dog from the tree? You should explicitly set a new blackboard on the tree to make it happen, right? And I'm not doing this.

I think we should remove the blackboard reference from Task, only pass down reference of the tree. So every this.object will become tree.getObject()

If I got it right this means we should remove the object argument from start, end and run methods.

[implicit-invocation]

For sure some tasks can have a null object, but how can it be a different dog from the tree? You should explicitly set a new blackboard on the tree to make it happen, right? And I'm not doing this.

Oh, my bad, it's because of my custom serializer.

But I still think it's better to remove object field in Task. After deserialization, when I call setObject, blackboard reference in node doesn't change.

If I got it right this means we should remove the object argument from start, end and run methods.

Agree.

[davebaol]

Done! See commit 59cddd95bb45cf8a52cbf3a8490eef9d7b5b2aec

[implicit-invocation]

Cool! That should help avoiding the problem of changing blackboard of a running tree.

[davebaol]

Yep, by the way I'm trying to improve Parallel in order to avoid having to add, remove and find running tasks. Do you think this implementation is correct? A diff will show you the (few) changes I made.

package com.badlogic.gdx.ai.btree.branch;

import com.badlogic.gdx.ai.btree.BranchTask;
import com.badlogic.gdx.ai.btree.Task;
import com.badlogic.gdx.utils.Array;

/** A {@code Parallel} is a special branch task that starts or resumes all children every single time, parallel task will succeed
 * if all the children succeed, fail if one of the children fail. The typical use case: make the game entity react on event while
 * sleeping or wandering.
 * 
 * @param <E> type of the blackboard object that tasks use to read or modify game state
 * 
 * @author implicit-invocation
 * @author davebaol */
public class Parallel<E> extends BranchTask<E> {

    private boolean[] runningTasks;
    private boolean success;
    private boolean noRunningTasks;
    private int currentChildIndex;

    /** Creates a parallel task with no children */
    public Parallel () {
        this(new Array<Task<E>>());
    }

    /** Creates a parallel task with the given children
     * @param tasks the children */
    public Parallel (Task<E>... tasks) {
        this(new Array<Task<E>>(tasks));
    }

    /** Creates a parallel task with the given children
     * @param tasks the children */
    public Parallel (Array<Task<E>> tasks) {
        super(tasks);
        this.success = true;
        this.noRunningTasks = true;
    }

    @Override
    public void start () {
        if (runningTasks == null)
            runningTasks = new boolean[children.size];
        else {
            for (int i = 0; i < runningTasks.length; i++)
                runningTasks[i] = false;
        }
        success = true;
    }

    @Override
    public void run () {
        noRunningTasks = true;
        for (currentChildIndex = 0; currentChildIndex < children.size; currentChildIndex++) {
            Task<E> child = children.get(currentChildIndex);
            if (runningTasks[currentChildIndex]) {
                child.run();
            } else {
                child.setControl(this);
                child.start();
                child.run();
            }
        }
    }

    @Override
    public void childRunning (Task<E> task, Task<E> reporter) {
        runningTasks[currentChildIndex] = true;
        noRunningTasks = false;
        control.childRunning(this, this);
    }

    @Override
    public void childSuccess (Task<E> runningTask) {
        runningTasks[currentChildIndex] = false;
        success = success && true;
        if (noRunningTasks && currentChildIndex == children.size - 1) {
            if (success) {
                success();
            } else {
                fail();
            }
        }
    }

    @Override
    public void childFail (Task<E> runningTask) {
        runningTasks[currentChildIndex] = false;
        success = false;
        if (noRunningTasks && currentChildIndex == children.size - 1) {
            if (success) {
                success();
            } else {
                fail();
            }
        }
    }

    @Override
    public void reset () {
        super.reset();
        if (runningTasks != null) {
            for (int i = 0; i < runningTasks.length; i++)
                runningTasks[i] = false;
        }
        success = true;
    }

}

[implicit-invocation]

I don't see any problem in your implementation. Just some tiny little bit

    success = false;
    if (noRunningTasks && currentChildIndex == children.size - 1) {
        if (success) {
            success();
        } else {
            fail();
        }
    }

Is it safe to just call fail() after setting success = false

[davebaol]

Sounds more than reasonable :)

[ttilby]

I am confused by the implementation of the Parallel node. Suppose I have this simple example

...
Parallel
    noEnemyInSight?
    walk
...

Assume walk takes 10 steps of the tree to complete, and is therefore a running task. If after 3 steps an enemy comes into view, I would expect the noEnemyInSight task to fail causing the Parallel task to fail and therefore the walk task would be stopped.

However, the Parallel task waits until all children have finished before it will succeed or fail.

I see in the Dog example that RestTask does a condition check against isUrgent to decide if it should keep running or fail. This seems counter-intuitive since the whole purpose of the Behavior Tree is to make these decisions.

Putting conditions in the task nodes defeats the purpose of using a Parallel node to check conditions. And if these are removed from the tree then the behavior is no longer fully represented in the tree.

Is there a specific case that requires Parallel to allow all children to finish? Am I missing something?

[davebaol]

@ttilby @piotr-j I see your point, a parallel task that fails as soon as one of its children fails is likely more useful and intuitive. However I think that we should change/extend the API to properly support this policy. When one of the child tasks ends in failure, Parallel should somehow "terminate" all of the other children that are still running. We cannot just keep them in running state because this could make the game inconsistent maybe not freeing resources (such as acquired semaphores).

@implicit-invocation What do you think?

[ttilby]

One idea is to use an optional Task Attribute that specifies how many child fails are required to cause the Parallel task to fail. If not set, this could default to all, essentially keeping the current implementation.

...
Parallel childFail:2
    condition1
    condition2
    condition3
    runningTask
...

In this example, if 2 of the 4 children fail, then the Parallel task would fail, and it could call end() on any children that are running.

[piotr-j]

More options is definitely a good thing. Perhaps adding cancel() or something like that would be useful in this situation to distinguish it from end(), but it would require a lot of changes.

[davebaol]

@ttilby Well, letting childFail attribute default to all won't keep the current implementation because now parallel fails when one child failed and the other children are no longer running, regardless of whether they failed or succeeded.

[ttilby]

@davebaol You are correct. Another idea is to create a shortCircuit attribute that will cause a fail as soon as a child fails. This would default to false keeping the current implementation. Thoughts?

[piotr-j]

Perhaps something along the lines of parallel from jbt would work?

Parallel: task that concurrently executes all its children. A Parallel task does have a parallel policy. If the parallel task’s policy is sequence, the parallel fails if one child fails; if all succeed, then the parallel succeed. If the parallel task’s policy is selector, the parallel fails if all its children fail. If one succeeds, then the parallel also succeeds.

https://github.com/gaia-ucm/jbt/tree/master/UserGuide

[davebaol]

Yeah that's a more complete and object-oriented solution.

Just 2 considerations though:

• Our implementation does not use multi-threading, so parallel's children are not executed concurrently but rather sequentially within one frame.
• You could also imagine hybrid policies, where parallel returns success or failure after some specific number or proportion of its children have succeeded or failed. However, having too many policies might be confusing or even counterproductive in certain situations. Usually it's better to give level designers (that are not necessarily developers) a set of simple and useful tasks that they can intuitively understand and use to produce entertaining behaviors. In this case, simply making sequence policy the default policy should make designer's life easier, I guess.

[implicit-invocation]

Parallel failing on childFail sounds plausible to me too. But what should happen with running children? Will a reset() call sufficient? We can modify reset() on some types of task instead of adding a cancel method.

[davebaol]

Yeah looks like they are similar but reset implementation in Task calls itself on ALL children while cancel should likely call itself on RUNNING children only, if I got it right.

[piotr-j]

Cancelling on running tasks sounds like a reasonable idea.

[implicit-invocation]

If it's only about the Parallel, we can override reset to leave those non-runnings alone. Leave the parallel policy aside temporarily, we assume those non-runnings are succeeded tasks. So we just have to ensure reset does similar things to those running tasks as success or fail does.

@piotr-j If it's not reset but a new cancel method, what should cancel do? Should we allow LeafTask to override cancel?

[piotr-j]

From my point of view, cancel is about extra information for a task. I guess a task that cares about that might just check some internal state in reset or end.

[davebaol]

Personally I think that reset and cancel have different semantics and use:

• you reset a task (typically a whole tree) when you want to reuse it instead of cloning a new one from the archetype or parsing it once again
• you cancel a running task when you (typically the parent) have to terminate it for whatever reason

[implicit-invocation]

In case we have a parallel inside another parallel, selector inside a parallel inside another selector or any other branch task. When we cancel the parent, we need to cancel the whole subtree too. I'm just wondering what logic should we implement in cancel. If there are a lot of redundants, should we let cancel and reset call each other?

[davebaol]

Hmmmm... I'm going to start playing with task termination soon. We'll see what comes out. :)

BTW just added enum support in behavior tree files, see commit 9f6ef61db67626a7c4748606010e745c4745f051. This is a generally useful feature and will come in handy in case parallel's policy will be implemented by enums. For instance, in Java:

public class Parallel<E> extends BranchTask<E> {
    @TaskAttribute
    public Policy policy;

    ...

    public enum Policy {
        Sequence() {
            ...
        },
        Selector() {
            ...
        };

        ...
    }
}

In tree file

    parallel policy:"selector"

[davebaol]

Just started playing with task termination. I like the idea that cancel calls end. Just like start is called when the task is entered, end should be called when the task is exited regardless of whether it succeeded, failed or has been terminated. So cancel implementation in Task should be something like that

    /** Terminates this task and all its running children. */
    public void cancel () {
        if (runningTasK != null) {
            runningTask.cancel();
            runningTask = null;
            end();
        }
    }

However, I think that we have a problem with the current implementation of end in Decorator, i.e.

    @Override
    public void end () {
        child.end();
    }

When a running decorator is cancelled the end method of its child is called twice, which should never happen. If I got it right, Decorator should be like that (original code commented)

public abstract class Decorator<E> extends Task<E> {
    ...

    @Override
    public void run () {
//      child.run();
        // replace code above with the following
        if (runningTask == null) {
            runningTask = child;
            runningTask.setControl(this);
            runningTask.start();
        }
        runningTask.run();
    }

//  @Override
//  public void end () {
//      child.end();
//  }

//  @Override
//  public void start () {
//      child.setControl(this);
//      child.start();
//  }

    @Override
    public void childRunning (Task<E> runningTask, Task<E> reporter) {
//      control.childRunning(runningTask, this);
        // replace code above with the following
        this.runningTask = runningTask;
        running();
    }

    @Override
    public void childFail (Task<E> runningTask) {
//      control.childFail(this);
        // replace code above with the following
        this.runningTask = null;
        fail();
    }

    @Override
    public void childSuccess (Task<E> runningTask) {
//      control.childSuccess(this);
        // replace code above with the following
        this.runningTask = null;
        success();
    }
}

What do you think? Am I missing something?

[davebaol]

Just a thought that came to my mind while I was reviewing behavior trees implementation. Since each task owns a reference to the tree it belongs to, what about the possibility to add listeners to the tree? Listeners could be notified when tasks change status: RUNNING, FAILED, SUCCEEDED and CANCELLED. This should make debugging easier. Also, I'd say that tools like this one could really benefit from such a feature.

[piotr-j]

Would probably be useful for some visualization tools as well.

[implicit-invocation]

That's where our inheritance based approach show its weakness. Just a missing super call will cause no event firing at all :cry:

[davebaol]

@piotr-j The mentioned tool is a simple tree viewer with serialization/deserialization capability. I'd like to add an improved version to the tests.

@implicit-invocation Right, but we can add to the tree a boolean field that defaults to false. If it's true we check missing super call invocations.

[davebaol]

Also, the user will typically override only the methods start, run and end. I think that listeners should be notified on running, fail, success and cancel methods.

[implicit-invocation]

so final?

[piotr-j]

@davebaol ah i see, cool. making relevant methods final would prevent certain types of errors.

[davebaol]

not sure about final, it might be too constraining

[implicit-invocation]

running is already final so success, fail and cancel can be final too if you still want to allow overriding, we can have something like this

    public final void success () {
        onBeforeSuccess();
        tree.fire(Events.TaskSuccess, this);
        onAfterSuccess();
    }

    public void onBeforeSuccess() {
        end();
        control.childSuccess(this);
    }

    public void onAfterSuccess() {
    }

[davebaol]

running is already final so success, fail and cancel can be final too

Indeed, I got it working nicely with final. There should be no need to override them since you can already override the corresponding childXXX methods.

[davebaol]

Ok, this is what I got so far:

• Behavior tree API revised and improved:
  • Now tasks have a status that is updated each time they run.
  • Added enum support in behavior tree files.
  • Now parallel task can specify sequence or selector policy.
  • Added cancel method for task termination, mainly used by the parallel task.
  • Now task methods success and fail are final.
  • Now you can add listeners to the tree in order to be notified when a task has run.
  • Added some tasks, namely Repeat decorator and Wait leaf.
• Added a behavior tree viewer useful for debugging and learning purpose.
• Dog sample tree expanded.

See commit de8a16d3e0d290355b1a4444049556a45e41ea23

Please, run the BehaviorTreeViewer and play with it. There's still something wrong after loading a serialized tree: some tasks executed in the last step are gray instead of yellow.

[davebaol]

Recent changes:

• Added leaf tasks Failure and Success.
• Added Random decorator.
• Now the UntilFail decorator succeeds when its child fails.
• Now the Repeat decorator always succeeds when reaches the specified number of repetitions.
• Now listeners are notified when a child is added to a task which is required for lazy Include decorator.
• Now method addChild is final and Task's subclasses have to implement addChildToTask.
• Task's method setControl is now final.