Godot: Finite state machines

[groud]

Hello,

I was looking for a Finite State Machine implementation for my game, but found only limited implementations working as plugins.
As FSM are a commonly used tool to define objects behavious in video games, I was wondering why not implement it as a built-in feature for godot.

Thus, I open this issue to discuss multiple thing:

• Should it be implemented as a built-in function ?
• If the answer is yes, how ?

Here is my idea of a possible implementation:

• A FSM parent node is responsible for the state machine handling, while its children are the states.
• Hierachical FSM can be implemented by using a FSM a a child of another FSM.
• The initial state is the first child node (or predefined maybe).
• A transition between two nodes can be added using a function of the FSM node:
  add_transition(NodePath from, NodePath to, FuncRef[] conditions, FuncRef[] inverted_conditions, int priority=0)
  When the current state is the "from" node (or one of its children), the transition can be trigerred if all functions called in conditions return true and all functions called in inverted_conditions return false. The current state node is then set to to. Transitions with higher priorities are treated first.
• An "update" function in the FSM node triggers transitions util none can be triggered (up to a fixed limit of transitions, so that it does not goes in circles until infinity).
• State nodes can implement three functions that are automatically called when the FSM update is triggered:
  
  
  
  • on_state_enter is trigerred when the node becomes the current state
  
  
  • on_state_exit is trigerred when the node is no more the current state
  
  
  • on_state_update is triggered once per update FSM call, once we have found the new state.
  
  

This implementation could be completed with a specific editor view, with something like that:

What do you think ?

[n-pigeon]

Unity supports state machine (although only for animations).
I think generic state machine would be very useful tool in Godot:

• Basic AI
• Animations States
• Characters States
• Heavy UI games

and probably more.

[eon-s]

I don't like node-based implementations, also godot offer many ways to do it (code, node, signal), and 3 could let make complex designs to tweak with visual scripts for mechanics designers.

For generic FSM could be better to have a framework, like Escoria.

[bojidar-bg]

Strange that nobody yet mentioned the FSM plugin by @kubecz3k ... https://godotengine.org/asset-library/asset/5 (though it is slightly WIP it seems...)

[groud]

Well, I do not see why the three solution should be considered separately. I mean, scripts are basically an extend to a base node class. Creating a script attached to a node is like creating a class inheriting from its parent class node. When some features are used by a lot of people (FSM are), I think the considered features could be implemented as a real node.

Signals are, IMO, an unadequate design pattern (they correspond to the _Observer_ design pattern) for implementing FSMs. That is why I suggest an other implementation for them.

I do not get why you do not like Node-based implementations. I mean, even the GUI system is based on nodes, so why not provide the developper with node-based AI features ?

@bojidar-bg I saw the plugin and tested it, but it lacks some flexibility (no functions are called when states changes, but the global idea is what i propose). It is also still a plugin implemented in gdscript, the question was also "should it be implemented as a builtin-features ?" (I believe so) :)

[ghost]

As far as I know, something like this is already planned for 3.1 under the name transition graph.

[kubecz3k]

@groud what do you mean that no function is called when the state changes? You can connect a signal "stateChanged" to be notified about state changes. I'm using this plugin a lot in my projects, version on the asset store is very slightly outdated (cosmetic stuff).I think I will get some windows machine and try to test it on it since 'tool editor' part is not working on windows as far as I know. If I succeed I think I will record some tutorial on how to use it since it seems there might be need for that.

[groud]

@tagcup it seems that you are right. I hope this will be usable as a generic state machine too.
@kubecz3k well if you need to connect all children to the fsm node to detect if they are the current state, this is a little bit heavy no ? But I may miss something in how to use your plugin... ^^"

[kubecz3k]

@groud Yeah you totally missed the point how to use the plugin (I guess it's my fault in the end). Will create some video tutorial and put it on the net. You can use signal to be notified about state change, but you can also just use fsm.getStateID() method. Check fsm.gd script to see how api looks like: https://github.com/kubecz3k/FiniteStateMachine/blob/master/addons/net.kivano.fsm/content/fsm.gd
Also I have managed today to test the plugin on Windows 10 and it seems it's working fine in the end...

[groud]

@kubecz3k ok, I had a look to the code, I understand it a little bit better I believe. The enter(), update() and exit() functions, called for the children node do what I was looking for.
Anyway, does it features hierachical FSM ? I cannot see how they could be implemented in your code.
Aside from that, as your plugin does not provide a structure to store the transitions, I believe creating a visualization tool will be difficult.

[kubecz3k]

@groud no it does not provide stucture do store transforms. I didn't had an y good idea for this part at the time, there is just an option to hardcode transforms inside states (so you can implement computeNextState() from https://github.com/kubecz3k/FiniteStateMachine/blob/master/addons/net.kivano.fsm/content/StateTemplate.gd ) alternatively you can not use this option and just steer manually with fsm.setStateID(). I also think visual tool for FSM would be the best. Do you have any structure for storing transforms in mind? Some kind of function references 2 states map? That part sounds like something I could benefit from, if you have any ideas for this it would be great if you could open an issue on plugin github page (don't want to spam to much this discussion with discussion related to my plugin)
Also yes there is no support for hierarhical fsm since I'm not using those in my current games - I think the most close what you can have in this plugin is to have multiple FSMs and manually steer them from up to down (more important fsms know about atomic ones but not other way), but haven't tried this.
Also as I said the plugin is little outdated right now, I think I will update it tomorrow, changes are cosmetic in terms of LOC but handy sometimes (like passing custom arguments to update/init or having dictionary with states names so you dont need to use strings at all (more error prone)).

