Decouple State Machine logic from Animation logic

Jay2645 commented 5 years ago

Godot version: Commit ffcb5cd

OS/device including version: Any

Issue description:

I'd like to take a look at opening a PR that decouples the State Machine code from the Animation code, but before I went ahead and did so, I wanted to make sure that it's something that might get looked at for inclusion and see what the possible options are.

Why?

There's a lot of different use cases for having an FSM as part of the editor. It could be used as a baseline for character movement, ensuring that characters can't jump when they're already in the air and can't sprint while crouching, if a game calls for it. It can also be used to implement combos in a fighting game, for "old-school" button-based cheat codes, for managing achievements, for RPG quests, etc.

On top of that, it would still be used inside the animation engine to drive animation transitions and stuff -- all this would do is decouple it from that, so that players could easily modify state machines inside the editor. FSMs can be done in GDScript or GDNative already, but given we have most of an implementation already inside the engine, it makes sense to expose it, preventing users from having to roll their own (plus they benefit from having the speed of native engine code).

Current state

As it stands now, the state machine logic is contained in "animation_node_state_machine.h" and consists of 3 classes:

AnimationNodeStateMachineTransition, extending from Resource.
AnimationNodeStateMachinePlayback, also extending from Resource.
AnimationNodeStateMachine, which extends from AnimationRootNode.

There's also the editor tool AnimationNodeStateMachineEditor, which extends from AnimationTreeNodeEditorPlugin.

Changes

The first 2 would be pretty simple to keep without breaking any compatibility -- just create new StateMachineTransition and StateMachinePlayback classes with all the current logic, then have AnimationNodeStateMachineTransition and AnimationNodeStateMachinePlayback inherit from them.

The issue is in the AnimationNodeStateMachine itself. If we tried the same approach of just naively making a StateMachine class, it would need to inherit from AnimationRootNode to avoid potentially breaking compatibility, which isn't very intuitive. Instead, AnimationNodeStateMachine could potentially be changed to function as a wrapper for a StateMachine class. Other suggestions are welcome.

Another sticky situation is AnimationNodeStateMachineEditor. Right now, it provides a way to have users drop down State Machine nodes, link them, and then edit them. It would be nice to keep an editor for state machines, so it could probably simply be named to StateMachineEditor. However, refactoring it like that just to keep the editing code would still make it inherit from AnimationTreeNodeEditorPlugin, which would again imply that it's still part of the animation system. You could simply duplicate any code required for editing nodes and such and have it inherit from a new class, StateMachineEditorPlugin, but code duplication is Bad™. I haven't taken a close look at the editor side of things, however, so it could be that we can get by with minimal to no code duplication.

On a related note, right now the animation state machine simply provides a way to transition between animation states. This makes sense -- each node represents an animation in some form (whether that be a BlendSpace, another state machine, or what-have-you), and when you switch states you transition between them. The issue comes when you're using a FSM for something that isn't related to animation -- what do you use as the "nodes" in the graph? If a user wants to use a FSM for character movement, all they care about is what states are valid for the character to transition into -- which could be solved by looking at the name of the node. Animations have some kind of animation data associated with each node. Meanwhile, fighting games might have various combos that change moves based on the player's previous button presses.

A potential solution would be to create a new State class. State would have a name as well as signals that get broadcast when the state becomes active or inactive. These states would be selected as nodes in the StateMachineEditor class, with possible transitions defined between them. Since the concept of time isn't necessarily a thing when designing transitions between character states, I'm happy with just leaving transitions as data while giving users a way to query which state transitions are valid and manually transitioning between them.

This would also give a new purpose to the AnimationNodeStateMachineEditor, since it would accept a source StateMachine and then map each State to an AnimationNode. The AnimationNodeStateMachine wrapper would play the AnimationNode mapped to the State and automatically transition between them, as it does now.

Summary

Having a FSM that's decoupled from the animation system would let users create their own state machines inside the editor that they could use to power their character movement code, input system, achievement system, quest system, etc. These state machines would also work in the animation system, so a smart developer could use the FSM that determines character movement to also determine character animation.

However, there are a few problems:

