#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <random>
#include <chrono>
#include <string>
#include <SDL3/SDL.h>

class Maze {
private:
    int n_rows, n_cols;
    int real_rows, real_cols;
    std::vector<std::vector<int>> data;

public:
    const int EMPTY = 0;
    const int WALL = 1;

    struct Cell {
        int r, c;
        bool operator==(const Cell& other) const { return r == other.r && c == other.c; }
    };

    Maze(int r, int c) : n_rows(r), n_cols(c) {
        real_rows = 2 * n_rows + 1;
        real_cols = 2 * n_cols + 1;
        data.assign(real_rows, std::vector<int>(real_cols, WALL));
        generateMaze();
    }

    int getRealRows() const { return real_rows; }
    int getRealCols() const { return real_cols; }
    int getValue(int r, int c) const { return data[r][c]; }

    bool isValid(int r, int c) const {
        return (r >= 0 && r < real_rows && c >= 0 && c < real_cols);
    }

    // Algoritmo de resolución: Busca recursivamente el camino guardando el historial (visited)
    bool findShortestPath(Cell current, Cell target, std::vector<std::vector<bool>>& visited, std::vector<Cell>& path) {
        // Casos base: fuera de límites, obstáculo o ya visitado
        if (!isValid(current.r, current.c) || data[current.r][current.c] == WALL || visited[current.r][current.c]) {
            return false;
        }

        // Añadir la celda actual al camino provisional
        path.push_back(current);
        visited[current.r][current.c] = true;

        // Si hemos llegado al destino, el camino es válido
        if (current == target) {
            return true;
        }

        // Movimientos ortogonales en la matriz real (de 1 en 1)
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};

        for (int i = 0; i < 4; ++i) {
            Cell next = {current.r + dr[i], current.c + dc[i]};
            if (findShortestPath(next, target, visited, path)) {
                return true;
            }
        }

        // Backtracking: si ninguna dirección funcionó, quitamos la celda del camino
        path.pop_back();
        return false;
    }

    // Método auxiliar para lanzar la búsqueda del camino
    std::vector<Cell> getPath(Cell start, Cell end) {
        std::vector<std::vector<bool>> visited(real_rows, std::vector<bool>(real_cols, false));
        std::vector<Cell> path;
        findShortestPath(start, end, visited, path);
        return path;
    }

private:
    bool isLogicalValid(int r, int c, const std::vector<std::vector<bool>>& visited) {
        return (r >= 0 && r < n_rows && c >= 0 && c < n_cols && !visited[r][c]);
    }

    void generateMaze() {
        std::vector<std::vector<bool>> visited(n_rows, std::vector<bool>(n_cols, false));
        std::stack<Cell> cellStack;

        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};

        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        std::default_random_engine engine(seed);

        Cell current = {0, 0};
        visited[current.r][current.c] = true;
        data[1][1] = EMPTY;
        cellStack.push(current);

        while (!cellStack.empty()) {
            current = cellStack.top();
            std::vector<int> neighbors;

            for (int i = 0; i < 4; ++i) {
                if (isLogicalValid(current.r + dr[i], current.c + dc[i], visited)) {
                    neighbors.push_back(i);
                }
            }

            if (!neighbors.empty()) {
                std::shuffle(neighbors.begin(), neighbors.end(), engine);
                int dirIndex = neighbors[0];

                int next_r = current.r + dr[dirIndex];
                int next_c = current.c + dc[dirIndex];

                int current_real_r = current.r * 2 + 1;
                int current_real_c = current.c * 2 + 1;
                int next_real_r = next_r * 2 + 1;
                int next_real_c = next_c * 2 + 1;

                int wall_r = current_real_r + dr[dirIndex];
                int wall_c = current_real_c + dc[dirIndex];
                
                data[wall_r][wall_c] = EMPTY;
                data[next_real_r][next_real_c] = EMPTY;

                visited[next_r][next_c] = true;
                cellStack.push({next_r, next_c});
            } else {
                cellStack.pop();
            }
        }

        // Perforamos de forma segura la entrada y salida iniciales en la matriz
        data[1][0] = EMPTY;
        data[real_rows - 2][real_cols - 1] = EMPTY;
    }
};

