Diseño de un algoritmo de arrecifes de corales para la resolución de pantallas del videojuego Lemmings

Abstract

The game of Lemmings was developed in 1991 and achieved great popularity during that decade. In the game, a population of Lemmings enters the level at a specific point and a number of them must reach the exit. To do this, the player has a set of skills that can be assigned a given number of times at different Lemmings. With these actions Lemmings change the environment of the screen (building bridges, digging, climbing walls, etc. ) and build a safe path from the starting point to the exit of the screen. It has been proved that this game has a NP-Complete complexity. Regarding methods of Artificial Intelligence for screen resolution, the most common is the use of genetic algorithms and algorithms colonies ant. These Computational Intelligence algorithms provide good results because of their stochastic component. Recently, a new algorithm has been developed called bio-inspired Coral Reef Optimization. This new algorithm is based on the competition between corals by a space inside the reef. This algorithm has been applied successfully in various numerical optimization problems. In this Bachelor Thesis is proposed in the development and analysis of an coral algorithm for resolution of screens of the videogame Lemmings.

El videojuego de los Lemmings fue desarrollado en 1991 y alcanzó gran popularidad durante esa década. En el juego, una población de Lemmings entra al nivel por un punto específico y un número determinado de ellos deben alcanzar la salida. Para ello, el jugador dispone de un conjunto de habilidades que puede asignar un número determinado de veces a diferentes Lemmings. Con estas acciones los Lemmings modifican el entorno de la pantalla (creando puentes, excavando, trepando paredes, etc) y construyen un camino seguro desde el punto de entrada hasta la salida de la pantalla. Se ha demostrado que este videojuego tiene una complejidad NP-Completa. En cuanto a métodos de Inteligencia Artificial para la resolución de pantallas, lo más común es la utilización de algoritmos genéticos y algoritmos de colonias de hormigas. Estos algoritmos de Inteligencia Computacional proporcionan buenos resultados debido a su componente estocástica. Recientemente, se ha desarrollado un nuevo algoritmo bio-inspirado llamado Coral Reef Optimization. Este nuevo algoritmo se basa en la competición entre corales por un espacio dentro del arrecife. Este algoritmo se ha aplicado satisfactoriamente en la optimización de diversos problemas numéricos. En este Trabajo Fin de Grado se propone en el desarrollo y análisis de un algoritmo de coral para la resolución de pantallas del videojuego Lemmings.