FSM implementation

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By hexdump
:warning: Old Version Published before Godot 3 was released.

Hi,

I ussually use FSM’s in my games for almost everything. I have seen some implmentations of FSM but they are C++. As an example: → https://github.com/Wildregar/Godot-State-Machine/tree/master/fsm

Would not it make more sense to have this FSM implementation done in GDScript? I don’t know how slow it is for C++ to call GDScripts methos and viceversa, but it seems a fairly ammount of work to communicate between this 2 worlds.

Is anyone using FSM’s in godot?

Thanks

:bust_in_silhouette: Reply From: batmanasb

Actually, C++ modules are used to speed up parts of a project that are too slow in GDScript, and can easily and efficiently be bound to GDScript. I’m not too experienced with this, but if you look at the Docs, it explains how modules can be made and why they are useful. http://docs.godotengine.org/en/latest/reference/custom_modules_in_c++.html

One of the problems when you start making modules is multiplatform… You can get your hand dirty for sometime if you deal with different platforms. You are safe at GDScript side, this is why the best solution for me would be improve GDScript peformance.

Cheers.

hexdump | 2016-06-14 10:19

:bust_in_silhouette: Reply From: Hammer Bro.

I’ve got an FSM at the heart of a platformer engine (see it in action here), and it’s been a breeze to use. It’s entirely in GDScript, and not a lot of script at that. There’s no need to make a specific C++ implementation, and in fact doing so would prove too restrictive when you wanted to make minor customizations.

At its heard is the State superclass, State.gd. Note that it’s slightly specialized for my own purposes:

# Superclass (faux interface) common to all finite state machine / pushdown automata.

var player = null

# Return the unique string name of the state. Must be overridden.
func get_name():
    assert(false)

# Handle any transitions into this state. Subclasses should first chain to this method.
func enter(player):
    self.player = player
    _animate()

# Exit the current state, enter a new one.
func set_state(state):
    player.state.exit()
    player.state = state
    state.enter(player)

# Transition to a new animation; by default, one matching the name of the State (if it exists).
# Can be overridden without chaining.
func _animate():
    var name = get_name()
    if player.animation_player.has_animation(name):
            player.animation_player.play(name)

# Handle input events.
func _input(event):
    pass

# Update physics processing.
func _fixed_process(delta):
    pass

# Handle exit events.
func exit():
    pass

For an object that makes use of this FSM, I’ve got the following bits of code. I won’t explain them here since you’re already familiar with them, but for anyone who’s interested, there’s a fantastic tutorial at http://gameprogrammingpatterns.com/state.html

func _ready():
	# Initialize state.
	state = Starting_State.new()
	state.enter(self)

# The current state gets to intercept input events.
func _input(event):
	# Send the input to the current state if we haven't already handled it.
	var new_state = state._input(event)
	# Switch states but don't forward input, because presumably that event was handled.
	if new_state != null:
		printt("Input", new_state.get_name())
		state.set_state(new_state)

# Let the current state handle the processing logic; also handle the changing of states.
func _fixed_process(delta):
	# Update the current state; handle switching.
	_state_loop("_fixed_process", delta)

# Call the given function with the given arg and iterate if state changes.
func _state_loop(function, arg):
	# Keep a list of old states to prevent cycles.
	var old_states = []
	var new_state = state.call(function, arg)
	while new_state != null:
		var new_state_name = new_state.get_name()
		# Throw an exception if we re-enter a previously visited state this frame.
		assert(old_states.find(new_state_name) == -1)
		old_states.append(new_state_name)
		set_state(new_state)
		# Let our new state run this cycle since our old state ended.
		new_state = state.call(function, arg)

The state loop is a bit nonstandard – I wanted to make sure states would instantaneously advance to a final resting state when multiple conflicting conditions were received, and I wanted to make sure that there weren’t any infinite loops. So far, so good.

Creating new states is dead simple. Just extend my custom State.gd class and override whatever the desired functionality is. For instance, Standing.gd:

extends "res://Player/States/State.gd"

const Backflipping = preload("res://Player/States/Backflipping.gd")
const Ducking = preload("res://Player/States/Ducking.gd")
const Falling = preload("res://Player/States/Falling.gd")
const Jumping = preload("res://Player/States/Jumping.gd")
const Walking = preload("res://Player/States/Walking.gd")

func get_name():
    return "Standing"

func enter(player):
    .enter(player)
    # Reset double-jumps upon landing.
    player.has_extra_jump = player.can_double_jump

func _input(event):
    if player.should_jump(event) and not player.is_attacking():
            player.get_tree().set_input_as_handled()
            # Backflip.
            if Input.is_action_pressed("player_up"):
                    return Backflipping.new()
            # Regular Jump.
            return Jumping.new()

func _fixed_process(delta):
    if player.is_grounded() == false:
            return Falling.new()
    if Input.is_action_pressed("player_duck") or player.is_roof_blocked():
            return Ducking.new()
    if player.get_horizontal_movement() != 0 and not player.is_attacking():
            return Walking.new()

I think I’ve got about 13 states at present, most of which ought to be present in that video. It’s definitely worth the effort to set up and get comfortable with a state machine; complex behaviors are so much more elegant and the separation of code is manageable.

A snapshot of the source code for the project in the video is available here.

Thanks for showing a showcase of FSM in GDS.

hexdump | 2016-08-09 08:51

This is a great example and has helped me a lot in my current project. The tutorial in the link is great too. Thanks!

Rodeo | 2017-02-12 23:38

Do you have an example of the set_state method? I’m trying to implement it in my project but I cannot find success.

Taceor | 2018-04-07 15:25

I’ve updated the answer to include set_state and a link to the entire project’s code for reference.

Hammer Bro. | 2018-04-08 17:01

:bust_in_silhouette: Reply From: Warlaan

The first rule of programming patterns: patterns are a mental construct, not a piece of code.

Hammer Bro. supplied a good example for code that is built following the FSM pattern. Note that it consists purely of game code. A description like “the player can switch between different states: he can be falling, ducking, jumping, walking or backflipping. When he starts backflipping … happens…” could be taken from the game design document and could equally well be a comment in the code.

An implementation of an FSM that doesn’t contain any classes however is like asking someone to paint a Cadillac without painting a car. “Just paint what makes a car a Cadillac and leave out everything that belongs to a car.”

Powerful languages allow to create such a construct (like the FSM you linked written in C++), but imho the use of it is highly questionable. As you said, implementing it in C++ leads to unnecessary calls back and forth between C++ and GDScript since the pattern is merely a way to write gameplay code, not something that belongs in library code.
On the other hand implementing an FSM library in GDScript is a bad idea either since gameplay programming usually to a degree means programming by convention like e.g. Hammer Bro.`s comment on the get_name() method, “must be overridden” - the language is built for gameplay programming and therefore doesn’t have a mechanism to enforce overriding of methods - which imho is a good thing since programming by convention is faster and more flexible as long as you restrict it to short, readable code bases.

So tl,dr: Use C++ for library code and GDScript for gameplay code. Patterns are neither, they are a way to build either.

:bust_in_silhouette: Reply From: Ziflin

We integrated hierarchical state machines into our scripting language and (way) before that we implemented them in C/C++. It is far cleaner to have these as part of the scripting language than trying to implement it cleanly/properly in the scripting language or even C++.

The other nice thing about it being part of the language is that it becomes a standard and everyone can use it and share and understand code.

What do you mean by “our scripting language”? You weren’t talking about GDS, am I right?

Cheers.

hexdump | 2016-08-09 08:51

Correct. I worked at Vicious Cycle for 14 years.

Ziflin | 2016-08-09 14:02