# Block Cellular Automata
Blocks with sliding overlap make 2D textures.
# 1 Credits
This is all based on Guy Birkin’s great blog post which you should go read first:
https://aestheticcomplexity.wordpress.com/2026/07/17/block-cellular-automata/
# 2 Algorithm
Cells in a 2D grid can have one of C colours.
A set of rules maps top of N×N blocks to new bottom of blocks.
# 2.1 2×2
Given 1 row of input of even width, stack 2×2 blocks horizontally without overlap so that the top row of each block contains 2×1 adjacent cells of the input and 2×1 cells of what will be the next 1 output row below.
Then use each 2×1 cell input array as a key into a rule map, to find the next 2×1 cell array to fill the ouput row.
Then feed back the output to the input, shifting the block origin by 1 cell horizontally and vertically each generation.
# 2.2 N×N
A logical generalisation of algorithm above.
Given N-1 rows of input of width a multiple of N, stack N×N blocks horizontally without overlap so that the top N-1 rows of each block contain N×(N-1) adjacent cells of the input and N×1 cells of what will be the next 1 output row below.
Then use each N×(N-1) cell input array as a key into a rule map, to find the next N×1 cell array to fill the ouput row.
Then feed back the output to the input, shifting the block origin by 1 cell horizontally and vertically each generation.
# 2.3 3D
Another generalisation of algorithms above, given an N×N×(N-1), get the next N×N×1.
Offset in both x and y when evolving in the z axis.
# 3 Counting BCAs
With N×N blocks and C colours, in D dimensions, the total number of block cellular automata is
\[C^{(N^{D-1} \times C^{N^{D-1} \times (N-1)})}\]
which gets very big very quickly.
# 4 Symmetry
When the rules are symmetric, the patterns are more uniform (I conjecture each colour occurs with roughly the same density and their distributions are more isotropic).
I define a rule to be symmetric when the set of complete blocks is invariant under spatial symmetries of the square (including rotations and reflections) and cyclic permutation of the colours (so including 012, 120, 201 but not 021).
This doesn’t mean that each block is individually symmetric, but that applying any common symmetry to the set of all blocks gives the same set (sets ignore order of occurence and duplicates).
# 4.1 Counting Symmetric BCAs
I have not found a way to count them apart from enumerating them. My initial enumeration code has bugs that I spotted because some of the images looked very similar, I fixed it by canonicalizing colour permutations (colours names are arbitrary).
# 4.1.1 Counting 2D
N C count
2 1 1
2 2 2
2 3 1
2 4 4
2 5 2
2 6 8
2 7 3
2 8 20
2 9 14
...
3 1 1
3 2 132
...
4 1 1
...
# 4.1.2 Counting 3D
N C count
2 1 1
2 2 4
2 3 3
2 4 480
...
3 1 1
...
# 4.2 Enumerating Symmetric BCAs
Enumerating symmetric BCAs not trivial because the total number of BCAs is huge, so the simple approach of generating all BCAs (which is relatively easy) and filtering to just the symmetric ones is doomed to failure (you’ll be waiting nearly forever…).
The approach I settled on was to start with one block, generate all symmetries of it, and keep growing the rule set by adding new blocks until a complete rule set is achieved. The search space is pruned by rejecting at the earliest opportunity if an inconsistent rule set occurs (e.g. symmetries end up making two different blocks have the same key (the N×(N-1) top part)).
# 5 Catalog
I put some output of my program online:
# 6 Source Code
I used Haskell with the list Monad, with a
custom replicateM that avoids a space leak.
Compile like ghc -O2 block-cellular-automata.hs
and use like head -c $((256 * 256 * 256) < /dev/urandom > seed.bin && ./block-cellular-automata N C,
where the seed is used to populate the inital (N-1) top rows with C colours.
The seed file needs to be big enough for N-1 rows
(width currently fixed to around 256).
The 3D version is split into two files, one searches for symmetric rules and the other generates image sequences for a particular rule.