State Machine, Selection Utility, and Async Operations

Development Programming & Scripting
, ,
1

Is there a way to use async operations with ordered state selection?

The selection behavior of TrySelectChildren*, TrySelectChildrenWithHighestUtility or TrySelectChildrenAtRandomWeightedByUtility try and select states until the first successful SelectStateInternal.

The downside here is that you can only facilitate failure and continued ordered selection if you have logic that can fail immediately in the same frame. Sometimes a behaviors ability to execute is only truly known after an async operation, such as an EQS query.

Is there a way to facilitate async determination of state execution possibility, that maintains the ordered consideration of the state selection behavior?

So for example if TrySelectChildrenWithHighestUtility has 5 states to consider, but to execute those states, they need to run an EQS query, you don’t really have the ability for all 5 states to be considered in that expected order, because technically you’d need to enter one to begin executing an EQS task within it, and that’s all the selection behavior is really concerned with.

I’d prefer not to be forced to run EQS queries synchronously, so that they can be sure to fail immediately in the FStateTreeTasks_RunEQS::EnterState, so that the selection behavior can continue to execute properly and consider other child states based on the selection mode. It’s not ideal for scalability that async operations are incompatible with the selection modes.

Are there any state tree recommendations for situations like this?

For example sake, consider a subtree like so

  • MeleeCombat
    • ChargeAbility - needs to run an EQS query
    • LungeAbility - needs to run an EQS query
    • SpecialAbility1 - executes a GAS ability that does async pre-work
    • SpecialAbility2 - executes a GAS ability that does async pre-work

The ideal solution would

  • Consider each ability(with associated EQS query), in the order that the selection behavior demands
  • Allow the EQS query to run asynchronously
  • If the EQS query fails to find a solution, state selection should continue the ordered selection
  • Ideally not perform lower priority state EQS queries until it is determined that higher priority ones can’t run(to save processing)

Some possibilities I can think of

  • Run the EQS Queries in a global task or evaluator, allowing the child selection behavior to have access to all the potential query results at selection time.
    • Pros
      • Provides compatibility with child selection
    • Cons
      • Does a lot more EQS query work than is necessary, simply so that all results are known at state consideration time.
      • Inability to use conditions to gate the execution of the eqs, as they would normally be gated through the conditions on the child state.
      • The need to constantly run the EQS queries for all potential child states so the results are available within the same substate selection context
  • Create a custom task/evaluator that encapsulates the ordered and async execution of all the potential sub queries, with
    • Pros
      • As functional as I need it to be, as a supertask
    • Cons
      • Completely circumvents the state tree structure means that I’d be giving up conditionals, utility selection
      • Less plugin-able than using discrete states(linked assets, etc)

I don’t love fighting against the state tree in these ways, so neither of these is super appealing. Is there a way I don’t have to completely abandon or break the state tree structure just to maintain ordered state selection along with async tasks?

Thanks

Jeremy

[Attachment Removed]

2

[mention removed]​

So I got rid of the EQS query and make a specialised syncronous state tree task to do the job that I was using the EQS query for, but now I’m running into another problem, that as I debug it, is really throwing me thinking that how I thought state tree state selection works is not how it works at all, and it’s really breaking my brain and makes no sense to me.

  • I know that when states are selected, that FStateTreeExecutionContext::SelectStateInternal is called recursively, basically so long as the parent has child states.
  • The various ESelectStateBehavior modes are handled in here, TrySelectInOrder, TrySelectChildrenAtRandom, TrySelectChildrenWithHighestUtility, TrySelectChildrenAtRandomWeightedByUtility
  • Each of these is basically a different implementation of child selection. Most of them try their children in some order until one successfully activates.
  • And recurse it goes until it successfully lands on a leaf state

The part that I just realized doesn’t seem to work like I thought, is that I expect my Task.Enter() to be called during StateSelect(), such that if the Enter returns Failed, it will proceed on to the next selection in the chain.

But this isn’t how it works. Task.Enter() doesn’t get called during SelectState, meaning a Task doesn’t participate at all in state selection. This is bananas to me.

Are Enter Conditions the only mechanism to participate in state selection?

It seems so, and this blows my mind. This is very counter intuitive. Conditions don’t have the same data binding capabilities as a task, so how are you supposed to run something like a TrySelectChildrenAtRandomWeightedByUtility that asks 5 different types of abilities whether they can activate, and those ability substates have a task that tries to calculate a move-to goal for the attack to begin from? If an attack location can’t be found for that ability, I want it to fail selection, and for the SelectStateInternal to try the next state, based on the state selection rules.

You need a task to do this calculation, so that it can share its result with child states that act on it(move to). But if Task.Enter() isn’t part of the SelectStateInternal recursive activation, you can’t do this super basic prioritized ability evaluation common to AI utilizing the state tree. It makes no sense to do this sort of operation in a enter condition. You can’t share the result. You’d have to do it again in the task.

