Behavior tree renovation / documentation [$100]

[Cervator]

Edit: Actually heard from @synopia and should know more at the end of December

We've long had our behavior tree based AI thanks to @synopia but it hasn't moved some for quite a while. With the big v1.0.0 coming up I've been hoping to get some more tweaks applied along with a tutorial of some sort. Additionally Synopia actually worked on a v2 of behavior trees that lived mostly in a module. Ideally we'd get that dusted off and brought in as it seemingly came with a lot of improvements.

• Original behavior tree video demo: https://www.youtube.com/watch?v=gPwBSwq4_mg
• Forum thread: http://forum.terasology.org/threads/behavior-trees.882/
• Example of a creature using the existing setup: https://github.com/Terasology/WildAnimals/blob/master/assets/prefabs/deer.prefab
• @synopia's newer framework: https://github.com/synopia/jbt
• Module that went along with it (I think): https://github.com/Terasology/Behaviors
• The Maze module/world may help develop and test: https://github.com/Terasology/Maze/ (although Pathfinding also has a test world)

Two different scopes here. Naturally I'd prefer the bigger scope and for @synopia to come claim this, but it has been hard getting in touch :-)

Fine tune the existing setup in engine

I would consider this sufficient to claim the bounty I aim to put on here.

• Examine the system as-is and fix any note-worthy bugs, possibly involving the pathfinding or workboard system. Biggest obvious demonstration of this is spawning some L&S creatures and watching the logs go nuts with errors. Or then move out of range (let a chunk with creatures in it unload) and other errors may happen (used to crash the game, still might). I realize this may not directly be a consequence of the BT code, but the components are closely related. Pathfinding + spawning L&S creatures + unload chunks == boom! #1304
• Enhance the existing nodes with any missing utility. Main missing piece I can think of is pathfinding to a blocked location, assuming the presence of an ability to break through blocks. May put a separate issue/bounty in for that one.
• Add a bit of quality-of-life work to the BT editor. It works, but what could we add to make it more user friendly?
• Add (AI for) at least one more creature doing something more advanced than permanent "stray" or the order items in L&S
• Add javadoc to all involved classes that lack it, review any that have some
• Write a tutorial akin to the nice one @Josharias did for world gen: https://github.com/Terasology/TutorialWorldGeneration/ (probably including a utility module to go through each lesson)
• Record an updated demonstration video
• Some sensible unit tests if possible - edit: resolved issue #2231 #2245 "fixed" some unit tests that broke from an initial round of cleanup, but the fix may need a little more and/or some of the tests may need to be re-imagined some. This should include re-validating all the unit tests as sensible and actually covering code well.

Finish the new system

This would likely be worthy of GSOC for the added scope, and because GSOC is coming soon. None of these items are required for the bounty and are each optional bonuses (so enough of them == GSOC)

• Figure out where @synopia was going with JBT and the Behaviors module. IIRC he was very close to having it finished. I believe it would move at least some functionality out of the engine and allow easy definition of reusable nodes (that may already work for all I know)
• Split out a standalone version of the BT editor. Likely closely related to Standalone NUI editor #849, another GSOC task.
• Come up with examples of the new structure of the BT files/nodes
• Updated tutorial
• Updated video
• Updated sample module with more advanced behaviors, maybe multiple creatures interacting?

[oniatus]

I am experimenting with the current state and implemented some smaller fixes & refactorings for the system, all in small commits at https://github.com/oniatus/Terasology/tree/behavior.
Not ready for merging, but at least it is a point to start :)
Is there a page on the wiki with some documentation of the current system? If not, i would like to create a draft with some initial documentation for further development.
Some other notes (far from complete):

• The connection from one node to another node sometimes sticks to the mouse and can not be canceled by clicking the empty space
• The assign button does not seem to work in every case (clicking assign/run and selecting the entity some times fixed this in most of the cases)
• Missing some hotkeys, like delete for nodes
• The copy/paste buttons could need some tooltips or something
• Nearly all of the nodes require different components on the entity but the editor only requires the BehaviorComponent to be on an entity. In this case it is easy to crash the game, by assigning nodes like 'Move To' to an entity without a MinionMoveComponent, or CharacterMovementComponent. I think nodes should expose their required Components and the editor should highlight invalid nodes for the current entity with a red border or something. Assigning such a tree should not work too, maybe with a indicating error popup instead of a uncatched exception.
• Is there a reason, why the behavior logic is tied to the engine instead to a module?

Edit: Fix link

[emanuele3d]

Hi @oniatus, and thank you for looking into this.

A bit of a side question: how abstract or tightly integrated is the visual display of the behavior tree? I mean: could the graph/nodes be easily used for something completely different? We have been discussing a node-based approach to the rendering pipeline and I've been wondering if the behaviour tree display could be used to display the steps in the rendering pipeline instead.

At this stage I'm just curious about this though, nothing to rush about.

[synopia]

@emanuele3d : The rendering is fully decoupled from the internal behavior nodes. The otlb.nui package contains the rendering stuff. The tree + nodes are inside the tree package. Asset package contains code to load trees - also there is some code to create a tree for rendering from a behavior tree structure. Evaluating a tree should be possible without any code from the rendering stuff.

@oniatus : Thanks for looking into this topic ;-)

