THE BASIC CONCEPT
The basic concept behind “Finite State Machines” is that everything, from human behaviour/reaction to causes and
effects, can be broken down to individual states, the net effect of them all combined is what we come to recognise
as the end result. For example, a decision/action process can be broken down into smaller decisions to be made,
with every one of which to mean at the same time that he/she making the decision got into a particular state as a
result.
One of the most characteristic illustrations of the use and workings of a “Finite State Machine” is the “Traffic
Lights” paradigm. A set of traffic lights is actually nothing more than a “Finite State Machine” with a total of
four internal states: State I) Green light ON/Amber light OFF/Red light OFF, State II) Green light OFF/Amber light
ON/Red light OFF, State III) Green light OFF/Amber light OFF/Red light ON, State IV) Green light OFF/Amber light
ON/Red light ON.
.png)
It becomes apparent that in “Finite State Machines” the input stimulus (signal to change) produces different results
(pattern of lights) for each of the states, and determines the next state entered. The best design approach for a
“Finite State Machine”, is for us to handle the relationships between states through constructing a sort of “Network
Diagram”. In every such diagram, each “Node” represents a state. Nodes are interconnected by means of “Edges” (a term
we adapt from the Computer Network terminology list), indicating a change or, probably more accurately, a transition
between states.
In this concept, every “Edge” should have an arrow indicating direction. On the start of each connecting “Edge”, just
coming out of the “Node”, we can record what the input stimulus was that would trigger this particular change in state,
so for our “Traffic Lights” example we get something similar to the following:
This kind of diagrams are known as “State Transition Networks” (STN). In the case of the “Traffic Lights” paradigm the
“State Transition Network” is a fairly simple one, mainly because fairly simple is the State Machine itself as it possesses
only one input to change each state, and the sequence of states is a repeated unchanging pattern.
The following is a “State Transition Network” (STN) for a “Finite State Machine” that can internally “remember” a sequence
of three binary digits. As we key in each new binary digit, it provides at the output the one keyed three strokes before:
Download "FiniteStateMachineII"
The primary benefit of using a “Finite State Machine” is that of code organisation. Typically, a game may start off being
simple and following the code flow is easy, but computer games do not stay simple. As new features are implemented, the code
has to be changed. Control over the computer game logic is then maintained "if" statement after "if" statement.
We can immediately distinguish between seven different states which control our game: a) PlayState (Scene 1.1),
b) PlayState (Scene 1.2), c) WonState (Scene 1), d) LostState (Scene1), e) PlayState (Scene 2), f) WonState (Scene 2)
and, g) LostState (Scene 2). The arrows in a corresponding flow diagram would indicate all possible routes for state
transition. The main aim here is to maintain a “closed loop” for every level in the game, out of which we can escape
only in the case the “WonState()” has become the active state.
Activation of the “WonState()” is in fact indicative of us being ready, after successfully completing the current game
level, to make a progress to the next one.
In relation to the definition of Finite State Machines we are in many cases just interested to the input sequence to it
and, respectively, the corresponding output sequence produced by it. A Finite State Machine of this form is called a
"Transducer", since it directly maps Input sequences to Output sequences (G. H. Mealy, 1965).
In some other cases, we are equally interested in the output associated with the current state of the machine only. A
Finite-state Machine of this form is called a "Classifier" (E. F. Moore, 1965).
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)