Tecnologías Específicas

Computación

Descripcion y Objetivos

Todos los juegos de mesa tienen un punto común: el tablero. Pueden llegar a ser tan simples como una única pila de descartes para juegos de cartas, pero normalmente su complejidad es mayor. La distribución de los tableros de juego varía desde juegos como el ajedrez hasta juegos de gran complejidad como los de gestión de recursos. En este trabajo nos centraremos en los tableros de los juegos de rol de mesa, llamados mazmorras, ya que son altamente personalizables y con una complejidad muy variable. Hay que indicar que en este caso hay una gran diferencia con respecto a un juego de cartas tradicional o el ajadrez. Por ejemplo, el tablero de ajedrez 'normal' siempre tiene la misma configuración.

Sin embargo, una de las riquezas de los juegos de rol basados en escenarios con mazmorras, es que hay múltiples posibilidades de configuración, no solo en el número de zonas, sino también en cómo se interconectan, y cada configuración presentará unas características diferentes para ser jugadas. Con este trabajo, se tratará de encontrar distintas soluciones algorítmicas a la generación de estás mazmorras de forma automática, posteriormente analizando su complejidad y calidad mediante unas métricas cuidadosamente seleccionadas.

Los objetivos específicos de este trabajo son:

• Explorar diferentes algoritmos de generación de mazmorras: Investigar y describir los principales enfoques, entre los que podríamos considerar algoritmos de división de espacio, generación basada en grafos, generación procedimental basada en ruido y quizás técnicas de optimización combinatoria.
• Diseñar e implementar distintas soluciones: de entre los algoritmos escogidos como idóneos, elegir un subconjunto representativo e implementarlos de forma que se puedan generar escenarios.
• Analizar la complejidad de los algoritmos: Evaluar la complejidad computacional de cada algoritmo, midiendo aspectos como el tiempo de ejecución y el uso de memoria.
• Desarrollar un conjunto de métricas de calidad: Definir métricas que midan algunos aspectos que sean susceptibles de ser cuantificables, y que representen itinerarios de amplia variedad.
• Comparar las soluciones propuestas: Realizar experimentos con los diferentes algoritmos y comparar sus resultados según las métricas definidas, proporcionando una visión clara de los puntos fuertes y débiles de cada enfoque.

 

Metodología y Competencias

El trabajo seguirá un enfoque estructurado dividido en varias fases:

1- Revisión bibliográfica: Se llevará a cabo una investigación exhaustiva de los algoritmos existentes para la generación de mazmorras. 

2- Selección de algoritmos: De entre los algoritmos estudiados, se seleccionarán los más representativos, buscando diversidad en su enfoque para enriquecer la comparativa final. 

3- Implementación de los algoritmos: Se desarrollarán o adaptarán implementaciones de los algoritmos seleccionados en el lenguaje de programación Python. Se añadirá la posibilidad de crear una salida visual (fichero imagen, por ejemplo) para poder ver la representación de las mazmorras generadas. 

4- Definición de métricas de evaluación: Se definirán un conjunto de métricas cualitativas y cuantitativas para medir la calidad de las mazmorras generadas. Estas métricas podrían incluir  aspectos como cohesión, navegabilidad, variedad, riqueza y tiempo de ejecución.

5- Pruebas y comparación: Se realizarán pruebas de los algoritmos utilizando conjuntos de datos o parámetros previamente definidos, generando múltiples mazmorras y evaluándolas según las métricas establecidas. Se tratará de identificar las principales fortalezas y debilidades de cada enfoque.

Al final del desarrollo, la memoria del TFG documentará el proceso de diseño, los algoritmos desarrollados, la descripción y explicación de las métricas, la comparación en función de ellas, y los resultados obtenidos del análisis de esta comparativa. Se aportará también el código de programación, que se prevé realizar en python.

Se trabajarán principalmente (en distinto grado) las siguientes competencias específicas de la tecnología de computación:

• [CM1] Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
• [CM3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
• [CM4] Capacidad para conocer los fundamentos, paradigmas y técnicas propias de los sistemas inteligentes y analizar, diseñar y construir sistemas, servicios y aplicaciones informáticas que utilicen dichas técnicas en cualquier ámbito de aplicación.
• [CM5] Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes o entornos inteligentes.

 

Medios a utilizar

Se prevé que gran parte de la implementación se desarrolle en Python. Se espera que el alumno tenga un dominio de dicho lenguaje de programación, y buenas habilidades como programador. Se necesitará un ordenador de rendimiento CPU medio-alto, buena memoria RAM y buena capacidad de almacenamiento en disco.

 

Bibliografía

• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson.

• Noor Shaker , Julian Togelius , Mark J. Nelson (2016). Procedural Content Generation in Games. Springer [https://link.springer.com/book/10.1007/978-3-319-42716-4]

• Van Der Linden, Roland, Ricardo Lopes, and Rafael Bidarra (2013). "Procedural generation of dungeons." IEEE Transactions on Computational Intelligence and AI in Games 6.1: 78-89

• Apuntes de las asignaturas Estructuras de Datos, Metodología de la Programación, Sistemas Inteligentes y Diseño de Algoritmos