Source code for morphogen.automata.rules

"""Transition rules of binary cellular automata (states 0 and 1).

A rule maps the state of the lattice to the next one. Most rules depend on the number
``n`` of neighbours in state 1 (outer-totalistic rules):

``life`` (``B.../S...``)
    birth of a cell in state 0 when ``n`` is in the birth set, survival of a cell in
    state 1 when ``n`` is in the survival set (Conway's Game of Life is ``B3/S23`` in 2D).
``majority``
    the cell takes the state of the majority of its neighbourhood, itself included
    (voting rule): sharp interfaces of positive curvature retreat.
``anneal``
    twisted majority (Vichniac 1984): the outcome is inverted when the vote is closest
    to a tie. Interfaces then move with their mean curvature, as in the annealing of
    a binary alloy: domains coarsen into bicontinuous patterns.
``conserved``
    majority with a conserved volume fraction: the cells with the highest local
    density of phase 1 (random tie-breaking) take state 1, exactly as many as before.
    Domains coarsen at constant volume fraction (spinodal-like patterns).
``probabilistic``
    birth and survival probabilities depending on ``n``.
``activator_inhibitor``
    Young's (1984) model of Turing patterns: a cell weighs the active cells of a near
    disc or ball (activation) against those of a surrounding annulus or shell
    (inhibition); spots, stripes or labyrinths of a characteristic wavelength emerge.
"""

from __future__ import annotations

import re
from abc import ABC, abstractmethod
from dataclasses import dataclass

import numpy as np
from scipy import sparse

from morphogen.automata.lattice import kernel_sum, neighbour_counts, offsets
from morphogen.automata.tilings import TilingContext


