ECE2036_Lab3.htm



ECE
2036                                                                                                                   Spring 2015


Lab
3: Robot Obstacle Course


Assigned:
February 9, 2015                                                   Section
B: Due February 24, 2015


Section A: Due
February 25, 2015


 


In this lab we will be adding to our Robot class so
that a Robot object can automatically move from a starting location to a target
location on an obstacle course.  We will
also be creating a new class called Map. 
Map will have a private data member which is a 2d array (matrix) of ones
and zeros.  Objects of class Map will be
used to store the obstacle course, and to track the path followed by the
robot. 


This lab will be accomplished in three stages:


1.  In the
first stage, you will program the robot to move from a user-specified starting
location to a user-specified target location with no obstacles present.  The coordinates of both locations will be
input as integer x and y values on a 20-by-20 grid.  Each time the robot moves, it can move by one
step forward (+1 in the y direction), backward (-1 in the y direction), right
(+1 in the x direction), or left (-1 in the x direction).  The decision about which direction to move
should be made as follows: the robot should calculate the distance from its
current location to the target location in both x and y directions, and move
along the direction corresponding to the longest distance.


Examples:


·       if
the current robot location is (x=1, y=1) and the target is at (5, 10), the
robot should move one step forward, to (1, 2).


·       if
current location is (1,1) and the target is at (10, 5), the robot should move
one step right, to (2, 1).


·       if
current location is (12, 12) and the target is at (1, 7), the robot should move
one step left, to (11, 12).


·       if
current location is (12, 12) and the target is at (10, 2), the robot should
move one step backward, to (12, 11).


After each step the robot should record its current
location in an object of class Map whose purpose is to track the robot’s
path.  The robot should then recalculate
the distance to the target along each direction and take the next step
according to the same rules given above. 
This process should continue until the robot arrives at the target; at
which time the program prints a diagram of the path followed by the robot and
exits.


Alternatively you can use a different robot motion
algorithm than the one given above, but if you choose to do this, your
algorithm MUST involve an equal number or fewer steps taken from start to
finish compared to the algorithm above, for any combination of starting and
target locations.


 


O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


O  * 
*     
     
     
     
     
    O


O   
*  *   
     
     
     
     
    O


O   
  *  * 
     
     
     
     
    O


O   
    * 
*     
     
     
     
    O


O   
     
*  *   
     
     
     
    O


O   
     
  *  * 
     
     
     
    O


O   
     
    * 
*     
     
     
    O


O   
     
     
*  *   
     
          O


O   
     
     
  *  * 
     
     
    O


O   
     
     
    * 
*     
     
    O


O   
     
     
     
*  *   
     
    O


O   
     
     
     
  *  * 
     
    O


O   
     
     
     
    * 
*     
    O


O   
     
     
     
     
*  *   
    O


O   
     
     
     
     
  *   
    O


O   
     
     
     
     
     
    O


O   
     
     
      
     
     
  O


O   
     
     
     
     
     
    O


O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 


Example output, showing path of robot for starting location of
(1, 1) and target location of (15, 15). 
Locations visited by the robot are indicated with a ‘*’.


 


2.  In the
second stage, you should add the ability to scan in an obstacle map file
containing a 20-by-20 matrix of zeros and ones, where ones represent obstacles
that the robot can’t penetrate.  This map
will be stored as an object of class Map. 
For this stage all obstacles will be simple and convex.  Your robot must be programmed to find a path
around obstacles to the target.  This
should be done as follows.  After
determining the direction the robot should step as described in part 1, the
robot should determine if an obstacle is blocking that step.  If not, the step proceeds as before.  If so, the robot should
attempt to step in the ‘next best’ direction.
  If this fails, the robot should attempt to
step in the third best direction, and so on. 
The proper ranking of directions can be illustrated by example:


For a current location of (1, 1) and a target
location of (5, 10), the best direction is forward, the next best direction is
right, the third best direction is left, and the worst direction is backward.


After each step, the robot should record its current
location (as before) in an object of class Map whose purpose is to track the
robot’s path.  This continues until the
robot reaches the target, at which time the program prints to the screen a
diagram of the obstacle map with the robot’s path superimposed on it, and
exits.  As before, an alternative
algorithm can be chosen, but it must be equally or more efficient than the one
described above for all obstacles.


 


O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


O  * 
*     
     
     
     
     
    O


O   
*  *   
*  *  * 
*  *   
     
     
    O


O   
  *  * 
*  O  O  O  * 
*  *   
     
      O


O   
   O  O  O  O  O  O  O  *   
         
  O


O   
    O  O  O  O  O  O  O  *  * 
         
  O


O   
  O  O  O  O  O  O  O  O  O  * 
     
      O


O   
  O  O  O  O  O  O  O  O  O  * 
     
      O


O   
  O  O  O  O  O  O  O  O  O  * 
     
      O


