solver.c

/*
 
 COMP1011 milestone 3 super maze solver by Tang Ka Chun 17059339D and Tong Ka Wing 17063879D.
 
 The program will first read the diamension and the number of levels from the "config.txt" genereated by the generator.
 
 Next, read the corresponding maze level from the "maze.txt" generated by the generator to two 2D pointer variable "maze" and "shawdow". "maze" is the maze for output, "shawdow" is the maze for processing. The program is a muitple level solver so the level can be more than 1.
 
 First we will use the dead end filler to fill the maze. after that the maze will have only one single loop because the requirement of the maze can only delete one single wall from the original maze and make an imperfect maze, so there will be only 1 loop in the imperfect maze.
 
 The maze should have one long path with only 1 loop after the dead end filling. Then we constuct a path from starting point until it reach a brench road, marked as point1. next we check is the path connected the starting and ending point. if so move to next step. if not we constuct another path from the ending point untiul it reach a brench road, marked as point2. After that check again is the path connected the starting and ending. if so move to next part. if not then meaning there is a brench road for both points and need to find the shortest path from one point to the other.
 
 Then consider the loop and point1 as start and point2 as end. because only one loop is possible so there will be only two paths need to consider. First we find out which direction can point1 go and constrct a path from point1 to point2 when choosing the corresponding direction.  We choose the shorest path from those two path.
 
 Next we compare the "shawdow" maze with "maze" maze. For the cell that marked "." in the shawdow maze indicting the shortest path. If the cell in "shawdow" is "." and in "maze" is " ", then we mark the cell in "maze" to ".". Fianlly we have a original maze with only a path from start to end.
 
 Next output the maze to the user and print the maze to a text file entitled "maze_solution.txt".
 
 If there is another level of the maze haven't solved we read the next level and repeat the process above.

  **** Please make the working directory the same as the generator to ensure both program work. ******
 
 */
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

void read_diamension (int* length, int* width, int* level); // read the maze diamension from the config.txt
void read_maze (char** maze, int length, int width, int level);// read the maze content from the maze.txt
void dead_end_filler ( char ** maze, int length, int width);// fill all the dead end in the maze until it have no dead end
int check_dead_end (char ** maze, int length, int width);// check is the cell with given length and width coordinate is dead end.
void print_maze ( char ** maze, int length , int width);//print the maze
void find_start_and_end ( char ** maze , int length, int width, int* start, int* end);// scan the maze and find the starting point and the ending point.
void find_path (char **maze, int length, int width); // find the solution of the maze
int next_direction(char ** maze, int* node, int width);//to check where is the next possible step to take
void compare_solution_and_generate (char ** maze , char ** solution, int length, int width);// compare the shawdow maze with the oringal maze and then output a solution maze.
void find_shortest (char ** maze , int length, int width, int start , int end);// find the shortest path in the loop
void possible_direction ( char ** maze , int length, int width, int point, int* direction);//check how many possible direction can the current node go
void clear_dummy_path( char** maze, int length, int width);// clear the dummy path generated at the find_shortest function
int is_finish( int width, int point1, int point2);//check is the starting point and ending point are connected.
void instrcution (void); // print out the instrcutino of the maze.
void print_maze_txt (char** maze, int length, int width); //print the solution maze to txt
void clear_maze_solver (void); //clear the solver text to ensure it is empty.

int main() {
    
    instrcution();
    clear_maze_solver();
    //define the length and width and the level of the maze
    int length = 0, width = 0, level = 0;
    
    //read the diamension of the maze
    read_diamension(&length,&width,&level);
    
    //define a maze for output
    char **maze;
    maze = malloc((length)*sizeof(char*));
    for (int i = 0 ; i < length ; i++) *(maze + i) = malloc((width) * sizeof(char));
    
    //define a shawdow maze for processing
    char **shawdow;
    shawdow = malloc((length)*sizeof(char*));
    for (int i = 0 ; i < length ; i++) *(shawdow + i) = malloc((width) * sizeof(char));
    
    //read the maze level one by one and solve them one by one
    for ( int i = 1 ; i <= level ; i++){
        printf("\nSolution of level : %d\n",i);
        
        //read the corrisponding maze level to maze
        read_maze(maze,length,width,i);
        
        //read the corrisponding maze level to shawdow maze
        read_maze(shawdow,length,width,i);
        
        //fill all the dead end of the shawdow maze
        dead_end_filler(shawdow, length, width);
        
        //find the solution path of the maze
        find_path (shawdow, length,  width);
        
        //compare the shawdow maze with the original maze to get a clean maze with a shortest solution path
        compare_solution_and_generate(maze, shawdow, length, width);
        
        //print out the maze for the user
        print_maze(maze, length, width);
        
        //print the maze into text file
        print_maze_txt(maze,length,width);
        
    }
    
    // free the maze
    free(maze);
    
    // free the shawdow maze
    free(shawdow);
}

