FSM2.0 details and implementation

It's high time to get to the details of my personal view and implementation of this FSM2.0. First let's take a look at the progress. I've spent quite a lot of time iterating and trying different ideas for my personal take on FSM, perhaps a bit too much time. Without further delay, check this out:

It can get a bit dizzy I know, cause there's no ground/reference point yet. There's also no collision yet, but there are a few effects happening, but I'll be explaining those in later posts because they demand a separate look. With that said though, let's dig a bit into the turn-base system first and FSM second.

Turn-based loop

The idea is extremely simple, but it needs a few lines of explanation as at first glance it might not be intuitive how to set up a turn based system within a real-time engine such as Godot. Lets take a look at a few lines of code:

func _ready():
    while true:
        for a in $Actors.get_children():
            a.state = a.states[g.ActorState.THINKING]
            a.state.enter(a)
            if a.type == g.Actor.AI: a.perform()
            yield(a, "turn_ended")

A note of caution first. This code is (for the time being) presented inside of the _ready function because it's for demonstration & debug purposes, the game being at a very early state of development. The _ready function should really be used for initialization purposes only as it will make stuff easier later when you want to implement a menu, pause and resume, game restart and so on.

Back to the code. If you're not familiar with coroutines, the above code looks a bit strange, it looks like a never ending loop that would consume all the available resources and eventually stall the computer, but as you could see in the GIF above, the game runs just fine. So what's going on here? There is indeed an infinite loop here, but the magic part inside this loop is the line: yield(a, "turn_ended"). What this code tells Godot is to suspend the execution of the function until the moment it receives the "turn_ended" signal emitted by the object a (the current actor). If it's the player's turn for example, by interaction with the mouse in the appropriate fashion, the player can trigger a chain of events that will end up with a "turn_ended" signal being emitted some time in the future. At which point the while loop continues to the next $Actor.That's the magic behind the turn based system inside Godot. And as you can see it's extremely easy to implement and understand. Check the Godot documentation on coroutines for an official explanation.

"My" FSM implementation

If you read the FSM explanation from Game Programming Patterns (free) ebook, you'll know it's something about delegating actions to functions within the current state. And the state knows how to change variables/parameters on the object it manages (in our case Actor). This quickly becomes unmanageable though because each state has no knowledge of anything else other than what it can do so you end up reimplementing the same thing multiple times, state transition gets messy, there's all sorts of problems. That's why OOP programmers have come up with the HFSM solution, a more sophisticated implementation of FSM which allows for multiple states to be ran within a "mega" state., making stuff like ducking & shooting or jumping & shooting less of a hassle.

In my implementation I've been influenced by functional programming and I believe it's a very simple FSM idea that deviates form the traditional delegate-to-state implementation which allows for easy composition or chaining of states which bypasses the above problems and doesn't require the more sophisticated HFSM implementation. Let's check it out:

# State.gd (base class)
enum Type {
    INVALID,
    THINKING,
    INACTIVE,
    MOVING
}
var type = INVALID
func enter(a):
    pass
func exit(a):
    pass
func execute(a, msg={}):
    return {"state": self, "msg": msg}
func transition(a, s):
    if type == s.type or type == INACTIVE:
        return false
    a.state.exit(a) # out with the old
    a.state = s  # in with the new
    a.state.enter(a)  # finally enter the new state
    return true

The whole idea is extremely simple. Three E's and one T: enter, exit, execute, transition. That's it. The actual computation gets carried out inside of execute as I'm sure you figured out. This function returns a Dictionary with the (potentially) new state and a message to be passed on. The message is itself another Dictionary.

The transition function takes care of the automation of entering/exiting states and returns true if the transition was successful otherwise false. As we'll see, this information is used inside of a function in the Actor itself. So in my implementation, the states themselves don't actually apply any modifications to the Actor (other than setting the new state in transition) but rather return a new state to transition to while passing a message. This is how they're used inside of Actor:

# Actor.gd (AI version)
var states = {
    THINKING: preload("States/ThinkingAI.gd").new(),
    INACTIVE: preload("States/Inactive.gd").new(),
    MOVING: preload("States/Moving.gd").new()
}
var state = states[THINKING]
func perform(msg={}):
    var info = state.execute(self, msg)
    var wait = act(info.msg)
    if wait.obj: yield(wait.obj, wait.signal)
    var transitioned = state.transition(self, info.state)
    if transitioned:
        perform(info.msg)
func act(msg={}):
    var wait = {"obj": null, "signal": ""}
    match state.type:
        THINKING:
            # ... do Player/AI THINKING stuff
        MOVING:
            # ... do MOVING stuff
            wait.obj = self
            wait.signal = "moved"
        INACTIVE:
            # in this turn-based setup, the chain of state transitions
            # always end up with INACTIVE which emits "turn_ended"
            emit_signal("turn_ended")
    return wait

The idea is pretty simple, perform (because they're Actors, get it?) gets triggered when certain events occur such as the beginning of the AI turn or when the correct conditions for input from Player get met (correct key press or button press etc.). Once that happens, the execute function gets called and it returns (potentially) a new state and a message to be passed to the new state and act (because they're Actors, get it? :P). Because this is a turn-based implementation, we potentially wait for a signal before attempting to transition to the new state. Say if we trigger the moving animation, we perhaps want to first wait for the animation to complete before going forward. If the transition is successful (which means the beginning of the new state) then perform gets called recursively again. This is my solution to HFSM. With this implementation I believe you can easily chain states together until the required actions get performed so it's easy to implement duck & shoot as well as jump & shoot for example, without the need of complicating further.

Concluding remarks

You can find the actual implementation with the working example from the introduction GIF at the project GitLab repository. It has hopefully enough comments to explain my thought process and why I believe this is a good design approach, at least for small projects where you don't need super optimizations, because what's presented here is definitely not a design geared for optimization.

Until next time, when we're going to look at how metaballs can be made in Godot with the help of viewports and shaders, while adding a bit of physics to them. Here's a sneak-peek of how they look like clumped together: