Maze Lab 1

Your goal for this maze lab is to write a program that will present a two-dimensional maze to a human player and then get input from the player as he or she attempts to go through the maze.  You will utilize the Maze class, the interface for which is given below.  The constructor function for this class generates and displays a random maze.  A member function, move, is used to move up, right, down, or left (if possible) and to report whether the requested move could be made and, if so, whether it took the player out of the maze.  The program should get input from the player, utilize the move member function to move, and terminate the program if a move takes the player out of the maze.  Further, the program should update the graphic display to show the current cell in the maze and perhaps also to show which cells have been visited.  For this lab, you will use the arrow keys to get input from the player.  However, you will have one or more later labs where you will update this maze program so that it gets input from a joystick or a custom hardware device called a MIPPET.  Hence, we recommend encapsulating the input part of the program in a function getCommand, enabling the program easily to be switched from keyboard to joystick or MIPPET input by making changes only in getCommand.

If you are not yet proficient with loops, you can follow this model, whose purpose is to repeat the block statement delimited by the curly braces until the maze has been solved:
     do
     {  getCommand (. . .);
        . . .
        move (. . .);
        . . .
     }
     while ( ! out_of_maze );

The maze class has the following interface.  There is a bit more in the complete header file, basemaze.h, but you don't need to know any more than what is listed below.

class Maze {
public:
    Maze (int nrows,  // number of rows;
          int ncols); // number of columns;
          // this constructor function generates and displays a maze,
          // initializing curpos so that you start in the upper left cell.
    void move (Direction d, // Direction is an enumerated type with the
                            // following values: North, South, East, West;
               bool & move_success,  // i.e., you didn't bump into a wall;
               bool & exit_success); // when you reach the lower rt. cell,
               // you are viewed as having solved and exited the maze.
    bool canMove (Direction d) const; // i.e., won't bump into wall.
    bool atExit ( ) const; // i.e., reached lower rt. cell.
    Color getColor (int row, int col) const; // row and col are 0 to 2,
                    // specifying subcell in 3X3 grid in curr. maze cell.
    void setColor (int row, int col, Color c); // ditto.
private:
    BasicMaze<bool> * maze; // the private member variable maze is a
                            // pointer to the maze data.
    int x_size, y_size; // these variables store the maze dimensions.
    MPosition curpos; // this variable stores the curr. pos. in the maze.
};

The function getKey will allow you to get single keypresses from the person solving the maze.  If you have the declaration
  Key k;
you can use the function as follows:
  k = getKey ();
Key is an enumerated type, with the following values:  UP_KEY, DOWN_KEY, RIGHT_KEY, LEFT_KEY, HOME_KEY, END_KEY, ESCAPE_KEY, NO_KEY.  (NO_KEY means no key in this list was pressed.)  You will use statements like
  if (k == UP_KEY) ...
You may want to use the ESCAPE_KEY to allow the player to terminate the program even if the maze isn't solved, and you may want to use the HOME_KEY to allow the player to request a new maze..

Similarly the colors are an enumerated type, with the following values: White, Black, Red, Green, Blue, Yellow, Magenta, Cyan, Purple, DarkGray, LightGray.  Colors can be created by specifying the RGB values, if you know what that means (if not, don't worry about it); you can, for example, create your own color plum:
   Color Plum ( 150, 25, 100 );  // Note that each argument ranges from 0 to 255

Your program should start with the following include:
  #include "Basemaze.h"
It should not  #include "ccc.h"
Bazemaze.h contains most of the non-graphic aspects of ccc.h, e.g., strings, bool, etc., but adds to them the RowanGraphics implementation and the Maze class.

Since this is our first graphics project, be sure to follow the Instructions on Creating a Graphics Application.  See the updated web page Using Horstmann's CCC Library or the Rowan Graphics Library in Visual C++ projects for changes in C++ settings.  Note that after your program has run, you must click on the close button (X in a box) at the top right of the window.

You will prepare three or more versions of this program for this lab.  Each successive version of the program should retain the capabilities of the previous versions and add some new ones.  A good start is a "Hello, World"-style program that does nothing more than define and thus display a maze; if you run it and see a maze, then you know that you can access the RowanGraphics library, for example.  As you gradually add capabilities to this initial version of the program, you might want to introduce mode or version variables, that will allow you easily to select among the various capabilities.  You might have, for example, a display_mode variable which specifies how previously-visited maze cells will be displayed.  For grading purposes, you should demonstrate or submit version 3 and (if you could do it) version 4.  You will probably want to start with a small maze, e.g., 5 x 5, and later change to a larger one, e.g., 15 x 15.  Note that each maze cell consists of a 3 x 3 grid of subcells whose color can be retrieved or changed using the getColor and setColor functions.

1. Display the current position in the maze.  You might first set just the middle subcell of the current maze cell to a special color; later you should set the complete cell to the special color.
    Here is a 3 x 3 maze:
(maze destination or "exit" is here at bottom right of maze)

2. Highlight all maze cells which have been visited, as well as displaying the current position in the maze.

3. Show the path followed, as well as displaying the current position in the maze.  Note that when you backtrack to a cell which is a choice point and then go in a different direction, that cell will have a "T" in it (perhaps a sideways or upside-down "T").  Challenge: can you erase the "trail" as you backtrack, so that the path displayed does not include any side trips that dead-ended and has no "T"s in it?

4. (Optional / extra credit.)  Add the ability for the player to request the display of a solution, using the following simple algorithm for solving a maze: start at the entrance to the maze with your left hand touching the wall on your left, and walk forward, turning as necessary, so that your hand always is in contact with a wall until you exit from the maze.  Stated another way, move left (i.e., turn left and move forward) if possible; if not, move forward if possible; if not, move right if possible; if not, do a 180-degree turn and move forward to the maze cell that you just came from.  (This algorithm works only if the maze has no cycles or "loops" in it; the mazes generated by the Maze class constructor have no cycles.)  Implement this approach to solving the maze, and show the path followed, as in 3, above.  Challenge: can you show the path in the style of the following illustration?