IGNORED

# Assembly Language Programming - Lesson 7 - State Machines

## Recommended Posts

```Assembly Language Programming - Lesson 7 - State Machines:

--------------------------------------------------------

The next topic I want to raise is the idea of a state machine.

All digital computers are state machines.  Therefore the Atari

2600 is a state machine.  It will be easier to program a

computer/the-VCS if you understand the basic principles of state

machines.

Here is a link to website that I want to borrow the definition

for a state machine from:

Here is the basic definition from that website:

"finite state machine

Definition: A model of computation consisting of a set of

states, a start state, an input alphabet, and a transition

function that maps input symbols and current states to a next

state. Computation begins in the start state with an input

string. It changes to new states depending on the transition

function. There are many variants, for instance, machines having

actions (outputs) associated with transitions (Mealy machine) or

states (Moore machine), multiple start states, transitions

conditioned on no input symbol (a null) or more than one

transition for a given symbol and state (nondeterministic finite

state machine), one or more states designated as accepting

states (recognizer), etc.  Also known as finite state automaton."

---------

Lets break this definition down and look at each part:

"A model of computation consisting of a set of states" - This is

just fancy talk saying that you can do all the things a computer

can do on a piece of paper.  You can model a computer on paper,

or maybe a computer models work done on a piece of paper.  Its

one of those twilight-zone things.   The computer and the model

of the computer are equivalent.  The only difference is how long

it takes for each to complete the same job. Every computer has a

set of special circuits called registers.   Registers hold bits

of information, 1's and 0's.   All of the register bits in a

computer together form the "state" of the computer.  In future

lessons, I will introduce you to the registers in the Atari VCS,

but for now all you need to know is that they are there and they

are apart from your program.

"a start state" -  When you turn on a computer, electricity

floods into the circuits of the machine.   At that point all the

registers are scrambled and their state is unknown.   Luckily,

the designers of the hardware included reset circuits that force

at least some of the registers into a known state.  Just enough

of a known state so that the computer can start running a

program, your program.  When you turn on a VCS, the system

powers up to its start state.  It goes to a specific place in

the memory of the plugged in cartridge and begins executing the

program it finds there.

"an input alphabet" - The input alphabet is Assembly language

code!  It also includes all the switches and input ports on the

machine to a lesser degree.   You write a program using the

"alphabet" of assembly language instructions that the

microprocessor in the VCS is made to process.

"and a transition function that maps input symbols and current

states to a next state" - The transition function is implemented

by circuits in the machine that fetch the instructions

(alphabet) of the program and update the registers (state) of

the VCS based on what that input symbol (Assembly code

instruction) is.  When you learn to program in assembly language

what you are really learning is the transition function.   When

you know the transition function of the VCS (state machine),

then you will be able to string the instructions of the

computer's alphabet into programs (input string) that generate

the series of states that result in a video game.

"Computation begins in the start state with an input string"  -

Computation is what computers do.;)  I already defined the

start state.   The input string is your program code and the

variables you use to store changing information about the game.

--------

Now we get to a real mind bender.  Your program generates a

sequence of states within the VCS that render all the  graphics

and audio and player control that make up your game.  That

sequence is a subset of ALL THE POSSIBLE sequences of states

that a VCS can do.   In a way, your programming a VCS is like a

sculptor carving a statue from a large stone block.   The

sculptor cuts away the excess rock and leaves behind the desired

shape of stone.   Likewise, as a programmer you will cut away

all the excess sequences of states that the VCS can perform and

leave behind only the sequences that form your game.

--------

So from that reasoning we can see that it may make sense to look

at a video game as a state machine.  Or really as a series of

state machines.    Once you get down into the details of a

program you will find that there is no way your mind can keep

track of all possible sequences of states, so you will need to

break the program down into manageable problems (small sets of

simple states)  that you can understand.  A very common

programming approach is called top down design, and I think it

is a good place to start as a beginning programmer.   You take

the large problem of a program (the top) and break it down

repeatedly into smaller and smaller chuncks.   Eventually those

chunks become so small that they are individual Assembly

language instructions.  Lets take a look at a common video game

as a high-level state machine.    Let's look at Combat. Combat

is a very common game so its easy to use as a reference.   You

can even plug it in an refer to the game as you read my

explanation.

As we learned above, all state machines have an initial state,

and all video games are state machines, so Combat is a state

machine and it has an initial state.   Lets call that intial

state RESET.

In the reset state the program sets all of the registers in the

VCS to a known state, then it transistions the ATTRACT state.

(done)

RESET  ---------->  ATTRACT

(initial state)

In the ATTRACT state the Combat game draws the playfield with

different colors than those used during play.  It waits for the

user to push the Select, Reset, or difficulty switches.   If the

difficulty switches are changed, the program updates the state

of machine (not the game, the machine we are looking at Combat

from a simplfied/high level), and remains the ATTRACT game

state.   Likewise if the select button is pressed the machine

state is updated to show a new game option, but the game stays

in ATTRACT mode.   The only way to leave attract mode is to

press Reset.   Pressing reset transitions the game to PLAY mode.

(done)                 (Reset)

RESET  ---------->  ATTRACT  ---------> PLAY

In the PLAY game state the game timer begins counting down, and

the players controls are read and used to update the machine

state to reflect the game play.   The PLAY state is exited if

the player pushes Select, or the game timer runs out.  In either

case it returns to the ATTRACT mode.

Combat:

-------

RESET  ---------->  ATTRACT  ---------> PLAY

(initial state)            ^                  |

|                  |

|  (timer/select)  |

+------------------+

This is very simple state model for Combat.  Each of these

high-level states can be broken down into several smaller more

informative states.   Eventually, breaking the model down to

enough detail you reach the sequence of states that are the

individual Assembly language instructions in the Combat program.

As a programmer you will want to break the large problem of a

video game into smaller problems that you can reasonably tackle

one at a time until the complete game is done.

---------

Exercise:

Pick an Atari cartridge and create a high-level state diagram

for the game as I did above for Combat.   Provide as many states

as you feel like doing.   Post your diagram to this thread so

others can see it.   Its a pain to make diagrams in ASCII as I

did, so you may want to draw them in a painting program and then

post the picture in this thread.

```

##### Share on other sites

This sounds pretty intuitive.

I remember a 1970s interview with Nolan Bushnell who stated that using a joystick or paddle to interact with the computer via the TV screen was a low level of programming.

Rob Mitchell, Atlanta, GA

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
• ### Recently Browsing   0 members

• No registered users viewing this page.
×
×
• Create New...