MazeSolver

//Name: Stephen Ku
//Created on: 10/29/18
//Title: Project 4
//Due Date: 11/6/2018 12PM
//Course: CSCI 235

#include "MazeSolver.h"
#include <string>
#include <fstream>
#include <iostream>
#include <array>
#include <stack>

//constructor
//pre: input file is in correct format with first two values being integers
//      followed by valid maze characters in {'_', '*','$'}
//post: if input file cannot be read outputs "Cannot read from input_file"
//      otherwise sets maze_rows_ and maze_columns_ from the first two values in input file
//      and allocates two 2-dimesional array of size maze_rows_ and maze_columns_
//      both maze_ and solution_ are initialized with characters read from input
MazeSolver::MazeSolver(std::string input_file)
{
    Position pos;
    pos.row = 0;
    pos.column = 0;
    std::ifstream in_stream;
    in_stream.open(input_file);
    if(!in_stream.is_open())
    {
        std::cout << "Cannot read from " << input_file << std::endl;
    }
    else
    {
        in_stream >> maze_rows_;
        in_stream >> maze_columns_;
        // std::cout << maze_rows_ << std::endl;
        initializeMaze(maze_rows_, maze_columns_);
        fillMaze(in_stream);
        initializeSolution();
        // solution_[0][0] = '>';                                               //initializes starting position with '>' character
        // backtrack_stack_.push(pos);
        mazeIsReady();
    }
    in_stream.close();
}

// destructor
//post: deletes maze_ and solution_
MazeSolver::~MazeSolver()
{
    if(maze_ready == false)                                                 //checks if maze was initialized
    {
        maze_ = nullptr;
        solution_ = nullptr;
    }
    else
    {
        for(int i = 0; i < maze_rows_; i++)                                 //deletes maze_ character array
        {
            delete [] maze_[i];

        }
        delete [] maze_;
        maze_ = nullptr;
        for(int j = 0; j < maze_rows_; j++)                                 //deletes solution_ character array
        {
            delete [] solution_[j];

        }
        delete [] solution_;
        solution_ = nullptr;
    }
}

bool MazeSolver::mazeIsReady()
{
    if((maze_rows_ > 0)&&(maze_columns_ > 0))                               //if maze_rows_ and maze_columns_ greater than 0, input file has been read
    {
        maze_ready = true;                                              //sets maze_ready as true
        //returns true if mazeIsReady is called
    }
    else
    {
        maze_ready = false;                                             //if maze_rows_ and maze_columns unchanged, maze is not ready
    }
    return maze_ready;
}

bool MazeSolver::solveMaze()
{
    Position curr_position;                                                 //instantiates curr_position of datatype curr_position
    curr_position.row = 0;                                                  //initialize curr_position's row as 0
    curr_position.column = 0;                                               //initialize curr_position's row as 0
    bool solve = false;
    // std::cout << "solving..." << std::endl;
    backtrack_stack_.push(curr_position);
    // backtrack_stack_.pop();
    while(!backtrack_stack_.empty())
    {
        // std::cout << "in while" << std::endl;
        if(solution_[(curr_position).row][(curr_position).column] == '$')   //if current position is '$', exit has been found
        {
            std::cout << "Found the exit!!!" << '\n';
            std::cout << "The solution to this maze is:" << '\n';
            printSolution();
            solve = true;
            break;
        }
        else if(extendPath(curr_position) == true)                          //checks curr_position for extending in South then East direction
        {
            solution_[(curr_position).row][(curr_position).column] = '>';
            curr_position = backtrack_stack_.top();                             //current position = top of the stack
        }
        else
        {
            // std::cout << "else" << std::endl;
            backtrack_stack_.pop();
            maze_[curr_position.row][curr_position.column] = 'X';
            solution_[curr_position.row][curr_position.column] = '@';
            // std::cout << "end else" << std::endl;
            if (backtrack_stack_.empty()){
                break;
            }
            curr_position = backtrack_stack_.top();                             //current position = top of the stack

        }
    }
    // std::cout << "done while" << std::endl;

    if(solve == false)
    {
        std::cout << "This maze has no solution." << '\n';
        std::cout << "The solution to this maze is:" << '\n';
        printSolution();
    }
    return solve;
}

void MazeSolver::printSolution()
{
    for(int i = 0; i < maze_rows_; i++)                                     //for loop that moves through each row of array
    {
        for(int j = 0; j < maze_columns_; j++)                              //for loop that retrieves each column value for each row
        {
            std::cout << solution_[i][j] << " ";                            //outputs column value for each row then goes to next line, repeat
        }
        std::cout << "\n";
    }
}

