Avoiding bouncing between states in an FSM

Question

Suppose you have a simple state machine for a game character with two states:

• StandingIdle
• Walking

In the update logic for the StandingIdle state you have (pseudo code):

if input received
    setState(Walking)

In the Walking state you have:

intendedLocation = calculate new location based on current heading and speed

if intendedLocation is blocked
    setState(StandingIdle)
else
    move to intendedLocation

Now this creates the problem that the state machine can bounce back and forth between the states, which can result in an awful visual effect. This is because the StandingIdle state may switch to Walking, whereupon the Walking state may determine that something is blocking the way and subsequently switch back to StandingIdle. As long as there is input being received (ie. the player is trying to move), then the state machine will bounce back and forth between these two states.

In order to deal with this, the StandingIdle state could first check whether there is sufficient room in which to start walking. But that requires either duplicating logic that already exists in the Walking state, or exposing that logic in some fashion and calling it from the StandingIdle state. I am leaning towards the latter route at this stage.

Another option I considered was exposing some kind of canTransition() method from my state objects and having the state machine call it prior to allowing a state change. That way, the Walking state could return false if there is insufficient room to walk. This, however, creates other problems.

Is there a best practice way to deal with this problem?

Answer 1

There is nothing wrong with this

if (input received  && can walk) 
   setState(walking)

you can share the "can walk" logic between states.

Answer 2

Move intendedLocation to the scope of the state machine and set the 'blocked' flag to be true by default.

When input is received in either state, calculate intendedLocation and check if it's blocked. Therefore, intendedLocation will be in a different location from the player when input is received. 'Blocked' should also be true if intendedLocation == playerLocation (not receiving any input).

In both states:

if input received
    set and check intendedLocation

Then, in your StandingIdle state:

if intendedLocation is not blocked
   setState(walking)

In your Walking state:

if intendedLocation is blocked
    setState(StandingIdle)
else
    move to intendedLocation

It may be a good idea to put the code for setting and checking the intendedLocation in the base class of that the Walking and StandingIdle states derive from, since they'll be both checking for input.

Answer 3

Your canTransition() solution is good, but rather than a simple function you would want to have a class that defines the possible transitions from one state to another, since Walking can have multiple entry points, that may have different conditions. This will complicate your FSM design though. Here is the relevant Wikipeda page on the deterministic finite automaton

Alternatively, you could allow for more than one state change at a time. That would mean the entering Walking state which then switches immediately back to StandingIdle and since your input event is already consumed it won't bounce back. You have to take care though to not create circular paths, because that can stall your game. Of course you could introduce a DoNothing state, but I'd consider that bad form.