/*******************************************************************************************
* MazeGenerator
* This program will generate a maze based on user input in adherence to the
* following requirements:
* (1) Mazes are generated using depth-first searching. See
* https://en.wikipedia.org/wiki/Maze_generation_algorithm
* (2) (BONUS) A second maze-generation algorithm is implemented
* (3) There is exactly one S starting location
* (4) There is one or more G goal locations
* (5) Walls are generated as X
* (6) Corridors are generated as _
* (7) The user is allowed to select the size of the maze
* (1x2 is the minimum possible size)
* (Limit the user to 100 to a side)
* (8) All G goals are reachable and at the end of corridors
* (9) All _ corridors are reachable
* (10) (BONUS) The ability for the user to indicate the addition of rooms
* (11) The maze is solved with a Breadth-First approach
* (12) Mazes can be saved to .txt file(s)
* (13) Mazes can be loaded from .txt file(s)
* (14) The program loops until exited
*
* Grading Considerations Include:
* The program is written in C++. It is error-free and has been thoroughly
* unit-tested by multiple people.
* The program has a refined user-interface in which the users expectations
* are met.
* The program adheres to the StyleGuide (comments, clean code, and
* functions).
* The program is submitted on-time and according to the Submission
* Instructions
*
* Author: Abigail Mott
* Date: 5/8/2025
* Time Spent: lots and lots and lots and lots
*******************************************************************************************/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <stack>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm> // random stuff

using namespace std;

// maze size
int width = 0;
int height = 0;
bool loop = true;

// 2 = wall, 3 = start, 4 = goal, 5 = path, 6 = solution path
vector<vector<int>> maze;

struct position {
    int xPos, yPos;
};

// key positions
position startPos;
position goalPos;
position currentPos;

stack<int> xknownLoc;
stack<int> yknownLoc;

// for backtracking
stack<position> pathStack;

// for input stuff
double doubleCheck = 0.0;
int userInput = 0;

/****************************************************************
 * tryCatch 
 * Ensures user input is a valid integer.
 ****************************************************************/
void tryCatch() {
    bool validInput = false;
    do {
        cin >> doubleCheck;
        if (cin.fail() || doubleCheck != static_cast<int>(doubleCheck)) {
            cout << "\nInvalid input! Please give me a number: ";
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            validInput = false;
        }
        else {
            userInput = static_cast<int>(doubleCheck);
            validInput = true;
        }
    } while (!validInput);
}

/****************************************************************
 * menu 
 * Displays the main menu with options for the user.
 ****************************************************************/
void menu() {
    cout << "======== Maze generator & Solver ========\n";
    cout << "    1. generate new maze\n";
    cout << "    2. solve current maze with bfs\n";
    cout << "    3. load maze from file\n";
    cout << "    4. exit the program\n";
    cout << "choose (1-4): ";
}

/****************************************************************
 * amountMaze  
 * gets width and height from user, validates sizes
 ****************************************************************/
bool amountMaze() {
    cout << "What is the width of the maze going to be?\n";
    tryCatch();
    width = userInput;
    cout << "What is the height of the maze going to be?\n";
    tryCatch();
    height = userInput;

    // only force odd sizes if width and height are >= 3
    if (width >= 3 && width % 2 == 0) width--;
    if (height >= 3 && height % 2 == 0) height--;

    bool invalid = false;

    // allow these small sizes explicitly
    bool smallValid = (width == 1 && height == 2) || (width == 2 && height == 1) || (width == 2 && height == 2);

    // invalid if width or height less than 1 or 1x1, unless smallValid
    if ((width < 1 || height < 1) || (width == 1 && height == 1) || !smallValid && (width < 3 || height < 3)) {
        cout << "Can't work, try again please! The smallest maze I can do is 1x2, 2x1, 2x2, or odd sizes >= 3\n";
        invalid = true;
    }

    return invalid;
}



/****************************************************************
 * printMaze 
 * prints the maze with characters
 ****************************************************************/
void printMaze() {
    for (int j = 0; j < height; j++) {
        for (int i = 0; i < width; i++) {
            if (maze[i][j] == 2) cout << "X";
            else if (maze[i][j] == 3) cout << "S";
            else if (maze[i][j] == 4) cout << "G";
            else if (maze[i][j] == 6) cout << ".";
            else cout << " ";
        }
        cout << "\n";
    }
}

/****************************************************************
 * saveMazeToFile 
 * writes maze to a file
 ****************************************************************/
void saveMazeToFile(const string& filename) {
    ofstream outFile(filename);
    if (outFile.is_open()) {
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                if (maze[i][j] == 2) outFile << "X";
                else if (maze[i][j] == 3) outFile << "S";
                else if (maze[i][j] == 4) outFile << "G";
                else if (maze[i][j] == 5) outFile << " ";
                else if (maze[i][j] == 6) outFile << ".";
                else outFile << "X";
            }
            outFile << "\n";
        }
        outFile.close();
        cout << "Maze successfully saved to " << filename << "\n";
    }
    else {
        cout << "Unable to open file for saving\n";
    }
}

