orxBT (Behavior trees integrated with orx)

edited June 2015 in Projects - Tools
Hi Everyone,

I'd like to introduce you a new library I've been developing to use in my most recent game. I've developed this library, in response to the spaghetti code that would be required to implement the tutorial scene for the game.

After researching a while, I've realized that what I needed to properly implement an intelligent sequence was a behavior tree. Now that I have a pre-alpha version of the library, I've used it to develop the first sequence of the tutorial (there'll be more).

Here's a video of the result, followed by the code that implements it:


auto wait_for_food_behavior = sequence{
    execute_command(inherit, "none", "SetConstraints", $o("Sparrow"), "SparrowConstraints"),
    execute_command(inherit, "none", "SetController",  $o("Sparrow"), "SparrowEatConverger"),
    wait_for_state($o("Sparrow"), "Chew")
};

auto cursor_move_to_flake_behavior = sequence {
    execute_command(inherit, "Target", "GetFirstNodePosition", $o("Flake")),
    move($o("Cursor"), $v("Target"), 12)
};

auto cursor_behavior = repeat <<= sequence {
    invert <<= repeat <<= any {
        timeout(0.3),
        invert <<= cursor_move_to_flake_behavior
    },
    execute_command(inherit, "none", "Object.SetAnim", $o("Cursor") ,"HandTouchAnim"),
    timeout(0.2),
    execute_command(inherit, "Target", "Object.GetPosition", $o("Sparrow")),
    move($o("Cursor"), $v("Target"), 12),
    execute_command(inherit, "none", "Object.SetAnim", $o("Cursor") ,"HandHoverAnim")
};

auto tutorial_feeding_stage = sequence {
    create(inherit, "Text","TutorialWelcomeBoard"),
    timeout(1),
    create(inherit, "Sparrow","TutorialSparrow"),
    timeout(1),
    set_content($o("Text"),"TutorialSparrowIntroductionText"),
    timeout(1),
    create(inherit, "Flake", "TutorialCheeseFlake"),
    timeout(1.5),
    create(inherit, "Cursor", "TutorialCursor"),
    any {
        wait_for_food_behavior,
        cursor_behavior
    },
    set_content($o("Text"),"TutorialSparrowFeedCongratulations"),
    destroy(inherit, "Cursor"),
    execute_command(inherit, "none", "SetNextLevel", inherit, "RegularLevel"),
    constant(behavior_t::RUNNING)
};

Now, first of all, the down sides; I use GCC 4.8 to compile the game to my current target platforms and I'm using the latest C++ features, so the library will probably not compile with MSVC (possibly with MSVC 2015). I expect it to compile with recent versions of Clang though.

If you're still reading, I'll walk through the code, but you might want to read about behavior trees first if you're not familiar with them.

The first bit:
auto wait_for_food_behavior = sequence{
    execute_command(inherit, "none", "SetConstraints", $o("Sparrow"), "SparrowConstraints"),
    execute_command(inherit, "none", "SetController",  $o("Sparrow"), "SparrowEatConverger"),
    wait_for_state($o("Sparrow"), "Chew")
};

Here we define a sequence of actions to be taken and store this behavior under the "wait_for_food_behavior" variable. The sequence has 2 "execute_command" steps. These steps actually execute freeform commands that you can call from the orx console.

execute_command(inherit, "none", "SetConstraints", $o("Sparrow"), "SparrowConstraints")

The first argument "inherit" is the context, in which this command will be executed. The second argument "none", is the key that the result of the command will be stored in. In this case, we're ignoring the result. "SetConstraints" is the name of the command. Now, the interesting bit; the fourth argument $o("Sparrow") is an "extractor". It extracts an orxOBJECT stored in the command's context (the one we gave with "inherit") with the key "Sparrow". The extractor then feeds this argument to the orxCommand. The last argument is a simple string that will be passed along to the command as the second argument.

The purpose of this first step is to lift the restrictions on the Sparrow, that stops it from opening its mouth.

The second step, again an "execute_command" type behavior, causes the sparrow to open its mouth, and wait for any food pieces to eat (and eat it when it comes). Note that these "execute_command" type behaviors are instantaneous. If there's no problem with the execution, they immediately return "SUCCEEDED" and cause the sequence behavior to continue executing the next step.

The third step is a behavior that watches a "state machine" type object (which the sparrow is) and returns success when the object enters the given state. Unlike the previous two steps, this one blocks the sequence until the expected state is entered.

These steps together form the behavior which enables the sparrow to eat a piece of food, and waits until it does that.

The second bit:
auto cursor_move_to_flake_behavior = sequence {
    execute_command(inherit, "Target", "GetFirstNodePosition", $o("Flake")),
    move($o("Cursor"), $v("Target"), 12)
};

Here, we're describing the behavior of the cursor while it moves towards the food piece. We first acquire the position of the "Flake" with an "execute_command" type behavior and record it in the "Target" field of the current context.

The next step is a "move" behavior. It extracts the "Cursor" object and moves it towards the "Target" vector, again extracted from the enclosing context. The speed of the move is given with the "12" argument. Note that the move behavior is unlike a simple "Object.SetPosition". The move takes place over time, and the sequence blocks until the target position is reached.

The third bit:
auto cursor_behavior = repeat <<= sequence {
    invert <<= repeat <<= any {
        timeout(0.3),
        invert <<= cursor_move_to_flake_behavior
    },
    execute_command(inherit, "none", "Object.SetAnim", $o("Cursor") ,"HandTouchAnim"),
    timeout(0.2),
    execute_command(inherit, "Target", "Object.GetPosition", $o("Sparrow")),
    move($o("Cursor"), $v("Target"), 12),
    execute_command(inherit, "none", "Object.SetAnim", $o("Cursor") ,"HandHoverAnim")
};

Now, the behavior tree gets interesting. Here, we're describing the complete behavior of the cursor. The first step in the sequence is a composite behavior, and it does something very interesting. First, note the "invert <<= repeat <<= any" bit. This clause is a composition of the "any" type behavior with the "repeat" and "invert" type behaviors.

"repeat" repeats a given behavior until it returns failure. "invert" runs its child behavior, and it returns failure if the child returns success, and vice versa. The "any" behavior looks like the "sequence" behavior, but it runs very differently. "any" runs all of its children in parallel, and it returns success or failure if any one of them returns success or failure.

So, what's the purpose of this contraption you say:
invert <<= repeat <<= any {
    timeout(0.3),
    invert <<= cursor_move_to_flake_behavior
}

What happens here is that the previously defined "cursor_move_to_flake_behavior" is run in parallel with a timeout of 0.3 seconds. The timeout returns success after 0.3 seconds and causes the any to return success, which in turn causes repeat to restart the any. The result of this is that the cursor_move_to_flake_behavior is reinitialized and the target of the move is updated. The purpose of the double "invert"s is to terminate the repeat when the target is reached , in which case, move returns success => invert returns failure => any returns failure => repeat terminates with failure => outermost invert returns success!

So the whole purpose is to track the food piece while moving towards it.

Now, back to "cursor_behavior". The next step is:
execute_command(inherit, "none", "Object.SetAnim", $o("Cursor") ,"HandTouchAnim")

This command sets the target anim of the "Cursor" to "touch" to give the click impression. The next step is a 0.2 second wait, followed by a move towards the "Sparrow". The last command in the sequence lifts the finger of the cursor once it reaches the Sparrow. Note how the entire sequence is fed to a "repeat" behavior, so that the cursor continuously moves back and forth.

Now, the last bit:
auto tutorial_feeding_stage = sequence {
    create(inherit, "Text","TutorialWelcomeBoard"),
    timeout(1),
    create(inherit, "Sparrow","TutorialSparrow"),
    timeout(1),
    set_content($o("Text"),"TutorialSparrowIntroductionText"),
    timeout(1),
    create(inherit, "Flake", "TutorialCheeseFlake"),
    timeout(1.5),
    create(inherit, "Cursor", "TutorialCursor"),
    any {
        wait_for_food_behavior,
        cursor_behavior
    },
    set_content($o("Text"),"TutorialSparrowFeedCongratulations"),
    destroy(inherit, "Cursor"),
    execute_command(inherit, "none", "SetNextLevel", inherit, "RegularLevel"),
    constant(behavior_t::RUNNING)
};

This is the main behavior node that describes the entire tutorial sequence shown in the video. It starts by creating the objects in the video. Creates the text board and stores it under the key "Text", waits for a second, creates the sparrow, waits for another second, and sets the content of the text board to the object given in the config section "TutorialSparrowIntroductionText". It then creates the food piece and the cursor. Now the next step is interesting; it runs the bird opening its mouth and waiting for food, in parallel with the continuous back-and-forth movement of the cursor. Note that the cursor_behavior never terminates, but the wait_for_food_behavior terminates when the bird gets to the "Chew" state (as a result of being fed by the player).

Once the parallel step terminates, the "Text" is switched to a congratulations string, the cursor is destroyed and the "SetNextLevel" command is called on the current context (which destroys it.). If the context weren't destroyed, the next step would be executed, which is a "constant" behavior, that returns its argument whenever executed. In this case, it returns "RUNNING" ad-infinitum, causing nothing else to happen.

This is all that describes what's happening in the video. The code is all in C++, but I've designed the library since the beginning to expose it completely to the config module, so that this tutorial sequence could be programmed entirely without a single line of C/C++ code..

The library is intended to provide a continuum of dynamic coding. You can define behaviors in C++ and expose them to the config module with a single "register" function call.

Note that the Sparrow state machine is also using this library, so that the states are automatically exposed to the config module. I.e. the "Chew" state is registered automagically. I can talk about that as well if you're interested. In this library, I've merged state machines and behavior trees in an unconventional way, but this post is already too long, so I'll stop now.

I'm going to open-source this library, as soon as it reaches some maturity (for instance, as soon as one can actually define the behavior trees in the config files). Meanwhile, what do you think the syntax of the config sections be?

I can give more details on any part if you're interested.

Comments

  • edited June 2015
    This is pretty impressive. There's a lot to digest here. The trick between your definitons, and config entries, would be that yours contain variables and config doesn't. That could be a stumbling block.

    But I really need to sit down and read through this properly.
  • edited June 2015
    Thanks for taking the time sausage, about the Config not containing variables, that shouldn't be a problem since the variables in the behaviors actually refer to entries in the behavior's context. Currently, the context belongs to the root object (tutorial level in this case), but I'm planning to add behavior nodes that manipulate the context observed by its child tree. So, in effect, when you say SomeBehavior($o("SomeVariable")), this is analogous to calling a function Somebehavior(SomeVariable) in C++, where "SomeVariable" refers to a variable (of type orxOBJECT *) in the local scope. The whole purpose with the context is to be able to construct re-usable modular behaviors.

    I've been scratching my head over this for quite some time now, and I think behavior trees are awesome for representing behaviors (duh!). I also think they can be made to converge with orx's config and command systems seamlessly. I hope that this can be useful to the orx community in general.

    I'd really be grateful if I could get some feedback about the design decisions I've made and also some ideas about how to represent behavior trees in .ini files.

    To be more specific, how can we represent, say:
    auto cursor_move_to_flake_behavior = sequence { 
        execute_command(inherit, "Target", "GetFirstNodePosition", $o("Flake")), 
        move($o("Cursor"), $v("Target"), 12) 
    };
    

    One idea that comes to mind is:
    [MoveToFlakeBehavior]
    Type = sequence
    Behaviors = execute_command inherit Target GetFirstNodePosition $O>Flake #
                move $O>Cursor $V>Target 12
    

    I actually intend to get rid of all "inherit" arguments by passing the current context implicitly. If you need to create a subcontext, you'll be using a behavior transformer like "invert" or "repeat", so it should be more like:
    [MoveToFlakeBehavior]
    Type = sequence
    Behaviors = execute_command $V>Target GetFirstNodePosition $O>Flake #
                move $O>Cursor $V>Target 12
    

    Another alternative, that seems more orx configish (because it resembles an animation section and it uses lists) is:
    [MoveToFlakeBehavior]
    Type = sequence
    Behavior1 = execute_command # $V>Target # GetFirstNodePosition # $O>Flake
    Behavior2 = move # $O>Cursor # $V>Target # 12
    

    Neither of these can represent nested behavior branches as well as the C++ code, is that a problem though?

    Another important design decision is how to represent behaviors with arguments? In C++, you can easily write a function that takes arguments and returns a behavior using those arguments (even though there's no example in the code above, it's trivial, really, you can just return behaviors, they're not polymorphic, their type is a simple "behavior_constructor"). If the config-defined behaviors are to be first-class, they should also be able to accept arguments. Imagine that we wanted to write the same MoveToFlakeBehavior that accepts a speed argument, maybe we could do it like this:
    [MoveToFlakeBehavior]
    Type = sequence
    Behavior1 = execute_command # $V>Target # GetFirstNodePosition # $O>Flake
    Behavior2 = move # $O>Cursor # $V>Target # $$1:12
    
    Note $$1:12 means, the first argument with a default value of 12

    So that if you're going to use MoveToFlakeBehavior in another behavior you'd write:
    BehaviorN = MoveToFlakeBehavior # 15
    

    One last important point is how to represent behavior transformers like "repeat", I'm really leaning towards enabling a syntax like this:
    BehaviorN = invert # repeat # MoveToFlakeBehavior #  15
    

    Specifically, I'm leaning to allow that if the last argument of a behavior is another behavior, you can just write it in-place.

    I'd also like to mention that while you're defining behaviors, you don't actually construct any behaviors, you're just creating nested behavior_constructors. So a "sequence" term returns a behavior_constructor, which in turn contains behavior_constructor's that get called just in time to execute a given behavior. This actually enables me to expose a very simple interface, while reserving the possibility to do many optimizations. In time, we could for instance "compile" a behavior along with its context so that each of those string variables get assigned a variable_id that points to the elements of a context array, greatly improving efficiency without touching user code.

    A final point I'd like to touch, is that the "context" I keep talking about is similar to scopes in conventional programming languages. I don't know maybe I should have called it "scope" in the first place :/. Especially when you introduce behavior nodes that manipulate (replace or extend) the context, it starts to look like function scopes.

    Sorry, I know I've just added a bit more stuff on top of the poorly explained stuff I had already dumped here, but please take your time if you're interested. I'm not working on this until Thursday next week anyway.

    I'm really excited about this since I've realized my entire game logic can be implemented elegantly with behaviors assigned to objects and levels, and these behaviors can be made extremely efficient (rivaling hand-written code). I've also realized that a very nice behavior tree editor can be built on top of the config implementation.

    Cheers
  • edited June 2015
    Sorry for the delay, I wanted to get enough time to read everything and understand all the implications and thought I'd be able to do that this week end.
    Turns out I didn't, so hopefully I'll get enough time in the coming days.

    BTs are interesting, and having config-driven ones will definitely be a nice feature to have. A few years ago we did have a FSM module, but the contributor who wrote it left before finishing it (and that was much before the config days).

    Being an AI programmer by trade, I've used BTs extensively on some projects (though I personally prefer Hierachical FSM for a very similar result).

    At the moment, I feel like I can do all my UI/tutorial work using timelines, but that doesn't mean I wouldn't be using that later on.

    I'll comment again as soon as I can get enough "awake brain time" to go over your posts. :)
  • edited June 2015
    iarwain wrote:
    Sorry for the delay

    No problem, I really appreciate you thinking deeply about this. I'll be glad whenever you find the time. In the meantime, I'll be applying the library in its current form and get some hands-on experience, without attempting to expose it to the config module. I'm trying to figure out how much type-safety I can get while presenting an interface that will allow optimizations later.
    BTs are interesting, and having config-driven ones will definitely be a nice feature to have.

    What do you think about the fact that my current implementation relies heavily on C++14? Newer versions of Clang and GCC should be fine with it, so should MSVC2015 I think. Do you think it would be enough to create an extern "C" interface for the config-driven parts and some type-erased registration functions to add your own behavior nodes. We could then compile it for each platform and ship it as a C binary for incompatible compilers. Those who use compatible compilers can of course use the full power of the library.

    Being an AI programmer by trade, I've used BTs extensively on some projects (though I personally prefer Hierachical FSM for a very similar result).

    Great! Which BT infrastructure did you use? BTW, if I may ask, what game engine do you use at your day job?

    As for FSM, the library source files are actually sitting in a folder called orxFSM right now, since I first started implementing a library for that.

    The sparrow actually runs as a (flat) FSM when left alone, but I've played a bit with the FSM architecture and put some probes into it to be able to impose behaviors. In this architecture, you have a base FSM (sort of) which defines the physical constraints of the objects. Which transitions it can make under what circumstances, and how it interacts with the world in a given state. On top of that, you have a "controller" that defines the behavior of the object. So, for instance, the sparrow can tweet anytime it's idling and the base FSM defines the tweet behavior, but it's the controller that chooses when to tweet. The default controller for the sparrow occasionally tweets randomly, but you can assign other controllers, and that's how the behavior tree manipulates the sparrow without violating its constraints.

    My FSM implementation also provides somethings for free. For instance, you can externally forbid states, so the controller can't enter them, I'm also planning to enable forced transitions.

    I've also defined a generic controller called a "state converger". You create a state converger by giving it an ordered list of states, and that controller simply tries to get to a higher priority state (defined by the order) whenever possible. This way, when you tell the sparrow to "Eat", you can define how it should come to that state without violating its constraints.

    I'm not very experienced in FSMs nor in BTs, so, PLEASE warn me if all of this is nonsense. I've been thinking about FSM vs BT for a while, and I think the two are very closely related, and they can in fact be used to implement each other. But my feeling is that BTs are nicer if you have A LOT OF states with a sparse and regular transition graph. Juggling 1000s of states is tractable with BTs as long as they satisfy that condition. And FSM wins if you have less states (~10s?) but they have a dense and irregular transition graph. That's why my very-non-expert opinion is that they complement each other.
    At the moment, I feel like I can do all my UI/tutorial work using timelines, but that doesn't mean I wouldn't be using that later on.

    I'm actually planning to create an "orx timeline behavior node", which will assign a track to an object, and return SUCCEEDED once the timeline is completed. I'm also planning to add a similar FX node. Thanks to C++14 features, it's extremely easy and type-safe to define new nodes.

    I've considered using timelines to implement my tutorial, but the problem is that I want to be able to guide the user. For instance when they do something wrong I should be able to warn them, and I should also be able to advance the tutorial once the user does what's expected. One can of course achieve this through timelines + some code, but BTs seem to be more elegant and reusable.
    I'll comment again as soon as I can get enough "awake brain time" to go over your posts. :)

    Sure! Whenever you feel like it.
  • edited July 2015
    Sorry for taking so much time replying, I feel like I won't really have the time to think about it clearly before my vacations in August though. :/
  • edited July 2015
    No problem, really. Meanwhile, I'll be exploring my current implementation, so that we also have a concrete example. I've almost completed the tutorial and it's composed of roughly 200-250 behavior nodes. It's serving as a nice application to try out the idea.
Sign In or Register to comment.