How can I simplify my state machine transitions?

Question

I currently have the following base class which I inherit from for my player states (e.g. Idle, Walking, Jumping).

struct PlayerState : std::enable_shared_from_this<PlayerState> {
    virtual ~PlayerState() {
    }

    virtual auto handle_input(const Input& input) -> std::shared_ptr<PlayerState> {
        return shared_from_this();
    }

    virtual auto update(AudioQueue& audio_queue, double dt) -> std::shared_ptr<PlayerState> {
        return shared_from_this();
    }
};

handle_input and update can both be overridden to allow transistions between states, e.g.

struct IdleState : PlayerState {
    virtual auto handle_input(const Input& input) -> std::shared_ptr<PlayerState> override {
        bool jump = input.was_button_pressed(0);

        if(jump) {
            return std::make_shared<JumpingState>();
        }

        return shared_from_this();
    }
};

This works reasonably well and lets me write new states very quickly, however as the number of states is expanding I find I'm repeating myself a lot.

Take the example above, the code for handling jumping is duplicated in both the Idle and Walking states (as you can jump from either).

I'm sure there must be a better way to model these transitions but I just can't see it right now.

My first idea was to add an additional property to each state, e.g. bool can_be_jumped_from and then pushing the logic for jumping down into the base PlayerState class and ensure all inherited classes call the base handle_input method before their own. My concern here is that the number of these flags will grow every time I have a state that can be transitioned to from multiple places.

Is there an another simpler/tidier implementation I'm missing here?

Answer 1

This is rather tricky question. The problem here are not flags bool can_be_jumped_from per se, but what actually lies behind it - FSM state transition.
Number of state transitions required is not given by the implementation but rather by the model said FSM describes. Or in other words, bool can_be_jumped_from is not problem of shown implementation. Though you are very right about the maintenance issue.

A way to improve the ease of maintenance is to abstract more. Because code his its limits here, I would suggest employ some form of automation, may that be code generation frameworks (e.g. Visual Studio's T4 temples), tools capable of modeling FSM, custom markup language (e.g. XML describing transitions and states) or any other way that helps both de-coupling implementation from the model and conveniently letting you focus on designing the model itself.

Another way is optimizing the model, reducing the number of FSM states and transitions required. I will not go into the details for FSM optimization as it would be out of scope this question - there is whole mathematics field behind. In any case, drawing (either by hand or by tool) the FSM should help understanding it substantially.

---

Not to leave you empty handed, I would suggest using a bit different and maybe more conventional implementation. Following wiki definition, FSM is a quintuple: set F of exit points (irrelevant for us), set of states S, the the entry point S0 (member of S), *delta *set of transitions (for convenience, by current state) and sigma the input alphabet, giving you a draft:

//handles the logic associated with the state through callbacks
class State//abstract
{
   virtual void OnEnter(State* previousState);
   virtual void OnStay();
   virtual void OnExit(State* nextState);
}

class IDecision { //sigma given implicitly by implementation
   virtual bool Decide(State state) = 0;//evaluates to true/false or 0..1 in case on non deterministic
}

//binds two states together and holds the decision logic
class ITransition { //deltaB
  State fromState;//key
  State toState;
  IDecision decision; 
}

//to-do optimize shared state, rest of logic
class FSM {
 std::vector<State> States;//S
 State entryPoint;//S0
 std::map<State, std::vector<Transition>> Transitions;
 void Update() { 
    //not actual syntax, cut short for brevity
    auto transfer = std::find_first_of(Transitions[currentState], [&t] -> { t.decision.Decide(currentState); });
    if(!transfer) currentState->OnStay(); 
    else Transfer(transfer);
 }

 void Transfer(ITransition transition)
 {
   transition.fromState().OnExit(currentState);
   transition.toState().OnEnter(currentState);
   currentState = transition.toState();
 }
 //...currentState, constructors, serialization, generic logic...
}

with similar setup (did not check any syntax!), you could implement reusable Jumping:

class ShouldJumpDecision : public IDecision
{
  bool ShouldJump = false;
  ShouldJumpDecision(CommandManager manager) { 
    manager.Resgister<Input::Jump>([&] -> ShouldJump = true; ) 
  }
  virtual bool Decide(State state) override {
    return ShouldJump;
  }
}

class IddleState : public State {
  virtual void OnEnter(State* previousState) { animator.Play("IddleAnim") }
  virtual void OnExit(State* nextState)  { animator.Stop("IddleAnim") }
}

//PlayerFSM.xml parsed and automatically visualized and built by your engine tools
<Decisions>
  <Decision Name="ShouldJump">
    <Transitions>
      <Transition From="Iddle" To="Jump">
      <Transition From="Attacking" To="Jump">
    </Transitions>
  </Decision>
</Decisions>

//or created manually in code
fsm.AddTransition(iddle, ShouldJumpDecision, jump);
fsm.AddTransition(attacking, ShouldJumpDecision, jump);

If you are feeling generous, you can also implement something like the Command pattern for even more de-coupling.