Please tell me there is a workaround for this that I’m not seeing at the moment, because this seems like a deal breaking problem for the state tree for AI usage.

How would you do this rudimentary ability selection with the state tree child selection functionality allowing it to consider a series of ability selections in some selection order?(in order, utility based, etc)

[Attachment Removed]

3

You are correct that EnterState is only called after transitions are over and a state has been selected. This limits selection to Enter Conditions.

In your idea for async or deferred transitions for waiting on an enter “task”, should logic continue in the previous state that was completed/failed/succeeded? Or would it be almost a small pause while waiting for the next valid state to pass its conditions? I know we have had some internal projects using utility scoring that have had some issues/workarounds they needed. I will reach out to some of those teams to see if they have possibly dealt with this kind of scenario.

-James

[Attachment Removed]

4

If there is a condition necessary to be in the leaf state, and if that condition changes it should exit would make sense to have run as a task on a parent state in the hierarchy. You could use a delegate (or multiple delegates) to trigger a transition into a relevant state or by having the condition change which causes a transition in the leaf state such as your On Tick transition that checks that the location is valid. By using delegates, you could avoid the need for the tick checking the transition as the delegate would broadcast to any bound listeners. One delegate could even signal another task to run to find the next best attack given that the current is invalid, and when that task finds the next priority attack, it can trigger the transition.

I believe you may have spoken with Siggi about this during the StateTree livestream who tried to give some guidance as well. I am unsure of all that he shared, but our current approach has been intermediate states and optionally combining them with delegates. Speaking with Patrick, I do not think we have seen many other patterns for handling something like this in internal projects.

-James

[Attachment Removed]

5

For purposes of getting me beyond this road block, we can take the async element out of the equation. I replaced the EQS query with a specialized FStateTreeTasks_CalculateApproach that does what the the query was doing, much cheaper and simpler than EQS, with the expectation that if FStateTreeTasks_CalculateApproach::EnterState returned EStateTreeRunStatus::Failed, that the TrySelectChildrenAtRandomWeightedByUtility would move on and try selecting the next state.

This is a pretty basic functional expectation within AI. Lots of abilities might have a bit of state to gather or calculate as a precondition to its execution. And that calculation can often fail. And you want that failure to be accounted for in the child state selection of the parent. But the design of the state tree seems to paint itself in a corner in situations like this.

The core problem is that Tasks have no say in state selection, only conditionals. But conditionals are unsuitable for the job in this sort of situation, because they aren’t built to share state. I had an expectation, partly because every other state machine I’ve used has accommodated it, that Task::Enter failing would be treated by state selection as a reason to move on to the next state, based on the selection behavior of the parent.

The only work around I can really think of is

  • Clone a conditional version of FStateTreeTasks_CalculateApproach as FStateTreeConditional_CalculateApproach.
  • Allow the conditional to fill in mutable state results into a variable on the state, via the mutability of a TStateTreePropertyRef<FAttackPositionResult> property. To work around no property binding
  • But this has a second problem. You often need to periodically re-run logic like this to account for targets moving, so I’d still need the Task version of this logic to perform the job of periodic configurable recalculation intervals. Conditionals can’t do that. Not with configurable intervals anyways. I suppose it could be put on a transition out of the state, but that would run every frame.

Is there another approach I’m not seeing?

I can see some logic into state selection only considering conditions, but if that’s to be the case, there better be a way for conditions to calculate and share state, to cover situations like this. Like you should be able to property bind to enter conditions. But that still doesn’t answer the annoying third bullet point, which is that conditionals aren’t meant to perform periodic re-evaluations.

Maybe if they had configurable intervals, and you did a FStateTreeConditional_CalculateApproach as an EnterCondition, and a !FStateTreeConditional_CalculateApproach as a transition condition out of the state. That would at least save you the need for a redundant task. But it still feels sloppy, and completely devalues the meaning of Task enter() return values.

To me, it makes the most sense tasks should Enter() as part of selection. It’s the only approach that doesn’t create an avalanche of complexity. The whole idea of a task that can fail to enter is that I would expect it to effect the ability of the state to be selected.

I’ve gone into more detail in discord in hopes that I can get some more ideas from the public

https://discord.com/channels/187217643009212416/1459272122726875268

[Attachment Removed]

6

Here is the simplest approach I can come up with to account for this problem, and it’s still a pretty undesirable hack

The enter condition, and the transition out condition of the state use the same conditional class, and write their calculated state to a property struct that the children of this state bind to.

[Image Removed]

And something like this is necessary because tasks don’t participate in state selection, and to use a conditional means writing the calculated state elsewhere to share. The tree failed exit condition takes the role of what would be a task tick that could fail during execution. There’s still not a great way to interval check the failure tick condition. I don’t think delay transition is the same thing?

And all this to allow the simple situation of utilizing state tree child selection in a situation like this

[Image Removed]

When each child state needs to calculate some intermediate data as part of its selection, such that if it fails to do so, state selection can continue.

Hope I’m communicating the issue well enough.

[Attachment Removed]