Our StateMachine would have to remain a valid node in the animation player, so it would have to inherit from AnmiationRootNode. A couple solutions for this would be either changing AnimationNodeStateMachine to function as a wrapper to the StateMachine or using multiple inheritance (which I'm not sure is okay in Godot -- I'm fairly new to the engine, but I don't see multiple inheritance used anywhere).
The state machine editor would have to be decoupled from the animation plugin, too. I haven't looked at this too hard, so I'm not sure exactly how much things would need to change. Concerns involve possible code duplication as well as ensuring that the state machine editor still appears as an option when an AnimationTree is selected in the editor.
The "type" of node allowed in the State Machine would have to be specified somewhere. Right now, transitions between animations make sense, as does transitioning to something like a BlendTree. But how would transitioning to, say, a string work? A possible solution for this would be 2 separate editors -- a "normal" state machine editor which has a State class which users could subclass with their own logic (potentially), as well as a separate editor which allows users to pair each State in the state machine with an AnimationNode, such as a BlendSpace.
This is potentially a step down a slippery slope, as expanding upon the state machine system would lead to requests like hierarchical FSMs. As it is, this is expanding the "simple" state machine system already in Godot slightly just by the addition of a State class. While I think it's a potential step forward, I can also see how it could potentially lead to bloat -- this would turn a single AnimationNode into a mapping between a State and an AnimationNode, and allows for gameplay logic inside of the State class. The question at hand is whether enough games can find a use for a FSM for it to be warranted as a core engine feature. I'd say that FSMs are flexible enough that pretty much any game can find a use for them, but I've heard @reduz wanted to limit the system to something simple that's only used for animation.

Any changes would likely have to wait for 4.0. I know that there's been some discussion inside #19773 (which this system could potentially address), and there's also an active pull request expanding the animation state machines already (#24402).

Should we keep FSMs limited to the animation system and have users roll their own if they need them, or should we make them more generic?

razcore-rad commented 5 years ago

Why would StateMachineEditor have to inherit from AnimationTreeNodeEditorPlugin, couldn't AnimationTreeNodeEditorPlugin just use StateMachineEditor as a component? Sorry, I just skimmed through fast, I haven't read all other potential problems.

I think it's a good idea.

Jay2645 commented 5 years ago

@razcore-art As it stands right now, the editor side has AnimationNodeStateMachineEditor (allows editing of "State Machine" animation nodes) inheriting AnimationTreeNodeEditorPlugin (allows editing of all animation nodes).

I was suggesting that a naive approach would be to simply refactor AnimationNodeStateMachineEditor into a StateMachineEditor class, but that there might be code in AnimationTreeNodeEditorPlugin providing editing functionality that may need to be duplicated (disclaimer: I haven't taken a close look at the code in question).

In the end, though, it could use StateMachineEditor as a component if we decide not to make a dedicated State class, or it could have users input a "source" StateMachine and then map the nodes to animation files if we do wind up having a dedicated State class.

groud commented 5 years ago

Mostly duplicate of #8847.

The main argument against it is that there are plenty of ways to implement a Finite State Machine, so we do not want to implement that as built-in in Godot. And it is apparently the case for all AI features (such as behavior trees for example).

groud commented 5 years ago

Also, @reduz said once he did not wanted to complexify the StateMachine system, and keep it for animation. So such change is unlikely to happen.

jkb0o commented 5 years ago

I am super interested in this. I use a lot of Spine and for now, I'm badly missing something for managing states. Godot's AnimationTree looks promising, but I didn't find an easy way to integrate it with Spine runtime (generating native Godot animations from Spine isn't an option).

@Jay2645 I will be glad to contribute into this or at least help with testing integrations form StateMachine client side.

slapin commented 5 years ago

Well, I would be interested in some extension in AnimationStateMachine if it would have single special state which could send signal. Currently this can be implemented with function tracks, but that is quite slow (verbose) process to do so sending signal directly from StateMachine about getting to some state would solve all the problems. Otherwise code which works with state maching gets VERY hairy if state machine is complex enough.

If you want GUI-enabled FSM for your own, there is node editor in Godot where you can implement any node-based abstraction. From there you can generate json or Dictionary object and use that in your code for state management if you consider this effective.

As for AI tools in general the @reduz opinion is quite shallow. Yes, there are many ways to implement AI but there is quite limited set of AI needs for engine, mainly spatial hashing and awareness, which currently not possible to fullfill without some core developer help. Additionally, there is no multiple ways to properly (effectively) implement behavior trees in Godot currently (no way to implement that) unless your game is very slow pace. Do not even try this "pattern" with Godot, you will be sorry, just use actually provided tools (scripts and dictionaries are all you can have for AIs). You can implement kind of HSM with nodes and that is actually working pattern for small scale AI and it works well enough. If you're just going for visual AI editing as in "no coding needed" you're quite out of luck here and the actual concept of this is a bit ill, because you just replace one language with another and call it "no coding". Also most things are actually more work to do visually. Normal AI systems are mostly working with code, where you implement all the AI blocks you need. You use the tree to combine them in way for fast tweaking. Godot does not have any concept to produce this in efficient manner, as core for that is needed to be implemented in C++ and most blocks are written in C++ and you can add high-level blocks in scripting language on top of that. So the only current plausible scalable AI concept with Godot is HSM on nodes. This scales to 10-20 characters, but latter you will have hard time optimizing it. But if you instead of using nodes directly put all the construct into Dictionary at startup and use that instead you save about 15% CPU. Proper blackboard implementation using dictionaries for each parameter and each object as key works very effective, using that you can scale to about 40 agents on i7 each running AnimationTree too. If you use less AI ticks for distant/invisible objects or more simple AI navigation methods for them you can have even more if you want. Not tested that on low end hardware though.

ShawnMcCool commented 5 years ago

I always appreciate the argument against creating a general purpose tool of high complexity that only generates edge-cases. I'm entirely happy with sticking with code.

HOWEVER

It would be lovely to have a visual state machine for simple use-cases.

slapin commented 5 years ago

I think VisualScript extension might be implemented for this task. Also there is a lot of implementations based on node tree. The problem with things like this are they either suboptimal or will not work for particular purpose. Because state machine is more coding pattern than something you implement visually. GDScript has "match" syntax sugar which can be used for state machine scripts to look nicer. If you want pure visual state machine you better come up with PoC design with GUI in script so to understand what you consider proper implementation, this way it will be understood better. In general GUIs like this take only a few hours to implement using grapheditor. Generally I think every more or less complex game have a few of these GUIs as dev tools.

On Fri, Mar 29, 2019 at 4:37 PM Shawn McCool notifications@github.com wrote:

I always appreciate the argument against creating a general purpose tool of high complexity that only generates edge-cases. I'm entirely happy with sticking with code.

HOWEVER

It would be lovely to have a visual state machine for simple use-cases.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/godotengine/godot/issues/25021#issuecomment-477999995, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAX03xAeXlSUXHucMZ9JqaBRyy1VZ2Dks5vbhcSgaJpZM4aCTyS .

Xrayez commented 5 years ago

Reasonable or not, people will start to mess with this and do hacks and workarounds to turn an "Animation State Machine" to a "State Machine" via scripting. So might as well provide (perhaps separate) implementation for a simple state machine to prevent users from exploiting existing animation system and make this clear in documentation.

madmiraal commented 4 years ago

Feature and improvement proposals for the Godot Engine are now being discussed and reviewed in a dedicated Godot Improvement Proposals (GIP) (godotengine/godot-proposals) issue tracker. The GIP tracker has a detailed issue template designed so that proposals include all the relevant information to start a productive discussion and help the community assess the validity of the proposal for the engine.

The main (godotengine/godot) tracker is now solely dedicated to bug reports and Pull Requests, enabling contributors to have a better focus on bug fixing work. Therefore, we are now closing all older feature proposals on the main issue tracker.

If you are interested in this feature proposal, please open a new proposal on the GIP tracker following the given issue template (after checking that it doesn't exist already). Be sure to reference this closed issue if it includes any relevant discussion (which you are also encouraged to summarize in the new proposal). Thanks in advance!

Xrayez commented 3 years ago

For those interested, I've created a discussion about implementing a general-purpose FSM in Goost, see goostengine/goost#96. The main idea is that FSM functionality could be implemented as a new scripting language akin to VisualScript, but more specific.

I have previously resurrected so called multi-script PR: goostengine/goost#92, and I think a similar approach could be taken.

godotengine / godot