//read the diamension in the config.txt file which is generated by the maze generator
void read_diamension (int* length, int* width, int* level){
    FILE* fptr;
    fptr = fopen("config.txt","r");
    fscanf(fptr,"%d %d %d",length,width,level);
    fclose(fptr);
}

//read the maze content according to the level if level is above 1 then will ignore the previosus level. read the maze one character by one character when counter '\n' then add one to line_counter until it have read all the content of that maze level
void read_maze (char** maze, int length, int width,int level){
    char dummy;
    int x = 0 , y = 0 , line_counter = 0;
    FILE *fptr;
    fptr = fopen("maze.txt","r");
    
    //read the previous level that we dont want to read into the maze
    while ( line_counter != ((level-1) * length)){
        while ((dummy = fgetc(fptr)) != '\n'){
        }
        line_counter++;
    }
    
    //read the maze level that we wanted read the line character by charater and counter \n up date the x by one indicate next line.
    while ( line_counter != (level * length)) {
        while ((dummy = fgetc(fptr)) != '\n'){
            maze[x][y] = dummy;
            y++;
        }
        x++;
        y = 0;
        line_counter++;
    }
    
    //close the file
    fclose(fptr);
}

//scan the map until all dead end is filled. use check_dead_end function to check whatever the cell is dead end if so fill it up
void dead_end_filler ( char ** maze, int length, int width){
    int counter = 0;
    
    //if there is at least one dead end in the maze, then continue the filling.
    while ( counter != 1 ){
        counter = 1;
        
        // scan thought each cell of the maze
        for (int i = 1 ; i < length-1 ; i++){
            for (int j = 1 ; j < width-1 ; j++){
                //if the cell is dead end fill the space with wall
                if (maze[i][j] == ' ' && check_dead_end(maze,i,j) == 3){
                    maze[i][j] = '#';
                    counter = 0;
                }
            }
        }
    }
}

//check whatever the given length and width coordinate is dead end. only one direction is free out of the four dirctions
int check_dead_end (char ** maze, int length, int width){
    int counter = 0 ;
    
    //check how many wall is among the cell and return the number
    if (maze[length-1][width] == '#') counter++;
    if (maze[length+1][width] == '#') counter++;
    if (maze[length][width+1] == '#') counter++;
    if (maze[length][width-1] == '#') counter++;
    return counter;
}

//print the maze out to the user in the program
void print_maze ( char ** maze, int length, int width){
    for (int i = 0 ; i < length ; i++ ){
        for (int j = 0 ; j < width ; j++){
            printf("%c",maze[i][j]);
        }
        printf("\n");
    }
}

//find out the solution of the maze in few step. first use the dead end filler make the maze have no dead end, and then construct the path starting from the starting point and ending point to the cell that have more than 1 direction to go then findout the shortest path from point1 to point2. Because this project have only 1 loop, therefore will be only one loop and by considering which path is shortest for linking point1 and point2, we can obtain the shortest path for the maze.
void find_path (char **maze, int length, int width){
    //define some variables for the oath finding
    int start = 0 , end = 0, node = 0, point1 = 0, point2 = 0;
    
    //get the location of the start and the end
    find_start_and_end(maze, length, width, &start, &end);
    
    //set the node to start
    node = start;
    
    //constrcut a path from start until it reach a branch cell
    while (next_direction(maze, &node, width) != 0){
        //set the cell as part of the solution
        maze[node/width][node%width] = '.';
    }
    
    //set point1 as the location of node
    point1 = node;
    
    //set the node to end
    node = end;
    
    //check is the starting and ending point is already connected with one path. if so return.
    if ( is_finish(width, point1, end) == 1) return;
    
    //constrcut a path from end until it reach a branch cell
    while (next_direction(maze, &node, width) != 0){
        maze[node/width][node%width] = '.';
    }
    
    //set point2 as the location of node
    point2 = node;
    
    //if point1 is not the same location as end mean there is a brach cell for both points. indicating have a loop and need to determine which path is the shortest for the case
    if ( point1 != end)
        if (is_finish(width, point1, point2) == 0)
            
            //find the shortest path thought the loop
            find_shortest(maze, length, width, point1, point2);
}

//scan thought the maze and chack whatever the cell is 'S' or 'G'
void find_start_and_end ( char ** maze , int length, int width, int* start, int* end){
    for ( int i = 0 ; i < length ; i++){
        for (int j = 0; j < width ; j++){
            if (maze[i][j] == 'S' ) *start = (i*width) + j;
            else if ( maze[i][j] == 'G' ) *end = (i*width) + j;
        }
    }
}

