Question Confusion about BehaviorTree in DOTS

Hi guys, I am trying to create a BehaviorTree system in my DOTS project, and I found it difficult to imagine how to instantiate and maintain trees and loop through Nodes in a DOTS project properly. I didn't find much resources about this topic either.

Excuse me for not articulating my confusion since I am still on the early stages of the project. I am quite confused and unsure of how to build up the workflow. Any advice, any projects for reference or framework codes would be of great help.

 

How comfortable are you working with unsafe code/pointers/blocks of memory? I can suggest an approach based on that which has worked for me in a similar case.

 

If your BT is runtime static, look into BlobAssets.
If your BT is runtime dynamic, I'm not sure how best to handle it yet.

If you wouldn't mind could you elaborate? I've been wondering about how this is done.

 

I am really open to any possible solutions now.

 

Any behaviour tree can be converted to a FSM* (plus some handling for multiple states so you don't end up with a combinatorial explosion). The states can be modeled as classes (state + some instance-specific data). Of course, you can't have classes directly in Burst, and dynamic dispatch can only be accomplished via function pointers (which might work, but are really messy to use so I've avoided them). However, if you know the set of possible states, you can figure out the max size of them (or use BlobAssets for variable sizes if you must -- see Unity.Physics), and treat them as a discriminated union, eg

Code (CSharp):

1. enum State : ulong {
2.     WALKING,
3.     TALKING,
4.     CHEWING_GUM }
5. unsafe struct Node {
6.     State state;
7.     ulong paddingSoThatDataIsAlignedOn16Bytes;
8.     fixed byte data[240];
9.     void update(ref Blackboard e) {
10.          switch(me.state) {
11.              case WALKING: ((WalkingState*) (void*) data)->update(ref e); break;
12.              case TALKING: ((TalkingState*) (void*) data)->update(ref e); break;
13.              case CHEWING_GUM: ((ChewingState*) (void*) data)->update(ref e); break; }
14. struct WalkingState {
15.     float3 targetPosition;
16.     void update(ref Blackboard e) {
17.         if(float3.distanceSquared(e.position, targetPosition) <= 1f) {
18.             /* ... */ } }

You'll want to add a bunch of asserts to make sure none of the states take up more than 240 bytes (or whatever size you choose), and will need to play around a bit to get the API perfect. But once you have the concept of a discriminated union down, you're good to go; at that point it's just setting up an extensible framework that fits the needs of your project.

Multiple states can be handled in several different ways. You can preallocate space for a certain number of states - eg, allow up to 4 concurrent states and allocate 1 KiB data per entity that needs a behaviour tree. You can also use a NativeList or ECS BufferData if you're often going to have dozens of states, but those come with overhead and complexity.

The only piece left is coroutines to define sequential behaviour. Under the hood, coroutines (

yield return

in C#) are just state machines, but writing them explicitly can be a PITA. I prototyped automatically translating generated coroutines into Burst-compatible structs, but didn't figure out how to hook it into Unity's post-processing (but didn't try very hard; got distracted by real work). You can see where I was going here: https://gitlab.com/burningmime/native-enumerable

EDIT: The idea here is to define them in a way that is fixed size and does not require any sync points if using ECS. To the main thread, it's just, say 1 KiB data per entity. Somewhere deep in your job on a background thread you make that blob of data magically come to life, updating state-specific internals, changing states, etc.

EDIT 2: (*) There are important conceptual differences between a state machine and a behaviour tree, especially for designers, and these affect the shape of the API. The nuts and bolts implementation of either one can be built on top of this ADT/discriminated union approach. However, you may want to present an API that allows for implicitly adding and removing states, etc, so it doesn't become a finite spaghetti machine.

 

I haven't tried this yet and simply know of its existence, but since no one else has linked it yet: https://github.com/quabug/EntitiesBT

 

This is similar to what I do with a full graph editor; however it depends on "Unmanaged Constructed Types" found in C#8 (2020.2+)
I actually hope to show off my solution next weekend~ Been doing a lot of work on UI for last couple of weeks.

Disadvantages

• Incompatible with burst.

is a pretty big killer to me

 

As @TheGabelle said if you have a static (fix-sized, not necessary to be immutable) tree, then you can put the tree into `BlobAsset`. And leave the "dynamic" part in systems like `Blackboard`.
In my own work (thanks @DreamingImLatios mention it), I just "flat" tree structure into `BlobAsset` and access it at runtime (`BlobAsset` ought to be immutable, but it also safe to treat it as mutable data as lone as there's only one thread to access `BlobAsset` of tree at the same time).
https://github.com/quabug/EntitiesB...al/Runtime/Entities/NodeBlobExtensions.cs#L23

Since the data of `BlobAsset` just a raw binary (with limited type info) data, you have to find some way to "convert" binary data into your node class while running.
Also in my work, I save all the id of node and delegates of node functions in a static class, and dispatch functions by its node id at runtime.
https://github.com/quabug/EntitiesB...sential/Runtime/Core/MetaNodeRegister.cs#L117
https://github.com/quabug/EntitiesB.../essential/Runtime/Core/VirtualMachine.cs#L24

 

It is absolutely biggest flaw for someone (include myself) looking for high performance solution, that's why I put it on the top of this list...
But on the other hand, I have to make choice between burst support or extensibility, since "Function pointers don't support generic delegates" and burst itself do not support interface, which makes node have to have concrete type of `Blackboard` and `NodeData` that makes whole behavior tree bind to a specific implementation (ECS or GameObject, depend on `Blackboard`).

Anyway, it is not hard to support burst once burst DOES support FP with generic delegates.

 

A behavior tree is a graph and unity is working on a graph processing package for DOTS used in animation and ... but in general i would say a breadth first storage with an index of next level nodes can be a nice way and yes you have to limit your node type to a (Type,Value) and value can be 2,4,8 bytes depending on needs, also maybe a node ID if you need it and you don't have to make it a set of components on entities.

This can read/write ECS data but the tree itself and its execution doesn't have to be in ECS can can be burst code and highly optimized for what it does which is start from root and evaluate and find current state.
That current state can be written to ECS and parameters can be read from ECS
each row of the tree can be a NativeList or LativeArray if size is fixed and tree doesn't change at runtime. However if it is fixed just use a blob asset and go through that. The row (breadth based storage) is good if most of the times all nodes/most of them in a level should be evaluated before going to children nodes.

 

So just spent all day figuring out how to get some lines drawn and nicely linking with ui toolkit and want to show off.

So this is the AI solution I'm going with. It's not a behaviour tree (sorry for off topic), instead it's a utility AI implementation. Conceptually though it wouldn't be too difficult to take the same concept and build a BT instead. This is what my current progress looks like of the UI. (if it looks familiar, it's because I styled it similar to the deprecated apex package that I used to like using.)



This produces burstable graphs that are simply played back like this

Code (CSharp):

1. /// <inheritdoc/>
2. protected override void OnUpdate()
3. {
4.     // Populate the graphs with current frame data
5.     foreach (var graphs in this.graphRoots)
6.     {
7.         graphs.Value.PopulateContext(this, this.settings);
8.     }
9.  
10.     NativeHashMap<int, Reference<Selector>> utilityGraphs = this.aiUtilityGraphs;
11.  
12.     this.Entities
13.         .ForEach((Entity entity, in AI ai) =>
14.         {
15.             Reference<Selector> selector = utilityGraphs[ai.Current];
16.             Action action = selector.Value.Select(entity).Value;
17.             action.Execute(entity);
18.         })
19.         .WithReadOnly(utilityGraphs)
20.         .ScheduleParallel();
21. }
22.  

It uses an approach similar to what burningmime suggested earlier, which I took from unity physics. -edit- a little more at bottom
It is designed to be universal though and allows users to implement a class to generate a function pointer to pass in new actions/scorers without having to modify the library.

For example, custom scorers can be implement like this

Code (CSharp):

1.     [BurstCompile]
2.     public unsafe class CustomScorers : IScorerDelegates
3.     {
4.         FunctionPointer<ScoreDelegate> IScorerDelegates.Score { get; } = BurstCompiler.CompileFunctionPointer<ScoreDelegate>(Score);
5.  
6.         [BurstCompile]
7.         [MonoPInvokeCallback(typeof(ScoreDelegate))]
8.         private static float Score(Scorer* scorer, int index, int version)
9.         {
10.             var entity = new Entity { Index = index, Version = version };
11.             return scorer->ScorerType switch
12.             {
13.                 (ushort)Scorers.IsNearTarget => ((IsNearTarget*)scorer)->Score(entity),
14.                 (ushort)Scorers.IsInventoryFull => ((IsInventoryFull*)scorer)->Score(entity),
15.                 _ => 0,
16.             };
17.         }

The only thing I don't like at the moment is making developers add to this custom class (because it requires unsafe code.) So I'll probably add a tiny little bit of a code gen to generate this file instead.

-edit-
I should say with this approach, I don't use blob arrays, though reference is pretty much a BlobAssetReference just renamed to avoid any confusion

The selector factory looks like this, all the magic happens in Create and the result of this is what is used in jobs. The rest is just stuff for the editor.

Code (CSharp):

1. /// <summary> The base factory class for creating Selectors. </summary>
2.         /// <typeparam name="T"> The type of Selector. </typeparam>
3.         public abstract class Factory<T> : ISelectorFactory
4.             where T : unmanaged, ISelector
5.         {
6.             /// <inheritdoc/>
7.             public Type Type { get; } = typeof(T);
8.  
9.             /// <inheritdoc/>
10.             public string Name { get; set; }
11.  
12.             /// <inheritdoc/>
13.             public abstract string DefaultName { get; }
14.  
15.             /// <inheritdoc/>
16.             public string Description { get; set; }
17.  
18.             /// <inheritdoc/>
19.             public List<IQualifierFactory> Qualifiers { get; set; } = new List<IQualifierFactory>();
20.  
21.             /// <inheritdoc/>
22.             public IQualifierFactory DefaultQualifier { get; set; } = new DefaultQualifier.Factory();
23.  
24.             /// <summary> Gets the unique type of the selector. </summary>
25.             protected abstract SelectorType Key { get; }
26.  
27.             /// <inheritdoc/>
28.             public Reference<Selector> Create(IAISettings settings)
29.             {
30.                 var selector = default(T);
31.                 ref var root = ref UnsafeUtility.As<T, Selector>(ref selector);
32.  
33.                 var qualifiers = new UnsafeList<Reference<Qualifier>>(this.Qualifiers.Count, Allocator.Persistent);
34.  
35.                 foreach (var qualifier in this.Qualifiers)
36.                 {
37.                     qualifiers.Add(qualifier.Create(settings));
38.                 }
39.  
40.                 root.header.Type = this.Key;
41.                 root.header.Qualifiers = qualifiers;
42.                 root.header.DefaultQualifier = this.DefaultQualifier.Create(settings);
43.  
44.                 this.Init(ref selector, settings);
45.  
46.                 return Reference<Selector>.Create(&selector, sizeof(T));
47.             }
48.  
49.             /// <inheritdoc/>
50.             public void CopyFrom(ISelectorFactory factory)
51.             {
52.                 this.Name = factory.Name;
53.                 this.Description = factory.Description;
54.                 this.DefaultQualifier = factory.DefaultQualifier;
55.  
56.                 this.Qualifiers.Clear();
57.                 this.Qualifiers.AddRange(factory.Qualifiers);
58.             }
59.  
60.             /// <summary> Initialize the instance of <see cref="T"/>. </summary>
61.             /// <param name="t"> The selector. </param>
62.             /// <param name="settings"> The settings. </param>
63.             protected abstract void Init(ref T t, IAISettings settings);
64.         }

As I said above, this requires c#8 (2020.2) because of Unmanaged Constructed Types

If you have any questions happy to answer them.
It looks complicated, which it is, but now that it's setup it's super easy to add new nodes - implement an interface, fill in a couple of abstract properties for the sake of editor and you're done.

 

So inspiring to see all these possibilities and directions, although it is quite a lot for me to take in (figure it may take some time before I can seriously make something out of it)

 

@tertle Can you share how entities are scored how an action is executed in this setup? I'm trying to convert an IAUS setup and thought to use function pointers but I'm struggling to figure out how I would pass the components they need.

 

I don't use any function pointers for this so can't really help you with that (but I'd assume just pass a pointer)

As for how I was doing it, a lot of unsafe code.

While we use Utility AI at work we don't do it how I implemented here. This was mostly a max performance test idea I had for my own project.

It's much more maintainable just to do scoring in separate systems with buffers and separating decisions into buckets.

If I was going to do with what I did above in production, I'd generate a chunk of it with codegen.

-edit-

one thing i should add is at this stage I'm unaware of any standard (so excluding stuff like neural networks etc) AI implementations except utility AI that work exceptionally well with DOTS style ECS. I would personally avoid any type of behaviour tree or FSM.

 

I've come up with 2 designs for the Utility AI, the first would be fairly memory hungry. The second is with sort of delegate functions but I'm not sure how to execute it with jobs. Maybe there is a better way I can't wrap my head around.

1st design:

Components:

• Score - Final score for each Action
  
• Actor - Reference to the entity using the action.
• Consideration[Type of consideration] - The curve and other read only shared data, Can be a blobasset to save space.

Layout:

- "Body" entity: The main entity, naturally, contains all the sensory/context information, buffer of Action entities.
- "Action" entities: Actor component, component for each Consideration type, Score component.

Pros:

• Each consideration is done in parallel.

Cons:

• Need to duplicate all actions and all considerations for each actor, very memory hungry.
• Can't early out if an action is invalid.

~~~~~
2nd design, the one I like most but can't figure out how to jobify:

Actions and Considerations are functions, actions can add components, considerations take components and score them.

Pros:

• Can store everything in a single blob or buffer of blobs, one set of actions/considerations per ai type.

Cons:

• Can't get all components that may be required, for example, how to get an Ammo component from a Gun Entity component inside the function. Can't use EntityManager or SystemBase if the caller is a job, but it looks like you're passing an Entity into a Scorer.

• Considerations are not in parallel, but may actually be better with early outs.

 

My FSM and BehaviorTree work by enabling and disabling component data.
ComponentData defines actions and their Systems run those actions.
So FSM/BehaviorTree themselves runs no action at all, they just manage state and decide which component to enable/disable.

For FSM, it's super simple. each state is a collection of ComponentType to enable. And each event is a From-To state pair with a trigger variable.
For BehaviorTree. I defined various Compositor and Decorator Nodes. leave node is a collection of ComponentType too.
FSM/BehaviorTree archetype is stored as BlobAsset. FSM/BehaviorTree State is store as ComponentData on entity.

This implementation has a major difference from traditional FSM. There's no instant callback because of the nature of ECS. So Instant switch of states can not achievable by just defining FSM. But there are APIs for ComponentData to set the FSM state. so it's up to the enabled Component's System to decide if a quick jump is required. Also, all action runs only once per-frame (SystemUpdate). and actions can run in parallel (they are just ComponentTypes).
Start/End state is tracked and recorded.OnStart and OnEnd are not callbacks but events(bit flags indeed). Action can react to these events in their own system.
Most of these rules apply to my BehaviorTree too. but Decorator and Compositor are built-in and supports instant jumps by default.

This lib uses my Per-Component disable/enable SDK which can be found here.

 

Hey Lieene-Guo, going through your BT example. Dumb question - where is DataUnion4 defined? TIA

 

We're not comfortable working with pointers and unsafe code so we did it this way. Hope it helps.