Assignment 2 – Maze Traversal using C programming

60-141 – Introduction to Programming II
The following grid is a double-subscripted array representation of a maze.

The # symbols represent the walls of the maze, and the periods (.) represent squares in the possible paths through the maze. There’s a simple algorithm for walking through a maze that guarantees finding the exit (assuming there’s an exit). If there’s not an exit, you’ll arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you’ll arrive at the exit of the maze. There may be a shorter path than the one you have taken, but you’re guaranteed to get out of the maze.
For this assignment, the initial maze will use 1’s instead of #’s and 0’s instead of .’s, leading to the representation of the maze above in the form:
111111111111
100010000001
001010111101
111010000101
100001110100
111101010101
100101010101
110101010101
100000000101
111111011101
100000010001
111111111111
Your task is to:
Write a complete, well documented C program to walk through the maze, starting from the maze entrance location, and attempts to locate the exit from the maze.
Requirements and Hints:
1. Given the input maze, your program logic will: a. Find the maze entrance (start point, see Figure below) from the left side of the input maze (first column)
b. Then, start to traverse the maze to find the next valid move
c. If the movement is valid and it is not the maze exit (i.e. a coordinate on the maze edge, including the starting position)
i. place character X in that location in the path
ii. print the current state of the maze
iii. Go back to step (b)
d. Steps b. and c. will continue until finding the maze exit coordinate.
2. This solution assumes that there is only one entrance on the left edge of the maze and one exit on any other edges of the given maze (including the left edge). So, there are only two zeroes (one for entrance and one for exit) on the edges.
3. Your program should implement at least the following functions:
a) void findStart(), that will find the start point from the first column of the input maze (maze[][1]).
b) void mazeTraversal( ), is a recursive function that gives maze, current x and y coordinate and direction as an input. There are four valid directions of up, down, left and right. Also, the first (X,Y) coordinate to call mazeTraversal function is the found start point (maze entrance).
c) void printMaze( ), that will print the current state of the maze after each movement.
d) int validMove( ), that will determine the validity of the next movement (input coordinates).
e) int coordsAreEdge( ), that check the input coordinate are edge or not.
Declaration of maze data, or Input:
A 12-by-12 character array representing the maze that has 1 symbols showing the walls of the maze and zeroes (0) showing squares in the possible paths through the maze. You can get the maze from a file or easily declare the maze data in main() of your program, manually.
Output
Placing the character X in each square in the path and displaying the maze after each move so the user can watch as the maze is solved. (Note that a move can revisit a square with an X in it.)
Sample declaration of maze data, or input:
char maze[12][12] ={ {‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’, ‘1’},
{‘1’, ‘0’ ,‘0’ ,‘0’ ,‘1’, ‘0’, ‘0’ ,‘0’ ,‘0’ ,‘0’ ,‘0’ ,‘1’},
…
}
You can complete the above two-dimensional maze array definition from the following Figure 1.
Figure 1. Sample maze layout for Assignment #2.
Sample output:
If you run your program in interactive mode, one move at a time, then the output sequence shown below is reasonable for the example maze shown in Figure 1:
…
1 1 1 1 1 1 1 1 1 1 1 1
1 X 0 0 1 0 0 0 0 0 0 1
X X 1 0 1 0 1 1 1 1 0 1
1 1 1 0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 1 0 1 0 0
1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 0 1
1 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
Hit return to see next move
1 1 1 1 1 1 1 1 1 1 1 1
1 X X 0 1 0 0 0 0 0 0 1
X X 1 0 1 0 1 1 1 1 0 1
1 1 1 0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 1 0 1 0 0
1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 0 1
1 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
Hit return to see next move
…
However, for generating the output from the program for submitting for marks, simply output the final pathway or failure to solve the maze (e.g. Entrance, but no Exit). This is shown below in Figure 2 for a successful maze traversal, using the strategy of touching one’s right hand to the wall to the right; note that this solution is not unique – other correct solutions can be determined using various strategies:
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 1
0 0 1 0 1 0 1 1 1 1 0 1
1 1 1 0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 1 0 1 0 0
1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 0 1
1 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
Maze Entrance point
Maze Exit
Figure 2. Final maze traversal for sample shown in Figure 1.
Requirements:
– Write and document a complete C program that is capable of satisfying the requirements of this assignment problem.
– The question can use of I/O redirection. Please review the textbook for an example on using I/O redirection from flat files.

111111111111
1XXX1XXXXXX1
XX1X1X1111X1
111X1XXXX1X1
1XXXX111X1XX
1111X1X1X1X1
1XX1X1X1X1X1
11X1X1X1X1X1
1XXXXXXXX1X1
111111X111X1
1XXXXXX1XXX1
111111111111

Answer:

/*
Title: Assignment #2: Maze Traversal
Objective: Create a program to walk through the maze, starting from the maze
entrance location and attempts to locate the exit from the maze.
*/

//Includes
#include <stdio.h>//C-Preprocessor Directives
#include <stdlib.h>//C-Preprocessor Directives

#define ROW  12
#define COL 12
#define RIGHT 1
#define LEFT  3
#define UP    2
#define DOWN  0

