Jugando con autómatas celulares (19)
2013-10-06
Hace varios artículos, planteamos un interesante proyecto: una pequeña nnbiblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.
Ya tenemos una biblioteca completísima, pero nos falta un aspecto importante relacionado con la presentación de resultados: la capacidad de generar imágenes con las que representar el estado de un autómata. Las funciones que creamos para imprimir texto (translate-and-display-1d y translate-and-display-cartesian-2d) están bien para hacer una evaluación interactiva rápida del buen funcionamiento de un modelo de autómata celular, pero se quedan algo cortas. Una imagen permite ilustrar un autómata muy grande en poco espacio, pues podemos tomar un píxel por celda en vez de un enorme carácter por celda.
Vamos a generar imágenes PBM, PGM y PPM. Las imágenes PBM son monocromáticas con dos valores posibles (blanco y negro), las imágenes PGM son en escala de grises y las imágenes PPM son a color. Todos estos tipos están codificados sin compresión y pueden darse en formato binario y en formato ASCII; nos centraremos en el formato ASCII. En conjunto, se les conoce como PNM o el formato de Netpbm. Como no tienen compresión, las imágenes que guardamos en estos formatos ocupan bastante espacio de almacenamiento, pero tienen la ventaja de que son muy fáciles de escribir. Este proyecto ya ha crecido mucho y se aleja de su didáctica desarrollar funciones para hacer una codificación más complicada.
El formato PBM
El formato
PBM es muy sencillo. Es así:
P1
columnas filas
datos
Tanto columnas como filas son números
decimales. Los datos son una secuencia de ceros (píxeles
blancos) y unos (píxeles negros) que representa los píxeles en orden
de lectura de izquierda a derecha primero y de arriba abajo después,
con o sin espacio de separación entre números. El espacio de
separación puede consistir en espacios, tabuladores, caracteres de
nueva línea y retornos de carro. El contenido de datos ha
de ir dividido en líneas de no más de setenta caracteres.
El formato PGM
El formato
PGM es similar al PBM, pero tiene alguna complicación adicional
para poder codificar imágenes en escala de grises. Es así:
P2
columnas filas máximo
datos
El primer aspecto novedoso, además del cambio del número mágico
de P1 a P6, es el máximo
(superior a 0 e inferior a 65536) que se corresponde con el máximo
nivel de gris o el número de valores de gris que podemos codificar
menos uno. Seguidamente, vienen los datos, que igual que
antes son los píxeles de izquierda a derecha y de arriba abajo en
líneas que no superan los setenta caracteres, pero esta vez con alguna
cantidad no nula de espacio entre números siempre y con números que
puden tener varias cifras: de 0 a máximo.
El formato PPM
El formato
PPM es similar al PGM. Es así:
P3
columnas filas máximo
datos
En este caso, los datos codifican los píxeles con tríos
de números: uno para el rojo, otro para el verde y otro para el azul,
cada uno entre 0 y máximo.
Función para escribir imágenes PNM
Vamos a crear una función llamada write-pnm que aceptará
el nombre filename del fichero de salida, el número mágico
magick-number ("P1" para PBM, "P2"
para PGM y "P3" para PPM), el máximo
valor maximum (o el valor falso #f si el formato
omite este número) y una lista de filas list-of-rows. Esta
lista de filas es una lista de listas: cada elemento es una lista con
la representación de cada píxel en el formato correspondiente. Por
ejemplo, en el formato PPM, un píxel cuyo color es la terna
(1 2 3), quedaría representado mediante la cadena de
caracteres "1 2 3". La función en Scheme es así:
(define (write-pnm filename magick-number maximum list-of-rows)
(let* ((rows (length list-of-rows))
(columns (length (car list-of-rows))))
(with-output-to-file filename
(lambda ()
(display magick-number)
(newline)
(display columns)
(display " ")
(display rows)
(if maximum
(begin (display " ")
(display maximum)
(newline))
(newline))
(for-each (lambda (row)
(for-each (lambda (pixel)
(display pixel)
(newline))
row))
list-of-rows)))))
Las funciones de salida de Scheme R5RS dan código muy prolijo. La
típica función format o printf permitiría
escribir algo con una notación un poquito más compacta. La traducción
literal a Python es así:
def write_pnm(filename, magick_number, maximum, list_of_rows):
rows = len(list_of_rows)
columns = len(list_of_rows[0])
with open(filename, 'w') as fd:
fd.write(str(magick_number))
fd.write('\n')
fd.write(str(columns))
fd.write(' ')
fd.write(str(rows))
if maximum:
fd.write(' ')
fd.write(str(maximum))
fd.write('\n')
else:
fd.write('\n')
for row in list_of_rows:
for pixel in row:
fd.write(pixel)
fd.write('\n')
¡Esto no es ni mucho menos la forma más recomendable de escribir
la imagen en disco!
Utilización
Digamos que tenemos las generaciones generations de un
autómata elemental creadas mediante la función step. Los
valores adoptados por las celdas de este autómata son 0
y 1. Ya tenemos una lista de listas con la que podemos
alimentar a write-pnm para escribir una imagen PBM. El uso
sería así:
(write-pnm filename "P1" #f generations)
Ahora asumumamos que tenemos la lista de celdas cells de
una cierta generación del autómata del incendio forestal. Las
dimensiones del tablero están dadas en la lista sizes.
Queremos que los claros (valor 0) salgan grises, los
árboles (valor 1) salgan verdes y los incendios
(valor 2) salgan rojos. Podemos hacer que los colores
vayan de 0 a 2, de modo que codificamos el gris
como "1 1 1", el verde como "0 2 0" y el rojo
como "2 0 0". Hacemos así:
(write-pnm filename
"P3"
2
(cartesian-rows (map (lambda (cell)
(cond ((= cell 0) "1 1 1")
((= cell 1) "0 2 0")
(else "2 0 0")))
cells)
sizes))
Veamos qué hace esto. Lo interesante es la construcción del
cuarto argumento de write-pnm, la lista de filas.
Construimos esta lista con la función cartesian-rows que
para
imprimir por pantalla mallas cartesianas bidimensionales como las
del juego
de la vida de Conway y las
del modelo
del incendio forestal. Esta función acepta una lista plana y la
convierte en una lista de filas; esta lista plana no contiene las
celdas tal como salen del autómata del incendio forestal, sino tras
pasar por una etapa de procesado con map para convertir los
estados de las celdas en los colores de los píxeles que queremos.
Podemos ver lo que sucede en la generación número cincuenta de un
modelo del incendio forestal así:
(let* ((sizes '(320 320))
(tree-probability 1e-2)
(fire-probability 1e-3)
(rule (wrap-with-generator (forest-fire-rule tree-probability
fire-probability)
(uniform-generator 0)))
(initial-cells (repeat 0 (apply * sizes)))
(neighbourhoods (lambda (cells)
(cyclic-forest-fire-neighbourhoods cells
sizes)))
(number-of-generations 50)
(generations (step rule
initial-cells
neighbourhoods
number-of-generations))
(cells (list-ref generations (- number-of-generations 1)))
(cell->pixel (deterministic-rule '((0 "1 1 1")
(1 "0 2 0")
(2 "2 0 0"))))
(pixels (map cell->pixel cells))
(rows (cartesian-rows pixels sizes)))
(write-pnm "forest-fire.ppm" "P3" 2 rows))
Hemos aprovechado la función deterministic-rule para
convertir los estados de las celdas a los colores de los píxeles. El
resultado (aquí convertido después al formato PNG) es así:
Autómata del incendio forestal.
Otros artículos de la serie
- Introducción.
- Pequeño autómata de demostración.
- Función para crear reglas deterministas.
- Funciones para sacar por pantalla las listas de celdas.
- Funciones auxiliares útiles.
- Más funciones auxiliares útiles.
- Funciones para trabajar con mallas cartesianas.
- Extracción de vecinos en mallas cartesianas cíclicas
- Funciones para crear autómatas unidimensionales elementales.
- Funciones para crear generaciones sucesivas de autómatas cómodamente.
- Prueba con varios autómatas elementales.
- Funciones para imprimir autómatas bidimensionales cartesianos.
- Juego de la vida de Conway.
- Funciones para trabajar con autómatas no deterministas.
- Autómata no determinista: modelo del incendio forestal.
- Autómatas de segundo orden.
- Mejora del rendimiento mediante memoización.
- Más pequeñas modificaciones para acelerar notablemente el código.
Categorías: Informática
Permalink: https://sgcg.es/articulos/2013/10/06/jugando-con-automatas-celulares-19/
