How to implement FSM in ECS architecture

dongyiqi · April 13, 2018, 6:46am

I want to convert my game code from OOP(GameObject) to DOP(ECS). But I have no idea how to convert the Finite State Machine in the new system.
One way I know is change the composition the each component which represent a state. eg: if a entity is idle, idleComponet is attached to that entity, then the entity is running,then remove the idleCompoent and add runningComponent.
If there will be a best practice or not ?

floboc · April 13, 2018, 6:51am

If you look at the comments of this blog post : Designing Bomberman with an Entity System: Which Components? – T-machine.org you will see that some people consider that FSM are not a good fit with ECS. However, they also talk about a possible way to implement it if I remember right. Have a look

dadude123 · April 13, 2018, 10:38am

ECS is awesome, but it’s not something you can use for everything. It has its advantages and its disadvantages just like every other system.

Entities (as in the ecs) are about data, its layout in memory, access patterns, …
A state machine is about code structure, how you execute different things based on context.

The two concepts themselves don’t really seem compatible.

“to hammer everything looks like nail” think about it…

I’d be surprised if you’d actually get more maintainable AND faster code by somehow forcefully pushing your FMS-shaped block into a ECS-shaped hole.

Arakon · April 13, 2018, 1:20pm

ECS would be a pretty different approach.
This may be of some help:

Krajca · April 13, 2018, 1:22pm

@dongyiqi what if you implement each state as ECS component so you will have one system for each state that will do the job.

PhilSA · April 13, 2018, 2:47pm

My general, untested, initial idea would be:

StateMachineComponent

has an int/enum representing the “FromState”
has an int/enum representing the “ToState”
has a float representing the time at which the last transition was started
has a float representing the time that the last transition should last

StateMachineSystem

Advances the state simulation and updates the information in the StateMachineComponent

As for how state behaviours would actually be defined; they would all be implemented directly into their own system class that executes after the StateMachineSystem. So we’d have a “MyCharacterAnimationSystem” for example that operates on StateMachineComponents and MyCharacterAnimationComponents. Based on the info contained in StateMachineComponent, MyCharacterAnimationSystem would do some kind of switch case on the From/ToState ids of the StateMachineComponent and determine what animation to actually use with that.

If you want to trigger a transition, you simply get you MyCharacterAnimationSystem to modify the FromState, ToState, and transitionStartTime. The StateMachineSystem will automatically handle updating the transition on its next update

bcondran · April 13, 2018, 7:39pm

The state of an entity would be described by the components (most likely of the tag-like variety) it has attached.
The different systems would be responsible for changing the state of the entity.

Naive example:

EnemyEntiy with EnemyIdle, EnemyAttack and EnemySearch components

EnemyIdleSystem handles logic for spotting Player. Removes Idle component and adds Attack component when player is in enemy’s sights.

EnemyAttackSystem handles logic for attacking Player. Removes Attack component and adds Search component if player leaves enemy’s sights.

EnemySearchSystem handles logic for enemy searching for player. Removes Search component and adds Attack component if player re-enters enemy sights, or if the player is not found after a specified period of time, adds the Idle component.

Alternatively, as others have suggested, you could just have an EnemyStateComponent and EnemyStateSystem, which would probably be a better solution unless the system would end up being too complex

UCh · August 15, 2018, 8:08am

I’m working on an implementation of this in a similar concept that Ash framework (and ECS framework from the Actionscript). I didn’t figure out the implementation detail but is this line:

StateMachineComponent

State: actual state (enum,int,string…)
NextState: If different than State indicate pending transition
StateComponentsMap: A dictionary of stateId-array of component types

StateExitSystem

Runs first
If NextState is different of State, remove all component from State from the entity

Then you need to implement a system for each possible state that adds the components for that state and change the actual one.

Example:

State Idle (no components associated)
State TargetEntity (need Target component)
TransitionToTargetEntitySystem: Adds the target component with values selected by the UI stored somewhere, and sets actual state in the State machine component.

That way your targeting system doesn’t mix with the FSM system.

UCh · August 16, 2018, 6:53am

A bit more detail on the implementation I was talking about:

