Best way to implement a large state machine?

Question

Basically I have a state machine that controls a game character's attacks, with timings based on the animation length.

So for example:

I start at the default state, and if the player hits an attack button it starts an attack, switching the state and setting a timer based on the attacks length. The state machine gets more complex however when I consider charge attacks that can be cancelled, attacks that can move to different states depending on what they hit, and also every state has unique ways of dealing with the character being attacked. At the moment I have large switch statements. I thought about polymorphism but that would require a new class for every state for which there are a lot (starting attack, attacking and finishing attack all require separate states for example).

The switch statement works, but its quite large and also isn't as easily modified as an inheritance based system.

Any suggestions on good looking implementations?

EDIT: This is using java.

Answer 1

With larger state machines you must watch out for the "transition explosion" phenomenon. It turns out that the traditional Finite State Machines don't provide mechanisms to reuse common transitions across many states, so you end up repeating too much and your state machine "explodes" (this goes also against the Do-not-Repeat-Yourself (DRY) principle).

For that reason I would recommend using hierarchical state machines and and implementation technique that allows easy mapping such state machines to code. For more information about hierarchical state machines, see the Wikipedia article http://en.wikipedia.org/wiki/UML_state_machine.

Answer 2

Consider building a table-driven state machine. If you think about the definition of a state machine, you have basically a set of states with a distinguished initial state, a transition function, and (in this case) an input and output alphabet.

You can construct a table indexed by current state and input, and use a pointer to function, or a functor class, to represent what happens. That function should return the next state. Then you can build the state machine as (pseudocode):

 state := initial state
 while(state != STOP)
    state := (lookupTransition(inputs))()

where lookupTransition(inputs) simply finds the next state. I'm assuming here that the transition functions are functions of no arguments returning state, so lookupTransition(inputs) has to be a function of however many inputs you have, returning a pointer to function of void arguments returning state.

Set this up correctly, and you can put all the state machine and behavior into one table, which can be easily modified and recompiled.

(For extra credit, figure out how you can load that table from a file, so you don't need to recompile at all.)

Update

In Java, use something like a functor class in place of function pointers.

Another Update

Of course, another option is to use a state machine compiler like Ragel.

Answer 3

Boost has a perfectly fine state machine, the only drawback is getting used to template / type programming

http://www.boost.org/doc/libs/1_46_1/libs/statechart/doc/index.html

Answer 4

By my side I am using stateforge an HFSM( http://www.stateforge.com/ ). Parallel state ,Hierarchical approach and the observer can solve quite a lot of complex case.

Answer 5

I can't say I've ever used it but there is http://commons.apache.org/scxml/. It's also not that hard to write by hand, using the table based approach suggested by others.

Answer 6

You might want to use a state machine library that supports hierarchical states to avoid state explosion. Spring State Machine is an example, or this lightweight library that I recently created:

https://github.com/bertilmuth/act