/****************************************************************
 * loadMazeFromFile 
 * gets maze data from file + tracks S and G
 ****************************************************************/
void loadMazeFromFile(const string& filename) {
    ifstream inFile(filename);
    if (inFile.is_open()) {
        maze.clear();
        string line;
        int row = 0;
        while (getline(inFile, line)) {
            vector<int> currentRow;
            for (int col = 0; col < (int)line.size(); col++) {
                char c = line[col];
                if (c == 'X') currentRow.push_back(2);
                else if (c == 'S') {
                    currentRow.push_back(3);
                    startPos.xPos = col;
                    startPos.yPos = row;
                }
                else if (c == 'G') {
                    currentRow.push_back(4);
                    goalPos.xPos = col;
                    goalPos.yPos = row;
                }
                else if (c == '.') currentRow.push_back(6);
                else currentRow.push_back(5);
            }
            maze.push_back(currentRow);
            row++;
        }
        inFile.close();

        // fix dimensions
        width = (int)maze.size();
        height = (int)maze[0].size();

        cout << "Maze loaded from file:\n";
        printMaze();
    }
    else {
        cout << "Unable to open the file to load the maze\n";
    }
}

/****************************************************************
 * getNeighbors 
 * finds unvisited spots to move into
 ****************************************************************/
vector<position> getNeighbors(position pos) {
    vector<position> neighbors;
    int dx[] = { 0, 2, 0, -2 };
    int dy[] = { -2, 0, 2, 0 };
    for (int i = 0; i < 4; i++) {
        int nx = pos.xPos + dx[i];
        int ny = pos.yPos + dy[i];
        if (nx > 0 && ny > 0 && nx < width - 1 && ny < height - 1) {
            if (maze[nx][ny] == 2) {
                neighbors.push_back({ nx, ny });
            }
        }
    }
    return neighbors;
}

/****************************************************************
 * generateMaze 
 * generates maze using depth first search
 ****************************************************************/
void generateMaze() {
    // fill with walls for all sizes first
    maze = vector<vector<int>>(width, vector<int>(height, 2));

    // handle tiny maze cases explicitly
    if ((width == 1 && height == 2) || (width == 2 && height == 1)) {
        // start at (0,0)
        currentPos.xPos = 0;
        currentPos.yPos = 0;
        maze[0][0] = 3;  // start

        // goal at the other cell
        if (width == 1 && height == 2) {
            maze[0][1] = 4;  // goal
        }
        else if (width == 2 && height == 1) {
            maze[1][0] = 4;  // goal
        }
    }
    else if (width < 3 || height < 3) {
        // for 2x2 or other small sizes (but not 1x2 or 2x1)
        currentPos.xPos = (1 < width) ? 1 : 0;
        currentPos.yPos = (1 < height) ? 1 : 0;
        maze[currentPos.xPos][currentPos.yPos] = 3; // start

        int goalX = width - 1;
        int goalY = height - 1;
        maze[goalX][goalY] = 4;
    }
    else {
        // normal maze generation logic starts here

        // start in top left-ish
        currentPos.xPos = 1;
        currentPos.yPos = 1;
        maze[currentPos.xPos][currentPos.yPos] = 3;

        // clear history
        while (!xknownLoc.empty()) xknownLoc.pop();
        while (!yknownLoc.empty()) yknownLoc.pop();
        xknownLoc.push(currentPos.xPos);
        yknownLoc.push(currentPos.yPos);

        srand(time(nullptr));

        while (!xknownLoc.empty()) {
            bool moved = false;

            // try all directions
            vector<pair<int, int>> directions;

            if (currentPos.xPos - 2 > 0 && maze[currentPos.xPos - 2][currentPos.yPos] == 2)
                directions.push_back({ -2, 0 });
            if (currentPos.yPos + 2 < height && maze[currentPos.xPos][currentPos.yPos + 2] == 2)
                directions.push_back({ 0, 2 });
            if (currentPos.xPos + 2 < width && maze[currentPos.xPos + 2][currentPos.yPos] == 2)
                directions.push_back({ 2, 0 });
            if (currentPos.yPos - 2 > 0 && maze[currentPos.xPos][currentPos.yPos - 2] == 2)
                directions.push_back({ 0, -2 });

            if (!directions.empty()) {
                int randIndex = rand() % directions.size();
                int dx = directions[randIndex].first;
                int dy = directions[randIndex].second;

                // make new path
                maze[currentPos.xPos + dx / 2][currentPos.yPos + dy / 2] = 5;

                currentPos.xPos += dx;
                currentPos.yPos += dy;
                maze[currentPos.xPos][currentPos.yPos] = 5;

                xknownLoc.push(currentPos.xPos);
                yknownLoc.push(currentPos.yPos);

                moved = true;
            }

            if (!moved) {
                // undo last move
                xknownLoc.pop();
                yknownLoc.pop();
                if (!xknownLoc.empty()) {
                    currentPos.xPos = xknownLoc.top();
                    currentPos.yPos = yknownLoc.top();
                }
            }
        }

        // set goal near end
        maze[width - 2][height - 2] = 4;
    }
}




