Finite Machine State for gaming

I have made my first tutorial on the topic Finite Machine State. I tried to apply this concept to simple gaming examples. FSM are mainly used for AI but could also be used for other stuff such sa organising game workflow. Just a tricky example with the famous puzzle game Wolf, Sheep & Cabbage.
Rules are simples, you have to help aman in aboat to move the wolf, the sheep and the box of cabbage to the other side of the lake. You can only bring one of these with you at a time. It is very important to note that the unguarded wolf will eat the sheep and the unguarded sheep will eat the cabbage, when the man isn’t around.Without saying more I can tell you that FSM can help you create this king of brain game.

French version available on Mediabox.

---

Finite Machine State [English Version]
-- I am currently translating...I used googled translation to fasten the process...Working in progress

Introduction
The finite state machines  also called finite-state automaton  or state machine, is an  abstract concept used in  and mathematical computer. They are used in various fields such as electronics, robotics and programming. PLCs are often used to model complex problems where there is a finite number of possibilities.
"A finite-state machine (FSM) is an abstract concept often used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition, this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition."(Wikipedia)

A state machine is essentially composed of:

•  States (A starting element and any number of elements come)
•  Actions (or functions)
•  Events
•  Transition

• States determine the context in which the actions are executed. It can only be in one state at a time.
• The actions represent the work to be performed by state.
• Events must determine when carrying out the actions.
• Transitions determine how to move from one state to another