//check whatever there is only one possible direction to go, if so, then move the current node cell location one step to the possible direction and return 1 indicating node have step one step forward
int next_direction(char ** maze, int* node, int width){
    int counter = 0;
    if (maze[*node/width+1][*node%width] == ' ') counter++;
    if (maze[*node/width-1][*node%width] == ' ') counter++;
    if (maze[*node/width][*node%width+1] == ' ') counter++;
    if (maze[*node/width][*node%width-1] == ' ') counter++;
    
    //if only 1 direction update the node location.
    if (counter == 1){
        if (maze[*node/width+1][*node%width] == ' ') *node+=width;
        else if (maze[*node/width-1][*node%width] == ' ') *node-=width;
        else if (maze[*node/width][*node%width+1] == ' ') *node+=1;
        else if (maze[*node/width][*node%width-1] == ' ') *node-=1;
        return 1;
    }
    return 0;
}

//comapre the solution and the original maze, then combine them into one completed maze with the shortest path
void compare_solution_and_generate (char ** maze , char ** solution, int length, int width){
    for (int i = 0 ; i < length ; i++){
        for (int j = 0 ; j < width ; j++){
            if (solution[i][j] == '.' && maze[i][j] == ' ' ) maze[i][j] = '.';
        }
    }
}

//find the shortest path in the loop. because only have one loop and therefore there will only have 2 possible path from point1 to point2 and
void find_shortest (char ** maze , int length, int width, int start , int end){
    
    //define some variables for finding the path
    int *direction, *path_weight, counter = INT_MAX, way = -1, *mask, dummy;
    
    //declear direction indicte which direction is possible for point1
    direction = malloc(4 * sizeof (int));
    
    //declear path_weight for if we taking the corrisponding direction, how much is the path weight.
    path_weight = malloc(4 * sizeof(int));
    
    //mask is the mask for the cell location change
    mask = malloc(4 * sizeof(int));
    mask[0] = 0 - width;
    mask[1] = 1;
    mask[2] = width;
    mask[3] = -1;
    
    //initialize the pointer before using
    for (int i = 0 ; i < 4 ; i++){
        *(path_weight + i) = 0;
        *(direction + i ) = 0;
    }
    
    //get the possible direction of start
    possible_direction(maze,length,width,start,direction);
    
    //for the 4 direction if that direction is 1 we constrcut a path from point1 to point2 and record the weight
    for (int i = 0 ; i < 4 ; i++){
        if (*(direction + i) == 1){
            dummy = start + *(mask + i) ;
            maze[dummy/width][dummy%width] = ',';
            *(path_weight + i) += 1;
            while (next_direction(maze, &dummy, width) != 0){
                *(path_weight + i) += 1;
                maze[dummy/width][dummy%width] = ',';
            }
        }
        
        //clear the trial path created before to ensure it is error free
        clear_dummy_path(maze,length,width);
        
        //if the direction is 1 and the path weight is smaller than counter update the counter as the path weight
        if ( *(path_weight + i) != 0 && *(path_weight + i) < counter ) {
            counter = *(path_weight + i);
            way = i;
        }
    }
    
    //construct the path have smaller weighting as part of the solution.
    dummy = start + *(mask + way) ;
    maze[dummy/width][dummy%width] = '.';
    while (next_direction(maze, &dummy, width) != 0){
        maze[dummy/width][dummy%width] = '.';
    }
    
}

//to check how many possible direction for the starting node. ' ' indicating can pass thought.
void possible_direction ( char ** maze , int length, int width, int point, int* direction){
    if (maze[point/width+1][point%width] == ' ') *(direction + 2) = 1;
    if (maze[point/width-1][point%width] == ' ') *direction = 1;
    if (maze[point/width][point%width+1] == ' ') *(direction + 1) = 1;
    if (maze[point/width][point%width-1] == ' ') *(direction + 3) = 1;
}


//clear the dummy path created for counting the weight of the path
void clear_dummy_path( char** maze, int length, int width){
    for (int i = 0 ; i < length ; i++){
        for (int j = 0 ; j < width ; j++){
            if(maze[i][j] == ',' ) maze[i][j] = ' ';
        }
    }
}

//to check is the point1 and point2 are connected and indicating solution is found and the loop doesnot affect the solutio path.
int is_finish(int width, int point1, int point2 ){
    if ( point1 + 1 == point2) return 1;
    else if( point1 + width == point2) return 1;
    else if( point1 - 1 == point2) return 1;
    else if( point1 -width == point2 ) return 1;
    else return 0;
}

//print out the instruction
void instrcution (void){
    printf("This is a mutiple level maze solver.\nYou can sovle mutiple level of imperfect maze generated with the generator.\nPlease ensure the working directory is the same as the genereator.\n");
}

//print the maze into the text file
void print_maze_txt (char** maze, int length, int width){
    FILE *fptr;
    fptr = fopen("maze_solution.txt","a+");
 
    for (int i = 0 ; i < length ; i++){
        for (int j = 0 ; j < width ; j++){
            fprintf(fptr,"%c",maze[i][j]);
        }
        fprintf(fptr,"\n");
    }
    fclose(fptr);
    printf("solution is printed at text file.\n");
}

void clear_maze_solver (void){
    FILE * fptr;
    fptr = fopen("maze_solution.txt","w");
    fclose(fptr);
}