Laberinto con A Star y Raylib

//
// ██╗      █████╗ ██████╗ ███████╗██████╗ ██╗███╗   ██╗████████╗ ██████╗
// ██║     ██╔══██╗██╔══██╗██╔════╝██╔══██╗██║████╗  ██║╚══██╔══╝██╔═══██╗
// ██║     ███████║██████╔╝█████╗  ██████╔╝██║██╔██╗ ██║   ██║   ██║   ██║
// ██║     ██╔══██║██╔══██╗██╔══╝  ██╔══██╗██║██║╚██╗██║   ██║   ██║   ██║
// ███████╗██║  ██║██████╔╝███████╗██║  ██║██║██║ ╚████║   ██║   ╚██████╔╝
// ╚══════╝╚═╝  ╚═╝╚═════╝ ╚══════╝╚═╝  ╚═╝╚═╝╚═╝  ╚═══╝   ╚═╝    ╚═════╝

/*
Nombre del archivo: laberinto.cpp
Nombre del programa: Laberinto solucion por algoitmos de busqueda

Autor(es): Natxo Varona, IA's
Fecha de creación: 2024-04-12
Versión: 1.5
Licencia: GPLv3
Descripción breve: Este programa calcula la forma optima de salir de un laberinto.
Palabras clave: laberinto, aritmético, busqueda, cálculo, .
Contacto: [email protected], [email protected]
Dependencias: libreiria raylib

Descripcion: Resolucion de un supuesto laberinto utilizando el Algoritmo (A-star).*

Este código implementa el algoritmo A* para encontrar la ruta más corta en un laberinto representado
por una matriz de caracteres. Se utiliza una cola de prioridad para explorar los nodos de acuerdo con
su valor de f, que es la suma de los valores g y h. La función de evaluación h es la distancia
euclidiana desde un nodo hasta el nodo objetivo. La función de evaluación g es la distancia
recorrida desde el nodo inicial hasta el nodo actual.

Instrucciones de uso:
1. Compilar el programa: g++ laberinto.cpp -o laberinto -lraylib -std=c++11
2. Ejecutar el programa: ./laberinto
3. Ingresar los números separados por espacios: 1 2 3 4 5
4. El programa mostrará en una ventana grafica un laberinto y su solucion.

Historial de cambios:
- Versión 1.0 (2024-04-12): Implementación inicial del programa.
- Versión 1.5 (2024-04-14): Implementacion de impresion de inicio, final y ruta.
*/

#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
#include <climits>
#include <raylib.h>

using namespace std;

// Definicion de variables y constantes para el programa -----------------
Color Green = Color{38, 185, 154, 255};
Color Dark_Green = Color{20, 160, 133, 255};
Color Light_Green = Color{129, 204, 184, 255};
Color Yellow = Color{243, 213, 91, 255};
Color Grey = Color{29, 29, 29, 255};
Color lightGreen = {173, 204, 96, 255};
Color darkGreen = {43, 51, 24, 255};

const int START = 2;     // Carácter que representa el inicio
const int GOAL = 3;      // Carácter que representa la meta
const int mazeWidth = 10;
const int mazeHeight = 10;

// Definición del laberinto como una matriz de caracteres ---------------
int maze[mazeWidth][mazeHeight] = {
    {1, 2, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 0, 1, 0, 1, 0, 1, 1, 0, 1},
    {1, 0, 1, 0, 1, 0, 1, 0, 0, 1},
    {1, 0, 1, 0, 1, 0, 1, 0, 1, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 1, 1, 0, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 3, 1}
};

// Direcciones posibles para explorar (arriba, abajo, izquierda, derecha)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// Función para calcular la distancia euclidiana entre dos puntos en el laberinto
double heuristic(int x, int y, int goal_x, int goal_y) {
    return sqrt((x - goal_x) * (x - goal_x) + (y - goal_y) * (y - goal_y));
}

