El Secreto del Laberinto

El conocido mito griego del hilo de Ariadna sirve de contexto narrativo para trabajar en el problema de la navegación de entornos virtuales, tan habitual en el mundo de los videojuegos. En la historia tenemos un protagonista, Teseo, en principio heroico, y un villano, el temido Minotauro. Tenemos también el propio entorno donde se encuentran ambos personajes, el laberinto del Minotauro, y por último está el hilo mágico que Ariadna entregó a Teseo. Este hilo tiene la propiedad de burlar el embrujo del laberinto y ayudarnos a salir de él. Aunque en el mito se habla de la victoria de Teseo sobre el Minotauro, aquí vamos a aplicarle la “maldición” que le lanza Ariadna de forma anticipada, para que sea imposible acabar con la dichosa criatura. Lo único que hará el héroe cuando se encuentre próximo al monstruo es combatirlo, lo que en la práctica supondrá ralentizar sus movimientos. 

El segundo canto de El Hilo de Ariadna narra las aventuras de Teseo y su llegada a la isla de Creta, en busca de la cabeza del Minotauro. Ariadna, decidida a salvar al famoso héroe, le entregó un ovillo de hilo para que el laberinto perdiera por completo su secreto, y así Teseo pudiera escapar vivo de la isla. La princesa cretense empezaba a enamorarse perdidamente de él, y este le ofreció todo tipo de promesas que un hombre puede hacerle a una mujer. 
El destino de Teseo estaba escrito, mató al Minotauro y se llevó consigo a Ariadna hasta la isla de Naxos, en la cual se celebró hasta el amanecer la gloria del héroe. A la mañana siguiente, Teseo abandonó a su prometida, mientras ella dormía en la playa. Por eso el canto termina con la maldición que Ariadna realiza sobre su amado…

El mito de El Hilo de Ariadna

En esta ocasión, crearemos un prototipo en el que el jugador controla el movimiento de Teseo por los pasillos del laberinto. La bestia mitológica por su parte será un agente inteligente que se dedica a merodear por allí, siguiendo a Teseo en caso de percibirlo. El hilo de Ariadna funcionará, cuando lo activemos, dibujando una línea blanca el camino de menor coste que lleva a Teseo hasta la baldosa de salida. El hilo, al ser mágico, tiene en cuenta todos los costes, ya que la baldosa donde se encuentra el Minotauro es intransitable, y moverse a las baldosas vecinas al Minotauro (su “zona de influencia”) tiene mayor coste que el movimiento a través de una baldosa normal.

Este prototipo aplicará el algoritmo A* como técnica de navegación (búsqueda de caminos con información heurística), muy usada en videojuegos, en combinación con el algoritmo de suavizado de caminos y con los comportamientos de dirección que hagan falta (sean cinemáticos o dinámicos, reutilizados de prácticas anteriores).

Propuesta

La práctica consiste en desarrollar un prototipo de IA para Videojuegos, dentro de un entorno virtual laberíntico, con uno o varios agentes inteligentes que merodean por allí y un avatar, en principio controlado por el jugador. Al activar el hilo de Ariadna, Teseo pasará a ser controlado por la máquina y procederá a salir del laberinto navegando y moviéndose de manera automática, hasta que lo desactivemos. El prototipo será fácilmente usable, y se basará en un entorno de tamaño y complejidad configurable, con habitaciones y pasillos.

El punto de partida propuesto para esta práctica, con la documentación e implementación (código y recursos audiovisuales) necesaria, se encuentra en este repositorio de GitHub: IAV-Navegacion.

Las características principales del prototipo son:

A. Hay un mundo virtual (el laberinto del Minotauro) de tamaño y complejidad configurable, con un esquema de división de grafo de baldosas que incluirá una baldosa de entrada, donde se ubica inicialmente el avatar (Teseo) y una baldosa de salida. Debe haber varios caminos alternativos para llegar a la salida, algunos más anchos y la mayoría muy lineales y estrechos (pasillos de una única baldosa de anchura), intentando forzar que sea muy fácil el cruce entre el avatar y el enemigo. El avatar estará controlado manualmente por el jugador, preferiblemente con el clic izquierdo del ratón.

