Autómata Celular
Una de las técnicas más simples de implementar para PCG es el autómata celular. Es probablemente una de las primeras técnicas que encuentres si buscas cómo generar cuevas o dungeons procedurales para un videojuego. Un ejemplo de pseudocódigo del algoritmo consiste en lo siguiente:
function cellularAutomataPCG(matrix, iterations, rules) return simulated matrix workMatrix ← copy(matrix) for i in iterations do for each cellPosition in matrix do adjacencyMatrix ← get8AdjacencyMatrix(cellPosition, matrix) newValue ← applyRules(adjacencyMatrix, rules) workMatrix[cellPosition] ← newValue swap(matrix, workMatrix) return matrix
La función recibe una matriz booleana con sus valores ya inicializados, por ejemplo de forma aleatoria, el número de iteraciones que se aplica la simulación y las reglas que se usan. Dentro de cada iteración de la simulación se recorren todas las celdas de la matriz. Para cada una de ellas, se extrae una matriz 3x3 que contiene el valor de la celda actual y todos sus adyacentes. Por último, se aplica la matriz de adyacencia y las reglas de entrada para determinar el siguiente valor de la celda, almacenándose el resultado en una matriz auxiliar. Se interpreta que las celdas de la matriz con valores 0 o 1 son celdas muertas o vivas respectivamente. Algo a tener en cuenta es que la simulación es muy fácilmente paralelizable, por lo que se puede beneficiar de procesadores con varios núcleos o incluso ejecutarse en una GPU.
Lo más importante que determinará la evolución de la matriz es el conjunto de reglas que se hayan seleccionado, como por ejemplo B678/S345678 extraída de jeremykun.com. Esta regla particular significa que si una celda muerta tiene entre entre 6 y 8 celdas vivas vecinas, entonces pasa a estar viva; si una celda viva tiene entre 3 y 8 celdas vivas vecinas, entonces sigue viva; si una celda viva tiene menos de 3 celdas vivas vecinas, entonces pasa a muerta.
Los resultados que da este sistema de PCG son mapas que son similares a cuevas más o menos abiertas en función de las reglas y número de iteraciones. La simulación es muy local, en cada iteración solo se tienen en cuenta las celdas vecinas de una posición para determinar si pasa a vivo o muerto, por lo que no tiene control sobre conceptos de mayor abstracción como salas o pasillos. Debido a esto, no se tiene control directo sobre la topología de la cueva generada, ni las salas, ni pasillos, o si siquiera es conexo, por lo que pueden haber zonas que no pueden ser alcanzables. Es necesario hacer una etapa de post-procesado para detectar zonas no alcanzables para eliminarlas o abrir pasillos para que se pueda llegar a ellas. Además, también hay que buscar zonas interesantes de la cueva en los que poner inicio, final, recompensas, enemigos y demás objetos, pero el algoritmo no facilita información adicional que poder usar para esta etapa.
Algo interesante a mencionar es que, dado que el resultado del algoritmo es una matriz booleana, un tipo de post-procesamiento que se podría hacer es aplicar operadores morfológicos usando una librería como OpenCV. Con ellos se pueden hacer transformaciones como hacer las salas y pasillos mas grandes o mas pequeños, o conectar zonas de la cueva antes inaccesibles.
Por todo lo anterior, el autómata celular es adecuado solamente para generar entornos similares a cuevas e idealmente que requieran de poco post-procesado. Por ejemplo, en un videojuego como Terraria no es necesario que las cuevas sean conexas porque el jugador puede atravesar las paredes. Lo enemigos aparecen con probabilidad en cualquier lugar que sirva de suelo y las estructuras pueden destruir terreno de alrededor para acomodarse. Sin embargo, este algoritmo no seria adecuado si se requieren restricciones de mayor abstracción, como obligar un cierto número de salas o determinar su topología antes de generarlo.