// Estructura para representar un nodo en el laberinto
struct Node {
    int x, y;       // Posición del nodo
    double f, g, h; // Valores de la función de evaluación
};

// Sobrecarga del operador < para ordenar los nodos en función del valor f
bool operator<(const Node& a, const Node& b) {
    return a.f > b.f; // Orden inverso para que la cola de prioridad tenga el menor f en el frente
}

// Función para verificar si una posición está dentro del laberinto y es transitable
bool isValid(int x, int y, int mazeWidth, int mazeHeight) {
    return (x >= 0 && x < mazeWidth && y >= 0 && y < mazeHeight && maze[x][y] != '1');
}

// Función para encontrar la ruta más corta utilizando el algoritmo A*
vector<pair<int, int>> AStar(int start_x, int start_y, int goal_x, int goal_y, int mazeWidth, int mazeHeight) {
    // Crear una cola de prioridad para almacenar los nodos a explorar
    priority_queue<Node> pq;

    // Crear un arreglo para almacenar los valores de g y h de cada nodo
    vector<vector<pair<double, double>>> values(mazeWidth, vector<pair<double, double>>(mazeHeight, {INFINITY, INFINITY}));

    // Crear un arreglo para almacenar el camino encontrado
    vector<pair<int, int>> path;

    // Insertar el nodo inicial en la cola de prioridad
    pq.push({start_x, start_y, 0.0, 0.0, heuristic(start_x, start_y, goal_x, goal_y)});
    values[start_x][start_y] = {0.0, heuristic(start_x, start_y, goal_x, goal_y)};

    while (!pq.empty()) {
        // Obtener el nodo con el menor valor f de la cola de prioridad
        Node current = pq.top();
        pq.pop();

        int x = current.x;
        int y = current.y;

        // Verificar si se alcanzó el nodo objetivo
        if (x == goal_x && y == goal_y) {
            // Rastrear el camino desde el nodo objetivo hasta el nodo inicial
            int cx = goal_x, cy = goal_y;
            while (cx != start_x || cy != start_y) {
                path.push_back({cx, cy});
                double min_f = INFINITY;
                int nx, ny;
                for (int i = 0; i < 4; ++i) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (isValid(nx, ny, mazeWidth, mazeHeight) && values[nx][ny].first + values[nx][ny].second < min_f) {
                        min_f = values[nx][ny].first + values[nx][ny].second;
                        cx = nx;
                        cy = ny;
                    }
                }
            }
            path.push_back({start_x, start_y});
            reverse(path.begin(), path.end());  // Invertir el camino para que esté en el orden correcto
            return path;
        }

        // Explorar los nodos vecinos
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // Verificar si la posición vecina es válida
            if (isValid(nx, ny, mazeWidth, mazeHeight)) {
                double new_g = current.g + 1.0; // Distancia hasta el vecino (asumiendo un costo de movimiento de 1)

                // Verificar si se encontró una mejor ruta hacia el vecino
                if (new_g < values[nx][ny].first) {
                    values[nx][ny].first = new_g; // Actualizar el valor de g
                    values[nx][ny].second = heuristic(nx, ny, goal_x, goal_y); // Calcular el valor de h
                    pq.push({nx, ny, new_g + values[nx][ny].second, new_g, values[nx][ny].second}); // Insertar el nodo en la cola de prioridad
                }
            }
        }
    }
    // Si no se encontró ningún camino, devolver un vector vacío
    return {};
}

