3D-клітинні автомати — воксельне життя та об'ємні правила

1. Кубічна ґратка та 3D-околи

3D-клітинний автомат замінює 2D-сітку клітин на кубічну ґратку вокселів, кожен з яких має дискретний стан (зазвичай двійковий: живий або мертвий). На кожному поколінні всі воксели оновлюються одночасно на основі станів вокселів, що їх оточують — локальне правило, застосоване однаково скрізь, точнісінько як у 2D, лише з однією додатковою віссю сусідів для підсумовування.

Дві стандартні форми околу узагальнюються напряму з їхніх 2D-аналогів:

• Окіл фон Неймана (3D): 6 сусідів, дотичних гранями (±x, ±y, ±z). Компактний і обчислювально дешевий, але дає автомати із сильною симетрією вздовж осей.
• Окіл Мура (3D): усі 26 навколишніх вокселів у кубі 3×3×3 без центру (3³ − 1 = 26). Це прямий аналог 8-сусіднього околу Мура з гри «Життя» Конвея, і саме цей окіл використовує більшість популярних правил «3D Life».

Стрибок від 8 до 26 сусідів — найважливіший факт про 3D-КА: кількість живих сусідів тепер може становити від 0 до 26 замість 0–8, тож пороги народження/виживання потрібно переналаштувати — правила, скопійовані дослівно з 2D (як-от B3/S23), дають ґратку, яка або назавжди порожня, або майже миттєво заповнюється суцільно, адже поріг народження у 3 сусіди задовольнити у просторі з 26 сусідами занадто легко.

2. Нотація правил: народження/виживання у 3D

Правила 3D-КА записуються тією самою нотацією B/S (birth/survival — народження/виживання), що й для 2D life-подібних автоматів, поширеною на діапазон 0–26 можливих кількостей сусідів:

Оскільки простір кількостей сусідів набагато більший, ніж у 2D, якісна поведінка 3D-автоматів надзвичайно чутлива до найменших змін у порогах B/S. Невеликі набори народження й вузькі смуги виживання (як 4555) зазвичай дають стабільні, коралоподібні або кристалічні структури, що припиняють ріст, досягнувши стійкої форми. Ширші смуги виживання схильні призводити до неконтрольованого росту, що заповнює всю ґратку, а вузькі — до повного вимирання: «цікава» область простору правил являє собою тонку смугу, дуже подібну до межі краю хаосу Вольфрама для елементарних КА.

Діапазон околу також часто узагальнюють поза межі безпосереднього куба 3×3×3. Окіл Мура радіуса r включає кожен воксель у межах чебишовської відстані r, даючи (2r + 1)³ − 1 сусідів — радіус 2 вже дає 124 сусіди, чого достатньо для моделювання набагато плавнішого, органічнішого росту, ніж «блокові» автомати радіуса 1.

3. Відомі 3D-правила: 4555, Amoeba, Pyroclastic

4555 (B5/S45) — стабільний коралоподібний ріст

Відкрите Картером Бейсом у 1980-х під час систематичного пошуку 3D-аналогів «Життя», 4555 — найчастіше цитоване правило 3D-КА. Запущене з невеликого випадкового кластера, воно виростає у стабільні, коралоподібні або кристалічні утворення, що зрештою припиняють розширення — «Клас II» 3D-автомат у термінології Вольфрама, що осідає у статичну або повільно осцилюючу рівновагу замість хаотичного чи необмеженого росту.

Amoeba (B5678/S45678)

Широка смуга виживання (4–8) у парі з широкою смугою народження (5–8) дає блобоподібні маси, що пульсують, випускають псевдоподієподібні виступи та повільно дрейфують — візуально нагадуючи амебоподібні організми, звідси й назва. Оскільки обидві смуги широкі, невеликі локальні флуктуації можуть існувати нескінченно довго, не зникаючи й не вибухаючи, що надає значно динамічнішу, «живішу» поведінку, ніж статичне правило 4555.

Pyroclastic (B45678/S56789+, радіус околу 1)

