Header

#include <stdio.h>
#include <stdlib.h>

#include "scanner.h"
#include "maze.h"

struct maze
{
	int startX, startY;//coordinates for the starting point
	int finishX, finishY; //coordinates for the finish point

	int rows, cols; //the number of rows and columns in the 2D arrays

	int **maze; //holds the encodings
	char **visits; //holds the path
};

//these are the prototypes for our static functions
static Maze createMaze(int rows, int columns);
static void initializePath(Maze newMaze, FILE *fp);
static int step(Maze maze, int row, int column);
static void debugPrint(Maze maze);
static void displayRowTop(Maze maze, int row, int columns);
static void displayRowContent(Maze maze, int row, int columns);
static void displayBottom(Maze maze, int rows, int columns);


static int getCellHasTop(Maze maze, int row, int column);
static int getCellHasBottom(Maze maze, int row, int column);
static int getCellHasRight(Maze maze, int row, int column);
static int getCellHasLeft(Maze maze, int row, int column);
static char getVisit(Maze maze, int row, int column);
static void setVisit(Maze maze, int row, int column, char visit);

//will call createMaze to allocate memory and will initialize the 2D arrays
Maze initializeMaze(FILE *fp)
{
	int rows = readInt(fp);
	int cols = readInt(fp);

	Maze newMaze = createMaze(rows, cols); //allocates memory
	initializePath(newMaze, fp);//initializes values in the path

	//TODO: INITIALIZE MAZE
   int i, j;
	for(i = 0; i < rows; ++i)
   {
	for( j = 0; j < cols; ++j)
     newMaze->maze[i][j] = readInt(fp);
}
	//debugPrint(newMaze); //Used for testing initializetion

	return newMaze;
}

//the next 4 functions check if there is a wall on top, bottom, right, or left
static int getCellHasTop(Maze maze, int row, int column)
{
	return maze->maze[row][column] & 1;
}

static int getCellHasBottom(Maze maze, int row, int column)
{
	return maze->maze[row][column] & 4;
}

static int getCellHasRight(Maze maze, int row, int column)
{
	return maze->maze[row][column] & 2;
}

static int getCellHasLeft(Maze maze, int row, int column)
{
	return maze->maze[row][column] & 8;
}

//these two functions will handle updating and getting values from the visits array
//these make for more readable code than accessing the array directly
static char getVisit(Maze maze, int row, int column)
{
	return maze->visits[row][column];
}

static void setVisit(Maze maze, int row, int column, char visit)
{
	maze->visits[row][column] = visit;
}

//takes in a maze and calls step to start backtracking, provides the starting
//point as the first point to visit in the maze
void findPath(Maze maze)
{
	//TODO: MAY NEED TO ALTER THIS FUNCION TO HANDLE SPECIAL CASE
	step(maze, maze->startX, maze->startY);
}