B. En mitad del laberinto están los enemigos (uno o varios minotauros), que realizan un merodeo constante, pasando a perseguir al avatar si lo perciben con la vista o se hayan próximos a él. Debemos mostrar visualmente el área de influencia del minotauro, por ejemplo las baldosas vecinas a la que ocupa este.

C. El camino más corto a la baldosa de salida calculado mediante A* (hilo de Ariadna) se representa pintado con una línea blanca y destacando las baldosas que lo componen con bolitas blancas. Aparece cada vez que se activa la navegación y el movimiento automático del avatar hasta la salida (cosa que ocurre al pulsar el clic derecho del ratón). Desde una opción de la interfaz de usuario será posible elegir la heurística utilizada. Deben tenerse en cuenta cuenta todos los costes, incluido el de la baldosa en la que está el Minotauro y su zona de influencia, cuyas baldosas pueden costar, por ejemplo, 5 veces más que una baldosa normal.

D. Es posible elegir si queremos suavizar o no el camino generado por el algoritmo anterior (activando o desactivando la funcionalidad desde una opción de la interfaz de usuario). Esto reduce las baldosas que forman parte del camino original a la salida, y por tanto también reduce la cantidad de bolitas blancas mostradas.

E. El avatar navega y se mueve automáticamente en dirección a la baldosa de salida mientras está activo el hilo de Ariadna. Este movimiento va haciendo desaparecer la parte del hilo ya recorrido, para que sólo quede la parte del camino que falta por recorrer. Si desactivamos el hilo, el avatar vuelve al movimiento manual habitual, controlado por el jugador.

Condiciones

A la hora de desarrollar el proyecto es obligatorio:

