Introduction

The post is devoted to NuGet package Ikc5.Math.CellularAutomata. The library contains classes to create and investigate 2D cellular automata. There are cellular automaton classes, life algorithms and neighbors’ algorithms, cells, different interfaces’ implementation. These classes are ready for using with dependency injection container.

Sources

The package is open-source project, full code is accessible on GitHub NuGet repository. It contains Math.CellularAutomaton library and Math.CellularAutomata.Tests test library. Package is published at NuGet Gallery and symbol’s package is pushed to SymbolSource.org.

Package

Package refers to Ikc5.TypeLibrary and could be used in the applications that research cellular 2D automata. For example, well-known Conway’s Game of Life is an example of cellular automaton.

Cellular automaton could be considered as finite closed grid, where each cell could be dead or alive. Each cell have neighbors, and there are different algorithms that define how many neighbors are considered. The most useful algorithm is the Moore neighborhood, where each cell has 8 neighbors at distance 1. Then life algorithm defines how many neighbors dead cell should has to born again (for example, “B3” – it will born if there is exactly 3 neighbors), and how many neighbors living cell should has to survive (for example, “S23” – living cell survives if it has 2 or 3 neighbors).

Picture above demonstrates inherit and use relations between the main classes and interfaces. An example of using these classes via dependency container:

// init dependency container
_container.
    RegisterType<ICell, Cell>().
    RegisterType<IAutomaton, Automaton>().
    RegisterType<ICellViewModel, CellViewModel>().
    RegisterType<IAutomatonViewModel, AutomatonViewModel>().
    RegisterType<ICellLifeService, MooreCellLifeService>();

Automaton

Automaton class implements IAutomaton interface. It contains size of automaton, numerical characteristics, methods that add, remove or update set of living cells, and method to iterate the automaton:

/// <summary>
/// Describe cellular automaton. 
/// </summary>
public interface IAutomaton
{
    /// <summary>
    /// Size of cellular automaton.
    /// </summary>
    Size Size { get; }

    /// <summary>
    /// Return count of living cells.
    /// </summary>
    int Count { get; }

    /// <summary>
    /// Series of cells count depending on their age.
    /// </summary>
    IEnumerable<int> AgeSeries { get; }

    /// <summary>
    /// Method sets initial cells to automaton.
    /// </summary>
    /// <param name="newPoints">Set of new cells that are added to automaton.</param>
    /// <param name="statistics">Statistics with count of changed cells</param>
    void SetPoints(IEnumerable<Point> newPoints, ref Statistics statistics);

    /// <summary>
    /// Method update current cells.
    /// </summary>
    /// <param name="addedPoints">Set of new cells that are added to automaton.</param>
    /// <param name="removedPoints">Set of cells that are killed in automaton.</param>
    /// <param name="statistics">Statistics with count of changed cells</param>
    void UpdatePoints(IEnumerable<Point> addedPoints, IEnumerable<Point> removedPoints, ref Statistics statistics);

    /// <summary>
    /// Method returns current automaton points.
    /// </summary>
    IEnumerable<Point> GetPoints();

    /// <summary>
    /// Clear all cells.
    /// </summary>
    void Clear();

    /// <summary>
    /// Moves cells to the next stage - depends on used model
    /// they will survive, die, or born.
    /// </summary>
    bool Iterate(ref Statistics statistics);

    /// <summary>
    /// Returns (reference to) cell object at specified coordinates.
    /// </summary>
    /// <param name="x">Row.</param>
    /// <param name="y">Column.</param>
    /// <returns></returns>
    ICell GetCell(int x, int y);
}

Automaton constructors accepts size, life service and logger:

public Automaton(Size size, ICellLifeService cellLifeService, ILogger logger)

Cell

Cell implements ICell interface. It is separated to two parts: properties that define current state of the cell and properties that defines buffered data during iteration. Cell has Boolean State, where “false” is for dead cell and “true” is for living cell. In order to improve performance, cell keeps VertSum – count of living cells among current cell and two nearest vertical cells. When automaton is iterated, it applies life algorithm to each cell and fills the next state. When the next state has been calculated for all cells, changes are applied, that means State is changed. As ICell implements INotifyPropertyChanged, its properties could be bound to properties of Wpf controls.

/// <summary>
/// Interface describes the cell of cellular automaton.
/// </summary>
public interface ICell : INotifyPropertyChanged
{
    #region States

    /// <summary>
    /// Current state of the cell - Living/Dead.
    /// </summary>
    bool State { get; }

    /// <summary>
    /// Count of living cells among the current one and two nearest neighbors
    /// - above and below.
    /// </summary>
    short VertSum { get; }  // set; }

    /// <summary>
    /// Update count of living cells around current one.
    /// </summary>
    void AddVertSum(short delta);

    /// <summary>
    /// Age of the cell, so how many iteration it is living.
    /// </summary>
    short Age { get; }

    #endregion

    #region Buffered data during iteration

    /// <summary>
    /// Next state of the cell, used as buffered value during iteration.
    /// </summary>
    bool? NextState { get; set; }

    /// <summary>
    /// TRUE if next state and current state are different, otherwise are equal.
    /// </summary>
    bool IsChanged { get; }