public struct MovementCommandSM : IComponentData
    {
        public MovementState State;
        public MovementState NextState;
        private Dictionary<MovementState, ComponentType[]> StateComponents;

        public MovementCommandSM(MovementState initialState,
            Dictionary<MovementState, ComponentType[]> stateComponents) : this()
        {
            State = initialState;
            NextState = initialState;
            StateComponents = stateComponents;
        }
    }

    public enum MovementState
    {
        Idle,
        MoveToPosition,
        TargetEntity
    }

var fsm = new MovementCommandSM(
                MovementState.Idle,
                new Dictionary<MovementState, ComponentType[]>
                {
                    {
                        MovementState.Idle, new ComponentType[0]
                    },
                    {
                        MovementState.MoveToPosition, new ComponentType[]
                        {
                            ComponentType.Create<Destination>()
                        }
                    },
                    {
                        MovementState.TargetEntity, new ComponentType[]
                        {
                            ComponentType.Create<Destination>(),
                            ComponentType.Create<Target>()
                        }
                    }
                }
            );

capyvara · August 17, 2018, 1:55am

Anyone has thoughts about ValueTask ? all the async/await stuff in C# is basically a syntax sugar for a state machine.

github.com/dotnet/runtime

Allocation-free awaitable async operations with ValueTask<T> and ValueTask

opened 04:27AM - 25 Feb 18 UTC

closed 07:56PM - 31 Jan 20 UTC

stephentoub

area-System.Threading

