Cellular Automata

The beauty of cellular automata is that they are usually fairly simple discrete systems, but out of that simplicity comes a torrent of complexity. Cellular automations often have emergent properties. They are defined by simple rules, but they produce fascinating results through complex interactions within the system.

But just what is a cellular automation?

A cellular automation consists of a grid of cells. Every cell in the grid has one of a finite number of states. Each time the grid updates, the state of each cell is determined by a set of rules. These rules generally use the cell’s “neighborhood”, a set of cells near the cell in question, to determine the cell’s state. The simulation can continue indefinitely, and sometimes seems to take on a life of its own.

Take a normal every-day elementary school classroom for example. The teacher wants all the kids to form a line boy-girl-boy-girl. The teacher might tell the students to look at their neighbors and see if they’re a member of the opposite sex. If they are, stay there. If not, trade places with the one on your right and check again. It might not be the most efficient way to sort a line of kids, but eventually they’ll probably form a stable line in the specified order.

Let’s take a look at a more complicated example — freeway traffic. Cars move around following relatively simple rules, but often produce very complex situations.

Say you are on the freeway stuck in traffic. The cars in front, behind, and to the right of you are moving slower and blocking the way, but there’s room to your left to merge into a faster lane. So you turn your blinker on and merge into the space to your left, leaving another open space where you were for another car to merge in. Cars are always coming and going, moving around, following simple rules to get to their destination. Cellular automations have no destination, but they still follow a similar set of rules. They move in predictable patterns just as you can (to a limited extent) predict how traffic might flow on the freeway.

The agents of cellular automations are called cells. Cells are just pieces in the automation which have a position in the grid and a state. The simplest cells exist in a one-dimensional space, have binary states (alive or dead, there or not there), and change state according to a small set of rules. This kind of automation would be like the line of kids. It has one dimension, left or right, has only one binary state, boy or girl, and changes according to one simple rule, move right or don’t move. An automation with more dimensions, more states, and more complex rules could produce situations more akin to freeway traffic than school children. But they still operate in basically the same way — according to rules and states.

Cells usually don’t change state based only on their own state. They usually involve their neighbors in matters of state. A cell’s neighbors are a group of cells which have some special relationship to the cell, such as being right next to it. The Moore neighborhood is a common term for the eight cells immediately surrounding the cell. The Von Neumann neighborhood includes the four cells immediately surrounding the cell. This is basically the Moore neighborhood, but not including the cells adjacent to the corners of the cell.

Neighborhoods aren’t always right next to the cell. Sometimes the Von Neumann neighborhood extends two cells out from the center cell. There’s really no reason why cell neighborhoods need to be anywhere near the cell, it just seems to be a common way of doing things.

But what happens when a cell is close to the edge of the grid, so its neighbors are off the edge of the map? The easiest thing to do would be to just assign all the cells outside of the grid a single unchanging state. Another option is having special rules for edge cells to deal with the problem of a cell having fewer neighbors than the others. Sometimes this involves redefining what that cell’s neighborhood is, or even redefining the grid itself. The grid’s edges could loop back around to reference cells on the opposite side simulating a torus. A toroidal grid is edgeless, so cells can move freely around the map without stopping or dealing with edges.

Most cellular automations fit into one of four categories. The first type of automation stabilizes into an unchanging pattern. The second category evolves into a stable system of unchanging and oscillating structures. The third category evolves in a seemingly chaotic way with no end or stability. The fourth category is the most interesting. Category four automations are very complex patterns which cycle between chaotic and stable structures.

Emergence makes cellular automations so interesting. Simple structures interacting with simple rules creating complex systems. I’d highly recommend playing around with CA from time to time. You never know what you might find.

Advertisements