# Next Nearest Neighbors Cellular Automata

Wentian Li’s 1998 article “Complex Patterns Generated by Next Nearest Neighbors Cellular Automata” described a very simple method of generating a vast number of interesting pattern or fractal-like images.

The idea is to start with a randomly generated line of cells, i.e., dots/pixels/bits, and then generate another line below it using a rule applied to each original cell.

The rule takes as input the value of the original cell and the two closest cells on each side of it (next nearest neighbors) i.e., four nearby cells, for five cells total.

Using a rule applied in this way, each line generates a new line below it, and so the image grows downward.

The rule, then, is a function that takes 5 bits of data (the five nearest neighbors) and outputs 1 bit of data (black or white, on or off).

Because 5 bits can hold exactly 32 possible values, we can represent any particular rule as a 32 bit value, where each bit maps to the value the function will output for a particular bit.

E.g., in the rule 11010101110001001100000010011001:
00000 maps to 1, 00001 -> 1, 00010 -> 0 … 11110 ->  0, 11111 -> 1.

So, each rule is a 32 bit unsigned integer (or “Word32” in some programming languages). The rule therefore can be represented any way a 32 bit unsigned integer can be. It can be represented simply as a decimal number (e.g., 3586441369), or as a hexadecimal value (D5C4C099) or even as a quad value, like in an I.P. addresses (213,196,192,153).

Since a rule can be any 32 bit integer, this means that there are exactly $2^{32}$ or 4,294,967,296 rules.

So, the number of rules is finite. But, with over four billion of them, there are plenty to look through!

Not all of the rules produce images that are visually interesting, and there are a lot of slight variations on a theme. But even if you skip over a lot of images, that leaves quite a few interesting ones.

Once the framework code is written, producing new images is a simple as picking consecutive or random 32 bit numbers.

And then you may take the time to sort through the images to find the ones you like.

The code library used to produce these images was written in the Haskell programming language. The library is available at the Hackage package respository as free software under the GPLv3 license, once the library is properly packaged.

And here are a few more images. Enjoy!