static int step(Maze maze, int row, int column)
{
	//TODO: FINISH THE BACKTRACKING ALGORITHM
   int i,j;
   //int st;
   int successful;
   //maze->maze[row][column] = st;

   if(getVisit(maze, row, column) == maze->maze[maze->finishX][maze->finishY])
   {
       displayMaze(maze);
       return 1;
   }
 // findPath(maze);
   displayMaze(maze);
   getchar();
//	getVisit(maze, row, column);//gets pos
   for(i = -2; i <= 2; ++i)
   {
      for(j = -2; j <= 2; ++j)
      {
        //i*i != j*j dont move in diagonal
		 //row+i >= 0 && row + i < n, bounds checking
		 //col+j >= 0 && col+j < n, bounds checking
        if(i*i != j*j && row+i >= 0 && column+j >= 0 )
        {
          getVisit(maze, row, column);//Gets position
            if(getCellHasTop(maze, row, column + 1) != 1)//Wall check, Zero meaning NO WALL
            {
                     //++st;
                     //gets that position and sees if it is unvisited...
                     //need a test if it is visited.. if it has been visited before.. Set current spot as BAD_PATH
                     if(getVisit(maze,row,column+j) == UNVISITED)
                     {
		                setVisit(maze, row, column+1, GOOD_PATH);
                      successful = step(maze, row, column + 1);
                     }
                  // if(getVisit(maze, row, column+j) == GOOD_PATH)
                  //   {
                  //   setVisit(maze, row-i, column, BAD_PATH);
              //   successful = step(maze, row, column+j);
                //      }
                     if(successful)
			           return 1;
            }
            if(getCellHasLeft(maze,row - 1,column) != 1)
            {
                     if(getVisit(maze, row-1, column) == UNVISITED)
                     {
                     setVisit(maze, row-1, column, GOOD_PATH);
                     successful = step(maze, row-1, column);
                     }

                  //   if(getVisit(maze, row-i, column) == GOOD_PATH)
                   //  {
                  //setVisit(maze, row-i, column, BAD_PATH);
                  // successful = step(maze, row-i, column);
                   //  }
                     //++st;
                     if(successful)
                    return 1;
            }
            if(getCellHasRight(maze,row + 1, column) != 1)
            {
                     if(getVisit(maze, row+1, column) == UNVISITED)
                     {
                      setVisit(maze, row+1, column, GOOD_PATH);
                      successful = step(maze, row+1, column);
                     }

                   //  if(getVisit(maze, row+i, column) == GOOD_PATH)
      //               {
        //            setVisit(maze, row+i, column, BAD_PATH);
          //            successful = step(maze, row+i, column);
            //        }
                     //++st;
                     if(successful)
                    return 1;
            }
            if(getCellHasBottom(maze, row, column - 1) != 1)
            {
                     if(getVisit(maze, row, column-1) == UNVISITED)
                     {
                      setVisit(maze, row, column-1, GOOD_PATH);
                      successful = step(maze, row, column-1);
                     }

          //           if(getVisit(maze, row, column-j) == GOOD_PATH)
            //       {
              //        setVisit(maze, row, column-j, BAD_PATH);
                //    successful = step(maze, row, column-j);
                  //   }
                     //++st;
                     if(successful)
                    return 1;
            }
            //PART 2
            //Do not do else if because then each one would require... That is last resort
        if(getCellHasTop(maze, row, column + 1) == 0)//Wall check
            {
                     //++st;
                     //a test if it is visited.. if it has been visited before.. Set current spot as BAD_PATH
                     if(getVisit(maze,row, column+1) == GOOD_PATH)
                   {
                      setVisit(maze, row, column, BAD_PATH);
                      successful = step(maze, row, column + 1);
                    }
                    if(successful)
                  return 1;
            }
           if(getCellHasLeft(maze,row - 1,column) == 0)
            {
                     if(getVisit(maze, row-1, column) == GOOD_PATH)
                     {
                   setVisit(maze, row, column, BAD_PATH);
                    successful = step(maze, row-1, column);
                    }
       //++st;
                   if(successful)
                return 1;
     }
    if(getCellHasRight(maze,row + 1, column) == 0)
            {
                    if(getVisit(maze, row+1, column) == GOOD_PATH)
                    {
                     setVisit(maze, row, column, BAD_PATH);
                     successful = step(maze, row+1, column);
                    }
                     //++st;
          if(successful)
         return 1;
           }
           if(getCellHasBottom(maze, row, column - 1) == 0)
       {
                    if(getVisit(maze, row, column-1) == GOOD_PATH)
     {
                      setVisit(maze, row, column, BAD_PATH);
                      successful = step(maze, row, column-1);
                    }
                     //++st;
                     if(successful)
                  return 1;
           }
            //Part 3
           if(getCellHasRight(maze, row + 1, column) != 0 && getCellHasLeft(maze,row - 1, column) != 0)// If there is a wall at those locationsZZ
            {
                    if(getVisit(maze,row, column+1) == BAD_PATH)
                     {
                     setVisit(maze, row, column, BAD_PATH);
          successful = step(maze, row, column-1);
                     }
                     if(successful)
                    return 1;
     }
           if(getCellHasTop(maze, row, column + 1) != 0 && getCellHasBottom(maze, row, column - 1) != 0)
       {
                     if(getVisit(maze, row-1, column) == BAD_PATH)
                     {
                     setVisit(maze, row, column, BAD_PATH);
                      successful = step(maze, row+1, column);
                    }
                   if(successful)
                  return 1;
         }
            if(getCellHasTop(maze, row, column +1) != 0 && getCellHasBottom(maze, row, column - 1) != 0)
          {
                  if(getVisit(maze, row+1, column) == BAD_PATH)
               {
             setVisit(maze, row, column, BAD_PATH);
                 successful = step(maze, row-1, column);
                  }
             if(successful)
          return 1;
           }
   }
   }
}
  displayMaze(maze);
   getchar();
   return 0;
}
//this function handles allocating memory for the 2D arrays
static Maze createMaze(int rows, int columns)
{
   int i;
	Maze newMaze = malloc(sizeof *newMaze);
	newMaze->rows = rows;
	newMaze->cols = columns;

	//TODO: ALLOCATE THE 2D ARRAYS
   newMaze->visits = malloc(rows * sizeof(char*));
   for(i = 0; i < rows; ++i)
	newMaze->visits[i] = malloc(columns * sizeof(char));
   newMaze->maze = malloc(rows * sizeof(int*));
   for(i = 0; i < rows; ++i)
	newMaze->maze[i] = malloc(columns * sizeof(int));

	return newMaze;
}

