El Secreto del Laberinto

El conocido mito griego del hilo de Ariadna sirve de trasfondo narrativo para el problema de la navegación de entornos virtuales, tan habitual en el mundo de los videojuegos. En la historia hay un protagonista, Teseo -en principio heroico- y un villano, el temido Minotauro. Ambos personajes se enfrentan en un laberinto embrujado donde el hilo mágico que Ariadna entregó a Teseo será la clave para ayudarle a escapar. Aunque en el mito se habla de la victoria de Teseo sobre el Minotauro, aquí vamos a aplicar la “maldición” que le lanza Ariadna de forma anticipada, para que sea imposible acabar con el monstruo. Mientras el héroe esté cerca del enemigo, habrá un combate que lo único que supone es ralentizar su movimiento. 

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, vamos a querer que el jugador controle el movimiento de Teseo por los pasillos del laberinto del Minotauro. La bestia mitológica es una criatura inteligente que merodea por allí, persiguiendo a Teseo cuando lo detecta. El hilo de Ariadna funciona, al activarlo, dibujando una línea blanca en el camino de menor coste que conduce a Teseo hasta la baldosa de salida. El hilo, al ser mágico, tiene en cuenta todos los costes, teniendo en cuenta que la baldosa donde se encuentra el Minotauro es intransitable, y que las vecinas (la «zona de influencia» del monstruo) tienen mayor coste que las demás.

Lo que se pretende aquí es aplicar el algoritmo A* como técnica de navegación (búsqueda de caminos con información heurística) en combinación con el algoritmo de suavizado de caminos y con los comportamientos de dirección que hagan falta para realizar los movimientos.

Propuesta

La práctica consiste en desarrollar un prototipo 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 pasa a ser controlado por la máquina y procede a salir del laberinto navegando y moviéndose de manera automática, hasta que alcance la salida o nosotros desactivemos el hilo.

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: Minotaur – Base.

Las características principales del prototipo son:

A. Hay un mundo virtual (el laberinto del Minotauro) con habitaciones y pasillos de tamaño y complejidad configurable, con un esquema de división de grafo de baldosas que incluye una baldosa de entrada, donde se ubica inicialmente el avatar (Teseo), y una baldosa de salida. Hay varios caminos alternativos para llegar a la salida, alguno ancho y alguno estrecho (pasillos de una única baldosa de anchura, donde es muy probable toparnos con el enemigo). El avatares controlado por el jugador mediante el ratón. Si el puntero está más allá de cierta distancia del avatar, este camina en línea recta hacia la posición del puntero. Mientras se mantiene pulsado el clic izquierdo, el avatar corre más rápido.

B. En mitad del laberinto están los enemigos (uno o varios minotauros, de dos tipos y número también configurable). Unos son vigías que permanecen quietos en su sitio, rotando aleatoriamente. Otros son patrulleros que siempre están caminando en línea recta, pudiendo cambiar de dirección aleatoriamente al llegar a las encrucijadas del laberinto. Los dos tipos de minotauro tienen un cono de visión y si detectan al avatar del jugador se ponen a seguirlo. También tienen una zona de influencia, que se muestra visualmente, consistente en las baldosas vecinas (vecindad Manhattan de radio 3) con las que tenga línea de visión, las cuales ralentizan a Teseo si intenta atravesarlas para «escenificar» que héroe y minotauro están en pleno combate.

C. El camino más corto a la baldosa de salida (¡sin poder hacer navegación en diagonal, ojo!) calculado mediante A* (hilo de Ariadna) se representa pintado con una línea blanca y marcando cada baldosa que lo compone con un número en el centro de la baldosa que es el coste por entrar en ella. Un nuevo hilo se crea cada vez que intentamos salir del laberinto (con el clic derecho del ratón se crea o se destruye, como un interruptor). Se tienen en cuenta todos los costes, siendo los minotauros infranqueables y teniendo las baldosas de sus zonas de influencia coste 5 (el coste de una baldosa normal es 1). La conexión que permite llegar a una baldosa es la que tiene el coste de esa baldosa de destino. Desde una opción de la interfaz de usuario es posible elegir la heurística a utilizar en el algoritmo A*, habiendo al menos 2 diferentes.

