Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

How should I store transition tables for an FSM?

Discussion in 'Scripting' started by Sendatsu_Yoshimitsu, Sep 19, 2017.

  1. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    691
    I'm trying to implement a super-simple finite state machine to run my AI, every individual state (running/attacking/moving/idling etc) is a child of some CharacterState base class:

    Code (csharp):
    1.  
    2. public class CharacterState {
    3.  
    4.     public virtual void Enter(NPCObject myNPCObject)
    5.     {
    6.         //Do something when character enters this state
    7.     }
    8.  
    9.     public virtual void Exit(NPCObject myNPCObject)
    10.     {
    11.         //Do something when character exits this state
    12.     }
    13.  
    14.     public virtual void Execute(NPCObject myNPCObject)
    15.     {
    16.         //Runs every Update while state is active
    17.     }
    18. }
    19.  
    Changing states then becomes a matter of running oldState.Exit, then newState.Enter. Where I'm a little lost is when it comes to actually checking when to transition states. Right now I check for transitions in Execute, like so:

    Code (csharp):
    1.  
    2.     public override void Execute(NPCObject myNPCObject) //Move until you reach your destination, then transition to IdleState
    3.     {
    4.         if (!myNPCObject.myNavMeshAgent.pathPending && myNPCObject.myNavMeshAgent.remainingDistance <= myNPCObject.myNavMeshAgent.stoppingDistance + 0.1f)
    5.         {          
    6.                         myNPCObject.ChangeCharacterState(new IdleState());
    7.         }
    8.     }
    9.  
    This works, and is suitable for prototyping, but it's extremely inflexible and doesn't allow for multiple agents to have different transition rules. One way I could handle this would be to create some base TransitionRule class which has a virtual GetTransition method that runs every frame and checks for transition criteria, but that's quickly going to get clunky, and I'll still have to hardcode which transitions get added to which states for which characters. Is there a cleaner pattern I'm neglecting, or am I vaguely walking in the right direction with what I have?
     
  2. Invertex

    Invertex

    Joined:
    Nov 7, 2013
    Posts:
    1,539
    Why not just use Coroutines so you can cleanly transition from state to state?
     
  3. Sendatsu_Yoshimitsu

    Sendatsu_Yoshimitsu

    Joined:
    May 19, 2014
    Posts:
    691
    You're thinking of running a single coroutine that runs every 0.1s or something, and checks a global list of transitions? I had been assuming that a state table would be more efficient in the long run, since in most cases any given state only needs to check against a subset of its total possible transitions.
     
  4. Invertex

    Invertex

    Joined:
    Nov 7, 2013
    Posts:
    1,539
    With coroutines, you only need them to reference any info that is required to determine what they should be doing or when and how they should transition, you can also yield the processing of one coroutine until a coroutine it launches finishes processing, allowing for further sub-states to easily be added.
     
  5. Baste

    Baste

    Joined:
    Jan 24, 2013
    Posts:
    6,294

    You want to wait with creating abstractions until you have enough examples to create good abstractions from. Making a Transition concept before you have quite a few different enemies will probably end up with a design that's hard to work with and maintain. My main advice is to create a few different enemies the way you're doing it now, and see what abstractions appear naturally.

    That being said, here's my experience with making AI state machines from our last game:
    There's two main ways to design this. Either the states themselves are responsible for knowing where to transition, or there's a state machine that has states and transition rules be separate things.

    The upside to having the machine responsible is that, as you said, you can re-use different states for different machines. The downside with that is that the machine now needs to have state. ie. a bunch of variables you need to take care of.

    I ended up making the states themselved responsible for where to transition, forgoing the ability to re-use the same states between different enemies. That means that the states has this signature:

    Code (csharp):
    1. void OnStateEnter();
    2. void OnStateUpdate();
    3. void OnStateExit();
    4. State ShouldTransitionTo();
    And the state machine did this:

    Code (csharp):
    1. void Update() {
    2.     currentState.OnStateUpdate();
    3.     var newState = currentState.ShouldTransitionTo();
    4.  
    5.     if(newState != DontTransition) {
    6.         currentState.OnStateExit();
    7.         newState.OnStateEnter();
    8.         currentState = newState;
    9.     }
    I ended up there because I found that re-using AI states for different enemies were not viable at all. If you have enemies that are very similar (red goblin, blue goblin with more health), it might be. But I needed to have different animations play and different timings and such for each AI, so reusing the patrolling state would make it really, really complicated, with tons of initialization code necessary for making it work. It'd also be impossible to adjust how just one enemy patrolled.

    In theory, you'd think that you could do this:

    Code (csharp):
    1. public class GeneralizedChaseState {
    2.  
    3.     public override void OnStateUpdate() {
    4.         if(GetDistanceToPlayer() < attackDistance) {
    5.             if(TimeSinceLastAttack() < attackFrequency) {
    6.                 Attack();
    7.             }
    8.         }
    9.         else {
    10.             MoveTowardsPlayer();
    11.         }
    12.     }
    13. }
    And then specify attackDistance, attackFrequency, Attack and MoveTowardsPlayer through supplying components or dependency injection or inheritance or what not. Turns out, you get really, really boring enemies that way. And when you start specializing your enemies to do more interesting things, you can't really have that generalized chase state anymore. So I ended up on the solution further up.


    The juicy abstractions I ended up using that saved time were things like "NavmeshPatroller", which given a starting point and patrol area size would spit out semi-random patrolling destinations. Then each of the different patrol states could use that to create patrol points, while still having their own ways to do that.
     
  6. Baste

    Baste

    Joined:
    Jan 24, 2013
    Posts:
    6,294
    Also I don't really understand what coroutines have to do with any of this? It's an implementation detail that's completely orthogonal to how to define transition rules.
     
  7. Invertex

    Invertex

    Joined:
    Nov 7, 2013
    Posts:
    1,539
    Because it offers a clean solution to his problems and to the problems you had for adaptability. You can declare virtual IEnumerators and retain the locality of the code and its references, while allowing you to easily override any portion of it to modify parts of the behaviour for a given character, as well as have exposed properties to add your different animations, items, stats, whatever on a per-prefab level.
     
  8. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    I'm really not the biggest fan of IEnumerators, but that's not really the topic.

    For a general FSM controller, I'd combine a generic class with delegates.
    Code (csharp):
    1.  
    2. public class FSMController<T>
    3. {
    4.     public delegate T StateFunction();
    5.  
    6.     T state;
    7.     Dictionary<T, StateFunction> stateFunctions;
    8.  
    9.     public FSMController(T state)
    10.     {
    11.         this.state = state;
    12.         stateFunctions = new Dictionary<T, StateFunction>();
    13.     }
    14.  
    15.     public void Add(T state, StateFunction stateFunction)
    16.     {
    17.         stateFunctions.Add(state, stateFunction);
    18.     }
    19.  
    20.     public void Update()
    21.     {
    22.         StateFunction stateFunction = null;
    23.         if (stateFunctions.TryGetValue(state, out stateFunction))
    24.         {
    25.             state = stateFunction();
    26.         }
    27.     }
    28. }
    29.  
    Then you could use it like this:
    Code (csharp):
    1.  
    2. public enum MyStates { Running, Sleeping};
    3.  
    4. FSMController<MyStates> controller = new FSMController<MyStates>(MyStates.Running);
    5. controller.Add(MyStates.Running, OnRunning);
    6. controller.Add(MyStates.Sleeping, OnSleeping);
    7. controller.Update();
    8.  
    9. public MyStates OnRunning()
    10. {
    11.      // TODO: Return new state
    12. }
    13.  
    14. public MyStates OnSleeping()
    15. {
    16.      // TODO: Return new state
    17. }
    18.  
    You can of course also opt to just use an int as the state value, but the nice thing of the generic approach is that you can use a custom enum as well. And by using delegates you can directly send functions in your class as parameters to the FSMController. Very little overhead that way.
     
  9. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    FWIW we did our initial FSM implementation using Coroutines to evaluate the state each frame. The reasoning was that when a unit went idle there would be no coroutine. We threw it out because it turned into a rat's nest of inadvertently nested coroutines that resulted in blended state behavior. Explicitly starting and stopping a coroutine has improved in the years since we did that but I'd still do it the way we have it now.

    More to topic - we just let each state handle transitions out of itself. Ultimately, it's easy enough to have base states that handle the grunt of the processing and then we extend them for specific use cases (usually involving specific unit behavior and transitions). We're highly data driven as well which helps. If a unit declaration says that he needs to use a specific type of idle state then the base idle state checks the unit data for this and switches to the specific state instead. The world interactions that causes state switches just say "switch to idle state" and then the idle state says "does my owner need to use a more specific idle state".
     
  10. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    That would also be my approach, but it's really not that hard to check whether the state has changed and add an additional callback in case it has in my code above. And of course an option to have an outside influencer override the current state.
     
  11. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    If you want, certainly. I can see the value in raising events when a state change occurs.

    I'm not 100% following what your code above is trying to do or why you're using an enum to represent state (or the state of the state? or the state of the state machine?)
     
  12. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    The enum is representing the state of the FSM, but you could use any other object. FSMController simply contains a Dictionary that links a state to a method (delegate.) If you call Update(), it looks up the method belonging to the current state, calls it and sets the output as the new state.
     
  13. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    So....a great use case for an FSM is to eliminate having to declare every possible state as an enum; this seems like going backwards to me

    Only if your states are implemented as singletons that get the owners passed to them for processing. If the states are created and destroyed during transition then your dictionary lookup would fail. I guess you could use the type as the key but then you're back to attempting to account for all possible states.

    I appreciate the fact that this potentially decouples the transition decisioning from the states themselves and allows you to include third party "interrupts" to those transitions but you could achieve similar by raising an event in the machine's ChangeState method. It's an interesting idea but I don't see it being feasible as things got more complex and I'd generally favor being more eventful over something like this.
     
  14. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    Absolutely, I would indeed recommend the enum or int options. How you have a FSM without naming every possible state? That's the whole point for me. You define all the possible states and then break the thinking process down to the actions for each specific state. What I essentially did is turn a big state switch into a dictionary and separate methods for each state.
     
  15. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    Oh god. No :)

    Code (csharp):
    1.  
    2. public class StateMachine
    3. {
    4.     private IState currentState;
    5.  
    6.     public void ChangeState(IState newState)
    7.     {
    8.         currentState?.Exit();
    9.         currentState = newState;
    10.         currentState?.Enter();
    11.     }
    12.  
    13.     public void Update()
    14.     {
    15.         currentState?.Execute();
    16.     }
    17. }
    18.  
    19. public interface IState
    20. {
    21.     void Enter();
    22.     void Execute();
    23.     void Exit();
    24. }
    25.  
    26. public class IdleState : IState
    27. {
    28.     public IdleState(Actor owner) { }
    29.  
    30.     // implementation
    31. }
    32.  
    33. public class Actor : MonoBehaviour
    34. {
    35.     private StateMachine stateMachine = new StateMachine();
    36.  
    37.     private void Start()
    38.     {
    39.         stateMachine.ChangeState(new IdleState(this));
    40.     }
    41.  
    42.     private void Update()
    43.     {
    44.         stateMachine.Update();
    45.     }
    46. }
    47.  
    Now I can define as many states as I want as long as they implement IState. The FSM has absolutely no idea about the specifics of each state - it just handles updating the current state and switching states.
     
  16. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    Right, and that's not exactly the same at all...

    You have a class for each state and a function IdleState in there that is the implementation.

    I use an enum entry for each state and allow you to point to any function. Same thing, but allows you to put all implementations within the same class. Note that my FSMController also has no idea what the actual states are.

    Anyway, I'm done with this discussion. There are various options for a FSM implementation here now.
     
  17. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    No - IdleState is the implementation of the state as a class not an individual function. It is comprised of 3 methods mandated by the IState contract that control initialization, execution, and clean up of the state. My way also allows for code reuse among common states (ie - I have an EnterBuildingState that inherits from MoveState because it still involves path calculation and moving)

    This is bad. :)

    So now I have to initialize every state handler before I can use your controller? What happens if I try to transition into a state that has no handler defined? Yikes. You also have no way to init a new state or clean up an old one.

    Sure it does - you have them all defined as enums inside it.

    The whole idea is to have a discussion about possible implementations so that folks can make the best decision for their situation.
     
  18. Baste

    Baste

    Joined:
    Jan 24, 2013
    Posts:
    6,294
    I'm going to agree with @KelsoMRK, having functions as states isn't ideal. States have... state. They'll need to contain variables that define data they care about. You could send that data in from the outside, but then you end up putting a bunch of data that only the states care about outside of the states.

    A state as a function implies that you're sending in a bunch of state data to the state. If you need to know things like "how long is it since I entered the current state" to decide what state to transition to, that becomes a real mess if the state can't have data.

    The coroutine version gets around this, but then you end up creating a new IEnumerator object for every state change, which causes GC strain.
     
    KelsoMRK likes this.
  19. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    Now that is up for discussion of course and depends on the details of what you need. If you require multiple methods for each state, I would also go for an interface or abstract class for each state.

    Having a separate class for each state might not always be needed though and I presented an approach that could help keep things short and understandable in such a case. Because all methods are in the same instance, there really is no data to send, because all data in the instance is already available.

    The discussion I'm done with is the side talk on having to actually know the available states, because it doesn't seem to lead anywhere.
     
  20. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    Your approach executes the same bit of functionality every frame that the state is active. With any amount of complexity (and I mean any) it starts to crack. Now I have to keep state about the state in the controller.

    Take your running example. Assuming they run towards a spot in a straight line that's pretty simple. Move towards the thing; if I'm there return sleep otherwise return running. Fine.

    But what if it's not a straight line and I have to calculate a path? Now I need to track that in the controller
    Code (csharp):
    1.  
    2. Vector3 destination;
    3. bool pathCalced;
    4.  
    5. State OnRunning()
    6. {
    7.     if (!pathCalced)
    8.     {
    9.         CalcPath();
    10.         pathCalced = true;
    11.         return Running;
    12.     }
    13.  
    14.     transform.MoveTowards(destination, speed);
    15.     if ((transform.position - destination).magnitude < 0.5f)
    16.         return Running;
    17.     else
    18.         return Sleeping;
    19. }
    20.  
    Ok cool. Oh, but now I want to play a looping running animation. Can't start that every frame so I need to track whether or not I started it.
    Code (csharp):
    1.  
    2. Vector3 destination;
    3. bool pathCalced;
    4. bool runAnim;
    5.  
    6. State OnRunning()
    7. {
    8.     if (!pathCalced)
    9.     {
    10.         CalcPath();
    11.         pathCalced = true;
    12.         return Running;
    13.     }
    14.  
    15.     if (!runAnim)
    16.     {
    17.         RunAnimation();
    18.         runAnim = true;
    19.     }
    20.  
    21.     transform.MoveTowards(destination, speed);
    22.     if ((transform.position - destination).magnitude < 0.5f)
    23.         return Running;
    24.     else
    25.         return Sleeping;
    26. }
    27.  
    Oh, but now I need to play a particle system that kicks up some dirt behind the unit as it runs....you get the point.

    Ok so I made it to my destination and went back to Sleeping. But now I need to turn off all the state variables I turned on as part of Running. Where do I do that?
     
  21. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    Again, I would not use for all cases. But a FSM can exist for many different things. Lets say I have built in a secret code in a game, lets say it's ABBA. Lets expand the FSMController to also include a specific data type as input for Update, which it of course passes on to the delegate methods. Then I can use it as:
    Code (csharp):
    1.  
    2. public class SecretCode
    3. {
    4.     public enum History {Other, A, AB, ABB}
    5.  
    6.     private FSMController<History, Input> controller;
    7.  
    8.     public SecretCode()
    9.     {
    10.         controller = new FSMController<History, Input>(History.Other);
    11.         controller.Add(History.Other, HistoryOther);
    12.         controller.Add(History.A, HistoryA);
    13.         controller.Add(History.AB, HistoryAB);
    14.         controller.Add(History.ABB, HistoryABB);
    15.     }
    16.  
    17.     public void ReceiveInput(Input input)
    18.     {
    19.         controller.Update(input);
    20.     }
    21.  
    22.     protected History HistoryOther(Input input)
    23.     {
    24.         if (input == Input.A) return History.A;
    25.         return History.Other;
    26.     }
    27.  
    28.     protected History HistoryA(Input input)
    29.     {
    30.         if (input == Input.B) return History.AB;
    31.         if (input == Input.A) return History.A;
    32.         return History.Other;
    33.     }
    34.  
    35.     protected History HistoryAB(Input input)
    36.     {
    37.         if (input == Input.B) return History.ABB;
    38.         if (input == Input.A) return History.A;
    39.         return History.Other;
    40.     }
    41.  
    42.     protected History HistoryABB(Input input)
    43.     {
    44.         if (input == Input.A)
    45.         {
    46.             // Toggle secret mode
    47.         }
    48.         return History.Other;
    49.     }
    50. }
    51.  
    Now envision that split out into 4 different classes for the 4 different states.
     
  22. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    What you have there is more of a behavior tree than a finite state machine. You're not doing anything stateful, you're just waiting for some specific thing to happen.