(http://lamsonproject.org/docs/introduction_to_finite_state_machines.html )

Example: The wolf, the goat and the cabbage

(Extract from articleFinite Automata by Jean-Eric Pin)
"A smuggler must move from one bank to another wolf, a goat and a salad. However, the boat can carry only one passenger out of himself. Of course, he can not leave the wolf and the goat alone unattended, otherwise the wolf will eat the goat. Same thing for the couple goat salad because the goat dream of eating salad. Can you help the ferryman? "(Example also presents in the game Professor Layton on Nintendo DS)

To solve this puzzle it is possible to use a state machine.

• You can define the states by the presence of players on the opposite bank (or similarly the bank of origin). The possible states are as follows:
• N / A: no player on the opposite bank
• S: Salad on the opposite bank
• C: Goat on the opposite bank
• L: Wolf on the opposite bank
• P: Ferryman on the opposite bank
• And any combination SC, SL, SP, CL, CP, SCL, SCP, CLP, SCLP

We are 14 states

• Possible actions are:
• Cross only P
• Cross the wolf L
• Cross C with goat
• Cross salad with S

• The events are triggered by the person trying to make the puzzle. It triggers the action was performed.

• Transitions are passages from one bank to another (0 / P 0/SP, 0/CP, 0/LP, P / SP, P / 0, SP / 0 etc ...)

Transition diagram>

A state machine can be represented by a transition diagram. Two possible solutions are represented by the transition diagram below:

Implementation

Generally a state machine is programmed intuitively conditionally in a single class. It is however essential for complex systems separate states into different classes to facilitate the development and maintenance of the code.

Binary Example:The light

 

- Two states: On or Off (lightIsOn / lightIsOff)
- Two actions: Turn on or Turn off the light (SwitchOn, switchOff)
- An event: Press the switch (Key.isDown)
- Two transitions: On /Off and Off/On

if (Key.isDown && lightIsOn) 
     switchOff (); 
else if (Key.isDown && lightIsOff) 
     SwitchOn ();

When a machine is composed of a large number of states, if using, and / or switch to encode a state machine is not enough. To avoid overcrowded classrooms of thousands of lines of code, it becomes necessary to organize the code in several classes.

Practical Example of PLC: The security code

(Excerpt from the course Computer Industrial PLCs by Jacques Weber / Souhil Megherbi)

"A digital code comprises a 16-key keypad which constitutes the input of a controller whose output controls only the opening of a door. We restrict ourselves to a rudimentary digital code in which the PIN is fixed once and for all, without modification possible. Imagine, for example, the opening of the door is achieved by providing the C94 (as cachan + department). Obviously the controller must be informed that the user has opened the door, it is the role of signal "open". '

Modeling finite state machine

The work of the PLC can be summarized by the following diagram:

Conditional Programming

In the example of the three-digit security code, use nested if is reasonable but we can already realize how the code will become more complex if you choose to create a digital code 5 or 6 digits.
var state: int = 0; 
if (Key.isDown) { 
     if (state == 0) { 
          if (C == key.keyCode) { 
               state = 1; 
          else {
                state = 0; 
          } 
     }else if (state == 1) { 
          if (key.keyCode == 9) { 
               state = 2; 
          }else {
               state = 0; 
          } 
    }else if (state == 2) { 
           if (key.keyCode == 4) { 
                open(); 
           }else { 
                 state = 0; 
           } 
     } 
}

Object Oriented Programming in the state machine

An example of a structure used to program a state machine OOP (inspired RichardLord)

• A class that stores FiniteMachineState states and defines the transitions from one state to another.
• An interface that defines the methods IEtat Enter, Exit and Update are the actions to perform.
• A class that implements the interface IEtat State.
• Several states that classes inherits from the State.

Each state is independent.
Events (key press) can trigger actions (open the door) under certain conditions and / or may result in transitions (State1/State2, State1/State3, State2/State1, state2, STATE3, State3/State1).
MachinesEtats is the main class defined as default application (DocumentClass) FiniteStateMachine It instantiates the class that stores the state defines the initial state and the current state, and finally manages transitions. In our example of digital code we must define the three states with the initial state as State1. Then adds a listener to handle keyboard events.

private function _start (): void { // - Instantiate the state machine _fsm          FiniteStateMachine = new (); // - 3 states are added to the machine               _fsm.addState ("State1", new State1 (_fsm)); 
      _fsm.addState ("state2", new state2 (_fsm)); 
      _fsm.addState ("STATE3", new STATE3 (_fsm)); 
      // Add a listener to keyboard events 
      addEventListener (KeyboardEvent.KEY_DOWN, _onKeyDown, false, 0, true); 
} 

// When you press a key on the function onKeyDown call the current state 
private function _onKeyDown ($ evt: KeyboardEvent): void{        _fsm.currentState.onKeyDown ($ evt); 
      _dynamicTF.text evt.keyCode.toString = $ () // Displays a textField the key pressed } 

ISTATE is the basic interface
ISTATE {
public interface function enter ($ previousState: State): void // Called On entering the state 
function exit ($nextState: State): void // Called on leaving the state function update (): void / / Called while in the state finiteStateMachine 
function get (): FiniteStateMachine; finiteStateMachine 
function set ($ finiteStateMachine: FiniteStateMachine): void; }

IDigiCodeState interface is specially created for the tutorial. It defines the action following the keyDown event
flash.events.KeyboardEvent import; 
IDigiCodeState {
   public interface function onKeyDown ($evt:KeyboardEvent): void // Called on keydown event 
} 

State is the abstract class that implements both interfaces
flash.events.KeyboardEvent import; 
public class State implements ISTATE, {
    IDigiCodeState protected var _finiteStateMachine: FiniteStateMachine = null;  
     public function State (fms: FiniteStateMachine = null): void { 
         _initVar (fms) } // Init Var

     private function _initVar (fms: FiniteStateMachine = null): void {               _finiteStateMachine = fms; 
}

public function set ($finiteStateMachine: FiniteStateMachine):void{ 
     _finiteStateMachine = $ finiteStateMachine; 
} 
public function get finiteStateMachine () {
     FiniteStateMachine _finiteStateMachine return; 
} 
public function onKeyDown ($evt: KeyboardEvent): void { 
} 
public function enter ($previousState: State): void { 
}
public function update (): void { 
} 
public function exit ($nextState: State): void { 
} 
}


State1 is the initial state: None entered digit
import flash.events.KeyboardEvent; 
public class State1 extends State {// inherits from State 
public function State1 ($fms: FiniteStateMachine = null) { 
     super ($ fms); 
 } 
// ------ On Key Down ------------------------------------ 
override public function onKeyDown ($ evt: KeyboardEvent): void { 
     if ($ 67 == evt.keyCode) {// 67 is keycode for the C 
           trace ("Transition to State1 state2");   
           _finiteStateMachine.changeStateByName ("STATE2"); 
      else {
          trace ("Remain in State1"); 
       } 
    } 
}

State2: is the second state: A number entered
import flash.events.KeyboardEvent;
     public class State extends state2 {// inherits from State 
     public function state2 ($ fms: FiniteStateMachine = null) { 
     super ($ fms); } 
function onKeyDown ($ evt: KeyboardEvent): void { 
     if ($ 57 == evt.keyCode) {// 57 is the keycode for 9 
          trace ("Transition to STATE3 state2");    
          _finiteStateMachine.changeStateByName ("STATE3"); 
     }else {
           trace ("Back State1"); 
           _finiteStateMachine.changeStateByName ("State1"); 
      } 
     } 
}

STATE3 is the latest state: Two digits entered
import flash.events.KeyboardEvent; 
public class STATE3 extends State {// inherits from State 
public function STATE3 ($ fms: FiniteStateMachine = null) { 
     super ($ fms); 
} 
// ------ On Key Down ------------------------------------ 
override public function onKeyDown ($ evt: KeyboardEvent): void { 
     if ($ 52 == evt.keyCode) {// 52 is the keycode for 4 
           _open () 
     }else{ 
          trace ("Return to State1"); 
     } 
     _finiteStateMachine.changeStateByName ("State1"); 
} 
 private function _open(): void { 
     trace ("Open Door") // Trace Door Open trace ("Back State1");    
     _finiteStateMachine.changeStateByName ("State1") // Go back to the initial state 
     } 
}

Sources (open source):

 

Source.zip 

(heavily inspired tutorial RicharLord)

Conclusion

A state machine is the conceptualization of a situation, a system or a problem in the form of states, actions, transitions and events.
We can say that if it is possible to represent a structure in the form of states, actions, transitions and events, then this is a conceptual representation or state machine.

Another practical example: Car

To go further, the site active.tutplus graphically presents the more complex case of a car. In this example, state machines are very useful for organizing code and facilitate maintenance.

Useful Links:

- Richard Lord : Blog
- ActiveTutsPLus : Tutorial