Assembly Language Programming - Lesson 7 - State Machines

4 replies to this topic

#1 Robert MOFFLINE

Robert M

Stargunner

• 1,488 posts
• Rootbeer!
• Location:Western NY state

Posted Sun May 15, 2011 5:13 PM

Okay, so somebody reminded me I never finished my assembly language programming courses. Here is the next one after a five year hiatus. My bad

Assembly Language Programming

Lesson 7 - State Machines:
==========================

Written by Robert Mundschau in May 2011.

-----

The last topic we must cover before we can discuss programming the 6507 with
assembly langauge is state machines.  You need to understand state machines,
because the 6507 microprocessor is a state machine.  when you understand the
rules for state machines, assembly language programming (all programming
really) will make more sense.

At the root, state machines are abstract mathematical constructs.  What is
special about state machines is that they can be implemented as real mechanical
or electronic machines.  We will show that a state machine can impose a set of
logical control or rules onto a system. This control makes the real-world
device predictable and useful.

A state machine is a list of states, a list of possible inputs, and a matrix of
next states for each current-state/input combination.  For a really simple real
world example consider an electric light connected to and on/off switch.  In
our imaginary perfect world we can simplfy the state machine to the following:

SIMPLE LIGHT SWITCH:
--------------------
Lists of States: ( LIGHT_ON , LIGHT_OFF )
List of Inputs:  ( SWITCH_UP, SWITCH_DOWN )
Table of Transitions:
| Input:
current state:     | SWITCH_UP   | SWITCH_DOWN
+-------------+-------------
LIGHT_ON    | LIGHT_ON    | LIGHT_OFF   <<== The cells of the table
------+-------------+-------------     contain the next state.
LIGHT_OFF   | LIGHT_ON    | LIGHT_OFF

To understand this state machine, consider you have the current state of
LIGHT_ON or LIGHT_OFF, and given an input of SWITCH_UP or SWITCH_DOWN you find
the cell in the matrix that corresponds to the combination of the two.  The
contents of the matching cell in the table is the new state of the machine
following the given input.  All input to a state machine is processed one input
at a time in the order the inputs happened.  We wil tackle the problem of
simultaneous inputs later, assume for now that can not happen.

We have modeled a simple light switch.  We ignored real-world details to
simplify the model down to its bare essentials. We assumed a perfect electrical
supply to the system, and don't worry whether the bulb could burn out.  An
infinite number of inputs exist to any real-world system. As a programmer you
will need to learn to elimnate inputs you don't need to worry about in your
design.  Or which will be handled elsewhere in the system.

Hitting an atari with a baseball bat is an input to the system, but I doubt you
will bother trying to write any code to deal with that potential input.   A
broken joystick reporting both left and right directions at the same time,
however,  is a very real input to consider.  Will the state machine of your
game program handle that input?  Does it need to?

As a programer you need to consider all reasonable inputs or your game may act
glitchy or provide cheats to the player you never intended.  Using state
machines in your game design is a useful way to control player interaction with
the system.   When you see video game glitches it can be because an input/state
combination occurred that the programmer did not account for in their design
and implementaion.

-----

Now lets examine a slightly more complex and useful state machine.  Imagine a
simple gumball vending machine. The machine will only take pennies. The machine
has a vend button, and has the ability to detect when it is empty.  If a user
inserts a penny and presses the vend button, the machine will vend one
gumball.  If the user inserts a second penny, the first penny is returned.  Any
penny inserted while the machine is empty will be returned.  Using these simple
requirements we can generate the state machine design below.

PENNY GUMBALL MACHINE:
----------------------
List of States: ( {starting state}WAITING, READY_TO_VEND, EMPTY )
List of Inputs: ( PENNY, VEND_BUTTON, EMPTY_SIGNAL )
Table of Transitions:
| Input:
Current State: | PENNY           | VEND_BUTTON   | EMPTY_SIGNAL |
+-----------------+---------------+--------------+
WAITING       |READY_TO_VEND    | WAITING       | EMPTY        | < next state
exit action |            none |          none |         none | < extra work
--------------+-----------------+---------------+--------------+
exit action |    return penny |  vend gumball | return penny |
--------------+-----------------+---------------+--------------+
EMPTY         |EMPTY            | EMPTY         | EMPTY        |
exit action |    return penny |          none |         none |

