SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

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.
Autómata del incendio forestal.

Otros artículos de la serie


Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/10/06/jugando-con-automatas-celulares-19/