/proyecto-final-2023_0-grupo-4

proyecto final 2023-0 grupo-4 https://youtu.be/P9PDjKmyTfA

Primary LanguageC++MIT LicenseMIT

Maze logo

MAZE GAME🐍

Hola! 👨‍💻. Somos estudiantes del curso de Programación III de UTEC. Hemos aplicado conocimientos aprendidos durante el curso de Programación para desarrollar el juego Maze en C++.

Tabla de contenidos:
  1. Acerca del proyecto
  2. Instalación
  3. Instrucciones de uso
  4. Licencia
  5. Diagramas
  6. Link del video
  7. Autores
  8. Bibliografía

Acerca del proyecto

Descripción

Maze es un juego adictivo que tiene una fórmula clásica, debes deslizar y guiar al personaje a través del laberinto pero, ¡Cuidado! El tiempo puede estar corriendo. Tendrás que ser ágil al resolverlo para encontrar el camino adecuado para que llegue a su punto objetivo.

Características

  • Nuestro tablero es modificable.
  • Tenemos dos opciones de juego: Bot y Human.
  • Tiene timer.
  • 4 Algoritmos distintos para el bot (DFS, BFS, GBFS, A*)

Tecnologías

  • Lenguaje de programación C++20 o posterior
  • Librería raylib
  • Raylib-cpp (header only, fork)
  • Doxyegn (documentación)

Temas de interés

  • El uso de raylib como interfaz gráfica.
  • Algoritmos de busqueda
  • Algoritmos de generación de laberintos perfectos (arboles de expansión minima)

Algoritmos y contenedores utilizados

DFS (Depth First Search)

Este algoritmo emplea en su implementación el concepto de stack. Lo que hace es recorrer en su totalidad una estructura. Cada vez que se encuentra con dos o más caminos posibles, este recorrerá cada uno lo más profundamente posible, a la vez que almacena los nodos recorridos en un stack. Si alcanza un camino sin salida antes que el objetivo, este retrocede a la bifurcación anterior y repite el proceso. Este algoritmo, aunque puede cumplir con el objetivo, no es eficiente en lo absoluto, considerando que existen alternativas más eficientes.

BFS(Breadth First Search)

Una búsqueda en anchura (BFS) es un algoritmo de búsqueda, recorre los nodos de un grafo, comenzando en la raíz para luego explorar todos los vecinos de este nodo. Además, para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el grafo.

BFS va formando un árbol a medida que va recorriendo un grafo y se usa para algoritmos en donde resulta crítico elegir el mejor camino posible en cada momento del recorrido.

GBFS (Greedy Best First Search)

Este es un algoritmo de búsqueda heurística, es decir, necesita información adicional específica relacionada con el problema a resolver. En el caso de un laberinto, lo que requiere es el número de casillas de distancia a la que se encuentra cada casilla del objetivo. Lo que el algoritmo GBFS busca es reducir este número conforme se mueve de casilla en casilla. Si alcanza un punto sin salida, retrocede de nuevo al último cruce. A pesar de siempre buscar la casilla más cercana al objetivo, no puede garantizar que el camino elegido será el más eficiente.

A* Search Algorithm

Tenemos una celda inicial y una celda objetivo. Queremos llegar a la celda objetivo (si es posible) desde la celda inicial lo más rápido posible. Aquí A* Search Algorithm lo que hace es que, en cada paso, selecciona el nodo que le acorte o le permita llegar de manera más rapida u optimizada al punto de objetivo. Esto a menudo se denomina heurística, que no es más que una especie de suposición inteligente. Realmente no sabemos la distancia real hasta que encontramos el camino, porque todo tipo de cosas pueden estar en el camino.

Wilsons

El algoritmo de Wilson utiliza caminatas aleatorias borradas en bucle para generar un árbol de expansión uniforme, una muestra imparcial de todos los árboles de expansión posibles. Este inicializa el laberinto con una celda de inicio arbitraria. Luego, se agrega una nueva celda al laberinto, iniciando una caminata aleatoria. La caminata aleatoria continúa hasta que se vuelve a conectar con el laberinto existente. Sin embargo, si la caminata aleatoria se cruza a sí misma, el bucle resultante se borra antes de que continúe la caminata aleatoria.

Clases/funciones Templates

Templates

  • Compare: función heuristica para GBFS/A*
  • Solve: función para resolver el laberinto
  • Class Game/GameBase: template en función del modo de juego
  • Utils::RandomNum: función robusta para generar aleatorios
  • DrawAll: Función para dibujar caulquier tipo T con {T.Draw()}

Instalación

Requisitos

  • Compilador compatible con c++20 o posterior
  • Administrador de paquetes Cmake v3 o posterior
  • Libreria raylib (previamente no incluida)

Pasos de instalación

  1. Clonación de repositorio con
git clone https://github.com/CS1103/proyecto-final-2023_0-grupo-4.git
cd proyecto-final-2023_0-grupo-4
mkdir build
cmake -B build
cd build
sudo make install

Instrucciones de uso

  • ejecutable Maze 
    Maze
  • Crear entrada de escritorio 
    cd .. # Carpeta principal del repositorio
cp Maze.desktop /usr/share/applications/

Reglas de juego

Configuración

  1. Elegir tamaño del tablero
  2. Elegir modo de juego (Humano o computador)
  3. Elegir limite de tiempo prendido o apagado

Jugabilidad

  1. El laberinto tiene un punto inicial.

  2. Luego, debes elegir un cuadrado adyacente, ya sea hacia adelante o hacia un lado.

  3. Continuas creando el camino que creas adecuado.

  4. En caso llegues a un callejon sin salida, no podras avanzar, pero si retroceder.

  5. Finalmente, al crear el camino correcto, llegarás al punto objetivo.

Licencia

Distribuido bajo la licencia MIT. Ver LICENSE para más información.

Diagrama

Matriz del Tablero

Matriz tablero

Decidimos usar una matriz como estructura de datos debido a que el laberinto es cuadrado y cada una de las casillas contiene información relevante.

Link del video

https://youtu.be/P9PDjKmyTfA

Autores

  • Camila Villasana Boggiano
  • Diana Carolina Ñañez Andres
  • Jaime Alfonso Ramos Talla
  • Kevin Jonás Zevallos López
  • Enrique Francisco Flores Teniente
  • Luis Enrique Cortijo

Bibliografía

Back To The Top