Categorías
Informática Universitario Videojuego

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. Ambos personajes se encuentran en el laberinto del Minotauro, escenario donde se utiliza 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 aplicar la “maldición” que le lanza Ariadna de forma anticipada, para que sea imposible acabar con el monstruo. Cuando el héroe se encuentra próximo al enemigo, lo combate, lo que en la práctica supone 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, vamos a crear un prototipo en el que el jugador controla el movimiento de Teseo por los pasillos del laberinto. La bestia mitológica consiste en un agente inteligente que se dedica a merodear por allí, siguiendo a Teseo en caso de percibirlo. El hilo de Ariadna funciona, cuando lo activemos, dibujando una línea blanca en 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, a saber: la baldosa donde se encuentra el Minotauro es intransitable, y las baldosas vecinas al Minotauro (su “zona de influencia”) tienen mayor coste que las demás.

Este prototipo aplica 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 el movimiento.

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 pasa a ser controlado por la máquina y procede a salir del laberinto navegando y moviéndose de manera automática, hasta que desactivamos 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: IAV-Navegacion.

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 cruzarnos con el enemigo). El avatar esta controlado manualmente por el jugador, preferiblemente en línea recta hacia donde se haga clic izquierdo del ratón.

B. En mitad del laberinto están los enemigos (uno o varios minotauros, de número también configurable), que realizan un merodeo constante, pasando a perseguir al avatar si lo perciben con la vista o con el oído (basta con moverse para hacer ruido y ser detectado por un enemigo cercano). Además de gestionar los sentidos, se muestra visualmente el área de influencia de cada minotauro, las baldosas vecinas que ralentizan a Teseo si intenta atravesarlas.

C. El camino más corto a la baldosa de salida (sin navegación en diagonal) calculado mediante A* (hilo de Ariadna) se representa pintado con una línea blanca y destacando cada baldosa que lo compone con una esfera blanca. Aparece cada vez que se activa la navegación y comienza por tanto el movimiento automático del avatar hasta la salida (con el clic derecho del ratón se activa o desactiva, como un interruptor). Se tienen en cuenta todos los costes, incluido el de la baldosa en la que está cada minotauro y su zona de influencia, cuyas baldosas cuestan 5 veces más que una baldosa normal (la conexión hacia esa baldosa es la que se encarece). Desde una opción de la interfaz de usuario es posible elegir la heurística utilizada en el algoritmo A*.

D. Es posible 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.

E. El avatar navega y se mueve automáticamente (con comportamientos de dirección) hacia 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 a su estado habitual, volviendo a poder ser controlado por el jugador.

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

Revisión de la documentación

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

  • Documento de producción 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 IAV24-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 visitadas, 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. ¡Ojo, para que funcione bien el ejecutable hay que llevarse manualmente la carpeta Maps del punto de partida y copiarla dentro de la carpeta que se genera junto al ejecutable! (llamada por ejemplo IAV24-G02-P2_Data, junto a IAV24-G02-P2.exe).
  • Documental con las pruebas del juego, añadiendo al documento de producción el enlace a un video oculto en YouTube (llamado por ejemplo IAV24-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.

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.
  • 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.
  • Muestra visualmente las zonas de percepción visual y auditiva de todos los minotauros.
  • 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 á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.
  • 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.

Esta página está licenciada bajo CC BY-NC-SA 4.0 por Laboratorios Narratech.