[Proposal] Making it more "unreal"

[Xerios]

One of the things I was trying to do myself is to replicate the way Unreal did their behaviour trees.
Since the structure was too different and I had the urge to use UniRx, I made my own repository and tried replicating it basing on how they did it in their SDK. I never managed to finish it but the structure and code is there, never got to implement UniRx either since I realized that it wouldn't benefit at all in the end.

What I found really interesting is the way they structure their trees.
Notice how service sticks underneath their composition node? Or how decorators are always above either composites and tasks?

Seeing how this looks:
https://camo.githubusercontent.com/40566eaf7697442c61b3f4079f70a83d479f51ab/687474703a2f2f6c6162732e6e6b7565626c65722e64652f6e706265686176652f696d616765732f4e504265686176652d416e696d2e676966

I can't help but to think it could be better, and by better I mean by changing the way it's structured.

The way they do it is not that hard.

• Composites can have Decorators and Services, can have childs
• Tasks can have Decorators, no childs
• Services, child
• Root is just a Composite that doesn't have anything attached to it and can only have one task child ( see it more as an entry point to the BT )
• Decorators and Services are also nodes, but they can only be part of a composite child ( which is explained further below ).

Imagine if you could stack all nodes that share same scope.
Instead of :

• (Root)
• • (->)
• • • (Wait)
• • • • (Service)
• • • • • (Service)
• • • • • • (Repeater)
• • • • • • • (Succeeder)
• • • • • • • • (->)
• • • • • • • • • (Wait)
• • • • • • • • • • (=>) // Paralell

You could have this:

• (Root)
• • (Wait) [->] (Service)(Service)
• • • (Repeater) (Succeeder) [->]
• • • • (Wait) [=>]

In the end the structure for node class becomes like this :

• Node
• • Composite
• • Task
• • Decorator ( pre-condition/effect )
• • Service ( post-node-execution )

The difference is that most logic is executed in the composites themselves, they're the ones who are active/inactive and know which child is currently active - not the task itself.
The children in the composite are stored with a struct CompositeChild, which looks like this:

• CompositeChild
• • Decorators[]
• • Node
• • Services[]

In order to execute the node you need to pass through its decorators, and in order to execute its services you need to execute the node. All this done by the composite parent.

Details aside, I really thought it through and it makes sense to structure it like that.
Seeing that Unreal kept it this way for so long with no other change can only mean that it works.

What do you think of it?
I know it's a major change but it would look totally awesome and the behavior trees will be more readable.
Anyhow, look up their docs and tell me if you agree with this. I think we could create something powerful.

[Xerios]

• Made some edits to previous text -

[meniku]

Thanks for the suggestion :)

I worked the past 3 months with Unreal's behaviour trees and gotta say that Unreal's behaviour tree's structure is less prone to making errors (but I had a lot of WTFs there, too). However their behaviour trees are meant for designers and pretty huge projects and NPBehave is meant for coders and small projects primarily. Also you can achieve a similar flow like Unreal when you structure your nodes like it in NPBehave: Decorator -> Service -> Task/Composite. I don't find Unreals BT much more clearly or so (actually all AIs I made there had simpler behaviour and got pretty big trees too). Also they have quite some nasty limitations like no real parallel nodes - either they see a problem with it that I don't see, or their structure has some problems with it.

For the way how decorators are displayed in the debugger: I like the idea of placing decorators nearby their decorated nodes, I think it is a very good suggestion. I consider committing the change if it turns out to help me debugging.

Services are just decorators in NPBehave, displaying them differently than other decorators wouldn't make too much sense imo. Maybe you're right that we should consider having Services owned by Composites instead of them being a Decorator, it's just that I don't see a benefit here in mixing both responsibilities together (although I see them being a Node in the tree like they are right now doesn't make so much sense either).

I personally have no issues with NPBehaves debugger. That's quite a complex AI I have here and the library I used before to port it over from didn't even have a debugger. Also the AI isn't fully ported yet, so there are still some things I can simplify by using NPBehave. That debugger is helping me a lot and collapsing nodes helps me to focus.

Don't get me wrong: if you can get that implemented right and keep the library simple and elegant go on with it and I either will merge that back for some future 2.0 version or you create a fork of NPBehave, although honestly, it might be easier to start completely over. I checked the code from Unreal when I started NPBehave back then and it was way to complex for my taste. I understand that they have their reasons and I enjoy working with their Behaviour Trees a lot, it's just that I personally don't see a need for structuring NPBehave in a similar way.

Btw I think there exist quite some event-driven BT libs that mimic Unreals BTs already, also with visual editing support etc ;-)

