Finite State Machine (FSM) as a scripting language

[Xrayez]

Context

Finite state machine is a common computational model used in game development. Even Godot itself uses one for animation purposes. However, attempting to use Godot's animation FSM as a general-purpose FSM leads to further usability and maintainability problems, and it's not yet clear whether a general-purpose FSM would be actually useful for a variety of use cases. Godot's asset library provides >10 implementations of FSM, and they seem to solve different use cases.

See also Godot proposals like godotengine/godot#8847 and godotengine/godot#25021.

I've started this discussion in the search of ideas on how FSM could be implemented in Godot, taking advantage of C++ programming accessible to Goost.

Concept

After working on resurrecting the "multi-script" feature previously removed in Godot (see #92), I figured that an FSM can be implemented as an actual scripting front-end. The reason for that is because FSM could be considered a control flow model, and control flows are part of language designs. There are even some dedicated languages that implement FSM as a core construct.

Benefits include:

• Dedicated script editor which can be further customized (not via bottom panel like animation editor), so this gives much space for editing just like VisualScript.
• You will be no longer restricted to the node's base type, since a script can be attached to any node. This is especially important if you rely on node hierarchy to properly communicate transform notifications down to children. So you can use both Node2D and Spatial/Node3D just fine.

Note that VisualScript is not suitable for this task, because:

• it does not have a notion of transition nodes;
• it cannot have nested submodules, which would be needed to implement nested/hierarchical FSM;
• it's too complex for the specific purpose of representing and managing states, it was not designed for this purpose, so in all likelihood it wouldn't work as expected, so this would require making unnecessary workarounds.

Also note that the goal is not necessarily performance, but more like flexibility. Yet if there's an opportunity to make it performant, we should take advantage of that.

Implementation

The way I see it, the new FSM scripting language could introduce the following classes:

• StateScript: the script which can be attached to any node, turning a node into a FSM manager of some sort. A node which has such script attached will have state_changed/traveled signals and methods to transition between states. The script instance will instantiate dummy objects for each state that will handle the logic one at a time.
• StateScriptNode: will represent an individual state in the FSM, similarly to VisualScriptNode The node will provide necessary virtual callbacks such as _enter(), _exit(), _process(), _physics_process() etc.
• StateScriptTransition: allows to define valid transitions between StateScriptNodes. It will provide _can_travel() virtual method, returning true if current state can transition into the next state automatically.

Both StateScriptNode and StateScriptTransition can be optionally extended via other scripts (GDScript, VisualScript, C# etc.), giving you the ultimate flexibility.

I'll be refining this post once more ideas come, but for now I'm unlikely to work on this in the near future. Feedback welcome!

---

Q&A

Why StateScript and not StateMachineScript or FiniteStateMachineScript or FSMScript?

It's mostly about the State pattern, and FSM is implementation detail. Other names are either too verbose or too cryptic.

Can I attach StateScript directly to my KinematicBody root nodes to handle character states that way?

No, not really. There would be no way to define the main script (like using GDScript) to handle the FSM. It would be mainly useful as a child component, just like you add sprite/mesh instance nodes to physics bodies. You could use virtually any built-in node as an FSM as well.

[Xrayez]

For inspirations, I've also stumbled upon https://github.com/imjp94/gd-YAFSM plugin. Design-wise, it looks to me that the plugin is more targeted at handling GUI transitions, with no ability to use scripts to define the actual logic which may be complex in nature (signals are used for that instead, but emitting process, and physics_process signals every frame is quite costly, and could overwhelm the message queue).

However, the idea that states can be nested looks great. For that, the FSM functionality must inherit from StateScriptNode itself, and by default, the root node will contain no states.

YAFSM also gives ability to define transition conditions via editor inspector. Even though this kind of approach may be intuitive for designers rather than coders, I find such approach potentially bloaty. One would have to handle other type of conditions rather than just boolean/equality operators. Transition conditions could be scripted using VisualScript for that matter, which is already something which could be considered designer-friendly, or at least advertised to be so.

[nonunknown]

I have a implementation of State Machine which makes the use of FuncRef, this way you dont need to waste match or switch and register all in ready:

https://github.com/nonunknown/gdnative-state-machine

Also you can use it recusirvely, like a state that contains another State Machine, the only downside (as far as I know) is that for each state you need 3 functions, as you can see in the example.gd

[Shadowblitz16]

I would rather not have to attach a script to a node for fsm's

take a look at state charts it uses expressions and signals to manage state and you don't need to know the path to the state you want to travel to

https://github.com/derkork/godot-statecharts

I would suggest using a node graph though instead of nodes mainly due to the fact you can have nested things in graphs as well