• Atenerse a nuestras recomendaciones generales en la realización de prácticas.
• Documentar claramente los algoritmos, heurísticas o cualquier “truco” utilizado. La documentación deberá ser adecuada (datos correctos, resumen completo del enunciado, descripción del punto de partida con suficiente detalle, investigación de posibles referentes…) e incluir el diseño de la solución mediante diagramas y/o pseudocódigo de Millington (similar a Python), así como el reparto del trabajo y el esfuerzo.
• El ejecutable será práctico y fácil de usar, comprendiendo -con la calidad mínima esperable en el prototipo de un videojuego- las características principales anteriormente descritas, además de los recursos audiovisuales adecuados para representar el entorno y a los distintos agentes.
• Diseñar y programar de la manera más organizada, genérica y elegante posible, separando totalmente la parte visual e interactiva del juego (preferentemente programada en Visual Scripting), del modelo y las técnicas de IA implementadas (preferentemente programadas en C#). Sin olvidar los comentarios. 
• Utilizar únicamente las herramientas de Unity y a lo sumo los plugins de terceros proporcionados por los profesores, sin reutilizar código ajeno a estos.
• Limitarse, en la medida de lo posible, a los recursos del punto de partida proporcionado por el profesor, evitando el uso de recursos audiovisuales pesados, extraños, o que ralenticen la ejecución.
• Personalizar la interfaz con el número de grupo, nombre de los alumnos u otros rasgos inequívocos en el contenido del juego que subrayen la autoría sobre el resultado.
• Para realizar las pruebas y facilitar las revisiones de los profesores, intentando aprovechar el esfuerzo de desarrollo, conviene crear una interfaz gráfica cómoda para mostrar distintos escenarios de ejemplo, instrucciones de uso, etc. Por ejemplo, habilitando una “consola de trucos” (o teclas rápidas) que permitan ver los datos de los desarrolladores, reiniciar la ejecución, cambiar la cámara, establecer situaciones específicas para hacer pruebas, hacer invencible al avatar, etc. El manejo debe ser ágil e intuitivo para poder realizar rápidamente todas las pruebas con aquellas variaciones que puedan resultar interesantes.
• El prototipo debe ser funcional y su manejo usable, preferiblemente con mando y con teclado, para poder realizar de manera rápida, intuitiva y frecuente todas las pruebas necesarias.

Revisión

Tener el repositorio a disposición de los profesores con todos los entregables, preparados en tiempo y forma por todos los miembros del grupo de manera equitativa, supone un 10% de la nota de la práctica. Los profesores tendrá una lista con los datos de todos los grupos y los enlaces a las organizaciones en GitHub (por ejemplo IAV23-G02, la del grupo 2 del curso Inteligencia Artificial para Videojuegos 2022-2023) donde se encontrarán los repositorios de las prácticas (IAV23-G02-P1, IAV23-G02-P2, etc.).

Los entregables son:

• Documentación del proceso de producción según la estructura habitual, en el README.md. Supone un 10% de la nota.
• Todos los ficheros de código fuente y recursos del proyecto Unity. Se incluirá un enlace a una carpeta compartida con los profesores de Google Drive (llamada por ejemplo IAV23-G02-P2) desde donde descargar todo lo que por peso o problemas de licencia no deba mantenerse alojado en GitHub. Se tendrán en cuenta las buenas prácticas de desarrollo software (commits frecuentes en la rama principal, organización de recursos en el proyecto y de objetos en la escena, escritura sistemática de los comentarios en todas las clases y métodos, etc.). Supone un 20% de la nota.
• Fichero con la versión ejecutable para Windows de 64bits (llamado por ejemplo IAV23-G02-P2 1.0.0.zip), publicada como “lanzamiento” en el repositorio. Cada característica del prototipo (A, B, C, D y E) correctamente implementada supone un 10% de la nota. Además se dejará constancia de sus posibilidades mostrando por pantalla aquellas métricas que permitan valorar la eficiencia de la implementación: en este caso, tamaño del entorno en número de baldosas totales, número de baldosas exploradas, longitud en número de baldosas y coste del camino encontrado, así como el tiempo en milisegundos tardado por el algoritmo en encontrar dicho camino.
• Enlace a un video oculto en YouTube (llamado por ejemplo IAV23-G03-P2), de menos de 5 minutos de duración, donde quede documentado y comentado por voz y/o subtítulos todo el banco de pruebas realizado. Deberá estructurarse por características (de modo que la sección A1 sea la primera prueba de la característica A, la sección C3 la tercera prueba de la característica C, y así sucesivamente). Supone un 10% de la nota.

Más información

Además de la bibliografía recomendada, se pueden investigar las siguientes referencias. En ningún caso se debe replicar código de terceros sin entenderlo bien y “hacerlo nuestro”, y siempre asegurándonos de que funciona exactamente como se requiere en esta práctica.

• Unity 2018 Artificial Intelligence Cookbook, Second Edition (Repositorio)
  https://github.com/PacktPublishing/Unity-2018-Artificial-Intelligence-Cookbook-Second-Edition 
• Unity Artificial Intelligence Programming, 5th Edition (Repositorio)
  PacktPublishing/Unity-Artificial-Intelligence-Programming-Fifth-Edition: Unity Artificial Intelligence Programming – Fifth Edition, published by Packt (github.com)

Se pueden realizar ampliaciones para ir más allá en el aprendizaje.

• Genera procedimentalmente el entorno con verdadera forma de laberinto, utilizando algoritmos específicos para ello. La interfaz de usuario permitirá decidir el número de habitaciones, minotauros o zonas especiales.
• Modifica a los minotauros para que patrullen siguiendo un camino con patrones de vigilancia concretos, o incluso calculando el camino mínimo para llegar a ciertos sitios (por ejemplo para localizar a Teseo, o acercarse a él, al menos). De hecho hasta se podría usar A* para mover al propio Teseo con el simple clic de ratón (aunque eso haría que el hilo de Ariadna -y la práctica entera- deje de tener sentido, jeje…)
• Añade zonas de baldosas con distinto coste al laberinto, como agua, barro, pendientes…
• Permite añadir varias baldosas de salida al laberinto y modifica a Teseo para que, si hay varias salidas, salga por la más cercana, utilizando un algoritmos similar al algoritmo completo de Dijkstra.
• Haz que el hilo cambie de color a amarillo si el minotauro se acerca a él, poniendo en contacto su área de influencia con el camino marcado. En ese caso Ariadna podría “recalcular” el hilo manual (porque se lo pidamos nosotros) o incluso automáticamente. De hecho podría hacerlo sólo de manera parcial, desde donde se ha producido el cambio en adelante.
• Haz que el hilo se “corte” si el minotauro lo cruza, atravesando el camino marcado. Si existe otro camino a la salida que no esté bloqueado, que aparezca un nuevo hilo a esa salida… y si no existe, que se muestre un icono de exclamación con un sonido frustrante, porque el problema no tiene solución ahora mismo.