There are three big differences between this state machine and the first state
machine we looked at:

1. It has more states and inputs than the first example.  A state machine can
have any number of states and inputs, and they do not have to be the same
number of each.

2. In the list of states I marked the WAITING state at the {starting state},
which means the state machine is in the WAITING state when it starts running.
If you don't specify a starting state for your state machine, it can start in
any state which may cause unwanted behavior.  For the light switch example the
starting state didn't matter.

3. In the cells of the state transition table I added an exit action to be
performed before transitioning to the new state.  The addition of actions
changes the state machine into something useful. Our design has three possible
exit actions which we could add to the design as a list like this:

List of Exit Actions: ( none, return penny, vend gumball).

To operate this state machine, when an input arrives the following happens:

1. Lookup the the transition table entry corresponding to the current
state and the input.
2. Perform the exit action in that table entry.
3. Change the current state to the next state in that table entry.

Using this algorithm the exit actions represent real world interactions with
the user.  The underlying state machine acts as the controller to limit the
interactions with the user to the correct order.  The user must insert a penny
and then press the vend button to receive a gumball.  Pressing vend and then
inserting a penny will not yield a gumball.

The Penny Gumball Machine example uses exit action items to join the logical
control aspects of an state machine to real world interactions with the user.
You can imagine that the actions "return  penny" and "vend gumball" are
implemented with a mechanism  activated by the mechanical or electronic device
that implements the state machine logic.  Hopefully, it is clear now why state
machines are so useful.

----

You can tie actions to more than just the exit from a given state.  There are
three distinct places to attach actions to a state machine:
1. Exit Action - Performed on exiting the current state. (as above)
2. Transition Action - On the specific transition from current state to
the next state.
3. Enter Action - On entering the next state.

Any combination of the 3 actions can happen when the state machine processes an
input.  The listed order is the same order the actions will be taken during
input processing.  First, the Exit Action is performed.  Second, the Transition
Action is performed.  The state is changed to the new state, and lastly the
Enter Action for the new state is performed.

Hopefully, the operation of the Exit Action and Enter Action are clear, but the
Transition Action may be harder to grasp at first.  A transition action can be
different for every combination of current and next states that can be made
from the List of States.  We can show all the combinations of current and next
states as a 2-dimensional matrix with the current state on the rows and the
next state on the columns.  The cells of the matrix hold the Transition Action.

Below is an example of the Transition Action Table for the Simple Gumball
Machine.  Imagine we delete the Exit Actions in the original design and replace
them with these Transistion Actions.

Table of Transition Actions:
| Next State:
Current State: | WAITING       | READY_TO_VEND | EMPTY        |
+---------------+---------------+--------------+
WAITING       | none          | none          | none         | <= Actions
--------------+---------------+---------------+--------------+     NOT
READY_TO_VEND | vend gumball  | refund penny  | refund penny |    States!
--------------+---------------+---------------+--------------+
EMPTY         | none          | none          | none         |

This alternate approach is almost identical to the original design.  It does
not handle the case, however, where the user inserts a penny into an empty
machine.   Using this alternate approach that case would result in the user
losing their penny.

Do not take from this limited example that exit actions are somehow superior to
transition actions or entry actions.  Each kind of action serves a different
purpose and can be equally useful.  Often state machines will use a fairly
complex combination of the different kinds of actions to model complex behavior
with a relatively simple design.

----

At the start of the lesson I indicated that the 6507 microprocessor is a state
machine, and we will examine that state machine in detail next lesson.  Right
now it is important to recognize that as a programmer you can use state
see if the state machine paradigm can be applied to them. Once we start looking
at real code, we will return to state machines to see how they are really
implemented.

