Cellular automata, WinCA application VII

I continue explaining the basics of the WinCA application code, dedicated to the designing and execution of cellular automata. This time I will tell you about the implementation of the cells and other auxiliary classes needed to build and execute automata.

Here you can find the first article of the series about WinCA application.

In this link you can download the WinCA application executables, and in this other one you can download the source code of the WinCA solution, written in csharp with Visual Studio 2015.

The automaton cells

Each cell of the automaton is an independent object, with a certain state and which is connected with other cells, their neighborhood. All of them must implement the ICACell interface, which is located in the Interfaces namespace, in the CellularAutomata class library. It is defined as follows:

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);
}

As working directly with the states, or access them by name can be quite slow, and we may have to process many cells at each step of the automaton, the cells refer to their states by their index within the main list of states managed by the automaton.

At each step, all cells are processed, and the next state of each one is calculated using the state change expressions of its current state. This means that we cannot rule out the initial state of a cell until all of them have been processed, since its neighbors will use this initial state, not the final state, to perform their own state change calculations. Therefore, every cell stores at least two states, the state with which it starts the current step, and the final state with which it will end the step.

The ActualState and NextState properties are used to manage these two states. They can also be used to initialize the state of the cells (ActualState) or modify its final state (NextState).

With the GetState method the state change is performed definitively, and the final state becomes the current one. The step parameter is for the current step number of the automaton.

The remaining properties and methods are used to manage the cell's neighborhood. Neighbors are defined by their indices within the array of cells of the automaton, always in a specific order, which depends on the implementation of the automaton to which the cells belong. These indexes are initialized from the class that implements the automaton, so the cell is simply limited to storing them.

The Neighborhood property enumerates all of these indexes. NeighborCount provides the number of neighbors defined for the cell. With the AddNeighbours method you can pass the indices of the neighboring cells as an integer array. This array can be retrieved using the GetNeighborhood method or cleared with ClearNeighborhood. To obtain the index of a particular neighbor, you have to use GetNeighbor, passing the neighbor number in the array of indexes.

The BasicCell class, in the Automata namespace of the CellularAutomata class library, implements this interface. In this class, the current and final states are implemented using an array of two integers, _stateBuffer, and an index, _ixBuffer, which indicates which of the two array positions represents the current state. Neighbor indexes are stored in the _neighborhood array, just as they are provided by the automaton.

As with properties and states, there is a type of object which builds and provides cells to automata. These classes must implement the ICACellProvider interface, in the Interfaces namespace of the CellularAutomata class library:

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

It is a very simple interface. With the CellTypes property you can get an enumeration with all cell types that the provider can provide. With the GetCell method you get a new cell of the type indicated in the cellttype parameter and with the initial state indicated by the initial parameter.

The BasicCellProvider class, in the CellularAutomata.Automata namespace, is an implementation of this interface that only provides cells of the BasicCell class.

Automata optimization

At each automaton step, the state change expressions must be evaluated for each of the cells. This can be very costly in process time when the number of cells is high. We can try to optimize this procedure by thinking that, since the change of state depends on the state of neighboring cells, if we store a table of states for the most common combinations of cell states and their neighborhood, we can simply look in this table to decide the final state without the need to evaluate the expressions.

In order to implement such a procedure, there is the ICAOptimizer interface, in the CellularAutomata.Interfaces namespace, defined as follows:

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

The MaxCapacity property gets or sets the maximum number of transitions stored. With the AddKnownTransition method, you can add a transition from the from state to the to state, passing the neighboring cells state in the neighborhood array. GetTransition will return the final state from the from state with the neighborhood state indicated in neighborhood, or -1 if no information exists on this combination of states.

The BasicCAOptimizer class implements this interface. It uses an auxiliary class, TransitionTable, to store a dictionary that relates a string of text obtained from the state of the neighbors, with a final state. The _states variable stores a dictionary in which each key is for a different initial state, and whose value is the TransitionTable that corresponds to that state.

The TransitionTable class uses the _history list to store an ordered list of the most common transitions, eliminating the ones that occur less frequently once the maximum table capacity is reached.

And that's all. In the following article I will explain the classes and interfaces that implement the network of cells that constitute the automata.