Implementation Behavior Trees

[synopia]

Name: Behavior Trees
Summary: API + Implementation for stable and optimized behavior trees.
Scope: Engine / Mod
Current Goal: Implement the core elements of a behavior tree and the interpreter.
Phase: Design / Implementation
Curator: synopia
Related: Pathfinding, Minions

After coding for the Pathfinder, I found myself repeating some horrible code. Biggest problem is, most handler and events may take some time (frames) to finish. So you need kinds of state checking and code branching A LOT.
On my search for alternatives I found behavior trees. I think they are great. GREAT! This is the incubator for BT.
So far I got some code sketched together to show its working. For now its in the Pathfinding module. Since its not directly related to the pathfinder, this will probably move to another place.

Some references:
http://aigamedev.com/insider/presentations/behavior-trees/
http://aigamedev.com/open/article/bt-overview/

 

[synopia]

Okay, here is a short overview to behavior trees (BT).

First, look at the image I attached to this post. You will see the current behavior tree for minions. Its very basic and simply makes any minion to move to the local player.

The root box on top is the starting node of the BT. Its a composite node, because it has multiple children. The arrow indicates, this is a sequence, which means each child is processed after each other.

The node marked with (1) sets minions primary target to the local player position. Next is the movement to nearby walkable block (walkable blocks are part of the navigation graph). This ensures, the minion is always located in the navgraph. Node (2) is a parallel composite, which means all children are run in parallel. In this case, the children are MoveToWalkableBlock (which is a sequence of finding next navgraph block and moving there) and PlayAnimation.

Node (3) and (4) are finally the actual move commands. First, we need to find a path (3) from current position to actual target (which was set by (1)). When we find the path, we need to move along step by step (4).

How this BT is executed? Basically, for each minion its very own BT is updated each game update tick. This is done by walking through the tree in depth first order (in the example: (1), (2.1)+(2.2), (2.1.1), (2.1.2), (3), (4), (4.1), (4.2)). Each node has an update method which must return either SUCCESS, FAILURE or RUNNING. As soon as the BT "interpreter" gets to a node returning RUNNING, the execution is interupted and restarted in the next game update tick.

Now, what is all this about? There are several things that a BT helps with.

• its relative easy to understand whats going on, without looking at code
• its a flexible data structure, which may be modified at runtime (without restarting the application)
• if there are good chosen nodes, virtually any behavior logic can be "implemented"
• Subtrees may be reused, to encapsulate common behaviors (the attached example may become the common walk behavior).

With this first short post I want to encourage every module developer to think about behavior nodes, their module may expose. Those nodes should be minimal and doing exactly one thing at a time. So designers and other coders may just use this nodes to build trees.
tbc.

 

[Immortius]

How does the node system integrate with the entity system? You should think about whether the tree can be composed of entities + components, in order to leverage the serialization support this provides (otherwise the AIs will forget what they are doing when a game is saved and reloaded).

It might also mean you can leverage the prefab system for defining the behavior trees, although it may need some improvements.

 

[synopia]

1. Integration with component system. For now, the nodes are no entities at all - just simple objects. In fact, there are two kinds of trees and nodes:

• actual nodes that compose the BT and is shared for all entities
• nodes required at runtime of the tree to hold state information (tasks) for each entity that is currently running a BT

The actual content required or modified by a node must be stored at the entity. For that I use components (for example FindPathTo is reading the target from and writing the found path to MinionPathComponent of the entity). So, only the state information must be serialized. Most implementations use a so called blackboard for that kind of information.

2. Definition of the BT itself. I played around a bit with prefabs. What BT needs is a hierarchical structure of different nodes, like that:

"Behavior" : {
  "sequence" : {
    "SetTargetToLocalPlayer" : {},
    "parallel" : {
      "Limit" : { "maxTime" = "10s" },
      "FindWalkableBlock" : {},
      "MoveTo" : {}
    }
  }
}

Maybe simplest way is to use Entities as BT-Nodes (so reading from prefab should be done already), which will then create Tasks whenever needed (ie when a Minion-Entity is running a BT).
In the long run we should even think about a graphical editor for the trees, using the property editors from TeraEd.

 

[Immortius]

