Assembly Language Programming - Lesson 7 - State Machines - 2600 Programming For Newbies

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:



http://www.nist.gov/dads/HTML/finiteStateMachine.html



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:

-------

           (task done)            (Reset)

    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.