[docs] @dataclass(frozen=True) class LatticeContext: """Neighbourhood and boundary of the lattice on which a rule acts.""" offsets: np.ndarray periodic: bool = True boundary: int = 0 dims: int = 3 @property def n_neighbours(self) -> int: return len(self.offsets)
[docs] def counts(self, state: np.ndarray) -> np.ndarray: return neighbour_counts(state, self.offsets, periodic=self.periodic, boundary=self.boundary)
[docs] class Rule(ABC): """Transition rule of a binary automaton.""" #: whether the volume fraction is conserved (synchronous updates only) conserves_fraction = False
[docs] @abstractmethod def next_state( self, state: np.ndarray, lattice: LatticeContext, rng: np.random.Generator ) -> np.ndarray: """State after one synchronous update of every cell."""
[docs] def describe(self) -> str: return type(self).__name__
def _count_set(text: str) -> set[int]: """'5678' (digits) or '13-14,17-19' (numbers and ranges) -> set of counts.""" text = text.strip() if not text: return set() if re.fullmatch(r"\d+", text) and "," not in text: return {int(c) for c in text} # Life-like notation: one digit per count out: set[int] = set() for part in text.split(","): part = part.strip() m = re.fullmatch(r"(\d+)(?:-(\d+))?", part) if not m: raise ValueError(f"rule: cannot read the counts {text!r}") a = int(m.group(1)) b = int(m.group(2)) if m.group(2) else a if b < a: raise ValueError(f"rule: empty range {part!r}") out.update(range(a, b + 1)) return out def _format_counts(values) -> str: """Counts as Life-like digits ('5678') when all are below 10, otherwise as numbers and ranges ('13,15-26'), so that :func:`_count_set` reads them back.""" v = sorted(values) if not v or v[-1] <= 9: return "".join(str(c) for c in v) runs = [[v[0], v[0]]] for c in v[1:]: if c == runs[-1][1] + 1: runs[-1][1] = c else: runs.append([c, c]) text = ",".join(str(a) if a == b else f"{a}-{b}" for a, b in runs) return f"{text}-{text}" if text.isdigit() else text # '13' would read as {1, 3}
[docs] class LifeRule(Rule): """Outer-totalistic rule ``B<birth>/S<survival>``. Counts are written as digits (``B5678/S45678``) or as comma-separated numbers and ranges for 3D neighbourhoods (``B13-14,17-19/S13-26``). """ def __init__(self, birth, survival): self.birth = frozenset(int(b) for b in birth) self.survival = frozenset(int(s) for s in survival) @classmethod def parse(cls, text: str) -> LifeRule: m = re.fullmatch(r"\s*B([\d,\- ]*)\s*/\s*S([\d,\- ]*)\s*", text, re.I) if not m: m2 = re.fullmatch(r"\s*S([\d,\- ]*)\s*/\s*B([\d,\- ]*)\s*", text, re.I) if not m2: raise ValueError( f"rule: expected 'B<counts>/S<counts>' (e.g. B5678/S45678 or " f"B13-14,17-19/S13-26), got {text!r}" ) return cls(_count_set(m2.group(2)), _count_set(m2.group(1))) return cls(_count_set(m.group(1)), _count_set(m.group(2))) def _lut(self, values, n: int) -> np.ndarray: lut = np.zeros(n + 1, dtype=np.uint8) for v in values: if 0 <= v <= n: lut[v] = 1 return lut
[docs] def next_state(self, state, lattice, rng): n = int(np.max(lattice.n_neighbours)) c = lattice.counts(state) born = self._lut(self.birth, n)[c] kept = self._lut(self.survival, n)[c] return np.where(state == 1, kept, born).astype(np.uint8)
[docs] def describe(self) -> str: return f"B{_format_counts(self.birth)}/S{_format_counts(self.survival)}"
[docs] class MajorityRule(Rule): """Majority vote over the neighbourhood and the cell itself; ``twist`` inverts the outcome of the two votes closest to a tie (Vichniac's annealing rule). With an odd number of neighbours (triangles across their edges, some Penrose rhombi across their vertices), the cell's own vote counts twice, so that the number of votes stays odd: ties keep the state of the cell. """ def __init__(self, twist: bool = False): self.twist = bool(twist)
[docs] def next_state(self, state, lattice, rng): n = lattice.n_neighbours own = 1 + np.asarray(n) % 2 # 1 on the grid (symmetric neighbourhoods) total = lattice.counts(state) + own * state m = n + own # odd half = m // 2 out = (total > half).astype(np.uint8) if self.twist: out[total == half] = 1 out[total == half + 1] = 0 return out
[docs] def describe(self) -> str: return "anneal" if self.twist else "majority"
def _top_fraction(score: np.ndarray, n_ones: int) -> np.ndarray: """Binary array with ones at the ``n_ones`` largest scores.""" flat = score.ravel() out = np.zeros(flat.size, dtype=np.uint8) if n_ones >= flat.size: out[:] = 1 elif n_ones > 0: out[np.argpartition(-flat, n_ones - 1)[:n_ones]] = 1 return out.reshape(score.shape)
[docs] class ConservedMajorityRule(Rule): """Majority with a conserved number of cells in state 1 (``fraction`` of the cells): the cells of highest local density of phase 1 win, ties broken at random (the density is the fraction of phase 1 in the neighbourhood and the cell when neighbourhoods differ in size).""" conserves_fraction = True def __init__(self, fraction: float): if not 0.0 < float(fraction) < 1.0: raise ValueError(f"fraction: must lie in (0, 1), got {fraction!r}") self.fraction = float(fraction)
[docs] def n_ones(self, n_cells: int) -> int: return round(self.fraction * n_cells)
[docs] def next_state(self, state, lattice, rng): n = lattice.n_neighbours if np.ndim(n) == 0: score = lattice.counts(state) + state + rng.random(state.shape) else: # fractions p / m differ by at least 1 / m_max^2: the noise only breaks ties m = n + 1 score = (lattice.counts(state) + state) / m + rng.random(state.shape) / m.max() ** 2 return _top_fraction(score, self.n_ones(state.size))
[docs] def describe(self) -> str: return f"conserved({self.fraction:g})"
[docs] class ProbabilisticRule(Rule): """Birth with probability ``p_birth[n]`` and survival with ``p_survival[n]`` (arrays indexed by the number ``n`` of neighbours in state 1).""" def __init__(self, p_birth, p_survival): self.p_birth = np.asarray(p_birth, dtype=float) self.p_survival = np.asarray(p_survival, dtype=float) for name, p in (("p_birth", self.p_birth), ("p_survival", self.p_survival)): if p.ndim != 1 or np.any((p < 0) | (p > 1)): raise ValueError(f"{name}: probabilities in [0, 1] indexed by counts")
[docs] def next_state(self, state, lattice, rng): n = int(np.max(lattice.n_neighbours)) c = lattice.counts(state) pb = np.zeros(n + 1) ps = np.zeros(n + 1) pb[: min(n + 1, len(self.p_birth))] = self.p_birth[: n + 1] ps[: min(n + 1, len(self.p_survival))] = self.p_survival[: n + 1] p = np.where(state == 1, ps[c], pb[c]) return (rng.random(state.shape) < p).astype(np.uint8)
[docs] def describe(self) -> str: return "probabilistic"
[docs] class ActivatorInhibitorRule(Rule): """Young's (1984) activator-inhibitor automaton. The score of a cell is the number of active cells within ``activation_radius`` (itself included) minus ``weight`` times the number of active cells at distances in (``activation_radius``, ``inhibition_radius``] (Euclidean distances in cells). The cell becomes active if the score is positive, inactive if negative. With a ``fraction``, the cells of highest score are active instead (conserved volume fraction). The default weight balances the two regions (a uniform state scores 0); on tilings whose discs differ from cell to cell (Penrose), it is balanced cell by cell. """ def __init__( self, activation_radius: float, inhibition_radius: float, weight: float | None = None, fraction: float | None = None, dims: int = 3, ): r1, r2 = float(activation_radius), float(inhibition_radius) if not (1.0 <= r1 < r2): raise ValueError("radii: 1 <= activation_radius < inhibition_radius (in cells)") self.r1, self.r2 = r1, r2 inner = offsets("euclidean", r1, dims=dims, include_center=True) outer = offsets("euclidean", r2, dims=dims, include_center=True) ring = outer[(outer * outer).sum(axis=1) > r1 * r1 + 1e-9] self.balanced = weight is None self.weight = len(inner) / len(ring) if weight is None else float(weight) if not self.weight > 0: raise ValueError("weight: must be positive") self.offsets = np.concatenate([inner, ring]) self.weights = np.concatenate([np.ones(len(inner)), -self.weight * np.ones(len(ring))]) self.fraction = None if fraction is None else float(fraction) self.conserves_fraction = self.fraction is not None
[docs] def tiling_kernels(self, lattice: TilingContext): """Discs (CSR, the cell included), rings (CSR) and weights on a tiling.""" key = ("activator_inhibitor", self.r1, self.r2, self.balanced, self.weight) if key not in lattice.cache: t = lattice.tiling n = t.n_cells def matrix(ball): ip, ix = ball return sparse.csr_matrix((np.ones(len(ix), dtype=np.int8), ix, ip), shape=(n, n)) disc = matrix(t.ball(self.r1)) ring = matrix(t.ball(self.r2)) - disc ring.eliminate_zeros() ring.sort_indices() inner = (disc.indptr.astype(np.int64), disc.indices.astype(np.int64)) outer = (ring.indptr.astype(np.int64), ring.indices.astype(np.int64)) w = self.weight if self.balanced: w = np.diff(inner[0]) / np.maximum(1, np.diff(outer[0])) w = float(w[0]) if np.ptp(w) == 0 else w lattice.cache[key] = (inner, outer, w) return lattice.cache[key]
[docs] def score(self, state, lattice) -> np.ndarray: if isinstance(lattice, TilingContext): inner, ring, w = self.tiling_kernels(lattice) t = lattice.tiling return t.counts(state, *inner) - w * t.counts(state, *ring) return kernel_sum( state, self.offsets, self.weights, periodic=lattice.periodic, boundary=lattice.boundary )
[docs] def next_state(self, state, lattice, rng): s = self.score(state, lattice) if self.fraction is not None: return _top_fraction( s + 1e-6 * rng.random(state.shape), round(self.fraction * state.size) ) tol = 1e-9 * (1.0 + self.weight) * len(self.offsets) out = state.copy() out[s > tol] = 1 out[s < -tol] = 0 return out
[docs] def describe(self) -> str: return f"activator_inhibitor({self.r1:g}, {self.r2:g}, w={self.weight:.4g})"
#: Named rules. ``clouds`` is a 3D Moore rule known to turn noise into cave-like #: structures (B13-14,17-19/S13-26). NAMED_RULES = { "majority": lambda: MajorityRule(twist=False), "anneal": lambda: MajorityRule(twist=True), "life": lambda: LifeRule.parse("B3/S23"), "clouds": lambda: LifeRule.parse("B13-14,17-19/S13-26"), }
[docs] def make_rule(rule, *, fraction: float | None = None) -> Rule: """A rule from a name (``majority``, ``anneal``, ``conserved``, ``life``, ``clouds``), a ``B.../S...`` string, or a :class:`Rule`.""" if isinstance(rule, Rule): return rule text = str(rule).strip() if text.lower() == "conserved": if fraction is None: raise ValueError("the 'conserved' rule needs the volume fraction") return ConservedMajorityRule(fraction) if text.lower() in NAMED_RULES: return NAMED_RULES[text.lower()]() return LifeRule.parse(text)