Ah, I see. Given they are stateless might make sense to do them as assets - then you can use that json format.

 

[Cervator]

And then as an asset ... load them into a shiny new editor option in NUI

 

[synopia]

Ok, instead of much text, I just post a video of what I am currently playing with:

The minions are following their behavior trees, you can see in the video, too. Of course there are many bugs :-D

 

[Cervator]

Awesome! I published the video to our social networks

 

[synopia]

Ok, found some time to explain the video a bit.

What you see is me playing around with minions, mazes and the behavior tree implementation. The four used tools (all have scissor icon) are:

1. Red spawner: Just spawns the next red model (pawn, fool, king, knight, queen, rook).
2. Assign Walk to job: Use selection tool to assign the walk to block job to any solid block in the selection.
3. Build wall: Fills the selection with dirt blocks. Any other block will be replaced.
4. Build maze: Builds a maze in the selection. May be even higher than 3 levels to get crazy multilevel mazes.

Each spawned minion has a "Behavior" component assigned. This will make the minion to behave in the world described using a behavior tree. The tree itself is displayed in the BTEditor. This editor not only shows the currently assigned tree (and its current execution state) but also allows you to fully edit the tree (add nodes, connect, disconnect).

The main missing part before having a somewhat useful editor is the property editor (each node may have different properties you can edit), some ui improvements and correctly storing/loading behavior trees to filesystem and assign them to entities.

The tree used in the video is basically the one I posted earlier. You can see the tree in the overlay. Its just straight forward (as I am writing this text, I can see some bugs in the tree ), a little moving around and playing an animation. The cool part is, how easy the pathfinding and the (currently just sketched) job system integrates into the tree.

For pathfinding, there is a node FindPathTo which will trigger the pathfinder (Notice: the pathfinding runs in a background thread). As long as the path is searched, this node will return RUNNING. Once a path is found (or not found), the node returns SUCCESS or FAILURE and the next task in the sequence starts.
In the example this is MovingAlongPath which will do exactly what its name says. Notice, this node uses another node (MoveTo) to operate.

The job system is implemented using nodes too. The FindJob node will find an available job (this is random by now), SetTargetToJob will assign minions move target to a position, so that the job can be fulfilled. Finally FinishJob will try to run the job (if the minion can reach the jobs target position) and remove it from the job board.

So far, I am really happy with the result.


Open questions:

• Nodes are not allowed to communicate to each other. The only way to change state informations between nodes (for example, FindPathTo needs to tell about the path to the MoveAlongPath node) is using the minion. For that, I dynamically add or remove components with the properties required to exchange. As an alternative, I may use a blackboard where each node can write to and read from. Each minion has its own blackboard. This way its also possible, to make nodes write/read from some kind of variables, so multiple calls to same node would be possible.
• Introduce conditions as special nodes. Those nodes cannot modify anything (not even the blackboard) - they just checking the world for something and return either SUCCESS or FAILURE (no RUNNING). They are called every tick (only active nodes are called per tick) before any other node is called. Other names may be sensor or guard, since they help aborting deep runs into the BT very early.
• Nodes, nodes & nodes. We need many of 'em. And we need good ones.
• What to do with the editor? Currently its a basic swing application which gets started from inside a component system. This is not possible for any mod and should be changed soon. Many ways are possible: Enhance TeraEd to include it somehow. Needs massive refactorings to TeraEd. Fully extract the editor into its own app and using network to comunicate to a running Terasology. My favorite: Use NUI to implement the editor
• Behavior files: Its possible to store and load behavior trees to/from json. Actually its not one tree, but two trees. The first is the core tree, which can be executed. The second is another tree with additional information for the editor only (position, size, ...). Some of this trees may be included in mods (as an asset). Other may be saved to disk by the user.
• more to come

 

[synopia]

My weekly update, not as big as last ones:

• Added generic property editor for nodes. I built the code on the existing TeraEd property editor, but I made so many changes, I moved everything into my own package.
• Editor can now open/edit different trees from different minions.
• Introduced prefabs as the base for behavior nodes. With the prefabs, one can easily modify the apprearance (color, shape, text, etc) of nodes.
• Refactored/clarified some code details.

 