## Background `ValueTask<T>` is currently a discriminated union of a `T` and a …`Task<T>`. This lets APIs that are likely to complete synchronously and return a value do so without allocating a `Task<T>` object to carry the result value. However, operations that complete asynchronously still need to allocate a `Task<T>`. There is no non-generic `ValueTask` counterpart today because if you have an operation that completes synchronously and successfully, you can just return `Task.CompletedTask`, no allocation. That addresses the 80% case where synchronously completing operations no longer allocate. But for cases where you want to strive to address the 20% case of operations completing asynchronously and still not allocating, you’re forced to play tricks with custom awaitables, which are one-offs, don’t compose well, and generally aren’t appropriate for public surface area. `Task` and `Task<T>`, by design, never go from a completed to incomplete state, meaning you can’t reuse the same object; this has many usability benefits, but for APIs that really care about that last pound of performance, in particular around allocations, it can get in the way. We have a bunch of new APIs in .NET Core 2.1 that return `ValueTask<T>`s, e.g. `Stream.ReadAsync`, `ChannelReader.ReadAsync`, `PipeReader.ReadAsync`, etc. In many of these cases, we’ve simply accepted that they might allocate; in others, custom APIs have been introduced specific to that method. Neither of these is a good place to be. ## Proposal I have implemented a new feature in `ValueTask<T>` and a counterpart non-generic `ValueTask` that lets these not only wrap a `T` result or a `Task<T>`, but also another arbitrary object that implements the `IValueTaskSource<T>` interface (or `IValueTaskSource` for the non-generic `ValueTask`). An implementation of that interface can be reused, pooled, etc., allowing for an implementation that returns a `ValueTask<T>` or `ValueTask` to have amortized non-allocating operations, both synchronously completing and asynchronously completing. ### The enabling APIs First, we need to add these interfaces: ```C# namespace System.Threading.Tasks { public interface IValueTaskSource { bool IsCompleted { get; } bool IsCompletedSuccessfully { get; } void OnCompleted(Action<object> continuation, object state, ValueTaskSourceOnCompletedFlags flags); void GetResult(); } public interface IValueTaskSource<out TResult> { bool IsCompleted { get; } bool IsCompletedSuccessfully { get; } void OnCompleted(Action<object> continuation, object state, ValueTaskSourceOnCompletedFlags flags); TResult GetResult(); } [Flags] public enum ValueTaskSourceOnCompletedFlags { None = 0x0, UseSchedulingContext = 0x1, FlowExecutionContext = 0x2, } } ``` An object implements `IValueTaskSource` to be wrappable by `ValueTask`, and `IValueTaskSource<TResult>` to be wrappable by `ValueTask<TResult>`. Then we add this ctor to `ValueTask<TResult>`: ```C# namespace System.Threading.Tasks { public struct ValueTask<TResult> { public ValueTask(IValueTaskSource<TResult> source); ... } } ``` Then we add a non-generic `ValueTask` counterpart to `ValueTask<TResult>`. This mirrors the `ValueTask<TResult>` surface area, except that it doesn’t have a `Result` property, doesn’t have a ctor that takes a `TResult`, uses `Task` in places where `Task<TResult>` was used, etc. ```C# namespace System.Threading.Tasks { [AsyncMethodBuilder(typeof(AsyncValueTaskMethodBuilder))] public readonly partial struct ValueTask : IEquatable<ValueTask> { public ValueTask(Task task); public ValueTask(IValueTaskSource source); public bool IsCanceled { get; } public bool IsCompleted { get; } public bool IsCompletedSuccessfully { get; } public bool IsFaulted { get; } public Task AsTask(); public ConfiguredValueTaskAwaitable ConfigureAwait(bool continueOnCapturedContext); public override bool Equals(object obj); public bool Equals(ValueTask other); public ValueTaskAwaiter GetAwaiter(); public override int GetHashCode(); public static bool operator ==(ValueTask left, ValueTask right); public static bool operator !=(ValueTask left, ValueTask right); } } ``` And finally we add the System.Runtime.CompilerServices goo that allows `ValueTask` to be awaited and used as the return type of an async method: ```C# namespace System.Runtime.CompilerServices { public struct AsyncValueTaskMethodBuilder { public static AsyncValueTaskMethodBuilder Create(); public void Start<TStateMachine>(ref TStateMachine stateMachine) where TStateMachine : IAsyncStateMachine; public void SetStateMachine(IAsyncStateMachine stateMachine); public void AwaitOnCompleted<TAwaiter, TStateMachine>(ref TAwaiter awaiter, ref TStateMachine stateMachine) where TAwaiter : INotifyCompletion where TStateMachine : IAsyncStateMachine; public void AwaitUnsafeOnCompleted<TAwaiter, TStateMachine>(ref TAwaiter awaiter, ref TStateMachine stateMachine) where TAwaiter : ICriticalNotifyCompletion where TStateMachine : IAsyncStateMachine; public void SetResult(); public void SetException(Exception exception); public ValueTask Task; } public readonly struct ValueTaskAwaiter : ICriticalNotifyCompletion { public bool IsCompleted { get; } public void GetResult() { } public void OnCompleted(Action continuation); public void UnsafeOnCompleted(Action continuation); } public readonly struct ConfiguredValueTaskAwaitable { public ConfiguredValueTaskAwaiter GetAwaiter(); public readonly struct ConfiguredValueTaskAwaiter : ICriticalNotifyCompletion { public bool IsCompleted { get; } public void GetResult(); public void OnCompleted(Action continuation); public void UnsafeOnCompleted(Action continuation); } } } ``` ### Changes to Previously Accepted APIs At the very least, we would use the `ValueTask` and `ValueTask<T>` types in the following previously accepted/implemented APIs that are shipping in 2.1: - **Pipelines**. Instead of pipelines having a custom `PipeAwaiter<T>` type, it will return `ValueTask<T>` from the `ReadAsync` and `FlushAsync` methods that currently return `PipeAwaiter`. `PipeAwaiter<T>` will be deleted. `Pipe` uses this to reuse the same pipe object over and over so that reads and flushes are allocation-free. - **Channels**. The `WaitToReadAsync` and `WaitToWriteAsync` methods will return `ValueTask<bool>` instead of `Task<bool>`. The `WriteAsync` method will return `ValueTask` instead of `Task`. At least some of the channel implementations, if not all, will pool and reuse objects backing these value tasks. - **Streams**. The new `WriteAsync(ReadOnlyMemory<byte>, CancellationToken)` overload will return `ValueTask` instead of `Task`. `Socket`’s new `ReceiveAsync`/`SendAsync` methods that are already defined to return `ValueTask<int>` will take advantage of this support, making sending and receiving on a socket allocation free. `NetworkStream` will then expose that functionality via `ReadAsync`/`WriteAsync`. `FileStream` will potentially also pool so as to make synchronous and asynchronous reads/writes allocation-free. - **WebSockets**. The new `SendAsync(ReadOnlyMemory<byte>, …)` overload will return `ValueTask` instead of `Task`. Many `SendAsync` calls just pass back the result from the underlying `NetworkStream`, so this will incur the benefits mentioned above. There are likely to be other opportunities in the future as well. And we could re-review some of the other newly added APIs in .NET Core 2.1, e.g. `TextWriter.WriteLineAsync(ReadOnlyMemory<char>, ...)`, to determine if we want to change those from returning `Task` to `ValueTask`. The tradeoff is one of `Task`'s usability vs the future potential for additional optimization. ### Limitations `Task` is powerful, in large part due to its “once completed, never go back” design. As a result, a `ValueTask<T>` that wraps either a `T` or a `Task<T>` has similar power. A `ValueTask<T>` that wraps an `IValueTaskSource<T>` can be used only in much more limited ways: - The 99.9% use case: either directly await the operation (e.g. `await SomethingAsync();`), await it with configuration (e.g. `await SomethingAsync().ConfigureAwait(false);`), or get a Task out (e.g. `Task t = SomethingAsync().AsTask();`). Using `AsTask()` incurs allocation if the `ValueTask`/`ValueTask<T>` wraps something other than a `Task`/`Task<T>`. - Once you’ve either awaited the `ValueTask`/`ValueTask<T>` or called `AsTask`, you must never touch it again. - With a `ValueTask<T>` that wraps a `Task<T>`, today you can call `GetAwaiter().GetResult()`, and if it hasn’t completed yet, it will block. That is unsupported for a `ValueTask<T>` wrapping an `IValueTaskSource<T>`, and thus should be generally discouraged unless you're sure of what it's wrapping. `GetResult` must only be used once the operation has completed, as is guaranteed by the await pattern. - With a `ValueTask<T>` that wraps a `Task<T>`, you can await it an unlimited number of times, both serially and in parallel. That is unsupported for a `ValueTask<T>` wrapping an `IValueTaskSource<T>`; it can be `await`ed/`AsTask`'d once and only once. - With a `ValueTask<T>` that wraps a `Task<T>`, you can call any other operations in the interim and then await the `ValueTask<T>`. That is unsupported for a `ValueTask<T>` wrapping an `IValueTaskSource<T>`; it should be `await`ed/`AsTask`’d immediately, as the underlying implementation may be used for other operation, subject to whatever the library author chose to do. - You can choose to explicitly call `IsCompletedSuccessfully` and then use `Result` or `GetAwaiter().GetResult()`, but that is the only coding pattern outside of `await`/`AsTask` that’s supported. We will need to document that `ValueTask`/`ValueTask<T>` should only be used in these limited patterns unless you know for sure what it wraps and that the wrapped object supports what's being done. And APIs that return a `ValueTask`/`ValueTask<T>` will need to be clear on the limitations, in hopes of preserving our ability to change the backing store behind `ValueTask<T>` in the future, e.g. an API that we ship in 2.1 that returns `ValueTask<T>` around a `Task<T>` then in the future instead wrapping an `IValueTaskSource<T>`. Finally, note that as with any solution that involves object reuse and pooling, usability/diagnostics/debuggability are impacted. If an object is used after it's already been effectively freed, strange/bad behaviors can result. ### Why now? If we don’t ship this in 2.1, we will be unable to do so as effectively in the future: - Some methods (e.g. the new `Stream.WriteAsync` overload) are currently defined to return `Task` but should be changed to return `ValueTask`. - Some methods return `ValueTask<T>`, but if we’re not explicit about the limitations of how it should be used, it’ll be a breaking change to modify what it backs in the future. - Various types (e.g. `PipeAwaiter<T>`) will be instant legacy. - Prior to .NET Core 2.1, `ValueTask<T>` was just OOB. It’s now also in System.Private.CoreLib, with core types like `Stream` depending on it. ### Implementation Status With the exception of pipelines, I have these changes implemented across coreclr and corefx. I can respond to any changes from API review, clean things up, and get it submitted as PRs across coreclr and corefx. Due to the breaking changes in existing APIs, it will require some coordination across the repos. (EDIT stephentoub 2/25: Renamed IValueTaskObject to IValueTaskSource.) (EDIT stephentoub 2/25: Changed OnCompleted to accept object state.)