Назване за схожість із клубами вулканічного попелу, Pyroclastic використовує дуже широкі смуги народження й виживання, породжуючи щільні, вирові об'єми, що швидко розширюються з невеликого зародка, перш ніж осісти у великі, хмароподібні статичні структури. Воно демонструє, що, на відміну від 2D «Життя», де широкі смуги майже завжди означають «усе гине або все заповнюється», додатковий вимір дає широкосмуговим 3D-правилам простір для формування складних внутрішніх порожнин і оболонок замість простих суцільних блоків.

4. Розріджене зберігання: октодерева та хеш-набори

Щільний 3D-булевий масив зі стороною N коштує O(N³) пам'яті — навіть скромна сітка 256³ уже налічує 16,7 мільйона клітин, а більшість станів 3D-КА розріджені: переважна частина ґратки порожня, особливо на початку симуляції або з такими стабільними правилами, як 4555, що ніколи не заповнюють більше тонкої оболонки активних вокселів. У практичних реалізаціях домінують дві структури даних:

• Хеш-набір координат живих клітин: зберігати лише трійки {x,y,z} (упаковані в один 32- або 64-бітний цілочисловий ключ) для живих клітин у Set чи хеш-мапі. Підрахунок сусідів стає 26 хеш-пошуками на живу клітину та її сусідів — ефективно, коли жива популяція становить малу частку обмежувального об'єму; саме цей підхід використовують високопродуктивні реалізації гри «Життя» Конвея, розширені до розріджених представлень у стилі «hashlife».
• Розріджене воксельне октодерево (SVO): рекурсивно поділяє простір на 8 октантів, зберігаючи лише гілки, що містять живі воксели, і згортаючи порожні піддерева в один «порожній» листок. Октодерева проміняють швидкість пошуку на значно кращу масштабованість пам'яті для кластеризованих, просторово когерентних популяцій — та сама структура, яку використовують у трасувальниках променів для вокселів і в движках у стилі Minecraft для зберігання чанків.

5. Від вокселів до поверхонь: marching cubes

Рендеринг живих вокселів як окремих кубів простий і швидкий, але для плавніших, органічніших візуалів — особливо з широкосмуговими правилами на кшталт Amoeba й Pyroclastic — корисно виділити неперервну ізоповерхню з дискретного вокельного поля. Алгоритм marching cubes (Лоренсен і Клайн, 1987) робить саме це:

1. Розглянути кожен блок 2×2×2 кутів вокселя як «куб» і обчислити 8-бітний індекс, що показує, які кути всередині поверхні, а які зовні (живий/мертвий, або вище/нижче порогу густини для автоматів із дробовим станом).
2. Знайти індекс у попередньо обчисленій таблиці 256 можливих конфігурацій трикутників (зведеної до 15 унікальних випадків за симетрією), щоб отримати ребра трикутників, що перетинають цей куб.
3. Інтерполювати позиції вершин уздовж кожного ребра перетину (лінійно або за згладженим полем густини) і згенерувати трикутники.

Для суто двійкового вокельного КА marching cubes на порозі 0.5 дає класичну «блокову, але тріангульовану» поверхню; попереднє згладжування поля станів КА (наприклад, фільтрацією нижніх частот булевої сітки в неперервну густину) дає округлі, «біологічні» оболонки, що часто використовують у генеративно-мистецьких рендерах 3D-КА.

6. JavaScript: функція кроку 3D-КА

Мінімальна реалізація на щільному масиві, що узагальнює функцію кроку 2D гри «Життя» на кубічну ґратку з налаштовуваним рядком правила B/S:

class CellularAutomaton3D {
  constructor(N, birth, survive) {
    this.N = N;                                  // сітка N x N x N
    this.birth = new Set(birth);              // напр. [5] для B5
    this.survive = new Set(survive);          // напр. [4,5] для S45
    this.grid = new Uint8Array(N * N * N);
  }

  idx(x, y, z) { return (x * this.N + y) * this.N + z; }

  countNeighbours(x, y, z) {
    const { N, grid } = this;
    let n = 0;
    for (let dx = -1; dx <= 1; dx++)
      for (let dy = -1; dy <= 1; dy++)
        for (let dz = -1; dz <= 1; dz++) {
          if (dx === 0 && dy === 0 && dz === 0) continue;
          const nx = (x + dx + N) % N;   // тороїдальне загортання
          const ny = (y + dy + N) % N;
          const nz = (z + dz + N) % N;
          n += grid[this.idx(nx, ny, nz)];
        }
    return n;
  }