//this function handles initializing the values in the visits array
static void initializePath(Maze newMaze, FILE *fp)
{
	//TODO: INITIALIZE THE VISITS ARRAT. REMEMBER TO USE THE DEFINES IN .h
   newMaze->startX  = readInt(fp);
   newMaze->startY  = readInt(fp);
   newMaze->finishX = readInt(fp);
   newMaze->finishY = readInt(fp);
   int i,j;

   for(i = 0; i < newMaze->rows; ++i)
    {

      for(j = 0; j < newMaze->cols; ++j)
         newMaze->visits[i][j] = UNVISITED;

     }
      newMaze->visits[newMaze->startX][newMaze->startY] = START;
      newMaze->visits[newMaze->finishX][newMaze->finishY] = FINISH;
}

//used only for debugging purposes
static void debugPrint(Maze maze)
{
	int i,j;
	printf("Maze\n");
	for(i = 0; i < maze->rows; ++i)
	{
		for(j = 0; j < maze->cols; ++j)
		{
			printf("%d ", maze->maze[i][j]);
		}
		printf("\n");
	}

	printf("Visits\n");
	for(i = 0; i < maze->rows; ++i)
	{
		for(j = 0; j < maze->cols; ++j)
		{
			printf("%c ", maze->visits[i][j]);
		}
		printf("\n");
	}
}

//The next four functions handle displaying the maze
void displayMaze(Maze maze)
{
	int i;
	for(i = 0; i < maze->rows; ++i)
	{
		displayRowTop(maze, i, maze->cols);
		displayRowContent(maze, i, maze->cols);
	}
	displayBottom(maze, maze->rows, maze->cols);
}

void displayRowTop(Maze maze, int row, int columns)
{
	int i;
	for(i = 0; i < columns; ++i)
	{
		printf("+");
		if(getCellHasTop(maze, row, i)) //checks if wall is needed
			printf("---");
		else
			printf("   ");
	}
	printf("+\n");
}

void displayRowContent(Maze maze, int row, int columns)
{
	int i;
	for(i = 0; i < columns; ++i)
	{
		if(getCellHasLeft(maze, row, i)) //checks if wall is needed
			printf("|");
		else
			printf(" ");
		printf(" %c ",getVisit(maze,row, i));
	}
	if(getCellHasRight(maze, row, columns - 1))
		printf("|\n");
	else
		printf("\n");
}

void displayBottom(Maze maze, int rows, int columns)
{
	int i;
	for(i = 0; i < columns; ++i)
	{
		printf("+");
		if(getCellHasBottom(maze,rows-1,i))
			printf("---");
		else
			printf("   ");
	}
	printf("+\n");
}

void freeMaze(Maze maze)
{
	//TODO: FREE THE MEMORY FOR THE MAZE
   //TODO: FREE THE MEMORY FOR THE MAZE
   free(maze->cols);
   free(maze->rows);
   free(maze->visits);
   free(maze->maze);
   free(maze);

}