Cherniak Nibbles (Dmitri Cherniak cell-eating cellular automata)

Math essence

Maintain an occupancy grid O of size (H, W) initialised to -1 (empty). At step t: pick an alive nibble n uniformly at random. For each cell c in n's cells, find the empty 4-neighbours and score them by alignment with the local growth-preference direction d(c) = (cos(2*pi*perlin(c)), sin(2*pi*perlin(c))). Greedily add the best-aligned empty neighbour to n (with 25% probability take the second-best for stochastic variation). If n has no empty neighbours, mark it dead.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/hobbs_cherniak_penne_deep/CherniakNibbles/reference.py

"""CherniakNibbles — Dmitri Cherniak cell-eating cellular automata.

A homage to Dmitri Cherniak's algorithmic style of *Nibbles* —
small 2D shapes that "nibble" through a grid of cells by
selectively removing neighbours.  Each nibble is a Voronoi-like
growing cell: at every step it picks a random cell on its
boundary, grows by 1 pixel, and stops if the new pixel would
collide with another cell or the canvas edge.

Cherniak describes his generative practice (LACMA, 2021):

    "One question is at the heart of Dmitri Cherniak's practice
     – what are the possibilities of automated art? Using
     algorithms, he crafts intricate abstract artworks that vary
     in mood and design."

The Nibbles kernel we implement:

    1. Initialise a 2D grid of "live" cells (a low-density
       starting layout: a few seeds at random positions, or a
       single block in the centre).
    2. Maintain a list of "nibbles" — each is a connected
       component of live cells with a known boundary.
    3. At each step, pick a nibble uniformly at random, then
       pick one of its boundary cells, and grow the nibble by
       1 pixel in a direction chosen by a noise-driven "growth
       preference" field (so different nibbles grow in different
       preferred directions, producing asymmetric forms).
    4. If the new pixel would collide with another nibble or
       the canvas edge, the nibble "dies" — its growth halts.
    5. Repeat for many steps.  The result is a grid of
       asymmetric 2D forms, each shaped by its growth history.

This is essentially an asymmetric Voronoi tessellation driven
by cellular-automata growth.  The visual is a tessellation of
irregular polygonal cells, like a Voronoi diagram but with
boundaries that look slightly noisy / hand-drawn (because the
growth is stochastic, not perfectly radial).

Reference:
- https://www.dmitricherniak.com
- https://www.youtube.com/watch?v=HoMt5vXmtP0  (LACMA interview)
- Voronoi tessellation: https://en.wikipedia.org/wiki/Voronoi_diagram
"""
from __future__ import annotations

from typing import ClassVar

import numpy as np


def _noise_2d(perm: np.ndarray, x: np.ndarray, y: np.ndarray) -> np.ndarray:
    """Tiny value-noise sampler (we don't need full Perlin here)."""
    # Hash-based pseudo-Perlin, returning values in [-1, 1].
    xi = np.floor(x).astype(np.int64) & 255
    yi = np.floor(y).astype(np.int64) & 255
    xf = x - np.floor(x)
    yf = y - np.floor(y)
    h = perm[(perm[xi] + yi) & 255]
    gx = ((h & 1) * 2 - 1).astype(np.float64)