ldhongen1990 · August 17, 2018, 2:49am

PhilSA:

My general, untested, initial idea would be:

StateMachineComponent

has an int/enum representing the “FromState”

has an int/enum representing the “ToState”

has a float representing the time at which the last transition was started

has a float representing the time that the last transition should last

StateMachineSystem

Advances the state simulation and updates the information in the StateMachineComponent

As for how state behaviours would actually be defined; they would all be implemented directly into their own system class that executes after the StateMachineSystem. So we’d have a “MyCharacterAnimationSystem” for example that operates on StateMachineComponents and MyCharacterAnimationComponents. Based on the info contained in StateMachineComponent, MyCharacterAnimationSystem would do some kind of switch case on the From/ToState ids of the StateMachineComponent and determine what animation to actually use with that.

If you want to trigger a transition, you simply get you MyCharacterAnimationSystem to modify the FromState, ToState, and transitionStartTime. The StateMachineSystem will automatically handle updating the transition on its next update

I briefly read the material referred to by Arakon (it’s a book by a veteran game programmer), it’s all theory and not much reference code but I think he is trying to say FSM done right in ECS is by being stateless in a way that we don’t need to have variables holding the current state. Instead, we utilise ECS implicit “state” by adding and removing entity from system (what he meant by table, if I am not wrong). This way each system operating on different types of state just need to operate directly on their specific data, instead of always checking “if I am in this state blah blah blah, if I am in that state blah blah blah”.
Still learning though.

