What is the best practice for a hierarchical state machine using the state pattern?

Question

I'm about to implement a hierarchical state machine in C# using the state pattern. As a guide I'm using this example. The example doesn't provide an answer regarding hierarchical states though. Unfortunately, I can't seem to find good examples elsewhere. My first thought is to create nested classed for the hierarchical states. But is this considered best practice or are there better solutions?

Greets!

UPDATE:

I've been sitting all afternoon on trying to implement the state pattern as described above. The HSM is based on a very simple media player:

alt text http://www.freeimagehosting.net/uploads/e8d2d6486a.jpg

I thought I've done it but one thing I do not understand. First the code I've written (sorry, it is quite al lot):

public class MediaPlayer
{
    public MediaPlayerStates state;

    public MediaPlayer(MediaPlayerStates state)
    {
        this.state = state;
    }

    public void OnButtonPressed()
    {
        state.OnButtonPressed(this);
    }

    public void DeviceBooted()
    { 
        state. ?????
    }

    //Other Functions
}

//The 3 initial states (Start, On, End) know only 2 events.
public abstract class MediaPlayerStates
{
    public abstract void OnButtonPressed(MediaPlayer player);
    public abstract void OffButtonPressed(MediaPlayer player);
}

//The very beginpoint of the state machine
public class Start : MediaPlayerStates
{
    //When hitting the onbutton, the state changes to the OnState state
    public override void OnButtonPressed(MediaPlayer player)
    {
        player.state = new OnState(player);
    }

    //No need to implement this one
    public override void OffButtonPressed(MediaPlayer player)
    {
        throw new NotImplementedException();
    }
}

//OnState implements the 2 events from the MediaPlayerStates abstract class.
public class OnState : MediaPlayerStates
{
    //When entered the OnState state, a new entrypoint is creaeted: the Start state
    public OnState(MediaPlayer player)
    {
        player.state = new OnStartState();
    }

    //The OnState doesn't have a OnButtonPressed event so it doesn't need to be implemented
    public override void OnButtonPressed(MediaPlayer player)
    {
        throw new NotImplementedException();
    }

    //When hitting the offbutton in the OnState, the new state is End
    public override void OffButtonPressed(MediaPlayer player)
    {
        player.state = new End();
    }

    //The OnState itself containts 3 events, therefore these need to be implemented by every state whitin the OnState state
    public abstract class SubStates : MediaPlayerStates
    {
        public abstract void DeviceBooted(MediaPlayer player);
        public abstract void PlayButtonPressed(MediaPlayer player);
        public abstract void StopButtonPressed(MediaPlayer player);
    }

    //The OnStartState is the pseudoState where the On state starts
    public class OnStartState : SubStates
    {
        //When booted, the state of the player changes to the ShowMediaFileState state
        public override void DeviceBooted(MediaPlayer player)
        {
            player.state = new ShowMediaFileState();
        }

        //The events below don't need to be implemented since they don't exist. 
        public override void PlayButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        public override void StopButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        public override void OnButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        public override void OffButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }
    }

    public class ShowMediaFileState : SubStates
    {
        //This event doesn't exists for this state
        public override void DeviceBooted(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        //When hitting the play button in this state, play the mediafile
        public override void PlayButtonPressed(MediaPlayer player)
        {
            player.state = new PlayMediaFileState();
        }

        //These events also don't exist for this state
        public override void StopButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        public override void OnButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        public override void OffButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }
    }

    public class PlayMediaFileState : SubStates
    {
        //This event doesn't exist for this state
        public override void DeviceBooted(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        //This event doesn't exist for this state
        public override void PlayButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        //While playing a file and hitting the stopbutton, the state changes to the ShowMediaFileState state
        public override void StopButtonPressed(MediaPlayer player)
        {
            player.state = new ShowMediaFileState();
        }

        //This event doesn't exist for this state
        public override void OnButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }

        //This event doesn't exist for this state
        public override void OffButtonPressed(MediaPlayer player)
        {
            throw new NotImplementedException();
        }
    }
}

//The endstate doesn't need any implementation since there cannot occur a event while being off
public class End : MediaPlayerStates
{
    public override void OnButtonPressed(MediaPlayer player)
    {
        throw new NotImplementedException();
    }

    public override void OffButtonPressed(MediaPlayer player)
    {
        throw new NotImplementedException();
    }
}

When defining the events in the MediaPlayer class, I can't call any other functions then

• OnButtonPressed
• OffButtonPressed

So I wonder, is my implementation any good? What is wrong? I also tried to look at the suggestion of using the composite pattern but I don't understand how it should be used with the state pattern. Hope anybody can help!

Answer 1

I think you'll want Composite as well; that will allow you to link state machines together.

Answer 2

For making a HSM with the state pattern, each state with substates has to be a state machine itself. This way it the upper level has no knowledge of the substates (less side effects) and the state can better manage his substates (can have a default state, can remember the last state it was in etc).

BTW throwing an exception when you can't do anything useful with an action is wrong. You should just ignore it. You only throw exceptions in exceptional cases, pushing a wrong button is expected user behavior.

Answer 3

Before you start implementing your own FSM framework, take a look at SMC - the State Machine Compiler.

SMC takes a textual definition of a state machine and generates the code to implement it. It has backends for a wide range of languages including C#. It can also output dot files to generate a diagram of the FSM.

SMC can create something similar to hierarchical state machines with the push and pop transitions - essentially push transfers control to a new state machine, and pop returns control to the original state machine.

Answer 4

To make it work in a generic manner, you'll need to treat the state machine's hierarchy as a tree structure; transitions between nodes can use a least common ancestor (LCA) algorithm for trees then exit from the node below the common ancestor on the source node ancestry (cascading the exit to any child nodes), then enter each node on the target node ancestry from the node below the common ancestor to the target node, finally, if the target node has children, you'll need to enter those as if you were entering any other composite state.

This is the method that's mentioned in the UML Superstructure Specification.

Take a look at the source code in https://github.com/steelbreeze/state.cs as this implements the method above.

To see a working example, take a look as the project site for the sister JavaScript version here: http://www.steelbreeze.net/state.js/