maze

maze1.1.cpp

// Assignment 07: maze.cpp
// Program that raverses mazes on a right-hand rule basis.
// Author: Daniel Vasquez 
// Date: Nov. 17th, 2011

#include <iostream> 
using std::cin; 
using std::cout;  

enum Direction { DOWN, RIGHT, UP, LEFT };

const int SIZE = 12;  //Assume the maze is always square

// function prototypes

// This function is invoked recursively in the solution provided by the text.  
void mazeTraversal( char maze[][ SIZE ], const int & xStart, const int & yStart,
   const int & xCoord, const int & yCoord, const Direction & dir );

// This function prints the maze
void printMaze( const char[][ SIZE ] );

//This function returns 'true' if the move is valid
bool validMove( const char maze[][ SIZE ], const int & row, const int & col );

//This function returns 'true' if we have exited the maze.
//NOTE: It is possible we exited the maze at the point that we entered 
//      (our solution should check for this possibility),
//      but if our algorithm is correct, this will only happen if there 
//      was no other exit from the maze.
bool coordsAreEdge( const int & x, const int & y );

int main()
{

// /*

// Maze 1
char maze[ SIZE ][ SIZE ] =
    { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
      {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
      {'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
      {'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
      {'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
      {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
      {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
      {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
      {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };

   int xStart = 2; // starting X and Y coordinates for maze
   int yStart = 0;
   Direction INITIAL_DIR = RIGHT;

// */

/*

// Maze 2
  char maze[ SIZE ][ SIZE ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
  {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
  {'#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '.', '.'},
  {'#', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
  {'#', '.', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
  {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
  {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'},
  {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };


   int xStart = 2; // starting X and Y coordinates for maze
   int yStart = 11;
   Direction INITIAL_DIR = LEFT;

*/

/* 

// Maze 3
   char maze[ SIZE ][ SIZE ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
  {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
  {'#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '.', '.'},
  {'#', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
  {'#', '.', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
  {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
  {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
  {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
  {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };


   int xStart = 2; // starting X and Y coordinates for maze
   int yStart = 11;
   Direction INITIAL_DIR = LEFT;

*/

   int x = xStart; // current X and Y coordinates
   int y = yStart;

   mazeTraversal( maze, xStart, yStart, x, y, INITIAL_DIR );

   system("pause");

   return 0;
} // end main



// This function prints the maze
void printMaze( const char maze[][ SIZE ] )
{

	for ( int row = 0; row < SIZE; row++ )
	{
		for ( int col = 0; col < SIZE; col++ )
		{
			cout << maze[row][col] << ' ';
		}
		cout << '\n';
	}
} // end of printMaze function

// This function is invoked recursively in the solution provided by the text.  
void mazeTraversal( char maze[][ SIZE ], const int & xStart, const int & yStart,
   const int & xCoord, const int & yCoord, const Direction & dir )
{
	int row = xCoord;
	int col = yCoord;
	Direction newDir = dir;
	
	switch( dir )
	{
		case DOWN:
			if ( validMove( maze, xCoord, yCoord - 1 ) )
			{	
				col--;
				newDir = LEFT;
				break;

			} else if ( validMove( maze, xCoord + 1, yCoord ) ){
				row++;
				break;

			} else if ( validMove( maze, xCoord, yCoord + 1 ) ){
				col++;
				newDir = RIGHT;
				break;

			} else {
				row--;
				newDir = UP;
				break;
			}
		
		case RIGHT:
			if ( validMove( maze, xCoord + 1, yCoord ) ){
				row++;
				newDir = DOWN;
				break;

			} else if ( validMove( maze, xCoord, yCoord + 1 ) ){
				col++;
				break;

			} else if ( validMove( maze, xCoord - 1, yCoord ) ){
				row--;
				newDir = UP;
				break;

			} else {
				col--;
				newDir = LEFT;
				break;
			}

		case UP:
			if ( validMove( maze, xCoord, yCoord + 1 ) ){	
				col++;
				newDir = RIGHT;
				break;

			} else if ( validMove( maze, xCoord - 1, yCoord ) ){
				row--;
				break;

			} else if ( validMove( maze, xCoord, yCoord - 1 ) ){
				col--;
				newDir = LEFT;
				break;

			} else {
				row++;
				newDir = DOWN;
				break;
			}

		case LEFT:
			if ( validMove( maze, xCoord - 1, yCoord ) ){	
				row--;
				newDir = UP;
				break;

			} else if ( validMove( maze, xCoord, yCoord - 1 ) ){
				col--;
				break;

			} else if ( validMove( maze, xCoord + 1, yCoord ) ){
				row++;
				newDir = DOWN;
				break;

			} else {
				col++;
				newDir = RIGHT;
				break;
			}

		default:
			cout << "Error: Direction must be 0, 1, 2, or 3. dir = " << dir;
			break;
	}

	maze[row][col] = 'P';
	maze[xCoord][yCoord] = 'X';
	printMaze( maze );
	//system("pause");
	//system("cls");
	cout << "\nHit enter key to see next move\n\n";
	if ( coordsAreEdge( row, col ) )
	{
		if ( (row == xStart) && (col == yStart) ){
			cout << "\nArrived back at the starting location.\n\n";

		} else {
			cout << "\nMaze successfully exited!\n\n";
		}
	} else {
		
		mazeTraversal( maze, xStart, yStart, row, col, newDir );
	}

} // End of mazeTraversal function

//This function returns 'true' if the move is valid
bool validMove( const char maze[][ SIZE ], const int & row, const int & col )
{
	if ( maze[row][col] == '#' )
	{
		return false;
	}

	return true;
} // end of validMove function

//This function returns 'true' if we have exited the maze.
bool coordsAreEdge( const int & x, const int & y )
{
	if ( x == 0 || x == (SIZE-1) )
	{
		return true;
	}
	else if ( y == 0 || y == (SIZE-1) )
	{
		return true;
	}

	return false;
} // end of coordAreEdge function