¿Qué es un autómata celular? ¿Cómo programar uno empleando Python?. En el siguiente video/artículo explicamos en qué consisten y de qué son capaces fijándonos como ejemplo en el Juego de la Vida de Conway. Vemos además cómo crear una versión funcional de este autómata celular clásico empleando Python y la librería PyGame.

¿Qué es un autómata celular?

Un autómata celular ( AC ) es un modelo que muestra el comportamiento de un sistema compuesto por un conjunto de elementos que interactúan entre si aplicando reglas simples. Estos se caracterizan por ser capaces de generar comportamientos complejos a partir de la interacción entre sus elementos.

Los AC se componen de los siguientes elementos básicos.

• Espacio: Un mosaico 2D semejante a un tablero conformado por los elementos simples que conforman el AC.
• Conjunto de estados: Indica todos los posibles valores/estados que puede tener cada elemento del AC:

Espacio de 8×8 elementos con 3 estados posibles representados con colores blanco, gris y negro.

• Configuración de partida: Es el conjunto de valores que poseen inicialmente los elementos del AC antes de ponerse en marcha.
• Regla de vecindad: Indica el patrón o norma que determina qué elementos se consideran contiguos a uno dada su posición en el espacio.
• Función de transición: Son el conjunto de reglas que conforman el algoritmo que se aplica sucesivamente sobre cada elemento para determinar su estado en base al estado de los elementos considerados vecinos según la regla de vecindad.
• Regla de frontera: Determina qué valores se asumen que tienen los elementos situados fuera de los límites del espacio si éste es limitado.

Uno de los modelos de AC más conocidos es el Juego de la Vida de Conway.

Si estás interesado en aprender a programar en Python, visita nuestro curso de python

El Juego de la vida de Conway

Se trata de uno de los autómatas celulares más populares que existen, creado en 1.970 por el matemático británico Jhon Horton Conway. Este AC se compone de una matriz cuadrada de celdas dada una de las cuales únicamente puede tener dos estados (activa o inactiva). Cada celda está rodeada a su vez por 8 celdas que se consideran sus vecinas:

Estructura de una celda (en el centro) y su vecindad (las 8 celdas que la rodean)

El estado de cada celda se actualiza cada poco tiempo mediante la aplicación de una serie de reglas simples en base al valor de las celdas vecinas. Estas son las siguientes:

• Una celda activa permanece así si está rodeada por 2 o 3 celdas activas, en caso contrario se desactiva.
• Una celda inactiva pasa a estar viva si está rodeada por exactamente 3 celdas vivas.

Estas normas conforman la función de transición clásica para este modelo de AC y se representan con la designación “23/3”, donde:

• 23: Determina el nº de celdas vecinas para continuar activa ( 2 o 3 )
• 3: Determina el nº de celdas vecinas activar para activarse ( 3 )

Existen otras funciones de transición para este AC que generan comportamientos diferentes:

• 23/36 (caótico) «HighLife» (tiene replicante)
• 4/2 (crece) generador de patrones de alfombras
• 51/346 (estable) «Larga vida» casi todo son osciladores

La evolución de este AC depende únicamente de la configuración inicial dada, a partir de la cual pueden aparecer diferentes patrones de celdas activas a lo largo del tiempo. Estos pueden agruparse en tres tipos básicos:

• Patrones estables: Son aquellos compuestos por conjuntos de celdas que mantienen su estado estable a lo largo del tiempo.

• Patrones cíclicos : Son aquellos compuestos por celdas que cambian de estado mostrando indefinidamente dos patrones de manera alternativa. Se denomina periodo al nº de patrones que son mostrados consecutivamente, que pueden ser 2, 3, o más.

• Patrones móviles : Son aquellos que migran entre las celdas pareciendo desplazarse. Es importante destacar que lo que se desplaza es el patrón, no las celdas.

Implementación empleando Python

Existen múltiples implementaciones excelentes del Juego de la Vida de Conway, algunas incluso disponibles on-line: https://playgameoflife.com/

En el presente artículo vamos a examinar como proyecto la implementación de este autómata celular empleando Python, el paquete pyGame, y PyCharm como entorno de desarrollo.

PyGame es una librería de Python dedicada al desarrollo de videojuegos y aplicaciones gráficas interactivas: https://www.pygame.org/wiki/GettingStarted

Emplearemos esta librería para poder representar en tiempo real el estado y evolución de las celdas activas. Para su instalación podemos emplear el gestor de paquetes pip introduciendo el siguiente comando en la consola de Python:

pip install pygame

Collecting pygame

Downloading pygame-2.0.1-cp38-cp38-win_amd64.whl (5.2 MB)

Installing collected packages: pygame

Successfully installed pygame-2.0.1

Una vez instalada podemos comenzar con el siguiente código en el módulo principal al que denominaremos main.py:

El código mostrado provoca la ejecución de la función principal main() que crea una ventana de 1000 x 564 píxeles. Esta muestra por ahora únicamente un fondo negro que se actualiza constantemente hasta que es cerrada por el usuario.

Implementación del Autómata Celular

A continuación, creando un nuevo módulo “conway.py” en el que vamos a definir la clase Conway que implementará toda la lógica del autómata celular:

La clase debe constar de los siguientes atributos:

Las constantes WIDTH, HEIGHT, LIVE y DEAD son constantes públicas accesibles desde los objetos. El resto de listas son de acceso interno.

A continuación definimos el método reset() y el constructor:

El constructor recibe como parámetro opcional una cadena que determina el patrón para la función de transición del AC. En caso de no indicarse se toma el patrón “23/3” clásico.

El método reset() es responsable de inicializar las dos listas que conforman el espacio principal y del de respaldo para las actualizaciones durante el proceso de actualización. Cada uno de los valores de ambas listas representa el estado de una celda. La lista __world contiene WIDTH * HEIGHT valores inicializados a 0, es decir; todas las celdas están inicialmente inactivas.

El constructor recibe una cadena con el patrón correspondiente para la función de transición, de la que se extraen las listas __alive y __born.

__alive : Contiene los recuentos de celdas activas vecinas que deben obtenerse para que una celda continúe activa, de lo contrario se desactiva.

__born : Contiene los recuentos de celdas activas vecinas que deben obtenerse para que una celda en principio inactiva se active.

A continuación, añadimos las propiedades iterations y livecells que devuelven respectivamente el nº de actualizaciones ejecutadas (también llamadas iteraciones), y el nº de celdas activas presentes en el espacio del AC:

Seguidamente implementamos los método read() y write() que permiten respectivamente obtener y modificar el estado de una celda dadas sus coordenadas X e Y en el espacio del AC:

La obtención de la posición de una celda en la lista __world dadas las coordenadas X e Y en ambos métodos se calcula aplicando el siguiente cálculo:

                fila * ( Celdas por Fila ) + columna => ( y * width ) + x

En el caso de coordenadas X e Y fuera de los límites se obtiene el valor simétrico (frontera reflectora) correspondiente al lado contrario aplicando las siguientes reglas:

• Si x > WIDTH : x – WIDTH ( derecha -> izquierda )
• Si x < 0 : x + WIDTH ( izquierda -> derecha )
• Si y > HEIGHT : y – HEIGHT ( abajo -> arriba )
• Si y < 0 : y + HEIGHT ( arriba -> abajo )

De este modo, las celdas de los bordes interactúan con las de los bordes contrarios dando lugar a un espacio cíclico. Esto se denomina regla de frontera reflectora.

Si estás interesado en aprender a programar en Python, visita nuestro curso de python

Por último, implementamos los dos métodos más importantes del autómata:

El método update() actualiza el estado de las celdas en el espacio del autómata celular. Para ello se recorren todas las celdas del espacio principal (__world). Por cada celda se obtiene su estado y el de las celdas vecinas (near). Se aplican a continuación las reglas de la función de transición y se almacena el estado resultante en la misma posición pero del espacio de respaldo (__next). Una vez recorridas todas las celdas se actualiza el espacio principal con los de respaldo:

El método draw() representa en un objeto superficie pygame.Surface que requiere como parámetro el estado de todas las celdas del espacio principal. Para ello todas las celdas del AC se muestran como rectángulos de 10 x 10 píxeles situados conforme a sus coordenadas en el espacio. Las celdas inactivas se muestran como rectángulos sin relleno y bordes grises. Las celdas activas se muestran como recuadros rellenos de blanco:

Implementación del interfaz de usuario con PyGame

Una vez completada la implementación de la parte lógica de la aplicación pasamos a implementar la interfaz de usuario en el módulo “main.py”:

La ventana a mostrar constará del siguiente aspecto:

Aspecto del interfaz de usuario de la aplicación con todas las celdas inactivas.

Cada una de las celdas del espacio existente en el autómata celular se mostrará como un recuadro gris o un cuadrado blanco en función de su estado.

Muestra de la representación del espacio del autómata mostrando un patrón de celdas activas.

