Introduce a generic Finite State Machine graph type

[tarragonfly]

Description

Visual scripting is particularly well geared towards finite state machine visualisation, so I think this would be a good fit for Orchestrator to handle use cases where EventGraph doesn't always make as much sense as an FSM. For example, when developing enemy AI, a custom animation state machine, a structured player controller or just the state of random doors - open, locked, closed, etc.

• This would likely be a different graph type - StateGraph.
• A new State Graph contains a single empty state that's marked as Start state, which is where the flow starts for this graph type.
• Right click doesn't open node finder, instead it gives options for State creation
• Individual States group nodes similarly to an EventGraph. The StateGraph goes a level higher and groups State and Transition nodes. EventGraph can be dragged into a StateGraph as a new state, or assigned to a Transition.
• Introduce a transition node, which also nests an EventGraph, doesn't have input or output ports, but listens to signals emitted in connected State nodes.
• Transitions are done with signals by emitting a signal from a State node to a connected Transition node. A transition has a baked in event trigger node - "Trigger State Transition", which passes the flow to the next connected state.
• Introduce Any State node with some kind of priority or weight system. Maybe priority with optional weights, overhead needs to be considered.
• Introduce two new events - On Enter State, On Exit State as the primary ways of executing logic in a state and performing state cleanup.
• States can also optionally contain all regular events such as Process, which execute only when the state is active
• Add a new Node type called SubState(?) for EventGraph that nests a StateGraph. It has two flow inputs - Start, Stop and two flow outputs - Started, Stopped. Dragging a StateGraph into an EventGraph nests it as a SubState node.
• A simple API to get a reference to some StateGraph and get its current active state in GDScript and do something based on that. Also listen to state_changed signal that passes the current state.

---

Implementation ideas

No response

[Naros]

Hi @tarragonfly, I think, in general, this sounds like an elegant idea. It would simplify our internal process, where we use another tool for Behavior Trees for enemy AI, and we certainly wanted to combine this technique somehow.

To provide some context on our internal process, we generally do this using Scene Node composition where we have a high-level scene node type that acts as our "AI" node that holds a blackboard, etc. Then as children of this node, we add and organize various control nodes like "Sequence" that then has a set of child behaviors. There is a core FSM in the "AI" node, but it's more defined around the notion of behavior trees.

So I want to clarify a few points to make sure I understand your point of view.

A new graph type, StateGraph is meant to provide a slightly different canvas style for organizing game concepts, and in this case its a series of states and transitions. A state or transition can reference a single EventGraph, allowing the StateGraph to be a higher-level organization abstraction around a FSM; effectively reducing the overhead a user would need to implement to coordinate a FSM in visual scripts.

That said, what isn't immediately apparent to me from the description is how would the FSM ultimately be called from the outset. Would you expect that an Orchestration Script (.os file) either be based on an EventGraph or a StateGraph or would the base "EventGraph" essentially call into one of your defined StateGraph instances that organizes various EventGraph instances into a FSM?

Since it seemed that your description indicates that an EventGraph can call into a StateGraph with a SubState node, that perhaps the outset is where an EventGraph calls into a specific StateGraph to initiate the FSM behavior, but perhaps I'm wrong?

[tarragonfly]

A new graph type, StateGraph is meant to provide a slightly different canvas style for organizing game concepts, and in this case its a series of states and transitions. A state or transition can reference a single EventGraph, allowing the StateGraph to be a higher-level organization abstraction around a FSM; effectively reducing the overhead a user would need to implement to coordinate a FSM in visual scripts.

Correct, but I'm starting to waver on referencing existing EventGraphs as states. Perhaps it would be better to have dedicated States still expressed as EventGraphs but separate from current EventGraphs with its own dedicated StateGraph UI.

That said, what isn't immediately apparent to me from the description is how would the FSM ultimately be called from the outset. Would you expect that an Orchestration Script (.os file) either be based on an EventGraph or a StateGraph or would the base "EventGraph" essentially call into one of your defined StateGraph instances that organizes various EventGraph instances into a FSM?

Yea, I wasn't that clear on it when writing the feature request, but after contemplating on the issue I think State Graphs should fire immediately as soon as they're ready from Start state. The relevant event being On Enter State. There should be no manual initialization to streamline the system and lessen confusion.

Also, rather than the orchestration being either EventGraph or StateGraph based, I think it would be better to have two graph types in the same .os since you can only have one orchestration per node. And by default, orchestration would be a blank slate that has neither of the graph types.