ldhongen1990 · August 17, 2018, 8:06am

To add on, as part of my investigation and research, I have further discovered that we can actually utilise the existing Reactive system to provide for an OnEnter and OnExit for individual state system. Perfect

dongyiqi · August 17, 2018, 2:45pm

This seems to be a really good way to implement kind of FSM structure~ thank you~

Reborn1214 · July 11, 2019, 11:52am

Hello,Do you have any examples?I have a piece of code for the video.But,I’m not sure how to switch status .I had to use switch to check status in ChangeJob.

ScriptsEngineer · September 24, 2020, 4:03pm

Can that be an answer?
https://github.com/Unity-Technologies/EntityComponentSystemSamples/tree/master/ECSSamples/Assets/Use%20Case%20Samples/1.%20State%20Machine%20AI

davenirline · September 25, 2020, 6:39am

The problem with using tag components to differentiate between states is that in introduces the usage of sync points. Components that can be enabled/disabled will solve this but for now, sync points are needed.

dongyiqi · September 30, 2020, 11:09am

After two years~
Finally comes the official explation of FSM in DOTS. Cheers~
But the “more things” is funny:

What if we wanted thousands of guards all looking for the player?

If there is a large area, do all the guards need to check if they can see the player? What if they are nowhere near the player? What kind of acceleration structure could you add to make this more efficient?

It is the problem I’m working on.
The implementation to change state by ComponentData flag in under the condition that just a few entities and change state not so often, what if there are thousands of them? Who knows~

WAYNGames · September 30, 2020, 11:52am

The issue I have with the tag state component are :

tagging/detaging has a cost although it will be reduced by the enable/disable feature when it will come
single state check : in a FSM, you are in one state at a time but you could have several tag state component at once on the entity, especially if anyone can add them.

That’s why I would prefer an implementation with a single component per FSM and an enum for the states.

Lieene-Guo · September 30, 2020, 11:58am

Agree with the structural change cost issue.
Not able to have parallel states is a defect of FSM. That’s where behaviors tree jumps out and beat FSM.
What’s so bad to have parallel states.
It makes FSM work better imo.

WAYNGames · September 30, 2020, 3:10pm

FSM is a tool with it’s set of rules and it’s uses.
Behavior tree is another.

Still if you don’t have too many state you could still use a single component to treat states in a bit mask manner.

Topic		Replies	Views
Made an FSM framework in ECS but fear that it might be slow Unity Engine Entities , com_unity_entities	20	3806	July 2, 2018
Why vanilla ECS is not enough Unity Engine Entities , com_unity_entities	43	6661	July 15, 2020
Figuring out State Machines in DOTS Unity Engine Entities , com_unity_entities	25	7202	December 6, 2020
Netcode + DOTS + FSM: How can you make an FSM that scales well? Unity Engine Entities , Netcode-for-Entities , Intermediate , Question , 6-2	8	161	April 16, 2026
C# Proper State Machine Unity Engine Scripting	122	88123	July 21, 2024

How to implement FSM in ECS architecture

Related topics