Part 5: Pseudocode

This section is written using pseudocode. Pseudocode is just English words or phrases that we all understand. They are not in any computer language like C, C++, Visual Basic or Java, etc. This means that well written pseudocode can be taken by any programmer and then be easily converted into the native code that that hardware requires or the programmer prefers.

Functions and Subroutines

Functions = Subroutines = Methods = Modules = Same Thing!!

If you deal with any programming languages, you will see that each one teaches one or more definitions for "A block of code that performs a specific task."

Years ago, the terms subroutine and function were used by most languages. As Object Oriented Programming grew, the terms method and module came into being. Ignoring the debate about which term is correct for a moment, I'll just say that for the purpose of this paper, these four terms are interchangeable. Since most robot code is written in C or a form of BASIC these days, and functions are common to both, I'll use the term function from now on.

And without justifying or explaining, I'll also say that there are advantages to using functions. If you don't know what I mean, it will become clearer when you study functions in whatever language you are using. What I will be doing is breaking down the larger program called "Solve a line maze." into smaller chunks of code that I will call subroutines.

Breaking Down the Program

The first reason for using functions has to do with the program structure. The maze solving program is actually going to be two programs:

  1. Robot makes a first pass through the maze to find the correct or shortest path. This usually includes identifying all dead ends and bad paths so that they can be avoided on the second pass. The path needs to be stored so the second pass can avoid all dead-end passages and/or, take the shortest route to the end.
  2. On the second pass, the robot will have discovered the shortest possible path to the goal and will follow some stored set of directions to take the quickest path through the maze.

Remember these as Program One and Program Two for the next few paragraphs.

Now, let's get very specific for a moment. The four main commands that the robot must be trained to perform correctly will be:

You could also subdivide the tasks the robot must perform into specific behaviors. This subdivision by behaviors will be beneficial here because both Program One and Program Two will need to access these behaviors, so we want to write the code only once and allow any part of either program to access these behaviors.

Robot maze solving behaviors: When the robot is traversing the maze, it will be performing one of the following main behaviors: (We will subdivide these later.)

  1. Following the line at the best possible speed. (Shown in red.)
  2. Detecting an intersection (Shown in green.)
  3. Determining the correct behavior for any intersection found. (Shown in blue.)
  4. Making a turn. (Shown in black.)

To help the reader, pseudocode will be colorcoded to indicate which of the behaviors above is taking place.

We can also say that in Program One, the robots main mission will be to detect and record all maze intersections and decide which turns were "good" and which were bad. In Program Two the mission changes. The robot should now have stored the correct direction to be taken at each intersection so that the maze can be traversed quickly and accurately. So we can refer to Program One as the "Write" phase of the program and Program Two as the "Read" phase of the program. But remember that the four behaviors just above also have to be available to the robot in both programs.

Since both Programs One and Two must be able to direct the robot to do the four behaviors above, it makes no sense to write the code for a RightTurn() function and put it into each program. So the most efficient way to do this is to write one or more functions for each of these behaviors and allow either Program One or Program Two to call on these functions.

The Big Picture

The process of defining the program in broad terms and then breaking it down into more discrete steps is often called Top-Down Design, and we will use this approach here. The first step is to state the program requirements in the broadest terms possible and then to take each part or section of the requirement and break it down into more specific actions.

Here is a first look at the program. We will then keep breaking it down until we have pseudocode that you can adapt to C or PBASIC or whatever programming language you are using.


If first time through maze, go to Program One, otherwise, go to Program Two

Program One:

- - Perform this loop until end of maze found:

. . . . At an intersection?

. . . . . If No, adjust speed and direction to go as fast as possible centered on the line.

. . . . . If Yes, determine the intersection type and decide which way to turn.

. . . . . Based on intersection type go straight, turn left, turn right or end program.

- - End Program One loop


Program Two:

- - Perform this loop until end of maze found:

. . . . Get direction of next turn from memory.

. . . . Go as fast as possible to next intersection.

. . . . At the end of the maze?

. . . . . If No, make the indicated turn.

. . . . . If Yes, end the program.

- - End Program Two loop

So, notice here, that both programs have a need for the same behaviors. Both need to travel fast on the line until an intersection is found. Both need to make the correct turn at each intersection. Both need to stop at the end of the maze. The main differences are that Program One must fumble around, go down an occasional dead end and somehow store information that will have that NOT happen in Program Two. Program Two will, theoretically, never go down a dead-end path. It can also probably speed up since it can know more about where it is going.

Why Pseudocode???

