The video shows visualizations of 3D cellular automata in which a cell’s neighborhood is the set of cells whose centers lie inside or on the boundary of an Lp-ball of radius r centered on the cell, where p corresponds to the Lp-norm and p>=1.
Other properties are as per the systems studied in A New Kind of Science on Page 182 and Page 183:
- Grid: Cubic Honeycomb (with cell centers at integer lattice points)
- States: {0, 1} (only cells with state=1 are drawn)
- Initialization: A single cell with state 1 at the center of the 3D grid
- Update Rule: Various Growth Cases are used in the video, typically Growth Case {1}
The limiting shapes are the convex hulls of the centers of the neighborhood cells. These shapes are special cases of integral polyhedra called generalized Waterman polyhedra, and include instances of Platonic Solids, Archimedean Solids and Catalan Solids.
Computing Lp-Ball Neighborhoods
The set of neighborhoods for the origin cell and for a given value of p can be computed by increasing r starting from 0 and noting that a new neighborhood is observed whenever the Lp-ball of radius r just touches an (integer) lattice point.
The following Wolfram Language code plots neighborhoods and limiting shapes for p=2 and where the maximum lattice point coordinate is four. In the labels, n is the number of neighbors.
p = 2;
radii = Rest[Sort[DeleteDuplicates[Norm[#, p] & /@ Tuples[Range[0, 4, 1], 3]], Less]];
GraphicsGrid[
Partition[
Table[
coords = Select[Tuples[Range[-Ceiling[r], Ceiling[r]], 3], Norm[#, p] <= r &];
Labeled[
Grid[
Partition[
{Graphics3D[Cuboid /@ coords], ConvexHullMesh[coords]},
UpTo[2]
]
],
StringJoin[{"p=", ToString[p], ", r=", ToString[r], ", n=", ToString[Length[coords] - 1]}]
],
{r, radii}
],
UpTo[4]
]
]
Neighborhood offsets can then be used as input into the CellularAutomaton function in the Wolfram Language to compute and plot the 3D CA.
Notable Polyhedral Neighborhoods
Some notable limiting shapes and their parameters are noted below (additional instances for larger neighborhoods have been observed but are still to be verified):
- Regular Octahedron (6): p=2, r=1
- Cuboctahedron (18): p=2, r=Sqrt[2]
- Cube (26): p=2, r=Sqrt[3]
- Rhombic Dodecahedron (32): p=2, r=2
- Truncated Octahedron (56): p=2, r=Sqrt[5]
- Rhombicuboctahedron (Variant) (80): p=2, r=Sqrt[6]
- Truncated Rhombic Dodecahedron (86): p=3/2, r=3
- Cuboctahedron (2) (92): p=2, r=2Sqrt[2]
CA Specifications
Specifications for the 3D CAs in the video are as follows:
- 146 Neighbors: p=2, r=Sqrt[10], t=83, rule={1}
- 250 Neighbors: p=2, r=Sqrt[14], t=77, rule={1}
- 304 Neighbors: p=2, r=Sqrt[14], t={39, 43, 45, 49, 51}, rule={1}
- 098 Neighbors: p=3/2, r=2^(5/3), t={83, 85, 87, 89, 95}, rule={1,3}
- 086 Neighbors: p=3/2, r=3, t=71-107, rule={1}
- 178 Neighbors: p=2, r=2Sqrt[3], t=85, rule={1}
- 116 Neighbors: p=3, r=17^(1/3), t={93, 103, 107, 109, 111}, rule={1}
- 364 Neighbors: p=2, r=Sqrt[19], t=39, rule={1}
- 280 Neighbors: p=3/2, r=(1+2Sqrt[2]+3Sqrt[3])^(2/3), t={35, 37, 39, 41, 43}, rule={1}
- 032 Neighbors: p=2, r=2, t=108, rule={1}
- 080 Neighbors: p=2, r=Sqrt[6], t=112-127, rule={1}
- 056 Neighbors: p=2, r=Sqrt[5], t={55, 79, 87, 91, 95, 103, 107, 111, 119, 128}, rule={1}
- 092 Neighbors: p=2, r=2Sqrt[2], t={105-120}, rule={1}
- 388 Neighbors: p=2, r=2Sqrt[5], t={35, 37, 39, 43, 45}, rule={1}
- 202 Neighbors: p=2, r=Sqrt[13], t=77-95, rule={1}
- 154 Neighbors: p=3, r=2^(2/3) 7^(1/3), t={47, 51, 55, 59, 71}, rule={1}
- 130 Neighbors: p=3, r=3, t=71, rule={1}, {1, 2}, {1, 3}, {1, 9}, {1, 3}
- 286 Neighbors: p=3, r=3×2^(1/3), t={31, 39, 43, 45, 47}, rule={1}
- 232 Neighbors: p=3/2, r=3^(4/3), t={43, 45, 51, 53, 59}, rule={1}
- 176 Neighbors: p=3/2, r=4, t=79, rule={1}
- 200 Neighbors: p=3/2, r=(2Sqrt{2]+3Sqrt[3])^(2/3), t=51, rule={1}
Related Work
- Evans (1996) proposed Larger than Life (Conway’s Game of Life with extended neighborhoods) including for the 3D case
- Zaitsev (2016) proposed a k-neighborhood for Cellular Automata which includes “narrow” and diamond shaped neighborhoods in d-dimensions