D. También se puede elegir si queremos suavizar o no el camino generado por el algoritmo anterior (activando o desactivando la funcionalidad desde otra 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 esferas blancas mostradas sobre ellas.

E. El avatar navega y se mueve automáticamente (con comportamientos de dirección creados en el proyecto) hacia la baldosa de salida en cuanto creamos un nuevo hilo de Ariadna. Este movimiento va haciendo desaparecer la parte del hilo ya recorrida, para que sólo quede la parte del camino que falta por recorrer. Si destruimos el hilo, el avatar vuelve a su estado habitual, volviendo a ser controlado por el jugador. La implementación es eficiente y consigue maximizar las métricas (ej. escapar de un laberinto que tiene un gran número de casillas por el camino más corto, tardando el menor tiempo posible en calcular la ruta y explorando el menor número de nodos posibles durante esos cálculos).

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 IAV00-G02, la del grupo 2 del curso Inteligencia Artificial para Videojuegos 2000-2001) donde se encontrarán los repositorios de las prácticas (IAV00-G02-P1, IAV00-G02-P2 e IAV00-G02-P3).

Revisión de la documentación

En esta primera fase de revisión hay un único entregable:

• Documento de diseño y desarrollo software según la estructura habitual, en el README.md. Supone un 10% de la nota.

Revisión del resultado

En esta segunda fase de revisión los entregables son estos:

• Proyecto con todos los ficheros de código fuente y recursos del proyecto de Unity. Se incluirán enlaces a documentos compartidos en abierto (o con el profesor) mediante Google Drive, desde donde descargar todo lo que por peso o problemas de licencia no pueda mantenerse alojado en GitHub vía Git LFS. Supone un 20% de la nota.
• Fichero con la versión ejecutable para Windows de 64bits (llamado por ejemplo IAV00-G02-P2 1.0.0.zip), publicada como lanzamiento (release) en el repositorio. Cada característica del prototipo (A, B, C, D y E) correctamente implementada supone un 10% de la nota, sumando un total de 50%. El ejecutable muestra por pantalla las métricas que permiten valorar la eficiencia de la implementación: en este caso, tamaño del entorno en número de baldosas totales, número de baldosas iteradas (en la lista cerrada), número de baldosas visitadas (en la lista abierta o en la cerrada), longitud en número de baldosas y coste del camino encontrado, tiempo en milisegundos tardado por el algoritmo en encontrar dicho camino (y porcentaje del tiempo de un fotograma consumido por dicho algoritmo), y ratio de fotogramas por segundo.
• Documental con las pruebas del juego, añadiendo al documento de producción el enlace a un video oculto en YouTube (llamado por ejemplo IAV00-G02-P2), de menos de 5 minutos de duración, donde queda documentado y comentado por voz y títulos de texto el banco de pruebas realizado. El documental tiene tantas secciones como características a probar (esto es A, B, C, D y E). 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)
• FyiurAmron: PriorityQueue GitHub (2022), para cuando se usa una versión de Unity/C# (como Unity 6) que a pesar de seguir .NET 6 no ofrece nativamente el tipo PriorityQueue.

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

• Añade zonas especiales de baldosas con distinto coste al laberinto, como agua, barro, o distintas pendientes. Se puede hacer que el coste (y también la penalización de movimiento) de una casilla aumente acumulativamente según el número de minotauros que la tienen en su zona de influencia.
• Cuando se muestre el hilo de Ariadna mostrar también un hilo rojo alternativo que ignora la influencia de los minotauros (y por tanto el coste añadido a esas casillas), de manera que siempre muestre el camino más corto.
• Añade portales entre los que Teseo se puede teletransportar, pensando en heurísticas que puedan aprovechar mejor eso.
• 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, y la ubicación aproximada de minotauros y demás zonas especiales. Asegurarse de poner paredes exteriores para que los personajes no se caigan por los bordes del laberinto.
• Muestra visualmente las zonas de percepción visual y auditiva de todos los minotauros, simulando sentidos de la manera más realista posible.
• 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).
• 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 Dijkstra o sumando las heurísticas a cada salida en un mismo A*.
• Haz que el hilo cambie de color a amarillo si el minotauro se acerca a él, poniendo en contacto su zona 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.
• Implementa una variante de A* tipo D* o similar, para tratar de abordar las pruebas más extremas con laberintos muy grandes y un gran número de minotauros (que al moverse provocan un mayor número de cambios en sus zonas de influencia). Se pueden considerar heurísticas más extrañas o precalcular las rutas óptimas con respecto a la situación inicial del laberinto. De hecho se podría incluso tener varios héroes intentando escapar del laberinto a la vez.