Updates


Cellular Automata Project: Part 1

For the first deliverable of our project, you will become familiar with cellular automata (CA) and implement the building blocks for future deliverables. The two most important ideas for CA are the notion of a cell and its state. Just as our bodies are made of cells, a cellular automaton is made up of a configuration of cells. Each cell has a state; for our initial purposes, a state is either living or dead, which we will represent as 1 and 0 respectively.

Initially, we will only consider a one-dimensional CA. That is, the configuration is a single strand of cells, each of which (except the first and last) has a left and right neighbor. If we think of a string of cells as an organism, then from moment to moment those cells are changing state -- that is, living, dying, and being reborn. A cell's state will change according to a rule that considers the cell's current state and the states of its neighbors. CAs operating under different rules will exhibit different behaviors.

Next, we need to represent rules; that is, we need a way to determine the new state of a cell based on the pattern of its neighbors' states. For each possible situation (i.e., combination of a cell's current state and the state of its left and right neighbors), we need to specify the next state of the cell. For example, if the cell's current state is alive, and its left and right neighbors are both alive, a given rule may specify that the cell becomes dead. In this scenario, there are 8 possible situations -- 2 possible current states for the cell, 2 possible states for the left and 2 for the right. By representing numbers in a binary format, we can capture a rule very compactly as a vector of 8 new-state values (0 or 1). The new-state of a cell is indexed by its current state and the states of its neighbors (treated as a binary value and converted to a decimal value between 0 and 7 inclusive). The table below shows an example of a rule with the new state values in the right column, indexed by the decimal values in the left column, which correspond to the possible state patterns in the middle column. (A binary representation is like our normal base-10 representation, except instead of 1's, 10's, 100's, etc., it has places valued by powers of 2 -- 1's, 2's, 4's, 8's, etc. Of course, the only digits are 0 and 1. But when we count from 0 to 7, we see every possible combination of three states.)

decimal value of state pattern as binary code state pattern (binary code) new state of center cell
00000
10011
20100
30111
41001
51010
61101
71110
Thus, we use the situation of left neighbor, given cell, right neighbor, as a numeric index into a vector. Thus, a vector of 8 elements can represent a rule. The table above specifies one particular rule. Loosely, this rule says a cell (the center cell in a pattern) lives if it has exactly one neighbor, dies from crowding with two neighbors, and dies from loneliness with no neighbors. This is just one rule; the astute reader will note there are 256 possible rules. The content of an indexed vector-element will be the new value of the cell centered in the corresponding pattern. For the example above, we would have the rule: (vector 0 1 0 1 1 0 1 0); and if we have a situation where a cell is dead and with both neighbors alive (101 -- binary for the number 5), then the cell's new value would be found in (vector-ref this-rule 5), or 0 in the case of our example (if we refer to our rule as "this-rule"). Note: at either end of an organism, the cells do not have neighbors on one side or the other. In those cases, you will have to write your code to provide a virtual neighbor with a 0 value.

Preliminaries and Definitions

Having presented the basics of cellular automata, we need data definitions so we can implement them in Racket. We've already decided to represent a state as either 0 or 1, But we also need a way to represent organisms and rules. Since we're starting with a one-dimensional CA, let us represent a given organism as a list of cells. Finally, since we will be determining the new state of a cell by indexing into a given rule, let us represent a rule as a vector of states.

Although a string of cells will represent an organism, we will want to observe this organism over time. Thus, we will define a world as a list of organism snapshots. This list captures the organsim's history with the current state of the organism as the first element of the list. The last item in the list represents the organism's initial state. Since we will use the 2htdp/universe and 2htdp/image teachpacks, you will need to provide a world to big-bang in order to animate the evolution of your organism.

Requirements

As always, follow the design recipe and make sure your code conforms to the specifications. Function names and argument order must be followed precisely. I will test your program with code of my own so errors at testing time will result in significant penalties even if your code ostensibly ‘works’.

  1. Updating worlds. Write a function update-CA1 that consumes the representation of a world and returns a new world. In our case, the world is a list of organsims, and we want to take the current state and compute the next state. For this purpose, write the function compute-next, that consumes a single organism and returns a new organism based on the current rule. You should define a RULE identifier and refer to this as needed when updating.
  2. Rendering a world. Write the function, draw-CA1, that when given a world instance will return an image. The image that is returned should show the current organism across the top of the image, with previous states displayed successively below it. Individual cells should be rendered as solid circles when they are alive and as blanks (nothing) when dead.
  3. Generality. You must define and use identifiers that will allow easy modifications to: the number of cells in an organism, the size of a single cell when rendered, the size of the window, etc.
  4. Animating your CA. Write the function, run-sim: N organism -> (listof organism), that consumes a Natural-number representing how many time steps to simulate and an initial single organism. This function simply calls big-bang with an appropriate initial world, returning whatever big-bang returns. In addition to the to-draw and on-tick clauses to big-bang, you must include a stop-when clause that terminates the simulation after the specified number of time steps.

Submission

Do not forget to include the standard acknowledgements header at the top of your file. To grade this deliverable, I will review your code (including contracts, purpose statements, test cases, indentation, etc.), and then call run-simulation with your update-CA1 and draw-CA1 functions, together with an initial organism of my choosing.

Submit a single file with your username followed by “P1.rkt” as the name of the file, which should contain your code fulfilling the above requirements as well as your acknowledgements.