int main(int argc, char* argv[]) {
    if (argc != 3) {
        std::cerr << "Uso: " << argv[0] << " <filas> <columnas>\n";
        return 1;
    }

    int filas = std::stoi(argv[1]);
    int columnas = std::stoi(argv[2]);

    if (filas <= 0 || columnas <= 0) {
        std::cerr << "Error: Las dimensiones deben ser mayores que cero.\n";
        return 1;
    }

    Maze maze(filas, columnas);

    const float CELL_SIZE = 16.0f; 
    int window_width = maze.getRealCols() * CELL_SIZE;
    int window_height = maze.getRealRows() * CELL_SIZE;

    if (!SDL_Init(SDL_INIT_VIDEO)) {
        std::cerr << "Error al inicializar SDL3: " << SDL_GetError() << "\n";
        return 1;
    }

    SDL_Window* window = nullptr;
    SDL_Renderer* renderer = nullptr;

    if (!SDL_CreateWindowAndRenderer("Laberinto Interactivo (SDL3)", window_width, window_height, 0, &window, &renderer)) {
        std::cerr << "Error al crear la ventana/renderer: " << SDL_GetError() << "\n";
        SDL_Quit();
        return 1;
    }

    // Puntos de inicio y fin iniciales (coordenadas reales de la matriz)
    Maze::Cell startPoint = {1, 0}; 
    Maze::Cell endPoint = {maze.getRealRows() - 2, maze.getRealCols() - 1};

    // Calcular la ruta inicial
    std::vector<Maze::Cell> currentPath = maze.getPath(startPoint, endPoint);

    bool running = true;
    SDL_Event event;

    while (running) {
        while (SDL_PollEvent(&event)) {
            if (event.type == SDL_EVENT_QUIT) {
                running = false;
            } 
            else if (event.type == SDL_EVENT_KEY_DOWN) {
                if (event.key.key == SDLK_ESCAPE) running = false;
            } 
            // Manejo de clicks de ratón
            else if (event.type == SDL_EVENT_MOUSE_BUTTON_DOWN) {
                // Calcular qué celda de la matriz real se ha pulsado
                int clicked_c = event.button.x / CELL_SIZE;
                int clicked_r = event.button.y / CELL_SIZE;

                if (maze.isValid(clicked_r, clicked_c) && maze.getValue(clicked_r, clicked_c) == maze.EMPTY) {
                    if (event.button.button == SDL_BUTTON_LEFT) {
                        startPoint = {clicked_r, clicked_c};
                    } else if (event.button.button == SDL_BUTTON_RIGHT) {
                        endPoint = {clicked_r, clicked_c};
                    }
                    // Recalcular la ruta más corta tras cambiar un punto
                    currentPath = maze.getPath(startPoint, endPoint);
                }
            }
        }

        // Fondo de la ventana (Pasillos)
        SDL_SetRenderDrawColor(renderer, 15, 15, 20, 255); 
        SDL_RenderClear(renderer);

        // 1. Dibujar Muros
        SDL_SetRenderDrawColor(renderer, 45, 50, 65, 255); // Gris azulado para muros
        for (int i = 0; i < maze.getRealRows(); ++i) {
            for (int j = 0; j < maze.getRealCols(); ++j) {
                if (maze.getValue(i, j) == maze.WALL) {
                    SDL_FRect rect = { j * CELL_SIZE, i * CELL_SIZE, CELL_SIZE, CELL_SIZE };
                    SDL_RenderFillRect(renderer, &rect);
                }
            }
        }

        // 2. Dibujar el camino óptimo calculado (Azul celeste)
        SDL_SetRenderDrawColor(renderer, 0, 180, 255, 255);
        for (const auto& cell : currentPath) {
            SDL_FRect rect = { cell.c * CELL_SIZE, cell.r * CELL_SIZE, CELL_SIZE, CELL_SIZE };
            SDL_RenderFillRect(renderer, &rect);
        }

        // 3. Dibujar Punto de Inicio (Verde)
        SDL_SetRenderDrawColor(renderer, 50, 220, 100, 255);
        SDL_FRect startRect = { startPoint.c * CELL_SIZE, startPoint.r * CELL_SIZE, CELL_SIZE, CELL_SIZE };
        SDL_RenderFillRect(renderer, &startRect);

        // 4. Dibujar Punto de Fin (Rojo)
        SDL_SetRenderDrawColor(renderer, 255, 60, 60, 255);
        SDL_FRect endRect = { endPoint.c * CELL_SIZE, endPoint.r * CELL_SIZE, CELL_SIZE, CELL_SIZE };
        SDL_RenderFillRect(renderer, &endRect);

        SDL_RenderPresent(renderer);
        SDL_Delay(16);
    }

    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);
    SDL_Quit();

    return 0;
}