Estimados lectores, hoy me dirijo a ustedes con la intención de hablar sobre uno de los tantos temas apasionantes de la informática y que últimamente ha sido ampliamente utilizado en el desarrollo de videojuegos, el Procedural Content Generation (PCG de ahora en adelante) o en su traducción al español Generación Procedimental de Contenido. Dado que he visto que hay mucha gente interesada en esta temática y que no saben por donde comenzar, es que me decidí a hacer una serie de tutoriales, específicamente 3 tutoriales, los cuales comienzan con esta entrada. Decidí hacer 3 post, ya que en el primero pretendo presentar los conceptos y fundamentos más básicos del tema, luego en un segundo post espero presentar algoritmos más complejos y de nivel intermedio, para finalizar con un tercer post donde abordaré específicamente el tema del 3D. Sin nada más que decir, doy por comenzado este tema, que he venido investigando y utilizando desde hace un tiempo atrás, espero como siempre que estos post les sean de utilidad y cualquier cosa, pueden dejar sus comentarios abajo.
Introducción
¿Qué es el PCG?
Aquí debo comenzar diciendo que en realidad una definición certera y aceptada por toda la academia no existe, es por eso que voy a mencionar diversas definiciones que obtuve de las referencias en las que me base:
- El PCG es la creación algorítmica de contenido de un juego, con entrada de información limitada o indirecta por parte del usuario.
- El PCG es la generación programática de contenido de un juego, utilizando un proceso aleatorio o pseudo aleatorio que da como resultado un rango impredecible de posibles espacios de juego.
- El PCG es el concepto o paradigma por el cual todas las piezas de contenido de un juego pueden ser creadas solo mediante la utilización de la programación.
En otras palabras, el PCG es la creación de contenido de un juego mediante la programación. Y para comprender mejor esto, debo explicar su nombre. La palabra clave Procedural, viene de procedimiento, que en la programación es simplemente una instrucción que debe ser ejecutada. Por supuesto los procedimientos (también conocidos como funciones y métodos) son el principal paradigma en la programación. Por otra parte el Content o contenido es todo lo que se presenta ante el usuario, es decir, niveles, modelos, texturas, música, sonidos, historias, inteligencia artificial, entre otras tantas.
¿Por qué deberíamos utilizar el PCG?
Tal vez la respuesta a esta pregunta sea obvia, pero de igual manera es importante analizarla. Por supuesto la razón primordial para utilizar PCG es que nos quita la necesidad (casi en su totalidad) de contar con un diseñador o artista humano que genere contenido para el juego. Sabemos que los humanos somos lentos y costosos y por lo general se necesita cada vez más de ellos para crear contenido de alta calidad para los videojuegos de la industria. Pero si utilizamos el PCG como la roca fundamental sobre la que edificamos el videojuego, nos estaremos ahorrando varios hombres, que podrían haber diseñado o creado contenido de manera manual y no automática y eficiente como lo hacen los algoritmos. Se dice que las ventajas de utilizar el PCG son la unicidad, la robustez, la flexibilidad, la adaptabilidad que aportan al videojuego. Sobre todo ya que podríamos hacer un juego rejugable casi de manera infinita (como veremos más adelante al implementar algoritmos). Un claro ejemplo de esto es el sistema de generación de armas del famoso videojuego Borderlands que se puede apreciar en la imagen.
Teoría Fundamental
Números Pseudo Aleatorios
Los números aleatorios han sido utilizados en una gran cantidad de juegos desde hace mucho tiempo, desde juegos tradicionales como lo son los juegos de cartas hasta los juegos de mesa con dados. Los números aleatorios entregan al juego un factor que los hace impredecibles. Y sabemos que las cosas impredecibles son emocionantes, desafiantes y ofrecen una experiencia única, por lo tanto entregan un valor único a un universo.
En las ciencias de la computación el estudio de los números aleatorios se ha enfocado por lo general en su uso en la criptografía y la ciber seguridad, por supuesto mediante complejos algoritmos y fórmulas matemáticas, que aquí no serán estudiadas para su alivio. Unity de hecho ya provee una clase llamada Random, la que permite generar números aleatorios, como veremos más adelante.
Números Aleatorios VS Números Pseudo Aleatorios
Y aquí viene la cruda realidad nuevamente a recordarnos porque somos imperfectos. Han de saber queridos lectores que los números pseudo aleatorios tal como su nombre lo predicen, no son números aleatorios. Un evento realmente aleatorio sería por ejemplo lanzar un dado. Pero por otra parte los números pseudo aleatorios son preferidos en la programación de juegos ya que son mucho más sencillos de generar y por supuesto también de reproducir los mismos resultados una y otra vez (ya les explico por qué). Imaginen si lanzamos un dado de 6 caras y nos sale 1 en la cara, luego si lo lanzamos nuevamente y queremos reproducir el mismo resultado tenemos una probabilidad de 1/6 que el dado nos entregue el mismo resultado, ahora piensen en un dado de 1 millón de caras, si lanzamos y nos sale el número 424.342 en la cara del dado, entonces para poder reproducir el mismo resultado tendríamos 1/1.000.000 como probabilidad de que nos salga el mismo resultado, lo que significaría para nosotros gran inversión de tiempo seguramente, ¿ya ven por qué utilizar números pseudo aleatorios nos conviene más?
En los números pseudo aleatorios existe algo conocido como Seed o Semilla que no es más que la representación (en número, o string) de la aleatoriedad que usara nuestro generador de números pseudo aleatorios y la cual nos será de vital importancia a la hora de replicar un resultado o secuencia de acciones. Por ejemplo si generamos un nivel basados en un seed con el número 5 con X algoritmo, luego podemos replicarlo fácilmente al hacer que el seed simplemente tenga el mismo valor que antes. Pero por otra parte la desventaja que esto entrega es que puede darse el caso en que las combinaciones de reglas posibles de nuestro algoritmo se acaben y luego de un tiempo nuestra seed replique los mismos resultados antes vistos, pero en la mayoría de los casos eso será controlado fácilmente.
En fin, con esto ya comprendido creo que es hora de ponernos manos a la obra. Si llegados a este punto no comprendieron lo que arriba está escrito les recomiendo ver este video que quizás sea más preciso y exacto que mi explicación, de lo contrario pueden seguir con la lectura.
Programando
A continuación voy a presentar al lector 2 ejemplos que creo son indicados para poder comenzar a entender de manera práctica esta temática tan apasionante. El primero de ellos se trata de un programa que genera el típico “Hola Mundo”, pero esta vez ordenado de manera procedimental, si bien es cierto este es un ejercicio muy pequeño y sencillo, nos servirá para afirmar los conceptos anteriormente estudiados y aprendidos. Luego en un segundo ejemplo mucho más desafiante que el primero, explicaré paso a paso como crear la estructura de una cueva utilizando el PCG, por supuesto este algoritmo será mucho más complejo (aunque no imposible de entender) que el primero.
Hola Mundo
Bien conocido es el típico programa que la mayoría de nosotros, cuando dábamos nuestros primeros pasos en la programación, creamos en nuestra primera aventura con una IDE, y con la que logramos un resultado que a pesar de ser sencillo, nos permitió vislumbrar todo el potencial que tienen los computadores para seguir instrucciones de manera ordenada, siendo el único resultado en nuestra consola una cadena que dice: “HolaMundo”. Bueno tomando esto en cuenta quise esta vez llevarlo al plano de los algoritmos procedimentales, aunque no lo considero precisamente 100% apegado a la definición que vimos antes, pero si nos dará una primera impresión de lo que les venía hablando sobre los universos que pueden ser creados por un computador. Lo que se deseamos lograr como objetivo principal con este pequeño ejemplo, es que podamos generar todas las combinaciones posibles de las letras de las palabras “HolaMundo”, por supuesto cada vez que el seed tome un valor determinado, la combinación de letras debería ser distinta, considerando claro que tenemos 9 letras, entonces la cantidad total de combinaciones posibles para mezclar esas letras sería por fórmula 9! que es el equivalente a 362.880 combinaciones. Por lo tanto nuestra seed puede dar un resultado distinto 362.880 veces, y luego de eso, tal y como estudiamos anteriormente se comenzarán a repetir los resultados.
Sin más preámbulos vamos a analizar el siguiente trozo de código que nos permite generar de manera procedimental las combinaciones de letras de las palabras “HolaMundo”.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class HelloWorld_PCG : MonoBehaviour {
public int seed = 1;
private string palabraFinal;
private List<string> letras = new List<string>();
void Awake(){
letras.Add("H");
letras.Add("o");
letras.Add("l");
letras.Add("a");
letras.Add("M");
letras.Add("u");
letras.Add("n");
letras.Add("d");
letras.Add("o");
}
void Start(){
Random.seed = seed;
for (int i = 0; i < letras.Count; i++) {
palabraFinal += letras[i];
}
Debug.Log("Nuestra palabra inicialmente es: " +palabraFinal);
palabraFinal = "";
while(letras.Count > 0){
int index = Random.Range(0,letras.Count);
palabraFinal += letras[index];
letras.RemoveAt(index);
}
Debug.Log("Nuestra palabra finalmente es: " +palabraFinal);
}
}
Lo primero que debemos haber notado al mirar el código es que tenemos una variable de tipo int que almacena nuestra seed o semilla, que es la que se encargará por supuesto de decidir la secuencia de números que devuelve la clase Random. Luego se puede observar una variable de tipo string que almacena la palabra final generada por el algoritmo. Y por último una tercera variable que almacena todas las letras de la cadena “HolaMundo” de tipo List almacenando string. En el método Awake ingresamos las letras de la cadena a la lista de manera ordenada, aunque claro está que en este caso el orden no debería influir en lo absoluto más allá de mostrar como era la cadena antes de ser desordenada por la clase Random. Luego en el método Start lo primero que se hace es asignar el seed de nuestra variable al seed de la clase Random, después se recorre con un for la lista de letras y se van ligando a la cadena de la palabra final, para mostrar como era la palabra antes de ser desordenada por consola. Y por último se tiene un while con la condición: mientras queden letras en la lista, y si eso es cierto, entonces se obtiene un índice con la clase Random y el método Range con valores entre 0 y la cantidad de letras (aunque el último valor es exclusivo), posteriormente se concatena a la palabra final la letra que indica el índice obtenido y se quita de la lista de letras la letra ubicada en el índice (esto claro con el objetivo de poder salir en algún momento del ciclo while). Una vez finalizado el ciclo while se imprime por consola la palabra final entregada por nuestra aleatoriedad (especificada por el seed entregado).
Como podrán darse cuenta las posibilidades son muchas, como para generalas a mano, y con este simple algoritmo ya podemos comprender porque se dice que el PCG es una de las maneras más efectivas para generar mundos completos a partir de un seed, y porque le entrega rejugabilidad a los juegos casi de manera infinita (espero que sus mentes tengan la imaginación suficiente para pensar que cada cadena puede representar un mundo distinto).
Generando Cuevas
Pasando ahora a la parte más “compleja” de este post, nuestro objetivo será ahora generar una cueva de manera procedimental, con parámetros que nos permitan entregarle al jugador una solución distinta, y probablemente un mundo distinto cada vez que ejecute el programa. Pero para hacer realidad nuestro sueño dorado, primero debemos comprender un concepto conocido como Cellular Autómata o en su traducción al español Autómata Celular, que no es más que un modelo computacional discreto (asumo que el lector sabe el significado de discreto en términos matemáticos, y si no es así, espero lo puedan googlear). Los autómatas celulares han sido ampliamente estudiados en la informática, la física e incluso algunas ramas de la biología, como modelos de computación, de crecimiento, de desarrollo, de fenómenos físicos, etc. Pero para su alegría sus conceptos básicos son en realidad muy simples y pueden explicarse en unos pocos párrafos y una imagen o dos. Un autómata celular consiste en una cuadrícula de dimensiones de NxM, un conjunto de estados posibles, y un conjunto de reglas de transición. En esta cuadrícula cada celda puede tomar distintos estados, pero en el caso más simple, puede estar encendida o apagada (tomar un valor 1 o 0). A medida que se realizan iteraciones sobre el autómata este va evolucionando en pasos discretos y siguiendo sus propias reglas. En cada tiempo t, cada celda decide su nuevo estado basado en el estado de sí misma y todas las celdas de su entorno (sus vecinas) en el momento t-1. Estos vecinos pueden ser tomados en cuenta siguiendo 2 tipos de modelos, que se pueden observar en las siguientes figuras:
En nuestro caso utilizaremos el modelo de Moore, para capturar una celda especifica y aplicar su regla de transición tomando en cuenta los 8 vecinos de la celda actual (celda central C), como veremos más adelante.
Los parámetros que utilizaremos para el control de las cuevas generadas serán:
- Ancho de la cueva
- Altura de la cueva
- Semilla (seed)
- Porcentaje de Muros
- Cantidad de iteraciones de suavizado
Estos parámetros nos permitirán más o menos mantener un control sobre las cuevas que se generen, y por supuesto replicar las estructuras que encontremos interesantes. Entonces se estarán preguntando pero y cómo realmente generamos las cuevas, y aquí viene lo entretenido, ya que aplicando un autómata celular sobre un algoritmo de randomización veremos como el caos se convierte en algo estructurado. Fíjense en el siguiente código:
using UnityEngine;
using System.Collections;
public class GeneradorCaos : MonoBehaviour {
public int anchoCueva = 5;
public int alturaCueva = 5;
public int semilla = 26;
public bool semillaAleatoria = false;
[Range(0,100)]
public int porcentajeMuro = 50;
private int[,] cueva;
void Start(){
CrearCueva();
}
void Update() {
if (Input.GetMouseButtonDown(0)) {
CrearCueva();
}
}
void CrearCueva(){
cueva = new int[anchoCueva, alturaCueva];
LlenarCuevaAleatoriamente();
}
void LlenarCuevaAleatoriamente(){
Random.seed = (semillaAleatoria)?Random.Range(int.MinValue,int.MaxValue):semilla;
for (int i = 0; i < anchoCueva; i++) {//Filas
for (int j = 0; j < alturaCueva; j++) {//Columnas
if(i == 0 || i == (anchoCueva-1) || j == 0 || j == (alturaCueva-1)){
cueva[i,j] = 1;
}else{
int probabilidad = Random.Range(0,100);
if(probabilidad < porcentajeMuro){
cueva[i,j] = 1;
}else{
cueva[i,j] = 0;
}
}
}
}
}
void OnDrawGizmos(){
if(cueva != null){
for (int i = 0; i < anchoCueva; i++) {//Filas
for (int j = 0; j < alturaCueva; j++) {//Columnas
Gizmos.color = (cueva[i,j] == 0)? Color.white : Color.black;
Gizmos.DrawCube(new Vector3(i,j,0f), new Vector3(0.9f, 0.9f, 0.9f));
}
}
}
}
}
Este código simplemente genera caos, como pueden ver en la figura, a pesar de que utiliza algunos de los parámetros que nombré anteriormente, como por ejemplo el seed, el alto, el ancho, e incluso el porcentaje de muros, finalmente solo es capaz de generar caos, ya que no ha sido sometido al autómata celular, es decir, no evoluciona y su forma siempre es el caos, como se puede observar en la figura (los cuadrados o celdas negras representan muros y los blancos suelo, en este caso el porcentaje de muros fue 50%).
Ahora para solucionar esto simplemente hacemos uso del autómata celular, que como bien dije antes, permitirá hacer evolucionar al mapa de manera tal que una vez aplicadas sus reglas (la de conjugación de vecinos), entonces tomará una forma similar a la de una cueva, en términos de estructura, y el código es el siguiente.
using UnityEngine;
using System.Collections;
public class GeneradorCuevas : MonoBehaviour {
public int anchoCueva = 5;
public int alturaCueva = 5;
public int semilla = 26;
public bool semillaAleatoria = false;
[Range(0,100)]
public int porcentajeMuro = 50;
public int iteracionesSuavizado = 1;
private int[,] cueva;
void Start(){
CrearCueva();
}
void Update() {
if (Input.GetMouseButtonDown(0)) {
CrearCueva();
}
}
void CrearCueva(){
cueva = new int[anchoCueva, alturaCueva];
LlenarCuevaAleatoriamente();
for (int i = 0; i < iteracionesSuavizado; i++) {
SuavizarMapa();
}
}
void LlenarCuevaAleatoriamente(){
Random.seed = (semillaAleatoria)?Random.Range(int.MinValue,int.MaxValue):semilla;
for (int i = 0; i < anchoCueva; i++) {//Filas
for (int j = 0; j < alturaCueva; j++) {//Columnas
if(i == 0 || i == (anchoCueva-1) || j == 0 || j == (alturaCueva-1)){
cueva[i,j] = 1;
}else{
int probabilidad = Random.Range(0,100);
if(probabilidad < porcentajeMuro){
cueva[i,j] = 1;
}else{
cueva[i,j] = 0;
}
}
}
}
}
void SuavizarMapa(){
for (int i = 0; i < anchoCueva; i++) {
for (int j = 0; j < alturaCueva; j++) {
int cantidadVecinosMuro = ObtenerVecinosMuro(i,j);
if(cantidadVecinosMuro > 4){
cueva[i,j] = 1;
}else {
cueva[i,j] = 0;
}
}
}
}
int ObtenerVecinosMuro(int x, int y){
int cantidadMuros = 0;
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if(i >= 0 && i < anchoCueva && j >= 0 && j < alturaCueva){
if(i != x || j != y){
cantidadMuros += cueva[i,j];
}
}else{
cantidadMuros++;
}
}
}
return cantidadMuros;
}
void OnDrawGizmos(){
if(cueva != null){
for (int i = 0; i < anchoCueva; i++) {//Filas
for (int j = 0; j < alturaCueva; j++) {//Columnas
Gizmos.color = (cueva[i,j] == 0)? Color.white : Color.black;
Gizmos.DrawCube(new Vector3(i,j,0f), new Vector3(0.9f, 0.9f, 0.9f));
}
}
}
}
}
Lo único que ha cambiado ahora es que el código toma en cuenta la regla de los vecinos,que nos indica que si hay más de 4 vecinos que son muros (es decir más de la mitad del total de 8 vecinos), entonces nuestra celda actual debe convertirse también en muro, por el contrario si son menos de 4 vecinos muros, entonces nuestra celda debe ser un suelo, y solo con esta pequeña modificación y regla ahora nuestro algoritmo arroja resultados como estos, con los mismos parámetros anteriores pero con una cantidad de iteraciones de suavizado igual a 5.
Y ahora piensen en que este resultado es utilizando solo los siguientes parámetros simplemente:
¿Alcanzan realmente a asimilar lo que esto significa? Si su respuesta es no, entonces los invito a jugar modificando los parámetros para que puedan observar toda la cantidad de diversos resultados que pueden obtener. Y por cierto no sé si se dieron cuenta pero a nuestra seed cada vez que la variable seedAleatoria esta activada, entonces le asignamos un valor aleatorio entre el mínimo número entero posible para el procesador y el máximo (Random.seed = (semillaAleatoria)?Random.Range(int.MinValue,int.MaxValue):semilla;) y si quieren una seed infinita, podrían por qué no utilizar como medida el tiempo actual, que solo fluye hacia adelante como sabemos…
Pero no todo es perfecto y si se dan cuenta en realidad nuestra estructura genera en la mayoría de los casos al menos una zona en la que hay solamente suelo, pero que está a si mismo aislada de las demás, por lo que no hay una conexión directa entre las zonas. Para esto por supuesto existe una solución que por lo demás está más allá del alcance de este post pero que pueden buscar por su cuenta partiendo por algo denominado Flood Fill Algorithm o Algoritmo de relleno por difusión.
Este algoritmo puede ser perfectamente utilizado para reconocer todas aquellas zonas que quedaron aisladas de las demás y por supuesto poder conectarlas, claro si que en el caso de conectarlas deberán idear sus propias soluciones o bien recurrir al clásico A* Pathfindinüg Algorithm, pero eso ya es otro cuento, que requiere de un post aparte.
Pseudo-Conclusiones
En fin, espero que este post les pueda servir como una introducción a esta temática tan interesante (me extendí mucho más de lo que debía pero bueno son los gajes del oficio) y que para mi ha sido un área de estudio desde hace algún tiempo atrás. Sin más que decir, esperando que sus cerebros alucinen con tantos bellos algoritmos, de los cuales puedan sacar sus propias conclusiones, me despido de ustedes, y cualquier duda o consulta, ya saben donde la pueden realizar, saludos!
Stories about an indie video game developer 
Super completo e interensantisimo! Felicidades aunque lo orientas a Unity lo comparto en la comunidad de Unreal engine 4 https://www.facebook.com/unrealenginespain/?ref=hl
LikeLiked by 1 person
Hey! Muchas gracias por tu comentario. Si la verdad es que este blog completo en realidad esta orientado a Unity, que es el motor que actualmente utilizo para crear videojuegos, pero también agradezco tu interés por publicarlo en su comunidad de Unreal! Saludos! 🙂
LikeLike