Objectives: You will

• learn to implement an inheritance relationship
• learn to implement operator overloading

Problem Specification: A cellular automaton (CA) is an array of identically programmed automata, or "cells", which interact with one another. The arrays usually form either a 1-dimensional string of cells, a 2-D grid, or a 3-D solid. Most often the cells are arranged as a simple rectangular grid, but other arrangements, such as a honeycomb, are sometimes used. By building appropriate rules into a cellular automaton, we can simulate many kinds of complex behaviour, ranging from the motion of fluids governed by the Navier-Stokes equations to outbreaks of starfish on a coral reef.¹

For this assignment you will implement a CA in a one-dimensional array of 32 cells using simple rules to govern the interaction between cells. Specifically, these rules determine whether a given cell will live or die. The CA will be simulated over many generations of cell birth, death, and resurrection. To get a better sense of what I expect, you can download a working version of the program here.

Implementation: This won't be an extremely long program but you will be asked to implement some of the fairly complex ideas introduced in recent lectures: inheritance and operator overloading.

I require that you design and implement five classes: CACell, CARabbitCell, CATurtleCell, CAPopulation, and CASimulator.

The CACell is an abstract base class representing a generic cell in the CA. Your CACell class should be defined as follows:

class CACell {

public:
CACell ();
CACell (bool);
CACell (const CACell&);
~CACell ();

CACell& operator= (const CACell&);

inline bool GetState () const {return state;}
inline bool SetState (bool InState) {state = InState; return true;}

virtual void Mate (const CACell*, const CACell *, const CACell*) = 0;

friend ostream& operator<< (ostream&, const CACell&);

protected:
bool state; //either 0 or 1, true or false, dead or alive
};

CARabbitCell and CATurtleCell are derived from CACell. They should inherit most of their functionality from CACell. CARabbitCell and CATurtleCell will override CACell's Mate method, which is pure virtual in CACell. The CARabbitCell will implement the following mating scheme:

L, C, R -> result
___________________
0, 0, 0 -> 0
0, 0, 1 -> 1
0, 1, 0 -> 1
0, 1, 1 -> 0
1, 0, 0 -> 1
1, 0, 1 -> 1
1, 1, 0 -> 0
1, 1, 1 -> 0

The first row (0,0,0->0) indicates that if a cell (C) is dead in the current generation and its left neighbor(L) and right neighbor(R) are also both dead in the current generation, then the cell (C) will be dead in the next generation (result). The third row (0,1,0->1) indicates that if a cell (C) is alive in the current generation and its left neighbor(L) and right neighbor(R) are both dead in the current generation, then the cell (C) will be alive in the next generation (result). The other six cells are interpreted similarly.

For example, if the current generation of 32 rabbit cells is:
*---*---*---*---*---*---*---*---
(where '-' represents a dead cell and '*' represents a live cell) then the next generation of 32 rabbit cells will be:
**-***-***-***-***-***-***-***-*
(Note: The left neighbor of cell 0 is cell 31. The right neighbor of cell 31 is cell zero.)

The CATurtleCell will implement the following mating scheme:

L, C, R -> result
___________________
0 0 0 -> 1
0 0 1 -> 1
0 1 0 -> 0
0 1 1 -> 0
1 0 0 -> 1
1 0 1 -> 1
1 1 0 -> 1
1 1 1 -> 1

The CAPopulation class will be composed of either 32 CARabbitCells or 32 CATurtleCells. To have the ability to store either type of cell, the CAPopulation should, in its private section, keep an array of 32 elements, each a pointer to a CACell. These pointers have the ability to point to either CARabbitCells or CATurtleCells. Here is the minimal required CAPopulation class definition:

enum CellType {rabbit, turtle};

class CAPopulation
{
public:
CAPopulation(CellType InCellType = rabbit);
CAPopulation(const CAPopulation&);

~CAPopulation();

CACellPtr& operator[] (int i); //will return a reference to the ith item in the cellsInPop array

friend ostream & operator << (ostream&, CAPopulation&);

private:
CACellPtr cellsInPop[32];
};

You may add other class methods/data members as you see fit.

The CASimulator class will be composed of the current population of cells and the previous population of cells. As described above, the current population is generated from the previous population. Your CASimulator class should, at minimum, look like this:

class CASimulator
{
public:
CASimulator(CellType InCellType = rabbit, int InNumGenerations = 15);
~CASimulator();

private:
CAPopulation * currPop, * prevPop;
};

You may add other class methods/data members as you see fit.

To facilitate the manipulation of current and previous generations, you will use a technique called double buffering. Double buffering, in the context of this program, works as follows:

1. CurrPop and prevPop are made to point to two identical dynamically generated populations.
2. Use the previous population to generate the current population (as described above).
3. Output the current generation.
4. Swap the currPop pointer and prevPop pointer. In other words, if currPop points to population A and prevPop points to population B, then make currPop point to population B and prevPop point to population A.
5. Return to step 2.

Required Testing:You must run the CASimulator for 15 generations using a population of rabbit cells and a population of turtle cells. The initial population in each case should contain 31 dead cells and one live cell; the live cell should be the middle cell in the population.

15 generations of the rabbit-cell Population should look like this:
----------------*---------------
---------------***--------------
--------------*---*-------------
-------------***-***------------
------------*---*---*-----------
-----------***-***-***----------
----------*---*---*---*---------
---------***-***-***-***--------
--------*---*---*---*---*-------
-------***-***-***-***-***------
------*---*---*---*---*---*-----
-----***-***-***-***-***-***----
----*---*---*---*---*---*---*---
---***-***-***-***-***-***-***--
--*---*---*---*---*---*---*---*-

15 generations of turtle-cell Population should resemble the following:
----------------*---------------
****************-***************
*****************-**************
******************-*************
*******************-************
********************-***********
*********************-**********
**********************-*********
***********************-********
************************-*******
*************************-******
**************************-*****
***************************-****
****************************-***
*****************************-**

Extra Credit (+15): Find mating rules to produce the following pattern of generations:
----------------*---------------
--------------*-*-*-------------
------------*-*---*-*-----------
----------*-*-*---*-*-*---------
--------*-*---*---*---*-*-------
------*-*-*---*---*---*-*-*-----
----*-*---*---*---*---*---*-*---
--*-*-*---*---*---*---*---*-*-*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-
--*---*---*---*---*---*---*---*-

Note: Second-neighbors were used in the mating process above rather than adjacent (or nearest) neighbors.

¹Description of cellular automata taken from the Web site http://life.csu.edu.au/complex/tutorials/tutorial1.html.