While thinking and reading about flocking algorithms and cellular automata, I had the idea of mixing the two algorithms together. I came up with a cellular automaton which generates colorful tapestries which seem to endlessly evolve while avoiding any repetitive behavior. Click here or on the screenshot below to watch the automaton. It begins with randomly colored cells; be sure to wait a little while for it to settle into an evolving color display. Then read my comments below for a description of what is going on.
the complete code can be downloaded here: Cellular01.zip
About the code
A typical cellular automaton consists of a grid of cells which continually change their state based upon the current states of their surrounding neighbors. A “state” may refer to a color, which may simply be black or white, as in Conway’s Game of Life. Here I allow the current RGB color of a cell to be affected by the status of the neighboring cells.
This idea (which may not be original) comes from a confusing insertion of the ideas of a flocking algorithm into a cellular automaton. The well-known boids algorithm models a flock of birds, and is described by three principles:
- separation: steer to avoid crowding local flockmates.
- alignment: steer towards the average heading of local flockmates.
- cohesion: steer to move toward the average position of local flockmates.
Since colors can be described with three parameters — red, green, and blue — changing colors can be thought of as motion in a 3D space. The “flying direction” of a bird corresponds to the (3D) rate of change of color. The cellular automaton I created is based upon the flocking algorithm, but by purposely confusing the idea of “local flockmate” to mean “neighboring cell” rather than all other entities with nearby colors.
So the automaton here is described with the following principles:
- separation: if a cell’s color is too close to that of one of its neighbors, move away from that color.
- alignment: adjust the rate of change of a cell’s color towards the average rate of change of its neighbors.
- cohesion: move the color of a cell towards the average color of its neighbors.
The total rate of change of a cell is based on summing the rates of change described by these three effects. Note that the separation and cohesion effects work against each other, but they are computed in slightly different ways (The separation vector is normalized to a constant magnitude; I’ll let you examine the code for the details). What makes this cellular automaton a little different from something like Conway’s Game of Life is that it considers not only the states of neighboring cells, but also the rate of change of the states of neighboring cells.
The end result has each cell wanting to be of a color similar to its neighbors, but not too close, while also trying to change color in the same direction as its neighbors. (I’ll leave you to create your own social metaphor.)
One note about neighbors: in a rectangular grid such as this one, each cell in the interior has eight neighbors (upper-left, upper, upper-right, etc.) but I chose to simplify the algorithm by only considering the four neighbors above, below, left and right. I also played around with the eight-neighbor setup, but the results will have to wait for another posting another day. Also note that some cells on the edge have fewer than four neighbors (I didn’t implement wrapping).
One more note: attempting to optimize this code for greater speed, I avoided the use of arrays. So the cells are contained in a linked list, and each cell keeps track of its neighbors with a linked list. (For an excellent introduction to linked lists, see this tutorial by Michael Baczynski).
I hope you enjoy the effect. I find it kind of pleasant to watch, especially while standing back from the monitor a few feet. Maybe it could be modified to become an evolving backdrop for a webpage? Have fun experimenting with the code. The effect is pretty sensitive; you’ll find that small changes in the code can have big effects on the emergent behavior.