void MazeSolver::initializeMaze(int rows, int columns)
{
    maze_ = new char *[rows];                                               //intitializes maze_ character array by allocating space
    for(int i = 0; i < rows; i++)
    {
        maze_[i] = new char[columns];
    }
}

void MazeSolver::fillMaze(std::ifstream& input_stream)
{                                                                           //fills position row by column
    for(int i = 0; i < maze_rows_; i++)                                     //fills maze_ character array with values from input file using input_stream
    {
        for (int j = 0; j < maze_columns_; j++)
        {
            input_stream >> maze_[i][j];
        }
    }
}

void MazeSolver::initializeSolution()
{
    solution_ = new char *[maze_rows_];                                      //initializes solution_array
    for(int k = 0; k < maze_rows_; k++)
    {
        solution_[k] = new char[maze_columns_];
    }
    copyMazetoSolution();                                                    //fills array with characters from input file
}

//copies position values from maze_ to solution_
void  MazeSolver::copyMazetoSolution()
{
    for(int i = 0; i < maze_rows_; i++)
    {
        for(int j = 0; j < maze_columns_; j++)
        {
            solution_[i][j] = maze_[i][j];
        }
    }
}

bool MazeSolver::extendPath(Position current_position)
{
    // std::cout << "extendPath" << std::endl;
    bool extended = false;
    if(isExtensible(current_position,SOUTH))                        //if SOUTH valid move, then try moving south, push current position onto stack
    {
        backtrack_stack_.push(getNewPosition(current_position, SOUTH));
        extended = true;
    }

    if(isExtensible(current_position,EAST))                         //if EAST, then try moving EAST. if move still valid, continue to try moving EAST, push current postion onto stack
    {
        backtrack_stack_.push(getNewPosition(current_position, EAST));
        extended = true;
    }
    // std::cout << "end extendPath" << std::endl;

    return extended;
}

Position MazeSolver::getNewPosition(Position old_position, direction dir)
{
    Position NewPosition;

    if(dir == SOUTH)
    {
        NewPosition.row = (old_position.row + 1);                           //if direction is SOUTH, y+1, x stays the same
        NewPosition.column = old_position.column;
    }
    if(dir == EAST)
    {
        //if direction is EAST, y stays the same, x+1
        NewPosition.column = (old_position.column + 1);
        NewPosition.row = (old_position.row);                           //if direction is SOUTH, y+1, x stays the same
    }
    return NewPosition;
}

bool MazeSolver::isExtensible(Position current_position, direction dir)
{
    bool extensible = false;

    if(dir == SOUTH)
    {
        if((current_position.row+1) < maze_rows_)
        {
            if(maze_[(current_position.row+1)][current_position.column] == '_')         //checks if direction is SOUTH, if the next character is '_', and if the next row value is within the maze
            {
                extensible = true;
            }
            else if(maze_[(current_position.row+1)][current_position.column] == '$')        //checks if direction is SOUTH, if the next character is '$', and if the next row value is within the maze
            {
                extensible = true;
            }
            else if(maze_[(current_position.row+1)][current_position.column] == 'X')      //checks if direction is SOUTH, if the next character is 'X', and if the next row value is within the maze
            {
                extensible = false;
            }
            else if(maze_[(current_position.row+1)][current_position.column] == '*')        //checks if direction is SOUTH, if the next character is '*', and if the next row value is within the maze
            {
                extensible = false;
            }
        }
    }
    if(dir == EAST)
    {
        if((current_position.column+1) < maze_columns_)
        {
            if(maze_[current_position.row][(current_position.column+1)] == '_')         //checks if direction is SOUTH, if the next character is '_', and if the next row value is within the maze
            {
                extensible = true;
            }
            else if(maze_[current_position.row][(current_position.column+1)] == '$')        //checks if direction is SOUTH, if the next character is '$', and if the next row value is within the maze
            {
                extensible = true;
            }
            else if(maze_[current_position.row][(current_position.column+1)] == 'X')        //checks if direction is SOUTH, if the next character is 'X', and if the next row value is within the maze
            {
                extensible = false;
            }
            else if(maze_[current_position.row][(current_position.column+1)] == '*')        //checks if direction is SOUTH, if the next character is '*', and if the next row value is within the maze
            {
                extensible = false;
            }
        }
    }
    return extensible;
}


int main() {
    MazeSolver solver("input5.txt");
    if(solver.mazeIsReady())
    {
        solver.solveMaze();
        solver.printSolution();
    }
    return 0;
}