The following figure shows the general process that the finite state machine will follow.

When the robot is turned on, it will automatically start with State 0. This is to make sure the robot can move forward and follow the line to the next room in the maze. As long as the intersection is not detected, it will keep running State 0. The moment an intersection is detected, it will trigger the change to State 1 but it will not be going there right away. We are using Timer 1 to delay the transition for a certain amount of time so that the robot is in the center of the room. It will still be executing State 0 until Timer 1 has overflowed. All of this can be represented with the following flow chart.

Once the transition has occurred, it will go to State 1 and then spin in place. In order to implement the finite state machine, the structure of our main program will be changed. The code that was in the main loop will need to be removed. As a starting point, you should have just the label and the rjmp loop instruction.

loop:

    // all other code has been removed

    rjmp loop

From here, the code can be broken into three parts. One section is used to determine the appropriate state to execute. Another section will produce the output needed for State 0 and the last section will handle the output needed for State 1. In later labs, modifications will be made to the sections as needed but the general structure will stay the same. This can be represented by the following diagram.

loop:
    // Code to determine which state to execute
    // Will branch or jump to appropriate labels


    // Code for State 0 output
    // Will branch or jump to endloop label when done

    // Code for State 1 output
    // Will branch or jump to endloop label when done

endloop:
    rjmp loop

For the first section, we will need to create a variable to keep track of the next state to execute and to check what value it is. Variables are different from registers in that the data is saved in SRAM and it cannot be accessed by the CPU directly. While this may seem like a downside, it does not take up one of the 32 registers and will persist as long as the program is running. It will help with the problem of running out of registers to hold data in and can be retrieved at any time. To define this SRAM variable, you will need to use the following format.

table: .BYTE 4

The first column is the label assigned to the SRAM address being reserved for the variable. You can use any name as long as it is valid. In this case, we want to call it next_state. The second column defines the data type. It can be in terms of bytes (8 bit values) or words (16 bit values). We will typically be dealing with bytes but be aware of the alternatives. The third column indicates the number of SRAM address to reserve. This is more or less the size of the variable. The example variable will reserve 4 bytes of space for the variable called table. Use this knowledge to define the next_state variable which needs only one byte of space. One final detail about defining SRAM variables is that it must be placed in a different section of our program as SRAM is part of the data segment while FLASH is part of the code segment. What this means is that you will need to insert the following lines above .CSEG

.INCLUDE 

.DSEG
next_state: .BYTE 1

.CSEG
.ORG 0x0000
RST_VECT:

One common misconception people have about defining SRAM variables is that everything is ready to go once it has been defined. However, the starting value of the variable has not been defined. It will default to whatever value is currently at that SRAM address, which could potentially be any value. This means every SRAM variable will also need to be initialized in order to prevent any errors with calculations or checking which state to execute. The initialization is done by saving the desired value from a register to the SRAM variable. For the finite state machine, we want to define a value to represent the states. We will be defining the binary value of 00 as state 0 and 01 as state 1 as shown below with equate statements. From there, you can save the appropriate value.

// Equate statements
.EQU S0=0b00
.EQU S1=0b01

// Variable initialization
ldi r16, S0
sts next_state, r16

Now we can handle the code to determine what state to execute. As shown in the diagram at the beginning of the section, the main loop will begin by checking if next_state is equal to S0 or S1. As it is stored in an SRAM variable, you will need to load it into a register in order to perform a comparison as shown below.

loop:
    lds r17, next_state
    cpi r17, S0
    breq state0
    cpi r17, S1
    breq state1
    rjmp endloop

This will check what the value of next_state is for that iteration of the loop and branch to the appropriate state. If it does not match any of the valid states, it will not execute the code and go to the end of the loop. With that out of the way, we can focus on defining the code for State 0.