La ventana tendrá un tamaño de 1000 x 564 píxeles dividida en dos partes:

• El área de visualización del espacio del autómata : del Y = 0 a Y = 500.
• El área de controles donde se muestran los iconos que nos permitirán iniciar, parar y reiniciar el autómata celular. A la izquierda se muestra el estado del autómata ( PAUSE, RUNNING), y a la derecha el nº de iteraciones y el nº de celdas activas en cada momento.

Se pretende que el usuario pueda activar y desactivas las celdas que desee mientras el autómata permanezca parado para poder establecer la configuración de partida deseada. Para ello bastará con hacer clic sobre el recuadro correspondiente a la celda.

• Si la celda está activa : Se desactiva.
• Si la celda está inactiva : Se activa.

Para ello definimos la función auxiliar mouse_click(). Esta función es llamada desde el main() al detectarse la pulsación del botón izquierdo del ratón con el cursor sobre la ventana de la aplicación. El método recibe las coordenadas X e Y en píxeles del cursor dentro de la ventana en el momento de la pulsación y se ocupa de activar/desactivar alternativamente la celda correspondiente.

Para conseguirlo, las coordenadas en píxeles de la pantalla se convierten en coordenadas del espacio del autómata. Con ellas se obtiene el estado de la celda mediante el método read() y se le asigna el valor correspondiente a su estado actual con el método write():

Una vez definidas estas dos funciones auxiliares definimos unas cuantas variables globales:

A continuación modificamos la función main() implementando las siguientes fases de ejecución:

1.- Inicializamos la librería pygame, creamos la ventana del interfaz de usuario e instanciamos la clase Conway para obtener el objeto “world” que representa el AC. Dado que no indicamos ningún valor para el constructor el AC empleará el formato predeterminado “23/3” como función de transición:

2.- Cargamos los objetos que representan los iconos para iniciar, pausar y limpiar el AC así como la fuente para los textos con el estado y el recuento de iteraciones y celdas activas.

También iniciamos la variable “running” que determina el estado iniciado o detenido del AC. En estado parado (False) el AC se muestra, pero no se actualiza permitiendo configurar sus celdas. En estado iniciado (True) el AC se muestra y actualiza acumulando iteraciones y mostrando la evolución de las celdas:

3.- Iniciamos el bucle principal que se ejecuta mientras la aplicación está funcionando.

Este bucle tiene varias tareas que deben realizarse constantemente:

• Captura de eventos.

Si el evento es de tipo pygame.QUIT se trata del cierre de ventana por parte del usuario, el cual cierra la aplicación. Si el evento es de tipo pygame.MOUSEBUTTONDOWN se trata de una pulsación con el botón izquierdo del ratón sobre la ventana de la aplicación. En ese caso debe diferenciarse si:

• Si la coordenada Y del cursor es menor o igual que 500 píxeles : El usuario está pulsando sobre una celda del AC para cambiar su estado
• Si la coordenada Y del cursor es superior a 500 píxeles : El usuario está pulsando quizá sobre uno de los iconos de control para iniciar, parar o limpiar el AC.

En el primer caso la acción se deriva a la función button_click() implementada anteriormente. En el segundo caso se comprueba sobre qué icono está situado el cursor y se modifica el valor de la variable “running”, o se llama el método reset() del objeto world para limpiar el AC.

• Actualización de AC ( running = true )

• Repuntado de ventana

Esto implica repintar el estado de todas las celdas llamando al método draw() del objeto world pasando como argumento el objeto screen que representa la superficie de la ventana, así como el resto de iconos mostrados y los textos informando del estado del AC, el nº de iteraciones y el de celdas activas actuales:

Modo de uso.

Al iniciar la aplicación se muestra el AC con todas las celdas inactivas y en estado parado, por lo que podemos activar las celdas que deseemos para crear una configuración inicial:

Inicio del AC

A continuación podemos poner en marcha el AC pulsando sobre el icono PLAY . Se muestra entonces el estado “RUNNING” y El AC muestra la evolución del estado de las celdas al tiempo que se van mostrando el nº de iteraciones y el nº de celdas activas presentes.

Parada del AC

Para detener el AC pulsamos el icono

Se muestra entonces nuevamente el estado “PAUSE”:

Reinicio del AC

Por último, podemos limpiar el AC desactivando el estado de todas las celdas y poniendo el contador de iteraciones nuevamente a 0. Para ello pulsamos el icono:

Si estás interesado en aprender a desarrollar videojuegos, visita nuestros cursos de videojuegos