Next Nearest Neighbors Cellular Automata

autom-3142057717

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.

autom-3620459850
colorful wallpaper version

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.

autom-3406991364

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.

autom-2989489194

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

autom-2874966177

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).

autom-2813228870

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.

autom-2768674853

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

autom-2734709672

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).

autom-2492926114

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

autom-2460200544

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

autom-1858688907

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.

autom-1559972390

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

autom-1278393897

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

autom-1273091721

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.

autom-1127606298colorful wallpaper version

And here are a few more images. Enjoy!

autom-134957897

autom-1445123

autom-4686424

autom-724864770

autom-95156264.png

autom-1499973833

autom-1574524051

autom-2055483482

autom-3400381576

autom-3507681385