Cellular Automata Example

Ann Lewis and Roger B. Dannenberg

This example is based on a class project by Ann Lewis.This project harnesses the power of cellular automata for algorithmic composition. Cellular automata have been applied to graphics and visual patterns as well as music. In this work, the automaton consists of an array of boxes, where each box is initialized to either black or white (on/off, 0/1). At every step the next row/generation (represented visually as below the previous array) is computed from the first array using an update rule on each array element. An update rule (that defines the automaton itself) is simply a function from the array element's parent, and the parent's left and right neighbors. This concept is illustrated here: 

	A1 A2 A3 ... 
	B1 B2 B3 ...

Let B2 be the element whose value is being computed. B2 is therefore dependent on the values of A1, A2, and A3 only. An example of an update rule would be:

if A1 = A3 and A2 = 1 then B2 = 1, else B2 = 0

There are 2 possible values for each of A1, A2, and A3 which means there are 2^3 = 8 possible configurations. And there are 2^8 = 256 possible functions from A1, A2, and A3 to B2. Therefore there are only 256 possible update rules. Note that the number of possible update rules is not dependent on the number of elements in the array. The rules can be numbered from 0 to 255. In the picture below, rule 30 is used to generate a series of rows, starting with a single "one" in the first row.

Instead of B1 = 1 indicating that a box be colored black and B1 = 0 indicated that a box be colored white, in the music model this will correspond to turning certain sound objects on and off. For example, here we have an array of oscillators. 

Osc 60 Osc 65 Osc 67 Osc 70 Osc 75 Osc 76 Osc 79

If only the 1st and 3rd elements are "turned on" this would result in the chord (sum (Osc 60) (Osc 67)). So each array, or level of the automata would correspond to a chord, and the chord progression would change over time as the automata developed.

This feature very versatile, so the user can specify the basic sound array, the duration of each step, and which combining function to bring the activated sounds together. This design allows the user to use any expression to create sounds.

The main function, cell-aut, takes the following parameters:

  1. an array of sound objects, specified using expressions to be evaluated
  2. the duration of each time step (also the duration for computing sound objects)
  3. the update rule to use on array evolution, specified by number (0 - 255)
  4. the number of iterations/generations the automata should allow itself to grow

Some interesting rules to try are Wolram's two most famous rules: 30 (chaotic) and 90 (fractal patterns).

Algorithm Outline

Here is an outline of the algorithm implemented in cell-aut.lsp.

  1. create and initialize "current" and "previous" bit lists -- these should have the same length as the sound array the user gave this function) -- potentially there could be a feature here allowing the user to specify the initial state of the array.
  2. create and initialize the list of sounds to return
  3. loop iter times
    1. get the list of currently activated sounds from the "previous" bit list and extract the corresponding sounds from the sound array
    2. combine this set of sounds with the combining function (specified by the user), and add the resulting sound to the output list
    3. compute the "current" bit list from the "previous" bit list using the update rule iterated over all the elements -- this wraps around so that endpoints are treated as being adjacent to each other
    4. set the "previous" bit array to the "current" bit array
    5. (end loop)
  4. return the output list of sounds

Demo

The file demos/allewis/cell_aut.lsp includes the function cell-aut-demo defined as follows:

(defun cell-aut-demo () 
  (play (scale 0.5 (cell-aut (cell-aut-major-scale) 0.2 30 80))))

so you can run this to hear an example output from the cell-aut function.