O   
    O  O  O  O  O  O  O    * 
         
  O


O   
    O  O  O  O  O  O  O    * 
         
  O


O   
     
  O  O  O   
    * 
     
      O


O   
     
     
     
  *  * 
          O


O   
     
     
     
    * 
*     
    O


O   
     
     
     
     
*  *   
    O


O   
     
     
     
     
  *   
    O


O   
     
     
     
     
     
    O


O   
     
     
     
     
     
    O


O   
     
     
     
     
     
    O


O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 


Example
output, showing path of robot around a simple obstacle.
  Robot starting location was (1,1) and target location was (15,15) as before.  Obstacle points are indicated with ‘O’
characters, robot path indicated with ‘*’ characters.


 


3.  In the
final stage, the robot should be programmed to handle ‘dead end’ obstacles by
retracing its steps.  This should be
accomplished as follows.  As before, the
robot will keep a map recording where it has been (separate from the obstacle
map).  Before taking each step, in
addition to avoiding obstacles, the robot must avoid stepping into any location
it has already visited.  If the robot
ends up in a location where all possible steps are either blocked by an
obstacle or have been previously visited, the robot should retrace its steps
until it reaches a location where it has an unblocked and unvisited location it
can step into.  I recommend accomplishing
this by keeping a vector record of every move taken by the robot.  With each new step, use push_back
to add the move to the vector.  If the
robot needs to retrace steps, read the last move from the end of the vector,
force the robot to make the opposite move (e.g. if the last move was forward,
force the robot to step backward), and then delete the move that was just
undone from the end of the vector using pop_back. 


 


 O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 O 
*  *  * 
*  *  * 
*  *  * 
*  *  * 
*  *  * 
*  *  *  O


 O 
*  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 O 
*  *  * 
*     
     
     
     
      O


 O 
     
*  *   
     
     
     
     O


 O 
     
  *  * 
     
     
     
      O


 O 
     
    * 
*     
     
     
      O


 O 
     
     
*  *   
     
     
      O


 O 
     
     
  *  * 
     
     
      O


 O     
     
     
*  *   
     
     
  O


 O 
     
     
     
*  *   
     
      O


 O 
     
     
     
  *  * 
     
      O


 O 
     
     
     
    * 
*     
      O


 O 
     
     
     
     
*  *   
      O


 O 
     
     
     
     
  *  * 
      O


 O 
     
     
     
     
    * 
      O


 O 
     
     
     
     
     
      O


 O 
     
     
     
     
     
      O


 O 
     
     
     
     
     
      O


 O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 


Example of
an obstacle course where the robot was forced to retrace its steps.


 


 O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 O 
*  *   
     
     
     
     
      O


 O 
  *  O  O  O  O  O  O  O     
         
    O


 O 
*  *  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  * 
*  *  * 
*  *  O 
     
     
      O


 O 
*  O  O  O  O  O  O  O  O   
     
     
    O


 O 
*  *  * 
*  *  * 
*  *  * 
*  *   
     
      O


 O 
     
     
     
  *  * 
     
      O


 O 
     
     
     
    * 
*     
      O


 O 
     
     
     
     
*  *   
      O


 O 
     
     
     
     
  *  * 
      O


 O 
     
     
     
     
    * 
      O


 O 
     
     
     
     
     
      O


 O 
    
     
     
     
     
      O


 O 
     
     
     
     
     
      O


 O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O


 


Another
example.


Detailed
Lab Programming Requirements


Your code must consist of the following 5 files: Map.h, Map.cpp, Robot.h,
Robot.cpp, and main.cpp.  I will provide
the main.cpp file.  Your final code must
use the main.cpp file that I provide with no alterations, although you are
encouraged to temporarily alter the main.cpp file during your development
process.  All data members of class Map
and class Robot must be private.  Your
Map class must have a private data member which is a 2d array of bools or ints.  Your Robot class must have two private data
members of class Map: one to store the obstacle course, and one to record the
robot’s path.  Otherwise you are free to
design your code as you see fit.  I
recommend using an enum class to represent the
directions. 


I will provide the obstacle course map files shown
above so that you can test your code. 
When you are checked off by the TA, s/he will use a different set of
obstacle map files to test your code.


Attached
files


main.cpp


Empty
field map


Easy
barrier map


Simple
trap map


Another
trap map


Lab
3 Checkoff Sheet


Useful
example:  scanning in a text file to a
C++ program


Here is a sample member function of class Map that
scans in the mapfile. 
You can copy this code if you wish.


// you must
include header fstream in order to compile and run
the following function


#include
<fstream>


 


void Map::scanFile()


{


  ifstream
inputFile;


 


  inputFile.open(mapfile“, ios::in);


 


  for (int i = 0; i
< size; i++)


  {


    for (int j = 0; j < size; j++)


      inputFile
>> data[i][j];


   }  


}