1
\$\begingroup\$

I saw an example of code using HSM for user input, but to me it seems that Pushdown Automata would be a better fit. I'm confused.

If I'm right, then after Hierarchical State Machine exits a superstate via substate, and comes back, it must start at a default state and cannot return to the substate it left earlier(unless of course, that default state is the substate). And then, if I'm right, Pushdown Automata could replace that need, as it can return to an older state via its stack and discarding of states.

Say I have an actor I control, and it has several states that use user input as transitions. It supports jumping, ducking, standing and walking. When you are standing or walking, you can jump or duck, after which you return to the state you were in, thus standing or walking. If I were to use an HSM to prevent the duplication of code, I could not return to the last state. But if I used a Pushdown Automata, I could put jumping or ducking on top of the stack and discard them after they are done, and that way I could return to the state I was in.

Correct me if I'm wrong, and suggest me better options for user input than these two, if there is. Also, please don't post options like duplicating the FSM as the amount of states could vary and my question is related exactly to how to prevent that duplication.

Thanks,

me.

\$\endgroup\$
1
  • \$\begingroup\$ If you've had good luck using Pushdown Automata for this purpose, then I'd say continue using Pushdown Automata. It doesn't matter what someone on the Internet thinks is better, if what you have works for your needs. If you want to know why a particular example used a hierarchical approach, the best way to find out is to ask the author of that example (who might not be a user here). If you're having trouble applying your favoured approach to a particular problem, tell us about that situation and we can suggest solutions. \$\endgroup\$
    – DMGregory
    May 29, 2018 at 21:03

2 Answers 2

3
\$\begingroup\$

Pushdown automata and hierarchical state machines, at least in the context of game design, are both extensions of finite state machines. Neither contradicts the other, and so you can freely use both.

In hierarchical state machines, the substate/superstate relationship is one such that the substate is just a modified or extended version of the superstate. Lets say you have a superstate that is called RunningState that indicates your player is running. You can jump while running left if the A button is pressed, so one of your transitions is something like if (A_BUTTON_PRESSED) next_state = jump_state; However, you also want there to be an injured running state, for when the player has <50% health, that behaves like RunningState in every way except that a) you run slightly slower, and b) you cannot jump. So you create InjuredRunningState : public RunningState that has if (A_BUTTON_PRESSED) {next_state = NULL;} else { RunningState::transition(); } in its transition method.

You see that InjuredRunningState will behave in every way like RunningState except when the A button is pressed it will do nothing. This example I think encapsulates why you would use a hierarchical state machine. The downside to using a hierarchical state machine is that inheritance can make your code complex and difficult to read / manage relatively quickly. Change RunningState and your implicitly change every state that inherits from it, which may have entirely intended consequences or may not, if those substates were designed with some assumptions about how RunningState behaves.

Pushdown automata, on the other hand, are good because they maintain state history. In other words, a state, instead of being told to transition specifically into state X or state Y given conditions A or B, can be told to do something like "transition into the previous state" given some condition, where the previous state can be any state that transitions into this one. Say you want to be able to jump from standing and from crouching, and the jump animation and physics etc. are identical, but when you land you want to return to whatever state you were in before, be it standing or crouchihg. You could use a pushdown automata for this. Instead of transitioning to a JumpState, you push() a JumpState. When the JumpState is done, instead of transitioning into some explicitly named state, it simply pop()s, and the state underneath it, the state that pushed the JumpState, is returned to, be this StandingState or CrouchingState.

The downside of this is that you have to maintain a stack of states, and make sure that you pop() what you push().

Hopefully it is clear that you can have both at this point. You could have a StandingState and CrouchingState that transition into JumpingState, and then create InjuredStandingState or InjuredCrouchingState that inherit from their respective states (Hierarchical State Machine), while making sure any state that transitions into JumpingState does so by pushing it onto a state, and popping it when the jump is done (Pushdown Automata).

A final note: all the functionality described here could be achieved with regular finite state machines. For example, InjuredStandingState could just be its own completely independent state that repeats all the code of StandingState that it needs without inheriting from it. Similarly, instead of JumpingState you could have JumpingFromStandingState and JumpingFromCrouchState that, when done, transition back into the appropriate previous state. The problem here is repeat code and a rapidly expanding number of states, depending on the kind of behavior you want. It is up to you to decide if these extensions are even necessary. A regular finite state machine may be entirely sufficient for a very simple set of states and transitions.

\$\endgroup\$
0
\$\begingroup\$

You're right, finite state machines do not maintain history, and many extensions are often added to them in order to overcome their limitations (including pushdown automata).

More info on state machines (with a section on pushdown automata).

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .