ProgrammingArtificial Intelligence

Creating Artificial Life with Cellular Automata in C# .NET

modified | by

Introduction

Cellular automata is a model of artificial intelligence involving the creation of single-celled programmatic life forms, within a computer program. John von Neumann, the first scientist to implement cellular automata, came about the discovery while in search of a way to create self replicating robots. He devised a specific set of rules guiding the life, death, and reproduction cycle of each cellular automata cell. When put into action, cellular automata can create increasingly complex patterns, which seem to imitate forms of bacterial life, right on the computer screen. While the patterns it produces can be quite complex, the C# .NET code is surprisingly easy. In fact, the Wolfram Alpha computation engine is based, in part, upon cellular automata.

In this article, we’ll create our very own artificial intelligence bacteria by implementing cellular automata with the rule set from Conway’s Game of Life. To keep things interesting, we’ll also use the Strategy design pattern to implement the rule-sets for our artificial intelligence world. Let’s get started, and create some life!

Giving our AI a World to Live In

In order to create our artificial life forms, we’ll first need to devise a world for them to live in. Since cellular automata require very little with regard to life requirements, we’ll use a basic 2-dimensional array in C# .NET as their world.

1
private static int[,] field = new int[maxX, maxY];

Each cell within the world will occupy a single array space (also called a cell), and will have a value of 0 if no cell exists at this coordinate, or 1 if a cell is alive in this coordinate. For example, if field[5, 6] is equal to 1, a cell is alive at this point.

With the basics of the world defined, we now need to define the rules that each cell will follow during its lifetime.

The Physics of Cellular Automata

Just as life on earth must follow specific rules of physics, so too must the cells in our digital world, although the rules will be much more simple. The standard definition of cellular automata rule sets include two simple rules - what is required for a cell to continue living, and what is required to birth a new cell. Just by defining these two rules, we create amazingly complex cellular artificial life.

With the rules defined, we can follow the standard notation for cellular automata rule sets, which looks as follows:

23/3

The digits before the slash are what is required for a cell to continue living. The digits after the slash are what is required for a cell to be born. The digits refer to the neighbors of a cell in question. So for example, if we’re looking at the cell at position 5,6, we check its neighbors. If the cell has 2 or 3 neighbors, it can continue living and will not die. If the cell has 3 neighbors and it was not already alive (it had a value of zero), it will now be born (have a value of 1). Another way to consider this would be, if a cell only has 1 neighbor, it will die of loneliness, but if it has 2 neighbors, it will continue living. If the cell has exactly 3 neighbors, it will be born if was not yet living. Likewise, if the cell has more than 3 neighbors, it will die of overcrowding. As you can imagine, the rule set 23/3 is only a subset of a very large number of different patterns. 23/3 happens to be the rule set for the famous cellular automata implementation, Conway’s Game of Life. However, there are many different rule sets, all the way up to 8 digits on each side of the slash (depending on the dimensions of your world).

With the rule set definitions complete, we can now move on to setting up our artificial intelligence world in C# .NET.

Drawing the World and Creating Some Life

The full project source code can be downloaded here.

Since we’ll be creating a 2-dimensional world for our cellular automata, we’ll be using a 2-dimensional array. We’ll also define the max width and height of the array so we can fit the world on our screen. To keep things as simple as possible, we’ll display our cellular automata in a plain old C# .NET console window. We’ll draw each cell, which is represented by a 1 within the C# .NET multi-dimensional array, and redraw the screen upon each tick. The initial program code is shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Program
{
    private const char cellIcon = 'o';
    private const int maxX = 60;
    private const int maxY = 40;
    private static int[,] field = new int[maxX, maxY];

    static void DrawField()
    {
        Console.CursorLeft = 0;
        Console.CursorTop = 0;

        for (int y = 0; y < maxY; y++)
        {
            for (int x = 0; x < maxX; x++)
            {
                Console.Write(field[x, y] == 1 ? cellIcon : ' ');
            }

            Console.WriteLine();
        }
    }

    static void Main(string[] args)
    {
        // Initialize
        Console.SetWindowSize(maxX + 10, maxY + 10);
        Console.SetWindowPosition(0, 0);

        // Random initial positions
        Random r = new Random((int)DateTime.Now.Ticks);
        for (int x = 0; x < maxX; x++)
        {
            for (int y = 0; y < maxY; y++)
            {
                field[x, y] = r.Next(0, 1 + 1);
            }
        }

        // Instantiate the desired concrete RuleSet in this Strategy pattern.
        RuleSet ruleSet = new ConwaysGameOfLife(field, maxX, maxY);

        for (int i = 0; i < 5000; i++)
        {
            DrawField();
            ruleSet.Tick();
        }
    }
}