/****************************************************************
 * solveMazeBFS 
 * does breadth-first stuff to solve maze
 ****************************************************************/
void solveMazeBFS(position start) {
    queue<position> q;
    vector<vector<bool>> visited(width, vector<bool>(height, false));
    vector<vector<position>> parent(width, vector<position>(height, { -1, -1 }));

    q.push(start);
    visited[start.xPos][start.yPos] = true;

    position goal = { -1, -1 };
    bool found = false;
    bool brokenPath = false; // flag for broken path

    // bfs loop
    while (!q.empty() && !found) {
        position curr = q.front();
        q.pop();

        if (maze[curr.xPos][curr.yPos] == 4) {
            goal = curr;
            found = true;
        }
        else {
            int dx[] = { 0, 1, 0, -1 };
            int dy[] = { -1, 0, 1, 0 };

            for (int i = 0; i < 4; ++i) {
                int nx = curr.xPos + dx[i];
                int ny = curr.yPos + dy[i];

                if (nx >= 0 && ny >= 0 && nx < width && ny < height &&
                    !visited[nx][ny] && (maze[nx][ny] == 5 || maze[nx][ny] == 4)) {
                    visited[nx][ny] = true;
                    parent[nx][ny] = curr;
                    q.push({ nx, ny });
                }
            }
        }
    }

    if (found) {
        int steps = 0;
        position curr = goal;

        //going backwards
        while (maze[curr.xPos][curr.yPos] != 3 && !brokenPath) {
            position prev = parent[curr.xPos][curr.yPos];
            //lets user know that it broke because no previous parent function found
            if (prev.xPos == -1 && prev.yPos == -1) {
                cout << "broken path, path before broken\n";
                brokenPath = true;
            }
            else {
                if (maze[curr.xPos][curr.yPos] != 4) {
                    maze[curr.xPos][curr.yPos] = 6;
                }
                curr = prev;
                steps++;
            }
        }

        if (!brokenPath) {
            // show maze again
            for (int j = 0; j < height; ++j) {
                for (int i = 0; i < width; ++i) {
                    if (maze[i][j] == 2) cout << "X";
                    else if (maze[i][j] == 3) cout << "S";
                    else if (maze[i][j] == 4) cout << "G";
                    else if (maze[i][j] == 6) cout << ".";
                    else cout << " ";
                }
                cout << '\n';
            }
            //prints out the shortest path
            cout << "\nshortest path length: " << steps << "\n\n";
        }
    }
    else {
        //lets user know it can't make it to the goal
        cout << "\ncan't make it to goal\n";
    }
}

/****************************************************************
 * main()
 * runs the whole program
 ****************************************************************/
int main() {
    bool exitProgram = false;
    while (!exitProgram) {
        menu();
        tryCatch();

        bool validChoice = true;

        if (userInput == 1) {
            // generate maze, loop until valid size
            bool validSize = false;
            while (!validSize) {
                if (amountMaze()) {
                    // invalid size, try again
                }
                else {
                    validSize = true;
                }
            }

            generateMaze();
            printMaze();

            cout << "would you like to save the maze? (1 for yes, 2 for no)\n";
            tryCatch();
            if (userInput == 1) {
                cout << "enter file name to save:\n";
                string filename;
                cin >> filename;
                saveMazeToFile(filename);
            }
        }
        else if (userInput == 2) {
            // solve maze if loaded/generated
            if (maze.empty()) {
                cout << "load or generate maze first\n";
            }
            else {
                //starting a bit of maze here, to set up bfs for success
                position start;
                bool foundStart = false;

                //find s location
                for (int i = 0; i < width && !foundStart; ++i) {
                    for (int j = 0; j < height && !foundStart; ++j) {
                        if (maze[i][j] == 3) {
                            start = { i, j };
                            foundStart = true;
                        }
                    }
                }

                //initiate bfs
                if (foundStart) {
                    solveMazeBFS(start);
                }
                else {
                    //tell em maze can't be soved if no s location
                    cout << "no start point 's' (value 3) found\n";
                }
            }
        }
        else if (userInput == 3) {
            // load maze from file
            cout << "enter file name to load:\n";
            string filename;
            cin >> filename;
            loadMazeFromFile(filename);
        }
        else if (userInput == 4) {
            // exit program
            cout << "exiting program\n";
            exitProgram = true;
        }
        else {
            validChoice = false;
        }

        if (!validChoice) {
            cout << "invalid choice, try again\n";
        }
    }
}


