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.