The first part to note in the code is our DrawField() method. This method draws the pixels from our C# two-dimensional array in the console window. This method is called inside a loop and is ran each tick. It’s interesting to note that a delay could be inserted within the loop to slow down the ticks, by adding System.Threading.Thread.Sleep(10); However, for our case, the faster the speed of the cellular automata, the quicker our evolutions will occur.

In the main portion of code, we set the size and position of the console window and draw a series of random cells throughout the 2-dimensional array. This will be our initial position before we begin applying the rules for our cellular automata. You can create a vast number of different initial positions, which in turn, can create vastly different patterns of artificial life.

The most important part of the above code is where we instantiate an instance of our cellular automata rule set. The RuleSet class holds the job of manipulating the cells and applying the rules for life, death, and birth. Notice we use a RuleSet variable, which will be an abstract base class (or even an interface) and implement it with the concrete class ConwaysGameOfLife(). As you can tell, we could create many different implementations of the rule set to define different versions of rules for our artificial intelligence cellular life.

Let’s move on to creating the base RuleSet class, from which all rule sets will inherit from.

Create the RuleSet Class

Our base RuleSet class will take care of handling the common code, used by all the different versions of rule sets. For example, each rule set will need to be able to calculate its neighbors. We’ll define a function GetNumberOfNeighbors(x, y) which will return the count of neighbors for a particular cell at position x,y. This function itself, is the heart of any cellular automata rule set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public abstract class RuleSet
{
    protected int _maxX = 0;
    protected int _maxY = 0;
    protected int[,] _field;

    /// <summary>
    /// Instantiates the RuleSet with a copy of the game field, and the maximum X,Y boundaries.
    /// </summary>
    /// <param name="field">int[][] game field</param>
    /// <param name="maxX">Maximum X boundary</param>
    /// <param name="maxY">Maximum Y boundary</param>
    public RuleSet(int[,] field, int maxX, int maxY)
    {
        _field = field;
        _maxX = maxX;
        _maxY = maxY;
    }

    /// <summary>
    /// Returns the number of neighbors for a cell at X,Y.
    /// </summary>
    /// <param name="x">X coordinate of cell to check</param>
    /// <param name="y">Y coordinate of cell to check</param>
    /// <returns>number of neighbors</returns>
    protected int GetNumberOfNeighbors(int x, int y)
    {
        // Returns the number of neighbors for a specific coordinate.
        int neighbors = 0;

        if (x + 1 < _maxX && _field[x + 1, y] == 1)
        {
            neighbors++;
        }

        if (x - 1 >= 0 && _field[x - 1, y] == 1)
        {
            neighbors++;
        }

        if (y + 1 < _maxY && _field[x, y + 1] == 1)
        {
            neighbors++;
        }

        if (y - 1 >= 0 && _field[x, y - 1] == 1)
        {
            neighbors++;
        }

        // diaganols
        if (x + 1 < _maxX && y + 1 < _maxY && _field[x + 1, y + 1] == 1)
        {
            neighbors++;
        }

        if (x + 1 < _maxX && y - 1 >= 0 && _field[x + 1, y - 1] == 1)
        {
            neighbors++;
        }

        if (x - 1 >= 0 && y + 1 < _maxY && _field[x - 1, y + 1] == 1)
        {
            neighbors++;
        }

        if (x - 1 >= 0 && y - 1 >= 0 && _field[x - 1, y - 1] == 1)
        {
            neighbors++;
        }

        return neighbors;
    }

    /// <summary>
    /// Executes one generation of the game field, causing cells to live, die, or give birth.
    /// This is a template method, which calls the concrete method TickAlgorithm() to execute the cell movement details.
    /// </summary>
    public void Tick()
    {
        int[,] field2 = TickAlgorithm();           

        // Copy field = field2.
        Array.Copy(field2, _field, field2.Length);
    }

    /// <summary>
    /// This is part of the template method Tick() and contains the details for cell activity.
    /// This method examines the current field and returns a new field with the changes for 1 generation.
    /// </summary>
    /// <returns>int[][] new game field</returns>
    protected abstract int[,] TickAlgorithm();       
}

Notice in the above code, GetNumberOfNeighbors() is fairly basic in structure. We simply check each side across, up and down, and diagonals for a particular cell to count its neighbors. If any neighboring cell holds a value of 1, then we increment the count.

Two Patterns For One - The Strategy Pattern and the Template Pattern

Since we’re implementing the Strategy design pattern by creating an abstract base class, we’re going to be defining concrete implementations for each cellular automata rule set. We can also take advantage of the Template Pattern to make coding the concrete rule sets even easier. Notice in the above code, our public method Tick() calls a protected method TickAlgorithm(). The user who implements the RuleSet() class will have access to call the Tick() method, but not the TickAlgorithm() class. TickAlgorithm will be defined by the concrete class and will contain the code which actually modifies the world array, according to the rule set. The public method Tick() then copies the results in the main world, thus advancing our artificial life one generation forward.

Implementing a Concrete RuleSet for Conway’s Game of Life

With the base RuleSet class defined and a template method created, it’s quite easy to design a concrete rule set class. We simply inherit from the RuleSet class and implement the template method, TickAlgorithm(), as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class ConwaysGameOfLife : RuleSet
{
    public ConwaysGameOfLife(int[,] field, int maxX, int maxY)
        : base(field, maxX, maxY)
    {
    }

    protected override int[,] TickAlgorithm()
    {
        int[,] field2 = new int[_maxX, _maxY];

        // 23/3 - Conway's Game of Life
        // The first number(s) is what is required for a cell to continue.
        // The second number(s) is the requirement for birth.
        for (int y = 0; y < _maxY; y++)
        {
            for (int x = 0; x < _maxX; x++)
            {
                int neighbors = GetNumberOfNeighbors(x, y);
                if (neighbors == 3)
                {
                    // cell is born.
                    field2[x, y] = 1;
                    continue;
                }

                if (neighbors == 2 || neighbors == 3)
                {
                    // cell continues.
                    field2[x, y] = _field[x, y];
                    continue;
                }

                // cell dies.
                field2[x, y] = 0;
            }
        }

        return field2;
    }
}

Note in the TickAlgorithm() method, we execute the rules for our cellular automata artificial life and returns a new world array with the changes made. Since our rule set is 23/3 (which is also called Conway’s Game of Life), we’ll leave a cell alive (with a value of 1) if it has exactly 2 or 3 neighboring cells with a value of 1. If cell is currently a zero (meaning the cell is not alive), and it finds itself having 3 neighbors, the cell will become alive and get a value of 1. In all other cases, the cell will die and reset its value back to zero.

Naturally, we can create many different rule sets, based upon our RuleSet class, to implement different versions of cellular automata artificial life. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Rule125d36 : RuleSet
{
    public Rule125d36(int[,] field, int maxX, int maxY)
        : base(field, maxX, maxY)
    {
    }

    protected override int[,] TickAlgorithm()
    {
        int[,] field2 = new int[_maxX, _maxY];

        // 125/36
        // The first number(s) is what is required for a cell to continue.
        // The second number(s) is the requirement for birth.
        for (int y = 0; y < _maxY; y++)
        {
            for (int x = 0; x < _maxX; x++)
            {
                int neighbors = GetNumberOfNeighbors(x, y);

                if (neighbors == 3 || neighbors == 6)
                {
                    // cell is born.
                    field2[x, y] = 1;
                    continue;
                }

                if (neighbors == 1 || neighbors == 2 || neighbors == 5)
                {
                    // cell continues.
                    field2[x, y] = _field[x, y];
                    continue;
                }

                // cell dies.
                field2[x, y] = 0;
            }
        }

        return field2;
    }
}