//Function Prototypes
void findStart( char maze[][ COL ] );//find the start point from the first column of the input maze (maze[][1])
void mazeTraversal( char maze[ ROW ][ COL ], size_t xDir, size_t yDir, int dir );//gives maze, current x and y coordinate and direction as an input
void printMaze(  char maze[][ COL ] );//print the current state of the maze after each movement
int validMove(  char maze[][ COL ], size_t r, size_t c );//determine the validity of the next movement (input coordinates)
int coordsedge( size_t x, size_t y );// position the input coordinate are edge or not

//Declaration for the coordinates of the starting point in the maze
int firstXCor, firstYCor;

//main function
int main(){
   // Declare the Maze data array

    char maze[ ROW ][ COL ] =
   { { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
     { '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
     { '0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1'},
     { '1', '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '1'},
     { '1', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0'},
     { '1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
     { '1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
     { '1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
     { '1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
     { '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1'},
     { '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'},
     { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'} };

   //Call the function findStart() to look for the zero in the first column
   findStart(maze);
   //Call the function mazeTraversal()
   mazeTraversal( maze, firstXCor, firstYCor, RIGHT );
}//end of main function

/*
	Objective: find the start point from the first column of the input maze (maze[][1])
	input: an array
	output: first position in the maze
*/
void findStart( char maze[][ COL ]){
	int x;
	firstYCor = 0;
	for ( x = 0; x < ROW; ++x ) {
	  //position if the element in the first column is zero
      if ( maze [x][firstYCor] == '0') {
		    //Decide the coordinate(location) of the zero element in the first column only
			firstXCor = x;
			return;
		}
	}
}

/*
	Objective: This is a recursive function that gives maze, current x and y coordinate and direction as an input
	input: maze array, first coordinate for X and Y
	output: Decide the next move
*/
void mazeTraversal( char maze[ ROW ][ COL ], size_t xDir, size_t yDir, int dir ){
    //Declare and set the start position to zero
   int position = 0;
	//Set the x in the entrance position
   maze[ xDir ][ yDir ] ='x';
   //Call the printMaze() function to display the array
   printMaze( maze );

   //This is to check if we are in the starting position
    if ( xDir == firstXCor && yDir == firstYCor && position == 1 ) {
      printf( "\n***Starting position***\n" );
      return;
    }

	  //check if we are not in the starting position
    else if( (coordsedge( xDir, yDir ) && xDir != firstXCor) && yDir != firstYCor ) {
      printf( "\n***Done***\n" );
      return;
   }

   else {
	   //Declare counter n and next move variables
	  int n,next;
      position = 1;
        //loop through the four direction
        for ( n = 0, next = dir; n < 4; n++,next++, next %= 4 ) {
		 //This switch statement is used to decide the next move
         switch( next ) {
            case RIGHT:
			    //check if we have zero in the position y+1
               if ( validMove( maze, xDir, yDir + 1 ) ) {
				  //recursively call the function mazeTraversal to go one step in the DOWN direction
                  mazeTraversal( maze, xDir, yDir + 1, DOWN );
                  return;
               }
               break;
			case LEFT:
			    //check if we have zero in the position y-1
               if ( validMove( maze, xDir, yDir - 1 ) ) {
				  //recursively call the function mazeTraversal to go one step in the UP direction
                  mazeTraversal( maze, xDir, yDir - 1, UP );
                  return;
               }
               break;
			case UP:
			   //check if we have zero in the position x-1
               if ( validMove( maze, xDir - 1, yDir ) ) {
				  //recursively call the function mazeTraversal to go one step to the RIGHT direction
                  mazeTraversal( maze, xDir - 1, yDir, RIGHT );
                  return;
               }
               break;
			//The default if the move is DOWN
			default:
			   //check if we have zero in the position x+1
               if ( validMove( maze, xDir + 1, yDir ) ) {
				  //recursively call the function mazeTraversal to go one step to the LEFT direction
                  mazeTraversal( maze, xDir + 1, yDir, LEFT );
                  return;
               }
               break;
         }
      }
   }
}

/*
	Objective: print the current state of the maze after each movement
	input: An array (ROW * COL)
	output: Display the array on screen
*/
void printMaze( char maze[][ COL ] ){
   //count row and columns
   size_t x;size_t y;
   //Display the rows
   for ( x = 0; x <ROW ; ++x ) {
	  //Display the columns
      for ( y = 0; y <COL ; ++y ) {
		 //Display the maze array
         printf( "%c ", maze[ x ][ y ] );
      }
	  //to make sure the array is not displayed on the same line
      puts( "" );
   }
    //to separate each time when the array displayed by 2 break lines
    printf( "\n\n" );
}

/*
	Objective: determine the validity of the next movement (input coordinates)
	input: Array, x coordinate and y coordinate
	output: return zero or one (valid next movement or not)
*/
int validMove( char maze[][ COL ], size_t r, size_t c ){
  //make sure that we are moving through the zero and not exceeding the 2 dimension array boundary
  return ( r >= 0 && r <= 11 && c >= 0 && c <= 11 && maze[r] != '1' ) ;
}

/*
	Objective: position the input coordinate are edge or not
	input: x and y coordinate
	output: return if there is edge or not
*/
int coordsedge( size_t x, size_t y ){
   int edge;
   //check the outer walls of the maze and return 1
   if ((( x == 0 || x == 11 ) && ( y >= 0 && y <= 11 ) )||( ( x >= 0 && x <= 11 ) && ( y == 0 || y == 11 ) )) edge = 1;
   //otherwise we are inside the maze and return 0
   else edge = 0;
   return edge;
}