However I would also appreciate to see more sophisticated variants of the NPBehave library.

[Xerios]

Haven't seen many event-driven BTs around, can't really name any good ones :/

Funny, I had the same impression when I wanted to port unreal's BT over.
In the end I kind of managed to port few ideas over and at the same time I learned about few interesting concepts that I may or may not be able to implement them here.

As for the lack of parallel nodes in UDK, they did also mention that real parallel complicates BTs and makes things harder to debug, I can imagine this being true for complex cases..?

Services don't affect the state at all, so it doesn't make sense for them to be Decorators. Further more, they are only active if their parent is active, so it logical to stick them right after or together with a Composite. Perhaps new Sequence().AddService(1.0f, _=> {}) / .Monitor(1.0f, _=>{}) or something could be a nice way of handling this ?

The goal I want to achieve is to have stateless nodes for maximum performance and optimal memory usage, but I guess there's still a long road ahead.

Anyways, I'm not against the current design, I think it's nice and elegant.
I agree that sticking decorators near their composites/tasks in the debugger is enough to simplify the trees. I'll look into it later on.

[meniku]

Hmm maybe I'm wrong, but I think this lib is pretty popular and event-driven. Back when I started NPBehave, I didn't find any too (even though the mentioned library should already been there).

I just committed the changes I did to the debugger, so you don't need to repeat what I already did. I thought it would maybe be nicer when we would put all decorators together in one line? Or more inside the task label like in Unreal, I don't know ...

I'm not sure how much our the Service nodes affect the performance as you can put them pretty high in the hierarchy and depending on how you structure it, the service node shouldn't need be restarted often (is the same for unreal's Services though, when their node is started their services would be started together with them).

[Xerios]

Nice,

I have Behavior Designer and nope, it's not event-driven. It uses messages to do few things, but at its core it still ticks like any other BT.

I doubt the service uses any performance impact at all at this point, it's just that during the traversal of nodes it still goes through it --which doesn't really change or affect anything. For me, it's simply a matter of logic for this case, but oh well...

Btw, have you considered flattening your BT to one single array? UDK does it as well and this data-oriented design does have its benefits.
http://focus.gscept.com/2012ip19/2012/03/18/behavior-tree-implementation/

[meniku]

oh ok, I didn't know that. I thought it's event-driven :/ so NPBehave seems to be pretty unique in that regard yay ;)

One benefit of traversing through the service nodes in NPBehave is that they are started before the decorated node and execute their service-function already once there, ensuring that the service has been called at least once the decorated task or any subsequent decorators are called. And it also automatically stops when the decorated node stops. Of course you can do that in the implementation of a Composite too, it's just that you have to ensure to do this.
Maybe we can make it an optional feature on the Composites and leave the Service decorator until it turns out to be be better and mark the old one deprecated.

No I did not think about flattening yet. Why were you suggesting it? It could be helpful to reduce deep recursion stacks, I don't know. I didn't run into any performance issues yet, but that's good too keep in mind for possible optimisations. I guess this would mean a rather big change into the inner workings, but may be worth it.

[Xerios]

Yeah, flattening will completely get rid of recursion stacks, which will definitely be a pain to deal with if someone makes one of those deeply nested (dynamic) behavior trees. No particular reason for suggesting it, just thought that the case in that gamasutra article might end up in a stack overflow with the current nesting style, and also it's kind of cool in a way to have it in one dimensional array :)

Anyhow, my agenda's been slowly filling up lately so I'll come back at some random point in the future.

[meniku]

Is this still a thing?

I've created a Wishlist for NPBehave 2.0, if you still think we need this, we should add this there, else we could just accept that NPBehave is not UE4 and close this ticket.