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
tag flowchart - 2020-04-22.png
1920 x 1080 - 266K

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
Sign In or Register to comment.