int main() {
    // Comenzamos el programa ------------------------------------------
    std::cout << std::endl;
    std::cout << "Starting the program ..." << std::endl;
    std::cout << std::endl;

    const int screen_Width = 800;       // Sin interface entero seria 300
    const int screen_Height = 800;      // Sin interface entero seria 600
    int FPS = 60;
    bool lab = false;                   // Estado de la busqueda en el laberinto
    bool gameOver = false;              // Saber si ya hemos acabado, para no volver a imprimir
    const int cellSize = 50;

    // Posicion de el comienzo del laberinto y la salida del laberinto
    int start_x, start_y, goal_x, goal_y;

    // Crear un arreglo para almacenar el camino encontrado
    vector<pair<int, int>> path;

    InitWindow(screen_Width, screen_Height, "Resolucion de Laberintos con RayLib");
    SetTargetFPS(FPS);
    SetConfigFlags(FLAG_VSYNC_HINT);

    // 1. Event Handing ---------------------------------------------
    BeginDrawing();
    ClearBackground(WHITE);

    // Encontrar las coordenadas de inicio del laberitno '2' y objetivo de salida '3'
    for (int y1 = 0; y1 < mazeHeight; ++y1) {
        for (int x1 = 0; x1 < mazeWidth; ++x1) {
            if (maze[y1][x1] == START) {
                start_x = x1;
                start_y = y1;
            } else if (maze[y1][x1] == GOAL) {
                goal_x = x1;
                goal_y = y1;
            }
        }
    }
    //cout << endl;
    //cout << "Comienzo X: " << start_x << endl;
    //cout << "Comienzo Y: " << start_y << endl;
    //cout << "Salida X: " << goal_x << endl;
    //cout << "Salida Y: " << goal_y << endl;

    // Punto de inicio del tiempo
    clock_t start = clock();

    // Llamar al algoritmo A* para encontrar la ruta más corta
    path = AStar(start_x, start_y, goal_x, goal_y, mazeWidth, mazeHeight);

    // Punto de finalización del tiempo
    clock_t end = clock();

    // Calcula la duración de la ejecución en milisegundos
    double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000;

    // Imprime el tiempo transcurrido
    char durationText[30];
    snprintf(durationText, sizeof(durationText), "La busqueda tardó: %.2f ms", duration);
    DrawText(durationText, 400, 710, 20, RED);
    //cout << endl;
    //cout << "La busqueda tardó: " << duration << " ms en ejecutarse." << endl;

    // 2. Updating State --------------------------------------------

    // 3. Drawing Objects -------------------------------------------

    // Dibujar el laberinto
    for (int y1 = 0; y1 < mazeHeight; y1++) {
        for (int x1 = 0; x1 < mazeWidth; x1++) {
            if (maze[y1][x1] == 1) {
                DrawRectangle(x1 * cellSize, y1 * cellSize, cellSize, cellSize, darkGreen);
            }
        }
    }
    DrawRectangle(start_x * cellSize, start_y * cellSize, cellSize, cellSize, Yellow);
    DrawRectangle(goal_x * cellSize, goal_y * cellSize, cellSize, cellSize, Grey);
    if (!path.empty()) {
        //cout << endl;
        //cout << "Se encontró una ruta hasta el objetivo !!" << endl;
        //cout << endl;
        // Imprimir el camino encontrado
        //cout << "Camino encontrado:" << endl;
        for (int i = path.size() - 1; i >= 0; --i) {
            DrawRectangle(path[i].first * cellSize, path[i].second * cellSize, cellSize, cellSize, lightGreen); // Dibujar la solucion al laberinto
            // Impresion por consola del resultado del camino optimo
            //cout << "(" << path[i].first << ", " << path[i].second << ")";
            //if (i > 0) cout << " -> ";
        }
        //cout << endl;
    }

    // Mostrar mensaje de salida o repeticion.
    DrawText("Pulsa una tecla para salir", 400, 750, 20, RED);
    EndDrawing();
    bool keyPressed = false; // Variable para almacenar si se ha presionado una tecla
    while (!WindowShouldClose() && !keyPressed) {
        // Esperar a que el usuario pulse la tecla SPACE para continuar
        if (IsKeyPressed(KEY_SPACE)) {
            keyPressed = true; // Marcar que se ha presionado una tecla
        }
    }

    CloseWindow();
    return 0;
}