    /// <summary>
    /// Integer equivalence of the difference betwee next state and current state:
    /// 0 - if they are the same;
    /// 1 - if cell will born;
    /// -1 - if cell wil die.
    /// </summary>
    short Delta { get; }

    /// <summary>
    /// Cell goes to next state.
    /// </summary>
    void ApplyChange();

    /// <summary>
    /// Methods initiate cell by default values.
    /// </summary>
    void Clear();

    #endregion
}

Life algorithm

Life algorithm is defined by two interfaces – ILifePreset and ICellLifePreset. ILifePreset defines how many neighbors dead cell should has to born again and how many neighbors living cell should has to survive. Also package includes enumeration that defines several well-known life algorithms:

public enum KnownLifePreset : byte
{
    /// <summary>
    /// Conway's Game of Life, highly complex behavior.
    /// </summary>
    [Description("Conway's Game of Life (B3/S23)")]
    Life = 0,           // B3/S23

    /// <summary>
    /// Replicator Edward Fredkin's replicating automaton: every pattern is
    /// eventually replaced by multiple copies of itself.
    /// </summary>
    [Description("Edward Fredkin's replicaton (B1357/S1357)")]
    Replicator,         // B1357/S1357

    /// <summary>
    /// All patterns are phoenixes, meaning that every live cell
    /// immediately dies, and many patterns lead to explosive chaotic growth.
    /// However, some engineered patterns with complex behavior are known.
    /// </summary>
    [Description("Seeds (B2/S)")]
    Seeds,                // B2/S

    /// <summary>
    /// This rule supports a small self-replicating pattern which, when combined
    /// with a small glider pattern, causes the glider to bounce back and forth
    /// in a pseudorandom walk.
    /// </summary>
    [Description("Pseudorandom (B25/S4)")]
    Pseudorandom,        // B25/S4

    /// <summary>
    /// Also known as Inkspot or Flakes. Cells that become alive never die. It combines
    /// chaotic growth with more structured ladder-like patterns that can be used to
    /// simulate arbitrary Boolean circuits.
    /// </summary>
    [Description("Life without death(B3/S012345678)")]
    LifeWithoutDeath,   // B3/S012345678

    /// <summary>
    /// Was initially thought to be a stable alternative to Life, until computer simulation
    /// found that larger patterns tend to explode. Has many small oscillators and spaceships.
    /// </summary>
    [Description("Life 34 (B34/S34)")]
    Life34,                // B34/S34

    /// <summary>
    /// Forms large diamonds with chaotically fluctuating boundaries. First studied by Dean Hickerson, who 
    /// in 1993 offered a $50 prize to find a pattern that fills space with live cells;
    /// the prize was won in 1999 by David Bell.
    /// </summary>
    [Description("Diamoeba (B35678/S5678)")]
    Diamoeba,            // B35678/S5678

    /// <summary>
    /// If a pattern is composed of 2x2 blocks, it will continue to evolve in the same form; 
    /// grouping these blocks into larger powers of two leads to the same behavior, but slower. 
    /// Has complex oscillators of high periods as well as a small glider.
    /// </summary>
    [Description("Pattern 2x2 (B36/S125)")]
    Pattern2x2,            // B36/S125

    /// <summary>
    /// Similar to Life but with a small self-replicating pattern.
    /// </summary>
    [Description("High life (B36/S23)")]
    HighLife,           // B36/S23

    /// <summary>
    /// Symmetric under on-off reversal. Has engineered patterns with highly complex behavior.
    /// </summary>
    [Description("Day and night (B3678/S34678)")]
    DayNight,            // B3678/S34678

    /// <summary>
    /// Named after Stephen Morley; also called Move. Supports very high-period and slow spaceships.
    /// </summary>
    [Description("Stephen Morley's Move (B368/S245)")]
    Morley,             // B368/S245

    /// <summary>
    /// Also called the twisted majority rule. Symmetric under on-off reversal. Approximates the
    /// curve-shortening flow on the boundaries between live and dead cells.
    /// </summary>
    [Description("Twisted majority rule (B4678/S35678)")]
    Anneal,                // B4678/S35678 
}

ICellLifeService covers neighborhood algorithm. It provides property for ILifePreset instance and Iterate method. There are two implementations – MooreCellLifeService and NeumannCellLifeService – that uses different geometric distance and calculates the next state of the cell based on its right and left neighbors.

/// <summary>
/// Service calculates next states of the cells. Different
/// implementations use different geometric distance.
/// </summary>
public interface ICellLifeService
{
    /// <summary>
    /// Contains parameters for born/survive decisions.
    /// </summary>
    ILifePreset LifePreset { get; set; }

    /// <summary>
    /// Set next state of the cell - depends on used model
    /// they will survive, die, or born.
    /// </summary>
    void Iterate(ICell left, ICell current, ICell right);
}

History

• 2016.12.01 – Publish the version 1.0.0.0 package;
• 2017.01.13 – write this post, as a short description.

---

1. All used IP-addresses, names of servers, workstations, domains, are fictional and are used exclusively as a demonstration only.
2. Information is provided «AS IS».