The above code defines a different rule set for cellular automata, based upon 125/36. If a cell has 1, 2, or 5 neighbors, it will continue living (if it was already alive). If a cell has 3 or 6 neighbors it will be born (if it was currently a zero). Each different ruleset can create drastically different patterns of virtual life.

A Concrete Generic RuleSet to Rule Them All

Similar to the above concrete ruleset examples, we can actually create a generic ruleset implementation that you can pass the notation form of the rule to implement all of the different behaviors, without having to implement individual ruleset classes for each one. This class makes it much easier to try out different cellular automata rule sets. For example, if you wanted to create the rule set 123/45, you could simply call RuleSet = new RuleGeneric(field, maxX, maxY, 123, 45). Likewise, to create the rule set 876/5432, you could simply call RuleSet = new RuleGeneric(field, maxX, maxY, 876, 5432). The code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/// <summary>
/// Generic rule A/B, where A represents the set of digits for a cell to continue and B the set of digits for a cell to be born.
/// </summary>
public class RuleGeneric : RuleSet
{
    private int _a;
    private int _b;

    public RuleGeneric(int[,] field, int maxX, int maxY, int a, int b)
        : base(field, maxX, maxY)
    {
        _a = a;
        _b = b;
    }

    /// <summary>
    /// Converts a number to an array of digits. For example 123 becomes 1,2,3
    /// </summary>
    /// <param name="digits">Number, such as 123</param>
    /// <returns>List of numbers, such as 1,2,3</returns>
    protected List<int> ToDigitArray(int digits)
    {
        List<int> result = new List<int>();

        string digitString = digits.ToString();
        foreach (char digit in digitString)
        {
            result.Add(Convert.ToInt32(digit.ToString()));
        }

        return result;
    }

    protected override int[,] TickAlgorithm()
    {
        int[,] field2 = new int[_maxX, _maxY];

        // A/B
        // The first number(s) is what is required for a cell to continue.
        // The second number(s) is the requirement for birth.
        for (int y = 0; y < _maxY; y++)
        {
            for (int x = 0; x < _maxX; x++)
            {
                bool processed = false;
                int neighbors = GetNumberOfNeighbors(x, y);

                List<int> birthDigits = ToDigitArray(_b);

                foreach (int digit in birthDigits)
                {
                    if (neighbors == digit)
                    {
                        // cell is born.
                        field2[x, y] = 1;
                        processed = true;
                        break;
                    }
                }

                if (processed)
                {
                    continue;
                }

                List<int> liveDigits = ToDigitArray(_a);
                foreach (int digit in liveDigits)
                {
                    if (neighbors == digit)
                    {
                        // cell continues.
                        field2[x, y] = _field[x, y];
                        processed = true;
                        break;
                    }
                }

                if (processed)
                {
                    continue;
                }

                // cell dies.
                field2[x, y] = 0;
            }
        }

        return field2;
    }
}

Outputting Artificial Intelligence Life

With our RuleSet design created and our main loop defined, we can run the example program to view our cellular automata artificial life forms. An example output from the above code produces the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
                         oo   o
                        ooo   oo    ooo
                         oo    oo
                oooo            oo
               o    o       oo oo
                 o          oooo
              o   o  o
   o           oo  oo
  ooo           o o                               o
  o  o                                           o o
 oo   o o              ooo                       o o
  ooo     o        oo   o o                       o
  o  o    o      oo ooooo o
   o       o        o  o                     oo       oo
   oooo             o o                     o  o     o  o
   o  oo o o         oo                      oo       oo
    o oo        o
     oooo        o                                o
      o  o o     o            o                  o o
          o   o  o           o o                 o o
  o            oo             o                   o
 ooo
o  oo

