Design Pattern problem involving N states and transitions between them

Question

Hi All,

I have a problem at hand and I am not getting which design pattern to use. The problem goes as such:

I have to build a system which has 'N' states and my system has to do a transition from any state to any other state depending on some conditions. Ex: On condition 1, movement from State 1 to 3 and on condition 2 from state 1 to 4.

Even the transition from one state to other state can be done on 2 or more different conditions.

For example, transition from State 1 to state 3 can be done when:
condition 1 : "Its a Sunday"
condition 2: "Its Raining"
condition 3: "Its Raining and Sunday"
In each condition, the processing at State 3 can be different.

I hope I was able to understand the problem legibly. Kindly help.

Thanks a lot

Answer 1

won't the state pattern do the work?

Answer 2

This sounds like the typical use for a finite state machine

in short, the state machine describes the various states in which your system can be, and under which conditions it can go from state to state. A state machine is described exactly as your English description. And it can be formally described using state diagrams

in code you could make a state machine like this:

 enum State { Init, ShowMenu, ShowMsg, DisplayVideo, Exit };
 State state = State.Init;

 while (state != State.Exit)
 {
      switch(state)
      {
           case State.Init:
                init();
                state = State.ShowMenu;
                break;
           case State.ShowMenu:
                if(lastMenuItemSelected==1) state = State.ShowMsg;
                if(lastMenuItemSelected==2) state = State.DisplayVideo;
                break;
           case State.ShowMsg:
                ....
                break;
           ....
 }

I'm not sure if I got the exact syntax correct for Java...I'm more into C#

Answer 3

The first thing I noticed about your example was that State 3 = (State 1 == true && State 2 == true). This will not scale very well as more possible states become involved. If you are only considering whether it is raining or whether it is Sunday, you can have an enumeration like this, with 4 possible types:

enum State { CLEAR_OTHER_DAY, RAINING_OTHER_DAY, CLEAR_SUNDAY, RAINING_SUNDAY }

This would allow you to state conditions cleanly in a switch block when it is time to code. But if you have to also consider whether it is warm outside, you have to add 4 more values to that enum to capture all possible conditions. And later in your project, your code may need to capture more conditions than you currently envision.

As for a design pattern, the State pattern and its Java example on Wikipedia look like a good place to start.

Wikipedia's example has a StateContext class with a method called setState that takes in a name. I thought about suggesting that you add the state determination logic here, but that would make your StateContext class need to get too close to the implementation details of your other classes. It would be better to put a method for determining the system's state in a class that would easily know the conditions for going from one state to another. This way, if your project needs to change in the future and you either have more states to keep track of or different conditions, you only need to maintain the logic in one place.

Answer 4

As others have said a state machine can be modelled in procedureal code with a switch or in OO code with the state pattern, which is probably what you were after.

However a 3rd way is to actually code it as a graph, with states as nodes and conditions as directed edges. The visitor pattern can then be used to apply the graph to different uses. this would lend itself particularly well to designs where the states and/or the transitions could be user defined, but would probably be more memory intensive then the hard coded state machines described in the other answers.

Answer 5

Its clearly a case of a finite-state-machine but its better to combine the conditions rather than create a new condition for each combination. I didn't like the Java example for State pattern on Wikipedia as states know about other states which wouldn't make sense in a lot of scenarios. A transition table that keeps a track of the from state, applicable condition(s), and to state, helps take care of that problem.

My two cents for an object oriented-finite-state-machine. There are improvements you could do on the OO front, but it gets the idea across.

class Transition {
    State from;
    Set<Condition> conditions;
    State to;
}

class State {
    String state;
}

class Condition {
    String condition;
}

The state machine can be constructed with the above types. There is no error checking, but you could throw an exception or something if no next state is found for some conditions.

class StateMachine {
    List<Transition> transitions;
    State current;

    StateMachine(State start, List<Transition> transitions) {
        this.current = start;
        this.transitions = transitions;
    }

    void apply(Set<Condition> conditions) {
        current = getNextState(conditions);
    }

    State getNextState(Set<Condition> conditions) {
        for(Transition transition : transitions) {
            boolean currentStateMatches = transition.from.equals(current);
            boolean conditionsMatch = transition.conditions.equals(conditions);
            if(currentStateMatches && conditionsMatch) {
                return transition.to;
            }
        }
        return null;
    }
}

And a test run:

Edit: With some more transitions and new states based on your comment:

State one = new State("one");
State two = new State("two");
State three = new State("three");

Condition sunday = new Condition("Sunday");
Condition raining = new Condition("Raining");
Condition notSunday = new Condition("Not Sunday");
Condition notRaining = new Condition("Not Raining");

List<Transition> transitions = new ArrayList<Transition>();
transitions.add(one, new Set(sunday), three);
transitions.add(one, new Set(sunday), two); // <<--- Invalid, cant go to two and three
transitions.add(one, new Set(raining), three);
transitions.add(one, new Set(sunday, raining), three);
transitions.add(one, new Set(notSunday, notRaining), three);

StateMachine machine = new StateMachine(one, transitions);
System.out.print(machine.current); // "one"
machine.apply(new Set(sunday, raining));
System.out.print(machine.current); // "three

I had a bitter experience with using a state machine for a fairly large project. The problem was with composite states. Just like the composite condition you mentioned (sunday and raining), there could technically be composite states which could further be broken down into unit states. This may or may not be the case in your situation, but still worth mentioning. If that is the case, it's best to modify the classical finite state machine and use a set of states instead of a single state to represent the from and to states. If your N is large, this will help keep sanity levels intact. Think hotmail folders vs gmail tags. The transition table would then be presented as

Transition(Set<State> from, Set<Condition> conditions, Set<State> to)