Cómo funciona la generación de mapas procedurales en Reactor Heart

En éste artículo hablaré de las conclusiones a las que he llegado tras el desarrollo del sistema de generación de mapas procedimental de Reactor Heart. Lo que explico no tiene por qué ser lo mejor, de hecho hoy en día sigo buscando mejoras a mi sistema. Al principio cometí muchos errores de novato en este campo y aprendí bastante superándolos, espero que le sea de ayuda y si alguien sabe como mejorar mi sistema sus sugerencias serán bienvenidas.

Cuando empecé a desarrollar Reactor Heart pronto me di cuenta de que necesitaría un universo infinito y además que se generara automáticamente. Habría sido un juego muy malo si tuviera un universo limitado por lo que empecé a esbozar las primeras ideas basándome en la información que encontré en diversas páginas y artículos que hablaban sobre el tema de la generación procedural.

La primera idea fue la de hacer un generador de sectores gigantes que alojarían sistemas planetarios, nubes de asteroides y todo tipo de cosas. Así que empecé a hacer funciones que generaban los elementos básicos del sistema planetario: planetas, asteroides, lunas. Los planetas eran círculos rellenos de radio variable, las lunas eran lo mismo pero más pequeño y los asteroides los generaba con un algoritmo que creaba un contorno con una forma lógica y medianamente redonda.

PlanetWithMoon Asteroid AsteroidPlanet

Y con estos elementos conformé lo que sería la generación de un sistema planetario en el que habían planetas en determinadas órbitas alrededor de un centro(en el que colocaría una estrella). Se disponían con un ángulo y distancia del centro aleatorio, restringido con unos rangos razonables para que estuvieran posicionados coherentemente.

Generation

Efectivamente el sistema de generación funcionaba bien en cuanto a lo que generaba pero había cuatro problemas:

  • Tardaba 15 segundos en generarlo todo.
  • Las formas de los asteroides no se asemejaban a lo que yo quería conseguir.
  • Se tardaba mucho en generar cada asteroide con el agloritmo que había creado.
  • Dependiendo de la disposición aleatoria podían quedar espacios muy vacíos.

Para un mapa limitado un tiempo de 15 segundos no es tan malo porque haces la generación una vez y ya está, pero cuando se trata de un universo enorme que los usuarios van a querer recorrer durante horas es impermisible dejarlos esperando ese tiempo entre sistema y sistema. Además los asteroides no tenían una forma muy buena porque tendían a ser romboides ademas de que tardaban demasiado en generarse.

El primer problema que arreglé fue el de los asteroides que era el más evidente. Cree un editor de asteroides en el que podía pre-diseñar un set de asteroides y guardarlo en un fichero que luego cargaba el videojuego. Al eliminar la generación de la ecuación el tiempo mejoraba muchísimo. Mejoró más aún cuando incorporé pre-procesamiento a la hora de exportar en el editor. A parte de esto las formas de los asteroides eran más coherentes y al combinarse formaban asteroides más grandes con formas geniales.

Una vez solventado el problema de los asteroides seguía sin tener un tiempo aceptable, aunque era mucho mejor que el anterior. Tenía dos opciones:

  • Trabajar en paralelo para mejorar los tiempos del algoritmo.
  • Reducir la complejidad del sistema que generaba.

En muchos sistemas que requerían de generación en tiempo real lo hacían reduciendo el tamaño de la “unidad” de generación para así poder particionar mejor el trabajo en trozos que costaba menos tiempo de cómputo generar. En ese entonces mi “unidad” era el sector y para seguir esta nueva filosofía decidí hacerlos más pequeños. El sector sería un espacio de 6×6 chunks (frente a los 50×50 que ocupaba el sistema planetario) que podría estar ocupado por un planeta, un planeta con lunas o asteroides, una nube de asteroides, una nebulosa, una estrella, etc…  El sistema funcionó a la perfección. Reduje el tiempo a 0.07-0.1 segundos de media utilizando este método( y también mediante algunas optimizaciones del proceso a bajo nivel).

Tip: Utilizar una herramienta de profiling como gprof ayuda mucho para ver en qué funciones o métodos se hacen más llamadas y así identificar la parte del código que más necesitas optimizar .

SectorSystem

Todavía falta paralelizar el sistema aunque lo diseñé pensando en el futuro para que en versiones más avanzadas me sea fácil integrarlo. Ésta es mi experiencia pero seguro que hay muchas formas de mejorarla.