[synopia]

Next update:

• Moved BT code to engine. Currently its a branch (behavior) in my own github fork. Its not ready to be PR'ed.
• Rewrote most BTEditor code to NUI (yes, its working so far - however its not yet finished).
• Build some supporting classes for NUI (ZoomableLayout (will be renamed probably), MigLayout (Wrapper for MigLayout)) and some line drawing stuff (needed for the connections between nodes).

Immortius: Maybe you could look into this commit. Would love to know, what you think about the MigLayout integration and the line drawing. Maybe I should do a PR for this small change only? Here is an example how to use the miglayout.
Cervator: The pathfinding module fails to build right now in jenkins, because of the moved code. I think this is okay for now, but probably there is a way to setup the github-fork/branch for the engine to use in a jenkins build for a module? Just some ideas

 

[Immortius]

Look, I know everyone is really eager for NUI now that I've started on it, but when I ask for a little time to work on it can you please hold back, or at least talk to me about your intentions? I haven't even really started on layouts yet, and there is still a lot I'm playing around with in NUI. I probably shouldn't have even put any of it into develop. And yes, I know it is taking me too long - work has been keeping me extra busy :/. But I have a month off starting in a couple of weeks so should make good progress then.

From a brief look I'm somewhat saddened by the string based approach Miglayout uses - I always find these to be error prone, and Java has a perfectly good compiler that is happy to alert you of mistakes. But I'm not against its inclusion if people will find it useful. I would hold off on any merge until NUI is a bit more developed though.

On the line drawing, you seem to have the right idea but:

• Doesn't look like it takes into account subregioning. The start/end coords should be relative to the current subregion.
• I was trying to avoid OpenGL drawing primitives because they don't exist in OpenGL ES, so will cause issues when porting to Libgdx (this eventual port is part of the reason for the canvas approach). I would suggest using a mesh of two vertices, or possibly just use the billboard mesh and have a shader draw the line between corners - this would allow for aliasing and so forth.

On ZoomableLayout

• Consider using the math types. Your code could be a lot less verbose if you used Vectors and Rects, I think.

 

[synopia]

PR: You are absolutely right. Consider my code as proof of concept. I am totally fine, if none of the code is ever merged (only, if there is a proper replacement, of course ).

MigLayout: Again, you are right with the strings. I personally have no problems with this. I used MigLayout once a while for another project with its own OpenGL-Java-Gui and found it very useful to quickly sketch out user interfaces. Its almost the same thing like a table tag in HTML. The cool thing about MigLayout is, its totally independent of the actual render output. My binding implementation are just those two classes, thats all.

ZoomLayout: Again, some of this code is taken from another project, you can find in my github. I will refactor the code soon to use correct math types.

Layout in general: First, I was a bit confused to not see any widget positions. Took me a while to understand the region/subregion system. Next strange (to me) thing is having layouts as widgets (and not LayoutManagers, that are assigned to container widgets). Maybe you will restructure things here - for now the miglayout is implemented as a widget and it really works. You can even add a miglayout to another miglayout.

Lines: Subregions are supported in one of the following commits. I know, using direct draw operations is a bad thing. Again, think of it as proof of concept (I just want to see some lines). To better support line drawing (VBO + Shader) some refactorings are required to support GL_LINES in vertex buffers. This should be the next step on this topic.

To be honest, I didn't expected to get such far with the BTEditor using NUI, right now. So, nice work there

 

[Immortius]

Injectable layouts hadn't occurred to me, and while I can see the attraction (seperating the concerns of what elements are present and how they are positioned) my experience with them is that you generally need to tie some layout specific information to each element anyway. So you end up with with something a bit convoluted.

I guess my other considerations in this space were:
* all the specification of elements and their layouts in the UI Screen classes would ultimately move into json assets. The screen classes would just be controllers in this situation. Having layouts as widgets would simplify working with these files.
* Allows for dynamic and animated layouts.
* Occam's razor.

There are a lot of rough edges to the current set up though. I am adding some size calculation methods to the canvas so layouts have the option of sizing to fit their contents.

Would also be nice to have a layout where each side of an element can be positioned relative to the sides of other elements.

 

[Cervator]