State machines can be nested and interact with each other.  For example, an
given action may be to generate an input to one or more other state machines.
Or a state machine may only be allowed to process input when another state
machine is in the correct state.

When applying the state machine paradigm to a game element try to map states to
a high level framework of control.  For example, you probably don't want a
separate state for an object moving in each possible direction if the
constraints for motion are the same in all directions.  Rather, a single state
of IN_MOTION combined with some other infomration about direction and speed
stored elsewhere will yield a cleaner design. Let's take a look at an example
state machine for an existing video game object.

Consider the "square" hero from the Atari game Adventure, and how we might
describe the state machine that limits the user's control of this character in
the game.

List of States:
OFF:        This is the starting state at the game select screen.
ACTIVE:     The hero is free to move.
DEAD:       The hero is in the stomach of an dragon.
WINNER:     The player has won the game. No more motion allowed.

List of Inputs:
SELECT:  The player pressed the select switch.
RESET:   The player pressed the reset switch.
CHOMP:   A dragon has swallowed the player.
VICTORY: The chalice is in the gold castle.

State Transition Table

Current   | Input:
State: | SELECT   | RESET    | CHOMP     | VICTORY
----------+----------+----------+-----------+----------
OFF       | OFF      | ACTIVE   | OFF {*}   | OFF {*}
----------+----------+----------+-----------+----------
ACTIVE    | OFF      | ACTIVE   | DEAD      | WINNER
----------+----------+----------+-----------+----------
----------+----------+----------+-----------+----------
WINNER    | OFF      | ACTIVE   | WINNER{*} | WINNER{*}
----------+----------+----------+-----------+----------

The transistions marked with {*} should never occur.  In the real game
there is logic to prevent the player from being eaten after winning the
game.  Its helpful to consider these unexpected interactions in your
game designs.

Can you think of some actions to attach to this state machine?  Clearly
the RESET input should change the position of the hero in the game world.
Can you imagine a state machine to handle the player carrying and dropping
game objects?

----

As a last note, we have considered so far that only one input can happen at
a time. In the real world it is possible for inputs to happen simultaneously.
Or if not exactly at the same time, then within the time it takes for the
state machine to come finish processing one input and getting a chance to
process another input. For example, the user can press the select and reset switches at roughly the same time.

As a programmer you must deal with simultaneous inputs in one of two main ways:

1. Assign a different priority to all inputs.  The highest priority input is
always handled first.  Lower priority inputs are handled after, or ignored.

2. Create a new input that is a combination of multiple inputs. So if SELECT
and RESET are pressed at the same time, the input to the system becomes
SELECT_AND_RESET.  This approach can cause the number of inputs to balloon
exponentially if applied liberally.  It can be really useful on a limited
basis.

============================================================================

Exercises:
----------
1. Generate a state machine for a light with two control switches.  Changing
the position of either switch will toggle the light on/off.  Assume only one
switch can change at any time. Provide the lists of states, inputs and
transitions.

2. Add a "REFUND" input to the PENNY GUMBALL MACHINE specification above to let
the user get their penny back.

3. BONUS CHALLENGE:  Pick an element of an existing Atari VCS game and create
a state machine for the behavior of the element.

#2 ScumSoftOFFLINE

ScumSoft

Moonsweeper

• 373 posts
• Location:Polysorbate 60

Posted Sun May 15, 2011 5:18 PM

Better late than never?

#3 Random TerrainONLINE

Random Terrain

Visual batari Basic User

• 28,646 posts
• Controlled Randomness
Replay Value
Nonlinear
• Location:North Carolina (USA)

Posted Tue May 24, 2011 6:40 AM

An adapted version of lesson 7, along with the rest of the lessons so far, can be viewed here:

www.randomterrain.com/atari-2600-memories.html#assembly_language

#4 jdroseOFFLINE

jdrose

Chopper Commander

• 119 posts

Posted Tue Jan 3, 2012 6:03 PM

Great article.

#5 SheddyOFFLINE

Sheddy

Dragonstomper

• 726 posts
• Location:UK

Posted Sun Jan 8, 2012 7:10 AM

0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users