DISEÑO DE ALGORITMO DE GENERACIÓN PROCEDURAL ENFOCADO A VIDEOJUEGOS
Abstract
La generación automática de mapas para videojuegos es un problema crucial para poder ofrecer escenarios creativos, innovadores y que otorguen experiencias distintas cada vez que se vuelven a jugar los videojuegos. Dentro de las formas en que se puede abarcar este problema está la generación de contenido procedural o PCG por sus siglas en inglés, la cual entre todas las cosas que puede generar, se encuentra el generar mapas para videojuegos. Dentro de las formas en que se ha usado PCG en el pasado para abarcar este problema se encuentran: autómatas celulares, gramática generativa, algoritmos genéticos, basado en restricciones, entre otros. De estos enfoques se decidió utilizar un algoritmo genético, ya que entrega los mejores resultados de lo que se quiere lograr. Los algoritmos genéticos trabajan sobre una población de soluciones que son sometidas a las fases de evaluación, elitismo, selección, cruzamiento y mutación y esto se repite durante varias generaciones para ir mejorando las soluciones en cada una. Los parámetros usados fueron elegidos para tener el mayor control posible sobre los resultados finales, de manera de ajustar cada tipo de celda presente en el mapa. Los resultados obtenidos fueron satisfactorios para las instancias pequeñas y medianas, sin embargo fue en las instancias más grandes donde el algoritmo necesito de un mayor tiempo de cómputo para entregar los resultados deseados. The automatic generation of maps for videogames is a crucial problem to be able to offer creative, innovative scenarios and that they can give different experiences each time the videogame are played again. Among the way sin which this problem can be covered is the procedural content generation or PCG by its acronym in English, which among all the things that can generate, is to generate maps for video games. Among the ways in which PCG has been used in the past to cover this problem are: cellular automata, generative grammar, genetic algorithms, constraint-based, among others. From these approaches it was decided to use a genetic algorithm, since it delivers the best results of what we want to achieve with the algorithm. The genetic algorithms work on a population of solutions that are subjected to the phases of evaluation, elitism, selection, crossing and mutation and this is repeated over several generations to improve the solutions in each one. The parameters used were chosen to have the greatest possible control over the final results, in order to adjust each type of cell present in the map. The results obtained were satisfactory for the small and medium instances, however it was in the larger instances where the algorithm needed a longer computing time to deliver the desired results.