Autómatas celulares, aplicación WinCA VII

Continúo explicando lo más básico del código de la aplicación WinCA, dedicada a la construcción y ejecución de autómatas celulares. En esta ocasión voy a hablar de la implementación de las celdas y otras clases auxiliares utilizadas en la construcción de los autómatas propiamente dichos.

Aquí puedes encontrar el primer artículo de la serie sobre la aplicación WinCA.

En este enlace puedes descargar los ejecutables de la aplicación WinCA, y en este otro puedes descargar el código fuente del proyecto WinRQA, escrita en csharp con Visual Studio 2015.

Las células del autómata

Cada una de las células del autómata es un objeto independiente, que se encuentra en un estado determinado y que tiene un vecindario constituido por otras células. El interfaz que deben implementar todas ellas es ICACell, y se encuentra en el espacio de nombres Interfaces de la librería de clases CellularAutomata. Está definido de la siguiente manera:

public interface ICACell
{
int ActualState { get; set; }
int NextState { get; set; }
IEnumerable<int> Neighborhood { get; }
int NeighborCount { get; }
void AddNeighbours(int[] ixn);
int[] GetNeighborhood();
int GetNeighbour(int ix);
void ClearNeighborhood();
int GetState(int step);
}

Como trabajar directamente con los estados o acceder a ellos por su nombre es bastante lento, y tenemos que procesar muchas células en cada paso del autómata, las celdas hacen referencia a sus estados por su índice dentro de la lista de estados gestionada por el autómata.

En cada paso, se procesan todas las células y se calcula el siguiente estado de cada una utilizando las expresiones de cambio de estado de su estado actual. Esto hace que no podamos descartar el estado inicial de una célula hasta que no se han procesado todas, ya que sus vecinas utilizarán este estado inicial, y no el estado final, para realizar sus propios cálculos de cambio de estado. Por lo tanto, toda celda tiene al menos dos estados, el estado con el que inicia el paso actual, y el estado final con el que terminará el paso.

Las propiedades ActualState y NextState son las encargadas de devolver estos dos estados. También se pueden utilizar para inicializar el estado de las celdas (ActualState) o modificar su estado final (NextState).

Con el método GetState se realiza el cambio de estado definitivamente, y el estado final pasa a ser el actual. Como parámetro se le pasa el número de paso actual del autómata.

El resto de propiedades y métodos se utilizan para gestionar la vecindad de la célula. Los vecinos se definen mediante sus índices dentro de la matriz de celdas del autómata, siempre en un orden concreto, que depende de la implementación del autómata al que pertenezcan las celdas. Éstos índices son inicializados desde la clase que implementa el autómata, por lo que la celda se limita simplemente a almacenarlos.

La propiedad Neighborhood enumera todos estos índices. NeighborCount proporciona el número de vecinos definidos para la celda. Con el método AddNeighbours pasamos los índices de las celdas vecinas en forma de array de enteros. Este array lo podemos recuperar con el método GetNeighborhood o borrar con ClearNeighborhood. Para obtener el índice de un vecino concreto, usaremos GetNeighbour, pasando el número de vecino dentro del array de índices.

La clase BasicCell, en el espacio de nombres Automata de la librería CellularAutomata implementa este interfaz. En esta clase, el estado actual y final se implementan usando un array de dos enteros, _stateBuffer y un índice, _ixBuffer, que indica cuál de las dos posiciones del array representa el estado actual. Los índices de los vecinos se almacenan en el array _neighborhood, tal cual como son proporcionados por el autómata.

Al igual que sucede con las propiedades y los estados, existe un tipo de objeto encargado de construir celdas para los autómatas. Estas clases deben implementar el interfaz ICACellProvider del espacio de nombres Interfaces de la librería de clases CellularAutomata:

public interface ICACellProvider
{
IEnumerable<Type> CellTypes { get; }
ICACell GetCell(Type celltype, int initial);
}

Se trata de un interfaz muy sencillo. Con la propiedad CellTypes obtenemos una enumeración con todos los tipos de celda que puede proporcionar el proveedor. Con el método GetCell se obtiene una nueva celda del tipo indicado en el parámetro cellttype y con el estado inicial indicado por el parámetro initial.

La clase BasicCellProvider, en el espacio de nombres CellularAutomata.Automata, es una implementación de este interfaz que proporciona únicamente celdas de la clase BasicCell.

Optimización del autómata

En cada paso del autómata, se deben evaluar las expresiones de cambio de estado para cada una de las celdas. Esto puede resultar muy costoso en tiempo de proceso cuando el número de celdas es elevado. Podemos intentar optimizar este procedimiento pensando que, puesto que el cambio de estado depende del estado de las celdas vecinas, si guardamos una tabla de estados para las combinaciones más habituales de estados de celda y su vecindario, podemos simplemente mirar en esta tabla para decidir el estado siguiente, sin necesidad de evaluar las expresiones.

Para implementar un procedimiento de este tipo, existe el interfaz ICAOptimizer, en el espacio de nombres CellularAutomata.Interfaces, definido de la siguiente manera:

public interface ICAOptimizer
{
int MaxCapacity { get; set; }
void AddKnownTransition(int from, int[] neighborhood, int to);
int GetTransition(int from, int[] neighborhood);
}

La propiedad MaxCapacity obtiene o establece el número máximo de transiciones almacenado. Con el método AddKnownTransition añadimos una transición desde el estado from hasta el estado to, con el estado de las celdas vecinas pasado en el array neighborhood. GetTransition devolverá el estado final desde el estado from con el estado del vecindario indicado en neighborhood, o -1 si no existe información sobre esta combinación de estados.

La clase BasicCAOptimizer implementa este interfaz. Utiliza una clase auxiliar, TransitionTable, para almacenar un diccionario que relaciona una cadena de texto obtenida a partir del estado de los vecinos, con un estado final. La variable _states almacena un diccionario en el que cada clave es un estado inicial diferente, y cuyo valor es la TransitionTable que corresponde a dicho estado.

La clase TransitionTable utiliza la lista _history para almacenar una lista ordenada de las transiciones más comunes, de manera que se van eliminando las que suceden con menor frecuencia una vez que se alcanza la capacidad máxima de la tabla.

Y eso es todo. En el siguiente artículo explicaré las clases e interfaces que implementan las redes de celdas que cosntituyen los autómatas.