oo   o           ooo
 o               o o              ooo
 oo    o         oo                               o
       ooo       oo                               o    ooo
       oo      o                                  o
       oo
     o oo                                     ooo   ooo
      o  o                 oo   oo
      o  o  ooo            oo   oo                o
      o    o                                      o
      ooo o                                       o
     oo   oo oo
            o

Notice that clearly defined patterns begin to emerge from the initial random pixels we created. Each time the program is ran, the initial random pixels differ, yet similar patterns and movement emerge. It can be quite amazing how complex the patterns can evolve to be, using such simple rules for life. Since we are using the ruleset from Conway’s Game of Life, eventually the evolutions will stabilize and a final pattern will emerge.

The pattern below is a final stable pattern from an initial random configuration.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
                                     oo
                                     oo
oo       o
oo       o     ooo
         o
             o     o
             o     o
             o     o                              o
                o                                o o
                o                                o o
                o                                 o
                               ooo
ooo                     o                    oo       oo
                       o o   o     o        o  o     o  o
    oo                 oo    o     o         oo       oo
    oo                       o     o
                ooo                               o
       oo                      ooo               o o
      o o                                        o o
       o                                          o

                                   o
                                   o
          oo                       o                    o
          oo                                     ooo    o
      oo                                                o
      oo                                       o     o
                                               o     o
                 oo       oo    oo             o     o
                o  o     o  o   oo
             o   oo       oo                     ooo
            o o
            o o     oo
             o      oo

Applying Cellular Automata to Actual Work

While cellular automata artificial life in C# .NET is interesting to look at, perhaps even art, the functional use of cellular automata could go much further. Certain rule sets for cellular automata have been proven to implement universal computation, also called Turing machines. A universal machine can be programmed to solve any mathematical problem, given enough space, time, and memory (such as, with a PC computer). By knowing that cellular automata can implement a universal machine, it’s actually possible to provide input to a cellular automata artificial life pattern and receive coherent output in return, virtually programming the cellular life.

For example, the initial configuration of a cellular automata (such as the random configuration we used above) can be considered the input. The final stabilized pattern of the cellular automata can be considered the output. Both the input and output would be considered encoded data, which could be translated to known values. A more concrete example would be attempting to solve the basic math function AND. One could theoretically devise a method to encode the data of 0 and 1 in an initial configuration of cellular automata, then run the program (ie. allow the cellular automata to fully run until stabilization occurs), and then count the output cells to decode the final value. Thus, passing in the initial values for 1 AND 0, the expected output would decode to 0. Likewise, passing in the initial values for 1 AND 1, the expected output would decode to 1.

Cellular Automata and Genetic Algorithms

Since an initial configuration for cellular automata consists of a very large number of possibilities, one could speed up the process of solving a mathematical problem with a cellular automata network, by using a genetic algorithm to discover the proper initial configuration and stable configuration for output.

The key behind using a genetic algorithm would be to create a precise fitness test which moves each cycle of the cellular automata closer to the expected answer. For example, we could draw an invisible line down the center of the world grid. The left side could represent 0 and the right side 1. If only cells on the left side are alive (or the majority), the output could be considered a 0. If only cells on the right side are alive (or the majority), the output could be considered a 1. Using this method, we can effectively encode and decode cellular automata data. This would allow us to theoretically use artificial life to solve a mathematical problem. The generations of life evolving would be considered the program executing and the configuration of cells at start and end would be the input and output, respectively.

Conclusion

Cellular automata is a form of artificial life involving single-celled virtual life forms, within a C# .NET computer program multi-dimensional array. While the rule sets behind the life, death, and birth of each cell is simple, the patterns of life that emerge from each single cell and group of cells can be quite complex. Cellular automata was initially created in the hopes of discovering self-replicating machines, but has been mostly held as an interesting visual to display. While certainly interesting to look at, it’s possible for cellular automata to produce real-world solutions and computations, and be capable of solving complex mathematical functions, similar to any computer. Perhaps, the real power behind cellular automata is yet to be discovered.

About the Author

This article was written by Kory Becker, software developer and architect, skilled in a range of technologies, including web application development, machine learning, artificial intelligence, and data science.

Share