synopia - do you mean build the Pathfinding job in Jenkins drawing engine artifacts from a Terasology build pulling code from your develop branch (with your engine tweaks) ? If so yeah we can do that for experimental stuff if you like

Or maybe slightly more formally we can create a MovingBlocks/Terasology "bt" branch with your engine stuff, build that in a TerasologyBT job, then pull artifacts from there to Pathfinding.

That is, if there's any value to it yet - I don't want to be pushing the NUI envelope too hard! I certainly can relate to busy times in RL, pretty bad for me these days too

 

[Cervator]

synopia - here you go!

http://jenkins.movingblocks.net/view/Main/job/HighlightedBranch/18 = engine build from your "behavior" branch

http://jenkins.movingblocks.net/view/ModulesPending/job/Pathfinding/52 = pathfinding built with artifacts from the above engine build

It turned yellow as some unit tests broke - not sure why but it compiles. However, it doesn't run

Exception in thread "main" java.lang.NoClassDefFoundError: org/terasology/engine/modes/GameState

Downloaded highlight build 18 then downloaded latest pathfinding and added it to the modules dir. Had to run from command line against the .jar with -homedir on to get the error.

 

[Cervator]

Bump! Things are moving again in places. I talked to nh_99 a bit now that he's working on Questing again about the idea of a more generic "Tasks" module to help define things that could be quests, missions, achievements, etc. Some set of things to do before something else happens (some sort of reward usually). Could be used both by players and perhaps based on BTs by NPCs? Was curious about your ideas on the topic, synopia

A sample quest that could be interesting for the Cities module msteiger is working on is "Take item x from city y to city z" - with some start and end NPC. Easy enough to do for a player with questing as is (beacons a.k.a. location conditions are working now!) but how would an NPC digest that into BT nodes? Could we structure a Tasks framework in a way making it more conductive to BTs?

 

[synopia]

First things first, happy new year to everyone.

In my behavior tree example I already use a component (system) to handle some very basic support for jobs. There I use block components to assign jobs to specific blocks. The job component system keeps track of all open jobs. As for the behavior tree side there are three nodes involved:

• FindJobNode - simple takes a job randomly from the open job list.
• FinishJobNode - actually work at the job, if minion is next to the assigned block. Depending on the job, this may modify blocks or spawn new jobs.
• SetTargetJobNode - sets the assigned block as current target for pathfinder

Using this system, the "Take item x from city y to city z"-quest would be first assigned to the chest with item x. Once a minion reaches the chest it starts "working" on this first step of the job (taking the item). When finished, a new job step is created at the target chest (with the current minion assigned).
Another possible way to go may be to have a behavior tree for every quest, which is dynamically assigned to a chosen minion. Have to think about this

 

[synopia]

Status update after long time

I finally pull requested the behavior tree + editor to the develop branch. I have got the editor to work with NUI. You now can define your own nodes in modules, which will automatically found and are available in the palette. Maybe I will add a small tutorial to the README, how to do that.

I attached an image of the current "work on a job" behavior tree. What it does is asking for open jobs, if any is found, walk there. When arrived at target, do the jobs work (nothing, place block, remove block). It plays animations and has a simple stuck prevention (jump into the air a after 5s move).

Of course I expect bugs, but as long as there are no minions with BehaviorComponent, the code in the pull request will do nothing

Also note, actual useful nodes + the "work on a job" tree is defined in my Pathfinding module, which itself needs LightAndShadowResources Up to now, the Pathfinding module acts as a playground for this stuff.

 

[Mike Kienenberger]

I finally have a pretty good idea what the movement system in MoveToNode was doing. I forgot that we're working with path-finding and we are only getting one node at a time toward our target. I think we need to put a path consolidator in there so that we get the farthest unblocked direct path back as the target rather than moving one node at a time.

Fixing the height for redPawn helped greatly (1.0 instead of 1.6). As did lowering jump speed.

- "height" : 1.6,
+ "height" : 1.0,
"radius" : 0.3,
- "jumpSpeed" : 12
+ "jumpSpeed" : 2

Ran out of time, but I started an engine change that might let us limit total movement. Wasn't sure if it was working because I didn't realize we were only moving one block at a time until now