Since my students program in several languages, and each language has it's own distinct and different syntax, this paper will use pseudocode. Pseudocode is just the use of English phrases or statements that describe the action(s) to be taken. The pseudocode here can be adapted to any robotic programming language.

A turn in C for the 3PI robot might look like this:

void turn_left_90()
{
set_motors(0,255);
delay_ms(234);
set_motors(0,0);
}

...And in PBASIC (Parallax Basic) the same turn for a BOE-Bot might be:

For i = 1 to 15
...PULSOUT 14, 850
...PULSOUT 15, 650
Next

So to avoid confusion and to allow all readers to understand the process, pseudocode will be used. The pseudocode for a left turn will be simplified to:

Turn left 90 degrees

So, no matter which programming language you use, you understand that the robot needs to make a 90 degree left turn. How you write the code in C or Basic or another language depends on the specific syntax for that language, so any programmer can read the pseudocode and "translate" it into the correct source code for the language being used.

Pseudocode for Program One

Program One will decide which behavior is appropriate, then route program control to the correct function.

NOTES:

  1. The percent sign (%) is used in some languages to convert a decimal number into a binary number or in this case, a binary pattern. If 1 says this sensor is over the black line, and 0 says this sensor is over white, then the pattern %00100 says the robot is exactly over the center of the line and the pattern %01100 says either the line has moved left or the robot turned right, but in either case, the robot needs to adjust it's course to the left the get back on track.
  2. The code below repeats this loop until the end of the maze is detected: 1) Read the sensors 2)Decide next behavior 3) Execute that behavior
  3. Program One needs to store many of the turns taken, so it will call a routine named "storeThisTurn()" for those turns that need to be stored. Two turns, the Right-Only and the Left-Only are not stored because there is no choice. Other turns need to be stored. Whenever a U-Turn "U" is stored, we know the robot has just made a bad turn, so the code in storeThisTurn() needs to check this and unwind or correct the previous turn so the robot does not take the same bad turn next time through the maze.
  4. Comments are placed in parens (). They are not part of the code. They are provided to let the reader know what is happening.
  5. Color code: Red = Line Following, Green = Intersection Detection, Blue = Determine next move, Black = Execute a turn.

Do
  Gosub ReadSensors
  if sensors = %00100 then GoFastForward (Dead center - Go FAST!)
  elseif sensors = %01100 then GoSlightLeft (Just a little off to the right)
  elseif sensors = %01000 then GoMediumLeft
  elseif sensors = %10000 or %11000 then GoHardLeft
  elseif sensors = %00110 then GoSlightRight
  elseif sensors = %00010 then GoMediumRight
  elseif sensors = %00001 or %00011 then GoHardRight
  else (At an intersection if here)
    if sensors = %00000 then (Ran off the line)
      storeThisTurn(U)
      Gosub U-Turn
    if sensors = %11111 then Gosub inchForward (Go forward to check)
      If sensors = %00000 then (Only happens at a T intersection)
        storeThisTurn(L)
        Gosub LeftTurn
      If sensors = %11111 then (Only happens at end of maze)
        endProgram
      else
        storeThisTurn(Left) (Found a Four-Way intersection)
        Gosub LeftTurn
    if sensors = %11100 then gosub leftTurn (This can be a Left-Only or a Left-Straight intersection, but in either case, we go left. But only one gets stored. Find out which.)
      inchForward()
      if sensors = %00000 then gosub leftTurn
      else
        storeThisTurn(Left)
        gosub leftTurn
    if sensors = %00111 then (This can be a Right-Only or a Right-Straight intersection, so determine which)
      inchForward
      if sensors = %00000 then gosub rightTurn (This is Right-Only, so go right)
      else(Keep going straight - or do nothing)
      storeThisTurn(Straight) (But still need to record it)
Loop

leftTurn()
leftMotor = backwards; rightMotor = forwards
delay 500 (Keep turning for 1/2 second)
End leftTurn

rightTurn()
leftMotor = forwards; rightMotor = backwards
delay 500 (Keep turning for 1/2 second)
End rightTurn

U-Turn()
gosub leftTurn
gosub leftTurn
End U-Turn

storeThisTurn(whichWay)
Add whichway to the stored string of turns
(Check to see if next-to-last character is "U".)
If storedString, length - 1 = "U" then
  Record last three characters
  Chop off last three characters
    If lastThree = LUL then replace with S
    If lastThree = LUR then replace with U
    If lastThree = LUS then replace with R
    If lastThree = RUL then replace with U
    If lastThree = RUR then replace with S
    If lastThree = RUS then replace with L
    If lastThree = SUL then replace with R
    If lastThree = SUR then replace with L
    If lastThree = SUS then replace with U
End storeThisTurn