The basic idea is, entities with behavior should have a BehaviorComponent with a link to a behavior tree. This tree is decoupled from terasology entity system (the tree itself is not an entity).
The BehaviorSystem collects all entities with a BehaviorComponent and runs the assigned tree, using an interpreter.
The interpreter walks down the behavior tree and creates tasks for relevant nodes, that finally run code, specific to the node.
Now the question is, how to implement those nodes. An example is the movement system in the Pathfinder module, which uses a MovementComponent to store the actual movement data for an entity. But there are probably better ways to do this.

However, the rendering code itself is an experiment ;-) Its quite difficult to implement modifications in the underlying tree, especially because you may have to reorder children lists and such things.
In addition, the gui should show the actual state of a tree for a selected entity (think of a debugger).

Another implementation of a behavior tree system I made, can be found here. There are also some tests, to get an idea how it works. The main difference to the current terasology implementation is, it has the ability to compile a behavior tree to bytecode (which is a gigant switch/loop thing, encapsulated in a class). Then, for each entity, an instance of this (generated) class is created, instead of a deepcopy of the behavior tree. But I really dont know, if this is needed in any way.

There is a outdated and half done integration of this system into terasology.

The main problem is, how to implement the actual nodes (ie movement) in a way, that integrates nicely with the terasology entity system.

[Cervator]

There you are!

/me attempts to lasso @synopia

Appreciate you adding in some feedback. We still aren't locked down for v1.0.0/alpha (running late as expected) so if at all you find more time please heeeeelp! :D

@oniatus thanks for the updates. Any progress is progress and I'm sure there's much to do :-)

@emanuele3d you mean like showing the pipeline with TeraEd active, maybe even edit it on-the-fly to have effects applied in different sequence? That'd be sweet

[Cervator]

Oh and @synopia say hi on IRC sometime, if for no other reason so that @GooeyHub can finally deliver whatever message has been waiting for you for months haha. I have no clue what it is anymore.

[oniatus]

@synopia Thanks for the explanation :)
One question about the tree selection: If I select a tree and modify the tree, should this change all running instances of this tree?
For example, when i edit the engine:default tree and apply a "Set target to local player", I get an exception because the actor has no component required for this node.
The purpose of the global entity and the default behavior is unclear to me too.

I uploaded some more changes, e.g. it is now possible to create a plain new tree and I refactored some fields/javadoc. However, this breaks the current api, I am updating my Pathfinding fork in parallel for testing: behavior branch.
My main focus is the UI at the moment and i am using the pathfinding in my own small module (not online yet), guess this will take some more commits ;) I want to go for some Unit-Testing in the next Iterations too.

[Cervator]

@oniatus - great! Keep it coming and don't worry about breaking API. If we can have a new stable version here within a week or two we can grab it for the engine v1.0.0 / game alpha release.

Not by any means a final version or anything, just a sensible API level we can call a foundation to build on later :-)

[emanuele3d]

@synopia: Thank you for your reply!

@Cervator: initially I'd use it for debugging purposes, to make sure visual data is flowing through the pipeline in the right way. Eventually it might be useful for modules adding nodes to the rendering pipeline: it might be impossible for a module to programmatically determine where to attach its nodes, especially if the rendering pipeline has been already customized by other modules. But the author of a module could have published configuration instructions that a human being would be able to fullfil, even if the pipeline is no longer standard. And ultimately yes, each node might have a number of settings that the user could configure on the fly.

[Cervator]

Sounds great! Now we just need to make it happen, heh :-)

[dkambersky]

I'm looking into possibly getting this into a working (& documented) state for my GSoC project.

@oniatus as you seem to be working on this presently, do you think you could use a dedicated helping hand with lots of time to spend on the BT/AI rework? I'd be learning the ropes for a few days but then I think I could be of solid assistance, with both the internals and the GUI.

[oniatus]

@dkambersky Absolutely :) My personal goal is to get the system in a state where it is usable without crashing and maybe writing some short tutorials for it on the wiki. Aftwerwards I would like to step to another part, maybe the world generator or the ui as I want to get a deeper understanding of the whole thing, not only pathfinding/behavior.
I will be busy this week but I'll try to get a PR ready with my latest changes in the next 2-3 weeks.

[oniatus]

Added two PR: #2199 and Terasology-Archived/Pathfinding#23.
@dkambersky You can use them as a starting point for the gsoc if you want. Not too much code though but at least some small improvement.

@Cervator Let me know if I can provide any further assistance.
I would leave further changes for the gsoc in two weeks (assuming behavior gets a slot, maybe for @dkambersky? ;) ).

[Cervator]

Further assistance is always appreciated and needed hehe :D I left you some notes in the PR. Thanks!

And yep so long as we can stabilize that PR that should be a good foundation for this topic in GSOC :-)

[MarcinSc]

I've implemented the Behavior Trees in my game project, feel free to take it and use it under whatever license you are using.

You'd have to copy/paste the code into a module in Terasology and of course point the classes to correct injection of systems, registering of systems and the entity system classes, plus scanning+loading of behaviors.

The link is:
https://github.com/MarcinSc/jgd-platformer/tree/master/gaming/src/main/java/com/gempukku/gaming/ai

[Cervator]

I'm going to close this as completed as part of release management fun for Alpha 8 / end of GSOC 2017. The code isn't actually part of Alpha 8 since it is targeted for engine v2.0.0 - but that's close enough to finish this one item out, let the bounty be claimable, then get started on writing more detailed follow-up issues soon

Thank you very much for your work @dkambersky! And mentors + other participants on this issue and topic for years now :-)

GitHub project board over here https://github.com/orgs/Terasology/projects/7 and blog at https://dkambersky.github.io/tera/2017/08/24/google-summer-of-code-2017-final-report.html