Sometime around fifth grade I either invented or stole-and-then-forgot-about-stealing a kind of rule-based doodles that I later realized were cellular automata.

**Update:** Wherever I got them from, it looks like they’ve been
independently invented at least one other time. Paige Gulley was
posting art made with this style of automaton a few years
ago. She says she
didn’t learn about them anywhere, but came up with the idea herself, the
same way I remember doing it: doodling while bored in class.

~~ I've looked for information about them since and not been able to
find any --- which makes me think either I did invent them, or else wherever
I stole them from isn't very well-known. If I did did invent them, I'll call
them "lace automata," because a lot of them form open, lacy patterns of
crossing lines and cables.~~

I’ve started playing around with them again recently, and trying to work
out some of their properties. As cellular automata, they’re similar to,
but not the same as, Wolfram’s elementary cellular
automata. The
differences mean there are a *lot* more lace automata than ECAs:

(2

^{3})^{(23)}= 16777216

of them rather than

2

^{(23)}= 256.

And they mean that lace automata can do some things ECAs can’t, like make patterns that grow at irregular speeds, or at less than the “speed of light,” or that alternate between growing and shrinking.

## How they work

A lace automaton generates a pattern of vertical and diagonal lines drawn against a grid, like the one at the top of this post. It generates the pattern row-by-row, following a rule. The rule tells you things like “If two diagonal lines came together at a point at the end of the last row, draw a vertical line down from that point in the next row.”

For instance, the picture at the top of this post was generated by this rule:

Suppose we start with a single vertical line. Our rule says that it splits in three, like this — and that’s the end of our second row:

In the third row, we have to work out how each of the new lines evolves. There is a leftward diagonal, which — consult the rule above — splits in two;

a vertical line, which — as we already know — splits in three;

and a rightward diagonal, which splits in two. So here’s row three complete:

In the fourth row, we start to see lines meeting each other. Working from left to right, first we find a single left diagonal, which we know how to handle:

Then we find a left diagonal coming together with a vertical line. The rule specifies a different outcome for this than for a left diagonal alone:

And so on for the rest of the row:

Similarly, for the fifth row — for which I won’t work through all the steps — at the very center of the pattern, we have to apply for the first time the part of the rule that says what to do with three lines coming together:

## Lace automata are cellular automata

Intuitively, this sure seems like a cellular automaton. It’s built on a rectangular grid. It’s rule-generated. The rule refers only to a limited neighborhood — where the neighborhood consists of the lines converging at a single point.

But the business with the lines is unusual.

In a normal cellular automaton, each state occupies a single spot on the grid, rather than running from one place to another. So let’s see if we can represent lace automata in that more normal form.

### States

A normal cellular automaton has a fixed set of states. Each spot on the grid has a single state assigned to it.

The counterpart in a lace automaton is *the pattern of lines leaving a
single point*. There are eight such patterns, and so we are looking at
an eight-state automaton. It’s convenient to represent each state with
three binary bits, where the low bit answers the question “does this
point have a line leaving on the right diagonal?” and similarly for the
middle and high bits.

### Neighborhoods

In a normal cellular automaton, each cell’s state in generation n+1 is based on a *neighborhood* of cells in
generation n. In a lace automaton, a
cell’s neighborhood is the set of other cells whose outgoing lines can
reach it. Since lines are always vertical or (on a 45-degree) diagonal,
that means we have a three-cell neighborhood.

For instance, the cell marked with a black dot has three neighbors: the one marked with a red dot (which can reach it with a rightward diagonal line), the one marked with a green dot (whch can reach it with a vertical line), and the one marked with a blue dot (which can reach it with a leftward diagonal line).

### Limited information

But we haven’t said anything yet about the directionality of the lines.

Consider again the picture repeated below. The black dot has the red dot in its neighborhood. But unlike in a normal cellular automaton, it doesn’t know everything about its neighbor’s state.

It “can tell” that the red dot has a line coming out on the rightward diagnal. But it has no idea if the red dot is also emitting vertical or leftward diagonal lines. In other words, it just knows about the low bit of the red dot’s state.

Similarly, the black dot only knows about the middle bit of the green dot’s state, and about the high bit of the blue dot’s state.

## Implementation

Now that we’ve converted lace automata into something more familiar, it’s easy enough to write code to run them.

Let’s say a state is a number from `0b000`

through `0b111`

— or in other words, zero
through eight, but as we saw above it’s more convenient to think of them
in terms of bits. The leftmost bit represents a line leaving on the left
diagonal, and similarly for the middle and rightmost bit.

We can also represent the *inputs* to our automaton’s rule as numbers
from `0b000`

through `0b111`

. Here, the leftmost bit represents a line
*entering* on the left diagonal, and similarly for the middle and
rightmost bits.

With this implementation, a rule is just a map from three-bit numbers representing inputs to three-bit numbers representing result states. For instance, the rule we represented graphically as follows

is, in our Python representation:

```
RULE = { 0b000 : 0b000,
0b001 : 0b110,
0b010 : 0b111,
0b011 : 0b001,
0b100 : 0b011,
0b101 : 0b010,
0b110 : 0b100,
0b111 : 0b000 }
```

If states are three-bit numbers, then a row of automaton output is a list of such numbers, and the full output will be a list of rows. Given a specified width, we’ll populate the first row by hand, and then enter a loop where we calculate new rows until we reach a specified height. :

```
WIDTH = 200
HEIGHT = 100
rows = [[0b000]*(WIDTH//2) +
[0b010] +
[0b000]*(WIDTH//2)]
for i in range(HEIGHT):
rows.append(apply_rule(get_neighborhoods(rows[-1])))
```

To flesh out this skeleton of a program we need two more things: an
`apply_rule`

function and a `get_neighborhoods`

function.

Actually applying the rule is easy. If we’re given a list of neighborhoods, we just look each one up in the mapping we’ve already defined :

```
def apply_rule(neighborhoods):
return [RULE[n] for n in neighborhoods]
```

The tricky part turns out to be getting the neighborhoods. Let’s start
with a function that looks up just one cell’s neighborhood. We give it a
list of cell states and a number `i`

, and
it looks up the neighborhood for the `i`

th
cell.

```
def get_neighborhood(row, i):
# First, get the complete state of each neighbor.
left = row[(i-1) % WIDTH]
mid = row[i]
right = row[(i+1) % WIDTH]
# Then, keep only the information we'll use:
out = (((left & 0b001) << 2) |
(mid & 0b010) |
((right & 0b100) >> 2))
return out
```

That last line is worth a closer look. `(left & 0b001)`

gets only the
low bit of `left`

; and `(left & 0b001) << 2`

says “Take the low bit of
`left`

and make it my high bit.” Given the conventions we set up for
representing states and neighborhoods as numbers, this is the same as
saying “If a line leaves my leftward neighbor heading right, it comes to
me from the left.” Similarly, the other two parts of that line of code
mean “If a line leaves my middle neighbor heading straight down, it
comes to me in the middle,” and “If a line leaves my rightward neighbor
heading left, it comes to me from the right.”

Once we can get a neighborhood for one cell, we can do it for a whole row of cells.

```
def get_neighborhoods(prev):
return [get_neighborhood(prev, i)
for i in range(len(prev))]
```

Now we’re done calculating: we’ve supplied the `apply_rule`

and
`get_neighborhoods`

functions needed to create new generations of output. But
our output looks like this:

```
[0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 7, 0, 3, 0, 0, 0, 0]
[0, 0, 0, 7, 5, 3, 5, 3, 0, 0, 0]
[0, 0, 7, 7, 3, 2, 3, 2, 3, 0, 0]
[0, 7, 7, 2, 2, 2, 5, 2, 5, 3, 0]
```

With a little more code, we can output images instead of lists.

```
import cairo
SCALE = 5
surface = cairo.ImageSurface(cairo.FORMAT_ARGB32,
WIDTH*SCALE,
HEIGHT*SCALE)
ctx = cairo.Context(surface)
ctx.scale(SCALE, SCALE)
ctx.set_line_width(0.1)
for row in rows:
print(row)
for y, row in enumerate(rows):
for x, cell in enumerate(row):
if cell & 0b100:
ctx.move_to(x,y)
ctx.line_to(x-1,y+1)
ctx.stroke()
if cell & 0b010:
ctx.move_to(x,y)
ctx.line_to(x,y+1)
ctx.stroke()
if cell & 0b001:
ctx.move_to(x,y)
ctx.line_to(x+1,y+1)
ctx.stroke()
surface.write_to_png("test.png")
```

And here is the result!

## Gallery

Here are the outputs for a bunch more rules. Click to expand — they look much better at full size.

« How informative are shape notes?Write a LaTeX résumé; don't use a template »