  step() {
    const { N, grid, birth, survive } = this;
    const next = new Uint8Array(N * N * N);
    for (let x = 0; x < N; x++)
      for (let y = 0; y < N; y++)
        for (let z = 0; z < N; z++) {
          const i = this.idx(x, y, z);
          const n = this.countNeighbours(x, y, z);
          const alive = grid[i] === 1;
          next[i] = (alive ? survive.has(n) : birth.has(n)) ? 1 : 0;
        }
    this.grid = next;
  }
}

// 4555: B5/S45
const ca = new CellularAutomaton3D(32, [5], [4, 5]);

Ця реалізація на щільному масиві добре працює до кількох десятків вокселів на вісь; далі варто перейти на розріджене представлення через хеш-набір із Розділу 4, щоб step() відвідував лише живі клітини та їхніх сусідів, а не весь об'єм N³.

7. Рендеринг через інстансинг Three.js

Рендерити тисячі незалежних кубічних мешів при 60 fps непрактично з одним draw call на воксель — стандартна техніка — інстансований рендеринг, коли єдина геометрія куба й матеріал малюються один раз на живий воксель за допомогою буфера GPU-інстансів, звужуючи всю ґратку до одного виклику малювання:

const geometry = new THREE.BoxGeometry(0.9, 0.9, 0.9);
const material = new THREE.MeshStandardMaterial({ color: 0x0ea5e9 });
const maxVoxels = N * N * N;
const mesh = new THREE.InstancedMesh(geometry, material, maxVoxels);

const dummy = new THREE.Object3D();

function syncInstances(ca) {
  let count = 0;
  const half = ca.N / 2;
  for (let x = 0; x < ca.N; x++)
    for (let y = 0; y < ca.N; y++)
      for (let z = 0; z < ca.N; z++)
        if (ca.grid[ca.idx(x, y, z)]) {
          dummy.position.set(x - half, y - half, z - half);
          dummy.updateMatrix();
          mesh.setMatrixAt(count++, dummy.matrix);
        }
  mesh.count = count;                          // малювати лише живі воксели
  mesh.instanceMatrix.needsUpdate = true;
}

Виклик ca.step(), а потім syncInstances(ca) за таймером (або з обмеженням до кількох кадрів анімації, оскільки ріст на основі правил добре читається при 5–10 поколіннях за секунду) дає живу, обертальну візуалізацію воксельного життя. Для ґраток на сотні вокселів на вісь варто перенести сам крок підрахунку сусідів на GPU у вигляді compute-подібного фрагментного шейдера, що працює з 3D-текстурою, адже InstancedMesh сам по собі розв'язує лише половину проблеми продуктивності — рендеринг.

8. Застосування: ріст, рельєф, мистецтво

Процедурний ріст і біологія

3D-КА природно підходять для моделювання дифузійно-обмеженої агрегації, росту коралів і мінералів, а також проліферації пухлин: клітини займають або звільняють воксели на основі локальної густини поживних речовин чи сусідів, породжуючи розгалужені або оболонкоподібні структури без жодного явного геометричного правила — форма є емерджентним наслідком самого лише локального оновлення, так само як у 2D-системах реакції-дифузії, але з додатковим просторовим ступенем свободи для розвитку росту.

Процедурний рельєф і печери

Воксельні ігрові движки часто засівають 3D-сітку випадковим шумом і виконують кілька проходів КА зі згладжувальним правилом (приблизно «твердий, якщо ≥13 з 26 сусідів тверді»), щоб перетворити різкий шум на плавні, правдоподібні печерні системи й нависання — пряме 3D-розширення 2D-техніки клітинного автомата «народження 5 / виживання 4», яку давно використовують для генерації підземель у 2D-роглайках.

Генеративне мистецтво та візуалізація музики

Оскільки стани 3D-КА можна рендерити як напівпрозорі, кольорові воксельні поля або перетворювати на ізоповерхню через marching cubes, вони є популярним субстратом для генеративного мистецтва: відображення кількості сусідів або «віку з моменту народження» на відтінок і прозорість дає скляні, коралоподібні або кристалічні рендери, а керування порогами народження/виживання від аудіосигналу перетворює автомат на візуалізатор музики в реальному часі на основі правил.