#Implementation of behavior trees in ECS

1 messages · Page 1 of 1 (latest)

median onyx
#

I am kinda new to Unity and ECS so to avoid the XY problem (https://xyproblem.info) I will add more details about what I am trying to accomplish in the first comment of this post

I found this video (https://youtu.be/nKpM98I7PeM) about behavior trees in Unity and I really liked the concept. I thought about trying to implement it using ECS because it looks very useful for the AI of enemies and an Ability System that I am planning to develop. This is what I basically came up with:

  • In the GameObjects implementation each node starts from the abstract Node class and inherits a few other classes. For example, the DebugLogNode in the video inherits from ActionNode which inherits from Node. Since we can't inherit using structs I decided to separate each of these classes as components. So I have the Node, CompositeNode, SequencerNode, and a few other components.
  • We can't have duplicated components in the same entity (unless we use a buffer) so to solve this I decided to use one entity for each node in the behavior tree. All entities would have at least the Node component then a few more depending on their objective. For example, I have a node that changes the animation of the player so it has the Node and AnimationNode components
  • The GameObject implementation is very simple since they are classes and can run methods directly on itself, this makes it easy to keep control of which child node to run. Since I am using ECS I need to use the systems, but behavior trees have a specific execution order so the systems can't run all of them immediately. My solution for this was to change the Node component into an enableable component and by default it starts disabled. Then when the node needs to run it is enabled. The SequencerNode system for example, needs to run the children sequentially, so the respective component has an index and the system enables and disables the Nodes in the necessary order to execute the behavior tree. Each node has a dedicated system to run their logic

Ok so here are my questions:

  1. From my research it looks like behavior trees are popular, is there an already existing solution for this? Am I reinventing the wheel?
  2. Can you see any obvious flaws in my solution? Maybe a performance issue? Since I am new this is a bit hard for me to predict
  3. Is it an issue that I am creating too many entities for a single behavior tree? Usually they will have at most 20 nodes, so that's roughly 21 entities. I am planning to use it for an Ability System so each time an entity casts an spell all these entities would be created again then shortly after destroyed

I am attaching a sketch that I did when trying to figure out how to implement it, in case it helps to make sense of my big text

image.png
#

What I am trying to accomplish:
I found this video when researching about ways to implement my Ability System. I was looking for something modular that I could use to build lots of different skills so the behavior trees looked like a good fit since besides of having a list of actions, I could also add a bit of logic to the skills. Now I am also planning to use it for the enemy AIs

azure bloom
#

I'm not aware of any public behaviour trees for ecs, most users have opted for a utility solution instead as it tends to fit the ecs architecture better.

#

Also this type of system is pretty rough for a new user to implement well

#

There's a lot of nuances

#

This is not to say it's not possible and if it's what you want its totally doable

median onyx
#

yeah I won't try to implement a full standarlized behavior tree because it might be too much for me to chew and I won't need it. I built only a few simple nodes yesterday and it seems to work well so far, I managed to implement a simple attack combo with it. do you see any issues with the decision of using one entity for each node of the tree and recreating them on every spell cast?

azure bloom
#

Oh yeah that definitely won't scale amazingly, but it really depends on scope of your game

#

If you have have a couple of hundred creatures max who cares

#

If you want something stupid like 10000 then you'd probably need to start caring

median onyx
#

yeah I don't plan to have that many

median onyx
#

tbf what I liked the most with the behavior tree was the graph editor, but at the moment I am struggling to actually save them into a file (I was planning to use scriptable objects for that) and convert them into component/entities at runtime. authoring all the trees through code seems the worst solution so I am gonna play with other alternatives

#

thanks a lot for your inputs here

keen patrol
#

I'm utilizing polymorphic structs for skill/spell system. It's just a start so I can't tell you if it's good or bad. But certainly it's cleaner than having specialized systems for 30 skills.

rocky pelican
#

Having tons of entities isn't necessarily a bad thing in itself (if they are used well, it's efficient), but it can become a bad thing if the data of these entities needs to be accessed with lookups

While I haven't tried implementing behaviour trees, I'd assume you'll encounter this "many lookups" problem for a BT implementation where each node is an entity. On top of the lookups cost, there are also other things that could make this approach costly:

  • lots of jobs to schedule
  • enableable components result in a higher update cost in general

However, as others have said, this could still perform well enough to be usable unless you game has very high AI needs

Here's what an alternative implementation might look like though:

  • all nodes live in a dynamicBuffer on an AI agent entity
  • nodes are a struct that contains an enum to identify what type of node it is, and contains a minimal union of all the data that could be needed across all node types
  • you can "keep a reference" to a node by remembering its index in the buffer. Making sure this index is stable & reliable is the main technical challenge you have to solve in order to make this approach work
  • updating a node means getting the node by index, and doing a switch statement over its node type in order to execute the correct logic. Since you can store an index to another node, you have full control over update order

Performance-wise, this approach allows:

  • no component lookups (instead we access nodes by index directly, all on the same entity).
  • only one job needed for your AI update (instead of one job per type of node).
  • no overhead of enableable components (cost of enabling/disabling, cost of checking each entity for enabled, etc...).

In most of my tests, the cost of having to do switch statements & having to have all nodes store all possible data was much smaller than the costs associated with lookups, many jobs, & enableable components. But in reality it'll depend on your specific use case

rocky pelican
#

One thing that may or may not be a problem in your original approach is that your BT updates will have to happen over an undefined amount of frames. If you need to execute nodes of type A, then B, then A again, you'll get:

** Frame 1 **

  • enable a node of type A
  • run your various node jobs: it updates type A nodes and enables a node of type B
    ** Frame 2 **
  • run your various node jobs: it updates type B nodes and enables a node of type A
    ** Frame 3 **
  • run your various node jobs: it updates type A nodes

If each node job updates in sequence rather than parallel, then the updates of node types "A then B" might be able to happen on the same frame. But "B then A" still can't, and 30 ScheduleParallel() jobs in sequence is also much less efficient than 30 Schedule() jobs updating parallel to each other, assuming things are decently distributed. You could avoid this problem if you choose to re-run all of your node jobs as long as there are still any enabled nodes (and have a main thread sync point in between each re-run of the jobs, to check if we still need a re-run), but then you're multiplying the amount of jobs needed, which multiplies the jobs overhead cost problem. 30 node jobs with 5 re-runs means scheduling 150 jobs (they rely on enableable components, so each job will have to do at least some work even if the nodes are disabled)

The alternative approach in my previous post also avoids this problem entirely

rain harbor
#

basically, you'll have dozens of lookups to serve behaviour of different nodes

#

while the buffer struct size is going to grow massively as the need in different data layouts arises

#

on top of that + switch statement size of 500+ lines...

rocky pelican
#

All I can say is that in the StateMachine and UtilityAI use cases I've had where I've implemented & compared both approaches, the "union structs in buffer" approach typically performed 2-5x better than the "one job per thing + enabled components" approach

But there will be cases where the opposite might be true, like if one of your nodes needs 500 bytes of data while most other nodes need 10

rain harbor
#

so that nodes can write result directly to pointer instead

#

just needs a system that will manage allocation/deallocation of all that memory

#

and technically, this just reimplements objects

#

😅

rocky pelican
#

That would be great, but I haven't really explored that possibility so I can't say much about it

#

Also, for the problem of the size of the union structs getting bloated by only a few large node types, you could simply store an entity field there that points to another entity that holds all that big data.

That way, your union structs will remain small, and only a few specific node types will require a lookup

This strategy can also be used if you need your node to store an array (store an entity that holds a dynamic buffer)

median onyx
median onyx
#

I am only a bit worried about the switch statement getting really big and I am not sure if it would affect the performance (I think it might not since the interpreter would just skip all the code?), but I am gonna give it a try

#

what I also need to figure out is how to save the behavior trees to load them during runtime athinq I will play a bit with the scriptableobjects and think about a conversion to the structs

real schooner
#

@rocky pelican do you think that the polymorphic/union structs approach encourages anti dod practices? One system ends up being responsible for entire feature instead of being responsible for a specific thing. My current implementation uses the former actually, but @rain harbor and I have been discussing this quite a bit

rocky pelican
#

In my opinion, whichever approach ends up performing best is the most DOD approach. To me DOD is kinda just a way of saying "understand how CPUs process data so you're better equipped for finding the best solution".

If an enabled-components approach performs worse than a union structs approach for a certain problem, it's because when considering absolutely everything that happens in that solution (scheduling jobs, adding enabled bits to archetypes, checking for those enabled bits at every iteration, changing enabled state via lookup, etc....), that solution was less optimal at processing all the data that had to be processed than the other solution. And therefore, that solution is less DOD than the other.

In short, even if a solution "feels OOP" to some, it might still be the most optimal/DOD solution in reality despite the looks of it. Trying to force linear memory access patterns on a problem that naturally needs random memory access, for example, would be anti-DOD

#

It's easy to misuse polymorphic structs though, so in these cases they do facilitate anti-DOD practices

real schooner
#

What would you say are hallmarks of misusing it?

#

Some of these things you really need in a game naturally require random memory access, but at the same time you end up creating these really large systems that no longer feel like composition

rocky pelican
#

It's kinda hard to tell, other than "when there are better alternatives" 😅

For example if you have 2 types of enemies in your game, and handle these 2 types with a polymorphic 'Enemy' component rather than just simple composition + 2 systems, that would be misusing polymorphic structs

rocky pelican
median onyx
rocky pelican
#

Polymorphic structs really shine when they are the key to avoiding any of these;

  • cost of structural changes
  • cost of enableable components
  • cost of component lookups
  • cost of too many jobs

(...and when these costs are a greater evil than the costs of polystructs)

In your abilities example, since none of the above things are a problem, then using polystructs might be a mistake compared to simply using composition and one system per ability type

In the behaviour trees example, however, you need the concept of an execution order that can't be determined by archetypes. This leads to costs of enableable components, lookups, and many jobs when trying to go for a typical ECS approach. Polystructs let us avoid all these costs in that case

keen patrol
# median onyx I think its hard to draw the line of this because what I would be doing with spe...

I think I should tell you a bit about how I design the skill systems. At the beginning I thought that each skill is unique, so each should have some systems of its own. But after modeling them for a while, I realized that there is a general logic governs those skills, and it's possible to reduce the number of systems greatly. Because ultimately, at its triggered point (DoT or not), a skill would produce some hitboxes. Those hitboxes carry the actual damage value and are the actual entities that would interact with the target of a skill. So I only have these systems:

  • a system to start the skills
  • a system to move them around using the same set of components
  • a system to count the elapsed time for each of them (same set of components)
  • a system to produce the hitbox data at the triggered points (the only system that uses polymorphic structs because each skill should produce different amount of hitboxes, plus their varied location)
  • a system to spawn the actual hitbox entities
  • a system to check for collision between these hitboxes and the target, then apply damage to the target
  • a system to clean up hitbox entities
rain harbor
# keen patrol I think I should tell you a bit about how I design the skill systems. At the beg...

This actually looks pretty clean from ECS perspective.

Assuming production of hitboxes doesn't have much different options (so for example you have like Box/Sphere types), which also doesn't need to be extended frequently. It's probably fine to go along with it. It'll save on scheduling job per each type and at the same time it doesn't even forbid you from extending this way. So for example you can always just not add that polymorphic struct and isntead add different component in authoring, while system which queries it will update at the same order with polymorphic system.

#

Allthough, I'm a bit concerned by hitbox entities. Because seems like you spawn a lot of them, which can hurt performance noticably.

#

As alternative I can suggest to isntead fill a buffer of some sort with already resolved collisions

#

and at the end of frame/start of frame it'll be cleared

keen patrol
#

Of course this approach is very specific to my project since most of the skills do the same thing.

#

Even though I suggest polymorphic structs, in reality I haven't stumbled on many situations that need it. And most of the issues I've first thought of using polymorphic structs can just be solved with a set of ordinary components.

real schooner
#

And based on your test results they also seem to be the most performant

rain harbor
azure bloom
#

though this discussion has kind of ignored maintainability and usability which is a lot of the time more important than performance

rain harbor
#

the most performant would always be writing in assembler 😅

real schooner
azure bloom
#

i didn't say that

real schooner
#

Will open a new thread to discuss this to avoid hijacking this one further. would be great to learn more

rocky pelican
#

One more thought regarding the alternative behaviour tree implementation:
https://i.gyazo.com/ad024616a76c2faa3bc4474f92777b13.png

As you build your dynamic buffer of node structs, you can insert them in the buffer in order of most likely execution order. Based on the image above, the nodes would be inserted in that order: A, B, C, D, E, F, G, H

With this approach, your BT update can simply iterate on the buffer indexes in order, and update the nodes. The only exception here would be for "Selector" nodes, where we would jump to another node further down the buffer directly. We'd have to try in practice to be sure, but this would surely give you good cache-friendliness in most cases

rain harbor
#

honestly, I'd rather just have it as managed tasks, running in parallel with jobs, but having clean managed code

#

Rather curious though, how to manage dependencies in this case so that jobs can run safely in parallel

#

Have a fake job checking on NativeReference bool with while loop?

#

Rather annoying to take over a thread like this

rocky pelican
rain harbor
#

I really think that BT are not suited for ECS implementation

rocky pelican
#

I don't think there's anything special to do for parallellism here. All the data of one BT lives on the same entity, so your BT update job can be parallel and each BT is fully updated on its own thread. Your BT update job is just a IJobEntity that is ScheduleParallel

#

You'd be in trouble only if your game has one single giant BT and you want that to be parallel. But otherwise, if you have 4 threads and 100 AI agents, each thread would update 25 BTs

rain harbor
rocky pelican
real schooner
#

Different nodes presumably do different things requiring different lookups

#

Not the behaviour nodes

rocky pelican
# real schooner Different nodes presumably do different things requiring different lookups

ah, yeah that we can't avoid, no matter which solution we go with. If a Selector node needs to make a decision based on the health of another entity, you'll need to do a lookup whether you go with an entity nodes, polymorph structs, or OOP implementation of behaviour trees

Although any lookups needed for your game-specific behaviours could/should be ReadOnly here in order to allow parallelism. If any writing to other entities is required, it should be deferred using some flavor of event system or ECB

rocky pelican
# rain harbor I really think that BT are not suited for ECS implementation

I can agree with that, but if you think about it, the alternative approach follows this thinking. An ECS implementation of a BT would be the one-entity-per-node approach, and this has some big flaws. Instead, by storing all BT data on the same entity and coming up with our own non-entities strategy for iterating/accessing nodes, we're effectively avoiding ECS for our BT implementation. We're just using a custom unmanaged code approach, and our data just happens to all live on an entity, for the sake of being easily associated with other entity data that does need to be ECS (transforms, colliders, AI agent params, etc...)

median onyx
#

a lot of my action nodes actually need to read data externally from the BT tho, would that be a problem?

#

for example, the AnimationNode. the struct is basically this:

public struct AnimationNode : IComponentData
{
    public Entity Target;
    public FixedString64Bytes Name;
}

in my current implementation (one entity per node) I have a AnimationNodeSystem which is basically this:

public void OnUpdate(ref SystemState state)
{
    foreach (var (node, animation) in SystemAPI.Query<RefRW<Node>, AnimationNode>())
    {
        var target = animation.Target;
        var animator = SystemAPI.ManagedAPI.GetComponent<ManagedAnimator>(target);

        animator.Animator.Play(animation.Name.ToString(), 0, 0);
        node.ValueRW.State = NState.Success;
    }
}
#

I think the lookups you all are talking about is related to these SystemAPI.GetComponent(_entityReference_) calls which I should try to avoid because it will hit a random position in the memory?

tender thorn
#

I`m using blob assets and constructing a "virtual tree" with BlobPtr

rain harbor
median onyx
#

yeah but I need it for the animations since I am using the hybrid approach with mb. I guess I could create a component to "request" an animation change then use the managed API in another system? athinq

rain harbor
#

if you could do all heavy work in bursted jobs and then simply apply ready result to animator - that would probably be best

azure bloom
#

animation.Name.ToString()
this is just a waste of performance

#

just store the int hash for the param

#

this.Play(Animator.StringToHash(stateName), layer, normalizedTime);

#

otherwise you're having to do this everytime anyway

#

and you're just storing a lot more data on your node than you need (string vs int)

median onyx
#

thanks for the tips, I appreciate it

#

storing an int indeed makes a lot more sense. out of curiosity, I was using FixedString64Bytes for the name of the animation, does it always allocate 64 bytes even if the string is just "foo"?

#

@rocky pelican I got the behavior tree working with your idea!

#

lets ignore the fact that I almost gave up

#

this probably runs way faster since I am not enabling/disabling a lot of components and I am only using one entity now

#

but the code got kinda messier than before, since I am writing all the logic for the nodes in a single method instead of separated systems

#

I will clean up a bit of the code and share it here in case you are interested, but it is actually pretty simple and there are probably improvements to be made

azure bloom
median onyx
#

I am gonna send the code as attachments to avoid taking a lot of space in the thread (sorry if anyone is reading this on mobile). I didn't organize the files because its mostly a prototype

📎 BehaviorTreeSystem.cs 📎 Components.cs
#

this is the tree in the gif:

image.png
#

after doing all that, I am actually gonna try the suggestion from @rain harbor to just do a managed solution with ScriptableObjects in the components. it might be the slowest solution but I will be able to iterate faster on the skills with a UI editor, if I see any performance issues I can go back for these two that I just tried

rain harbor
#

they will offer similiar to managed abstractions approach with burst compatibility

#

but they will lack any mod support if you were planning any

#

allthough, not sure if they are updated for 1.0

#

@rocky pelican are they? github seems to be outdated

median onyx
#

I actually tried implementing the latest try with his library but I couldn't get my logic right, so I decided to write the struct by hand ThinkDerp

rain harbor
#

any reason not to consider Utility aI?

#

in my personal opinion - it fits ECS so much better

azure bloom
#

this isn't an AI system though

#

it's an ability system

#

i'm not sure how well utility fits that ^^

rain harbor
#

oh...

#

me pepega

#

😅

#

Not sure why even have those as graph then

#

I'd rather just treat ability same as any other entity in world

azure bloom
#

well the most successful ability system (ue) is graph based

rain harbor
#

but EU is also not using ECS

azure bloom
#

ue has ECS

rain harbor
#

it's in preview and it's separate from any existing stuff, no?

#

anyway, my point is: why treat abilities any different than just bullets?

azure bloom
#

there's a lot of logic that needs to go into abilities

#

windup timings, cancellation, animations, loop iterations, execution points

rain harbor
#

sounds like something easily solved with composition

azure bloom
#

i don't think so?

median onyx
#

let me draw an example of the first skill I made to test the first implementation of the behavior tree

azure bloom
#

composition isn't great for stages

rain harbor
azure bloom
#

so you want to create a dozen entities per ability?

rain harbor
#

initial stage is first prefab you instantiate, next stage is handled by initial stage

azure bloom
#

and lets say you have 40 abilities per character (mining, harvesting are all abilities, not just casting spells)

rain harbor
azure bloom
#

we dont have a single ability that doesn't have multiple stages

#

nearly every ability is going to have a wind up animation

#

lifting pick axe

#

start casting

#

etc

rain harbor
#

sounds like that's just part of AI

azure bloom
#

how is it part of AI

#

when the player is doing it

#

and i don't think it should be part of AI at all

#

the AI calls, use ability

#

that's the end of the AI's responsibility

rain harbor
#

can you give me some example?

azure bloom
#

mine a rock

rain harbor
#

does it involve getting close to it?

azure bloom
#

no

#

you should already be close to it before you start the ability

rain harbor
#

so player should take out pickaxe and then start channeling?

#

character*

azure bloom
#

not channeling

#

though it should loop execution points

median onyx
#

this is basically a combo attack with a sword. you can attack only once or if you time the attack key you can continue with the follow up attacks

image.png
azure bloom
#

yeah there we go, that's a good drawing 😄

median onyx
#

the "Check attack input" node will fail if you don't press the button (going to the node on the top) otherwise it continues the sequence

azure bloom
#

most basic version of an ability

#

i'd say what rafaelalmeidatk put would just be the execution block

median onyx
#

here is another one that is like the Q ability from Vi from league of legends but if you fail to charge the attack it does an attack in place

image.png
#

I found it very hard, specially these nodes with inputs that would change the logic of the ability, to do it with composition

#

but it might be that I am still new at ECS

rain harbor
# azure bloom mine a rock

so here my thoughts on this:

  1. you instantiate a prefab with leg. Root entity does not actually contain ability related stuff, but instead just basic ability details (who is caster, cast timestamp and etc).
  2. If ability has multiple stages, then only first stage (no matter which is it) is going to enabled initially, and it's responsible to enable next stage once it is done.
  3. So first stage is going to be windup stage which is equipping pickaxe. Once that is done - next stage is enabled.
  4. Next stage is already consists of logic that is not meant to early out without a condition. So it'll mine until hardcoded conditions are met (there's still ore to mine).
  5. Once cancellation is requested/end condition is met, next specified stage entity gets enabled.
  6. the last stage is going to point towards root entity, which manages it's cleanup and data writeback to caster if necessary.

So I guess it is kind of entity-graph after all...

azure bloom
#

it just kind of feels like your forcing ecs

rain harbor
#

I'm avoiding polymorphism

#

and tons of lookups

azure bloom
#

that doesn't mean it's faster

#

we have a pure ecs, data utility ai solution at work

#

complete perfect memory layout

#

it handles 2k-10k entities pretty nicely

#

my graph based utility ai with random lookups

#

can handle 100k in less time

rain harbor
azure bloom
#

not in my case

#

anyway are you talking for the engineer

#

or the designer

#

because all a designer wants is a graph

#

they don't to see nested lists in an inspector, overwhelming choices, 1000s of config files etc

rain harbor
#

Technically, it can be graph...

#

at least

#

in authoring stage

azure bloom
#

if you want to implement the front end as a graph then i don't really care how you implement the backend, i'm all about building tools for designers

rain harbor
#

but yeah, I realize that I came down to graph myself...

#

I totally get the simple authoring part

#

I have been trying hard to develop something nice to work with on personal project 😅

azure bloom
#

but yeah, i'm personally all for writing simulations outside of ECS that interact with ECS

#

my local avoidance, ai, ability, navigation are basically standalone simulations

#

that just take nicely formatted data from ecs and then gives a result

#

things like physics do the same thing

rain harbor
#

that's what physics does though

#

no?

#

yeah

#

exactly

azure bloom
#

(for the record i don't use phis level of polymorphic structs)

rain harbor
#

what's the worst switch you'd have?

rain harbor
# azure bloom

btw, I'm guessing your abilities does not support parallel nodes?

#

when it branches, but both branches execute

azure bloom
#

no, i leave parallelism to just separate things running

#

(my ability system is in it's infancy, i'm building it backwards)

azure bloom
rain harbor
#

what's inside of those 6?

azure bloom
# 
                var statModifyType = stat.ModifyType switch
                {
                    StatAuthoringType.Added => StatModifyType.Added,
                    StatAuthoringType.Subtracted => StatModifyType.Added,
                    StatAuthoringType.Increased => StatModifyType.Additive,
                    StatAuthoringType.Reduced => StatModifyType.Additive,
                    StatAuthoringType.More => StatModifyType.Multiplicative,
                    StatAuthoringType.Less => StatModifyType.Multiplicative,
                    _ => throw new ArgumentOutOfRangeException(nameof(stat.ModifyType)),
                };```
😄
#

beautiful code right

#

enum to smaller enum

rain harbor
#

doesn't seem bad tbh

#

at least

#

it's same as how colliders are managed

#

and amount of different colliders is really limited

#

and while it's number can grow, the growth itself is going to be very limited

#

After a bit of thinking I guess: what makes switch bad is when you start to have different inputs/outputs inside of it

rocky pelican
rocky pelican
# rain harbor what's the worst switch you'd have?

Switch statements might be faster than you'd expect, and having lots of cases has rarely been a problem in my experience (for performance at least). Here's one example that compares 2 different implementations:

Implementation 1: A job that updates a state machine of 100 states implemented with a union struct + switch statement:

 {
     switch (sm.CurrentState)
     {
         case 1:
         {
             sm.Time += DeltaTime;
             break;
         }
         case 2:
         {
             sm.Time += DeltaTime;
             break;
         }
         // (.....)
         case 100:
         {
             sm.Time += DeltaTime;
             break;
         }
     }
 }```


Implementation 2: 100 jobs that each take care of updating their respective state component (state components are enableable components)
```void Execute(ref State_1 state)
 {
     state.Time += DeltaTime;
 }```

---------------

Even when not switching states at runtime, and simply creating thousands of state machines that start off with a random state that never changes, the switch version performs better (2.3ms for switch, versus 2.75ms for 1-job-per-state). The performance advantage of the switch approach grows more and more when we do change states at runtime.

Basically, I don't think you should worry too much about quantity of switch cases. Other stuff like size of accessed data will matter a lot more
rain harbor
#

how much load per job was there?

rocky pelican
#

to be honest I don't have the numbers anymore, just got this from a past conversation

#

thousands of state machines, 100 states per SM, updating in parallel on a 12 thread CPU

rain harbor
#

sounds like having not even a full chunk per job is a waste tbh

#

I'd say this is way too synthetic to compare. And job count of 100 for same state machine is highly unlikely even in very mature games

rocky pelican
#

I redid the same test with 10, 20, and 100 states, and with varying amounts of data sizes per state, and the overall performance difference remained similar. It's at least just a way of showing that the cost of the switch itself is probably not going to be the thing to worry about even if it has lots of cases

rain harbor
#

so assuming 10 switches, 10 lookups used uniquely by that switch

rocky pelican
#

no that I haven't tested, but it would be pertinent

rain harbor
#

I don't know that word 😅

rocky pelican
#

"it would be useful to know"

rain harbor
#

right

tender thorn
#

Is using Blob assets for it not good?

rocky pelican
# tender thorn Is using Blob assets for it not good?

I could be wrong, but I think a blobassets implementation wouldn't help solving the main challenge of this problem:

  • we have many different node types, and many will be user-implemented
  • we must either be able to update nodes in an order that cannot be determined by node type, or to update only active nodes regardless of their type and allow the next nodes to update over multiple frames

With an approach where each node is a BlobAsset, think of how the behaviour tree update would run the current node logic and then "activate" the next node so that it gets updated next. Since nodes are blobassets and don't each have their specific component type, we can't create one job per type of node (we don't have a mechanism to query active nodes by type, since nodes aren't components). Therefore when we want to update the nodes that are active, we'd have a single job that iterates on entities that have the BehaviourTree component, and that BehaviourTree component would keep a blobAssetReference to the active node. We'd then have to figure out what the real type of that node is, and run different update logic depending on that type (probably using a switch statement over a node type enum). Then we'd get the blobAssetReference to the next node to update, and assign this as the active node in the BehaviourTree component. We'd basically be doing an alternative version of the "union structs in buffer" approach, except our union structs would be our blobAssets instead of being in a buffer.

Still curious to hear discussions about other implementation strategies if anyone has any, though

rain harbor
#

problem is that it's cost suddenly is n vs log n

#

but I guess with parallellism it might not be much of an issue

rocky pelican
#

I don't have lots of real life experience with BTs, but would it actually be possible to just update all nodes without caring about order? I've seen some BTs rely on blackboard values that get written to by some nodes, so that the following nodes do their update using that blackboard data, etc...

rain harbor
#

if there is a need to specific logic order - welp, ECS really won't fit here

rocky pelican
# rain harbor if there is a need to specific logic order - welp, ECS really won't fit here

True, but we must still figure out what the best solution is regardless. Our architecture must adapt to our design requirements; and not the other way around

If the best solution isn't ECS, then we must think about how to make it fit in our project that is otherwise mostly ECS, etc... Basically, I think it's always much more useful to think in terms of "what's the best solution" rather than "what's the most ECS solution". The latter will sometimes lead you down the wrong path, but the former will always be right

rain harbor
tender thorn