Ejercicio obligatorio 1
Fecha de entrega: Domingo 14 de septiembre
Autómatas celulares
Un automáta celular es un modelo computacional que simula la evolución de un sistema mediante pasos discretos.
Cada uno de los estados de un autómata celular es una matriz de valores, donde cada coordenada representa una célula y se aplican reglas sobre cada una de las células y su entorno para generar el siguiente estado.
Para simular un autómata celular partimos de una matriz con una determinada configuración inicial de células y en cada paso de tiempo utilizamos el estado de cada una de ellas para generar la matriz que representa el próximo paso temporal.
En cuanto a los valores de cada célula de un autómata los mismos son un valor entero que representa una clase de célula. Por ejemplo, podríamos tener un autómata celular donde una celda en 0 representa aire, una celda en 1 representa tierra y una celda en 2 representa agua.
La simulación, entonces, se iniciará con una matriz de determinado tamaño donde cada una de las celdas estará inicializada en 0, 1 o 2, representando cada una de ellas una determinada clase.
La evolución de ese estado será una nueva matriz donde se aplicarán reglas. Por ejemplo, si una celda en el estado anterior era de tipo tierra, en el siguiente estado será de tipo tierra. Es decir, la tierra permanecerá fija. Ahora bien, podríamos definir que si una celda es de tipo agua y la celda debajo de ella es de tipo aire, entonces en el próximo paso esa celda será aire. Y si una celda es aire y la celda superior a ella es agua en el próximo paso será agua. Es decir, el agua va a caer una celda entre paso y paso de la simulación. Estas reglas pueden complejizarse tanto como queramos, por ejemplo, ¿qué reglas deberíamos agregar para que el agua "moje" hacia los lados si ya están ocupadas las celdas debajo de ellas?
El formato PBM
En una imagen digital tenemos una matriz de determinado ancho y alto en la cual cada unidad es el pixel. Parecería ser una buena idea utilizar imágenes para representar los estados de un autómata celular, siendo que ambos son matrices de valores.
Para simplificar el proceso de generar imágenes utilizaremos uno de los formatos del paquete Netpbm que permite generar gráficos de forma muy sencilla. Particularmente en este trabajo utilizaremos la variante ASCII del formato PBM (portable bitmap).
Un archivo PBM es la secuencia de: El encabezado P1, seguido de las dimensiones en ancho y alto de la imagen, seguido de una secuencia de ceros y unos según el pixel sea blanco o negro respectivamente, recorridos de izquierda a derecha y de arriba a abajo.
Como una imagen vale mil palabras, por ejemplo el archivo:
P1
14 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 1 0 0 0 0 1
1 1 0 1 1 1 1 0 1 0 1 1 0 1
1 1 0 1 1 0 0 0 1 0 1 1 0 1
1 1 0 1 1 1 1 0 1 0 1 1 0 1
1 1 0 1 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
genera la imagen (ampliándola varias veces):
No hace falta que los pixeles estén estructurados como en una matriz, puede haber uno por línea y el formato es igualmente válido.
Siendo que este formato sólo admite dos valores por pixel, no nos permitirá representar células con más de dos clases (a menos que representemos más de una clase con el mismo valor).
Trabajo
Inicializar
Implementar una función void inicializar_matriz(size_t filas, size_t columnas, char matriz[filas][columnas]);
que inicialice en 0 cada una de las posiciones de la matriz recibida.
Copiar
Implementar una función void copiar_matriz(size_t filas, size_t columnas, char destino[filas][columnas], char origen[filas][columnas]);
que realice una copia de la matriz origen en la matriz destino.
Imprimir PBM
Implementar una función void imprimir_ppm(size_t filas, size_t columnas, char matriz[filas][columnas]);
que, imprima por stdout una imagen PBM en base a la matriz. Las celdas que
estén en 0 se imprimirán como 0, mientras que las celdas que estén en otro
valor se imprimirán como 1. Es decir, tendremos una imagen blanco y negro donde
las celdas en cero serán blancas y las de cualquier otro valor serán negras.
Pegar submatriz
Implementar una función bool pegar_submatriz(size_t mfs, size_t mcs, char matriz[mfs][mcs], size_t sfs, size_t scs, char submatriz[sfs][scs], size_t fi, size_t ci);
que copie los elementos de la submatriz en la matriz desplazándola en fi
filas y ci columnas. Es decir, la coordenada [0][0] de la submatriz se
pegará en la coordenada [fi][ci] de la matriz y así para cada celda. Esta
función sería el equivalente a una función de pegar un recorte en una imagen en
un programa como el Paint.
La función debe devolver true si el pegado es posible (es decir, ¿entra la
submatriz donde se indica?) y false en caso de no poder realizarse la
operación.
Sumar entorno
Implementar una función int sumar_entorno(size_t filas, size_t columnas, char matriz[filas][columnas], size_t fc, size_t cc);
que dada la celula matriz[fc][cc] sume el valor de las 8 células que la
rodean. Esta operación sólo puede computarse para celdas interiores a la
matriz, por lo que si fc y cc no están en rango deberá devolverse 0.
Evolucionar autómata
Implementar una función void evolucionar_celulas(size_t filas, size_t columnas, char final[filas][columnas], char inicial[filas][columnas]);
que evolucione una vez el estado inicial de un autómata para generar el
estado final.
Las celdas de nuestro autómata tendrán sólo dos estados: 0 y 1.
La evolución de cada una de las celdas tendrá que ver con el estado de las celdas que la rodean.
Si una celda está en 0 y tiene exactamente 3 celdas vecinas en 1 entonces cambiará a 1. Si no, seguirá estando en 0.
Si una celda está en 1 y tiene 2 o 3 celdas vecinas en 1 entonces permanecerá en 1, si no cambiará a 0.
Para simplificar la evolución se hará excluyendo las primeras y últimas filas y columnas, así todas las células tienen 8 células vecinas.
Aplicación
Se provee el siguiente main():
#define ANCHO 20
#define ALTO 20
#define CICLOS 10
int main() {
char m1[3][3] = {
{1, 1, 0},
{1, 0, 1},
{0, 1, 0},
};
char m2[2][4] = {
{0, 1, 1, 1},
{1, 1, 1, 0},
};
char m3[3][3] = {
{0, 1, 0},
{0, 0, 1},
{1, 1, 1},
};
char matriz[ANCHO][ALTO];
inicializar_matriz(ANCHO, ALTO, matriz);
pegar_submatriz(ANCHO, ALTO, matriz, 3, 3, m1, 15, 5);
pegar_submatriz(ANCHO, ALTO, matriz, 2, 4, m2, 15, 15);
pegar_submatriz(ANCHO, ALTO, matriz, 3, 3, m3, 5, 5);
char auxiliar[ANCHO][ALTO];
// Inicializamos toooda la matriz para garantizar que el borde esté en cero:
inicializar_matriz(ANCHO, ALTO, auxiliar);
for(size_t ciclo = 0; ciclo < CICLOS; ciclo++) {
evolucionar_celulas(ANCHO, ALTO, auxiliar, matriz);
copiar_matriz(ANCHO, ALTO, matriz, auxiliar);
}
imprimir_ppm(ANCHO, ALTO, matriz);
return 0;
}
El mismo deberá utilizarse sin modificaciones para generar un programa con las funciones desarrolladas por el alumno.
La ejecución de este programa deberá generar una imagen como esta:
Entrega
Deberá entregarse el código fuente del programa desarrollado y la imagen generada con este programa convertida a formato JPG o PNG.
El programa debe compilar correctamente con los flags:
-Wall -Werror -std=c99 -pedantic
y además debe ejecutarse correctamente con los flags:
-fsanitize=address -g
La entrega se realiza a través del sistema de entregas.
El ejercicio es de entrega individual.