I'm making a non-deterministic finite state machine

image
Salutations fellow enthusiasts (◕‿◕)つ

This is the scenario, I'm creating a video game (Side scrolling action platformer) where the player character may be in different states depending on conditions. The special sauce is that the character may be in multiple states at once, and some states require the character to be in other states. (e.g. its logical that if the character be in the state of walking, the character should be in the state of moving as well, rather than one or the other)

The initial idea was simple, I considered the states as tags, boolean values either true or false. They were triggered to be such values based on conditions. Although, the system became more complex as I went on... 'AND's , 'OR's, and 'NOT's became involved along with cyclic dependencies.

The problem is that I require an algorithm to determine, when triggering a target state | tag, what the dependencies (tags that are dependent on / depended by target tag) are and what value they should be.

Another problem could be drawing up a dependency graph (see image as example). It's enough for a human to intelligently interpret, though a systematic way to validate that there are no 'impossible' cases would be beneficial (e.g. requiring a tag to be both true and false).

Doing research, trying to find a pre-made solution; I looked into Finite State Machines (FSM), though it was not the right fit for my use case because it may only be in one state at a time. Quite interestingly diving into the topic of Automata Theory, I learned that a FSM is often assumed to be a Deterministic Finite Automaton (DFA), and my case I want a Non-deterministic Finite Automaton (NFA) because it may be in multiple states at once. That doesn't solve my problem, just indicates that I have an uncommon case. (See sources: FSM - Stack Overflow, FSM - Wikipedia, NFA - Wikipedia)

Dependency resolution being beyond the scope of an NFA, I looked into Package Managers since they solve a similar problem (if not the same). According to a convenient article, what I'm looking for is the features of a dependency manager.
Going further in depth with Dependency managers, in comparison with my use case it gets quite complicated, but it helps by providing some high level instructions. (see sources: Write package manager - Medium, Dependency Manager - Devopedia)

With all that said, I'm working on a solution, and plan to release it so those interested may look into it, use it, give feedback, etc.

I'm using the Godot game engine, and native language GDScript which is similar to Python and relatively easy to understand.

I'll likely post an update to this thread here (MGSA), and on the Gamejolt Forums once I make more progress.

This idea / undertaking is part of my current personal project 3lg00gtach which is open source if you want to take a look

Sources
FSM - Stack Overflow
FSM - Wikipedia
NFA - Wikipedia
Package Manager - Wikipedia
Write package manager - Medium
Dependency Manager - Devopedia

Comments

  • @megaguy32 Very interesting. Thanks for sharing.

    Here is an article relating to FSM that I found useful and informative on the subject as well. He describes how he has been iterating his solution over the years and why, with some real world examples you might find interesting too.

    Cheers,
    K

    Thanked by 2ashashza megaguy32
  • @megaguy32 interesting project. As I spend more time in gamedev, I realise more and more how core the state machine pattern is!

    @konman That's a great link, lots of learning condensed. The issue I've had with the last approach mentioned (having each state as it's own class) is that it means that states aren't easily able to modify the fields of the object which is changing state. For example If a Character behaviour has a JumpState class... then JumpState can't easily modity the protected/private fields of Character.

    In case it helps anyone else, I've been using a modified version of https://github.com/thefuntastic/Unity3d-Finite-State-Machine which is super-easy to setup, quite smart about auto-registering methods and allows states to easily modify the behaviour.

    Obviously there is no one-size-fits-all solution here and some folks might have very specific needs but it's a very powerful too to have in ones arsenal.
    Thanked by 2megaguy32 konman
  • Hey there, thanks for the replies.

    I'm making progress slowly, Its been a grind.

    Here's a glimps into the development:
    I've used scriptable objects (a.k.a Resources in Godot) to define the tags | states, and like a 2 way linked list I have each tag have a list that contains their immediate dependers and dependees.

    I'm making an algorithm to traverse these dependers and dependees to determine an acyclic, transitive dependency tree for each tag. That makes the method for determining the required values of tags significantly less complicated.

    As for determining the required values of tags and their dependencies. I've come up with this logic:

    image

    (It's really messy, but yeah. all I have to work with here is brain farts and blind hope)
    The git repo has not been updated yet because I haven't really gotten actual code to work properly yet, just a bunch of shots in the dark so far.

    Let's hope I'm getting somewhere with this (;^▽^)
    Screenshot_20200502_174355.png
    732 x 187 - 25K
  • Doing this project I found a disrupting bug in Godot
    see github issue
  • edited
    Hi

    Not sure how useful this will be for you at this point, but might be of interest :)

    An approach that has worked well for me is to make use of parallel state machines.

    Each "behaviour" of the character is its own state machine.

    So for example, you may have the "Movement" state machine, with states for Idle, Walking, Sprinting.

    Then a separate state machine for weapon handling, with states Inactive, Aim, Fire.

    All these separate state machines form part of a system, where the state machines are in a certain priority. Then you make use of "resources" to model dependencies.

    So basically, lets say you have two resources called "Lower Body" and "Upper Body". Then you mark all your weapon handling states (except for Inactive), as requiring the "Upper Body" resource.

    And for your "Movement" state machine, you mark all its states as requiring the "Lower Body" resource.

    This effectively then says that you can run any movement state, at the same time as any weapon handling state.

    But let's say you want to make it so that you can't use your weapons at all while sprinting, then you set your "Sprinting" state to also use both the "LowerBody" and "UpperBody" resource.

    Assuming you've set your movement state machine to be higher priority than your weapon state machine, then when you change from your "Walking" state to your "Sprinting" state, the system checks that you now want to use the "Upper Body" resource. It then tells any lower priority state that is currently using that resource, to "release" it, by going to a state that doesn't use the resource. So then if the weapon handling state machine was in its "Aim" state (i.e. weapon has been drawn), which was using the "Upper Body" resource, it will then go to its "Inactive" state (which doesn't use any resource).

    Conversely, if you were already sprinting, and then want to draw your weapon, it will be blocked because it doesn't allow the weapon state to acquire the resource that is already in use by the higher priority state machine's "sprinting" state.

    There are two other nice benefits of this model:
    - "behaviours" become very modular, because each one is separate. So you can have all your movement logic in one, weapon handling logic in another etc. And it becomes very easy to add new behaviours, without having to touch all the other ones. All you have to figure out is the correct resource usage and priorities
    - each state should be coded to have a "begin" and "end", which is used to initiate each state, and clean up after each state. So for example, with the weapon handling's "Aim" state, in its Begin function, you may trigger the "draw weapon" animation, and in its End function, trigger the "holster weapon" animation. That means that in our scenario above, where when you start sprinting, it forces your "Aim" state to go to the "Inactive" state to release the "Upper Body" resource, its End function will automatically be called, and the character will therefore automatically play their holster weapon animation.
  • Just had a major update regarding the tag based state system.
    Don't want to be redundant, so follow the details in the main project thread, 3lg00gtach
Sign In or Register to comment.