[groud]

Ok I see :)
Well, for now it was thinking in using a FuncRef to store transitions, instead of using hardcoded ones. I will try to code something in the next few days and see what i can came up with.

[kubecz3k]

@groud I have booked couple hours tomorrow to create video and clean/upload changes. I think I might give a shot for this transition structure as well since it's something that this plugin (and my projects :P) could benefit for sure.

[kubecz3k]

I know it has been couple of days and there still is no tutorials/new functions... but I think you will forgive me :)

(still wip but almost done)

[eon-s]

@kubecz3k what do you think about a structure to be used with Visual Script? I think that with custom nodes may be possible to do something.
This is one of the few things where I think VS may be useful :smile:

[n-pigeon]

@kubecz3k
Holly crap!

[kubecz3k]

@eon-s well I have prototyped fsm on visual script when I was giving initial feedback on visual script :) In short I don't have any strong opinion on it, I kind of like it even without any additional nodes/structures. But for now I think VS is not as readable for FSM purpose as much as that kind of simple graph that was designed only for FSM, to tell truth when I started implementing this on Monday I was using initially GraphNodes from VisualShaders but it was a little unreadable and I was not happy with this solution. But for sure I will experiment with VS a lot more in 3.0
ps. if you would have build with VS you could double click on state/transition and implement it in VS (at least I think it should work this way)

[groud]

Nice, awesome job ! 😄
I have been thinking a few days about how to implement those FSMs, and came up with a more or less similar design. The only difference I can find is that I though it was more easy to understand if you to put a transition as a child of the source node (instead of a direct child of the FSM node).

I am currently working on a built-in (C++) implementation of such module, let me know if you update your code on github, I am very interested by how you implemented the visualization part ! :)

[kubecz3k]

@groud in this implementation transition can have multiple source states (but only one target one). I'm finishing it right now, will test today if there will be no problems, maybe I will be able to record vid today.

[kubecz3k]

also curious why you want c++ implementation? I mean, runtime is really minimal, maybe couple dozens of gdscript loc running every update, linearly without any bigger loop or any other heavy stuff, and people will implement more heavy stuff (like actual game logic) in gdscript anyway so...

[groud]

Well it is not a matter of complexity or whatever... It is just because I believe this should be included into the godot engine itself (because it is a feature used by a lot of people), and not as a plugin. Thus it would need to be coded in C++. :)

[n-pigeon]

@groud
True. Also, next step would be Behavior Trees :) and then we will be on par with Unity and Unreal if AI/Logic systems are concerned :)

[kubecz3k]

@n-pigeon actually I believe all good fsm implementations for unity are a plugins :P

[kubecz3k]

I believe if we will have fsm functionality it should be extension for our visual scripting system (basically couple new VS nodes). There is no need to introduce two competing systems into core.

[kubecz3k]

I also think @reduz was already thinking about that kind extension, but we need to get people to start use VS in the first place and get real life feedback.

[n-pigeon]

@kubecz3k
I agree with you. FSM and BT logically belongs to VS. Probably new Controls will be needed for them but it would be the best if they would act as one system. It would be also easier to maintain :)

[kubecz3k]

In any case as I promised I made a quick vid on how to use the plugin: https://youtu.be/n4lJXjLAHoI

[groud]

I had a look to how visual scripting works and is implemented, but I hardly understand how we could combine them with either Behaviour Trees or State Machines. In terms either or visualization or implementation I find that it would be a little bit hacky to combine them. Also, this may overload the visual script editor.

The solutions I can imagine are the following:

• We use a scene node-based system, as with @kubecz3k 's plugin, with a special vizualization tool when a FSM node is selected. That would be a little bit similar to the animation system.
• We create two new types of scripts (like VS or GDScript), one for FSMs and one for behaviour tree, then implements a set of corresponding nodes. Both could have a different editor so that the VS editor stays simple and dedicated to its own "model". This would make sense IMO.

WDYT ?

[kubecz3k]

@groud I'm doing an overview of the old issues from this time period. Do you have maybe an new ideas on the topic? Do you still think this one should be build into the core?

[groud]

Probably, I think animation state machines are on the roadmap anyway. Maybe there's another issue about that and this one can probably be closed though.

[kubecz3k]

Yeah I feel like animation state machines will not have such much common with those

[ans3pl]

Hey guys!
I have to make any advanced C++ project for my lecturer and I thought that I could make godot module. I considered FSM.

[Calinou]

Closing in favor of #25021, as we have built-in state machines for animation since Godot 3.1.