So the user then decides which graph type to add and how many instances of that graph type to add. This is done by clicking the + button and the user chooses which graph to create from a dropdown.

Visual mockup of how both graph types would live together in the same .os:

Clicking on a state or transition would open it as event graph editor. Clicking on the StateGraph would open the state graph editor.

Since it seemed that your description indicates that an EventGraph can call into a StateGraph with a SubState node, that perhaps the outset is where an EventGraph calls into a specific StateGraph to initiate the FSM behavior, but perhaps I'm wrong?

The nesting idea is starting to get confusing in general. Perhaps it's just better to have FSM be its own thing as outlined in the image above. This way it's a lot easier to reason about StateGraph's concepts since it's self contained.

Nesting of different graph types is an interesting concept, but it's not that straightforward to implement or communicate about it. The idea stems from similar tools in Unity, but those are a lot more free-form and don't have a class/orchestration tying multiple concepts such as functions and signals together with several graphs. In those tools, there's just a single graph asset with a local variable blackboard and that's it. So nesting a graph asset inside another graph asset is not that complicated.

There's also an interesting GDC AI talk from Naughty Dog, where they nest Behaviour Tree graphs inside FSM graphs for a hybrid approach in Uncharted games. But behaviour trees are out of scope for this feature request I think. FSM has a much wider application than just AI. And they are two different concepts in general.

[Naros]

Correct, but I'm starting to waver on referencing existing EventGraphs as states. Perhaps it would be better to have dedicated States still expressed as EventGraphs but separate from current EventGraphs with its own dedicated StateGraph UI.

I completely agree. With this in mind, we've designed the UI to have a specific GraphEdit layout for when you want to create Macro Libraries and Function Libraries, so this would just be one additional layout. I think this should be relatively easy to manage with the existing tab infrastructure.

Yea, I wasn't that clear on it when writing the feature request, but after contemplating on the issue I think State Graphs should fire immediately as soon as they're ready from Start state. The relevant event being On Enter State. There should be no manual initialization to streamline the system and lessen confusion.

That sounds fair and definitely less confusing for the end user.

Nesting of different graph types is an interesting concept, but it's not that straightforward to implement or communicate about it. The idea stems from similar tools in Unity, but those are a lot more free-form and don't have a class/orchestration tying multiple concepts such as functions and signals together with several graphs. In those tools, there's just a single graph asset with a local variable blackboard and that's it. So nesting a graph asset inside another graph asset is not that complicated.

I also think that its more plausible for state and transitions to interact with functions and macros than they would with an event graph primarily on the basis that the interaction with Godot function overrides and callbacks are entirely abstracted away from the user in a StateGraph to guarantee the deterministic nature of the flow into and out of a state.

There's also an interesting GDC AI talk from Naughty Dog, where they nest Behaviour Tree graphs inside FSM graphs for a hybrid approach in Uncharted games. But behaviour trees are out of scope for this feature request I think. FSM has a much wider application than just AI. And they are two different concepts in general.

Absolutely, though I think I would like to see that GDC talk to gain some insight nonetheless. Thanks for the tidbit.

[tarragonfly]

I also think that its more plausible for state and transitions to interact with functions and macros than they would with an event graph primarily on the basis that the interaction with Godot function overrides and callbacks are entirely abstracted away from the user in a StateGraph to guarantee the deterministic nature of the flow into and out of a state.

For sure, sounds good.

Absolutely, though I think I would like to see that GDC talk to gain some insight nonetheless. Thanks for the tidbit.

Here's the talk: https://youtu.be/G8W7EQKBgcg?t=500 Although, they might not have used actual graphs but conceptually had FSM on the top level determine behaviours for Behaviour Trees. Node Canvas is a tool for Unity that does this with graphs, where you can nest behavior trees inside FSM.

[eobet]

There are two different FSM officially in Unreal, yet also tonnes of branching "dialogue/quest" plug-ins in the market place which all do something very similar to FSM. And in my (Unreal) game I wanted again a similar functionality to drive my menus.

Wouldn't it be a USP for Orchestrator to have such a general FSM implementation that it can cover all of these cases? For example, I can't speak for dialog/quest implementations, but to have it work in a menu system the way I want, I'd need a transition node which has more than one exit point (ie one for each menu option in the current menu) so I can keep things tight and organized (having one transition node for each menu option in each menu will quickly become too large and unwieldly).