L-системи та ріст рослин — граматики Ліндемаєра, черепашача графіка та 3D-гілки

1. Граматика — аксіома, алфавіт і правила породження

L-система — це формальна граматика G = (V, ω, P), де:

• V — алфавіт: множина символів. Символи, що мають правило породження, називаються змінними; решта — константи.
• ω — аксіома (початковий рядок): вихідний рядок.
• P — породження: відображення кожної змінної на рядок-заміну.

На кожному поколінні усі символи рядка переписуються одночасно — саме ця паралельна заміна відрізняє L-системи від стандартних граматик Хомського і природно породжує самоподібну структуру.

2. Інтерпретація черепашачої графіки

Рядок L-системи набуває візуального змісту, якщо інтерпретувати кожен символ як команду черепашки. Черепашка має позицію (x, y), напрямок θ та необов'язковий стек для розгалуження.

Операції зі стеком [ та ] якраз і створюють гілки: покласти стан біля основи гілки, заглибитися в гілку, повернутися до основи — фундаментальний прийом усіх L-систем дерев і кущів.

3. Класичні L-системи

4. JavaScript-рушій — розгортання та малювання

Рушій має дві фази: розгортання рядка (згенерувати рядок L-системи до n ітерацій) та інтерпретацію черепашки (пройти рядком і намалювати відрізки на Canvas 2D).

// ── 1. Розгортання рядка L-системи ──────────────────────────────────
function expand(axiom, rules, generations) {
  let str = axiom;
  for (let g = 0; g < generations; g++) {
    // Будуємо вивід символ за символом — уникаємо повторної конкатенації рядків
    const parts = [];
    for (const ch of str) {
      parts.push(rules[ch] ?? ch);  // замінити, якщо є правило, інакше лишити
    }
    str = parts.join('');
  }
  return str;
}

// ── 2. Інтерпретація черепашки на Canvas 2D ─────────────────────────
function draw(ctx, str, x0, y0, angle0, step, delta) {
  const stack = [];
  let x = x0, y = y0, angle = angle0;
  const RAD = Math.PI / 180;

  ctx.beginPath();
  ctx.moveTo(x, y);

  for (const ch of str) {
    switch (ch) {
      case 'F':
        x += step * Math.cos(angle * RAD);
        y -= step * Math.sin(angle * RAD);
        ctx.lineTo(x, y);
        break;
      case 'f':
        x += step * Math.cos(angle * RAD);
        y -= step * Math.sin(angle * RAD);
        ctx.moveTo(x, y);
        break;
      case '+': angle += delta; break;
      case '-': angle -= delta; break;
      case '[': stack.push({ x, y, angle }); break;
      case ']':
        ({ x, y, angle } = stack.pop());
        ctx.moveTo(x, y);
        break;
    }
  }
  ctx.stroke();
}

Приклад використання — фрактальна рослина на 6 поколіннях

const rules = {
  X: 'F+[[X]-X]-F[-FX]+X',
  F: 'FF'
};
const str = expand('X', rules, 6);

const ctx = canvas.getContext('2d');
ctx.strokeStyle = '#22c55e';
ctx.lineWidth   = 0.7;
draw(ctx, str,
  canvas.width / 2,  // початкова x
  canvas.height - 20, // початкова y (внизу по центру)
  90,                 // початковий кут (угору)
  5,                  // довжина кроку (зменшується з поколінням)
  25                  // кут дельта
);

5. Стохастичні та контекстно-залежні правила

Стохастичні L-системи

Замініть детерміноване правило A → xyz набором альтернативних породжень, кожне з імовірністю, що в сумі дає 1. Двократний запуск тієї самої граматики дає різні рослини — це необхідно, щоб уникнути штучної одноманітності детермінованих систем.

// Стохастична L-система — F має дві продукції, що обираються випадково
const stochastic = {
  F: [
    { weight: 0.33, result: 'F[+F]F[-F]F' },
    { weight: 0.33, result: 'F[+F]F'       },
    { weight: 0.34, result: 'F[-F]F'       },
  ]
};

function expandStochastic(axiom, rules, gens) {
  let str = axiom;
  for (let g = 0; g < gens; g++) {
    const parts = [];
    for (const ch of str) {
      if (rules[ch]) {
        const r = Math.random();
        let cumW = 0;
        for (const prod of rules[ch]) {
          cumW += prod.weight;
          if (r < cumW) { parts.push(prod.result); break; }
        }
      } else {
        parts.push(ch);
      }
    }
    str = parts.join('');
  }
  return str;
}

Контекстно-залежні правила

Правило може зумовлювати заміну лівим чи правим сусідом: A<B>C → D означає «замінити B на D, коли йому передує A і за ним іде C». Це моделює міжклітинну хімічну сигналізацію — початкову біологічну мотивацію роботи Ліндемаєра.

6. 3D L-системи у Three.js

Для 3D-розгалуження черепашка несе матрицю обертання 3×3 (вектори напрямку H, лівий L, верхній U), а не один кут напрямку. 3D-символи &, ^, \, / застосовують матриці обертання навколо кожної осі.

// 3D-черепашка — система координат напрямок (H), лівий (L), верхній (U)
import * as THREE from 'three';

class Turtle3D {
  constructor() {
    this.pos   = new THREE.Vector3();
    this.H     = new THREE.Vector3(0, 1, 0);  // напрямок: угору
    this.L     = new THREE.Vector3(-1, 0, 0); // лівий
    this.U     = new THREE.Vector3(0, 0, 1);  // верхній вектор
    this.stack = [];
    this.lines = [];  // Масив пар Vector3 [від, до]
  }

  rotate(axis, angleRad) {
    const q = new THREE.Quaternion().setFromAxisAngle(axis, angleRad);
    this.H.applyQuaternion(q);
    this.L.applyQuaternion(q);
    this.U.applyQuaternion(q);
  }

  forward(step) {
    const from = this.pos.clone();
    this.pos.addScaledVector(this.H, step);
    this.lines.push([from, this.pos.clone()]);
  }

  interpret(str, step, delta) {
    const r = delta * Math.PI / 180;
    for (const ch of str) {
      switch (ch) {
        case 'F': this.forward(step); break;
        case '+': this.rotate(this.U,  r); break;
        case '-': this.rotate(this.U, -r); break;
        case '&': this.rotate(this.L,  r); break;
        case '^': this.rotate(this.L, -r); break;
        case '/': this.rotate(this.H,  r); break;
        case '\\': this.rotate(this.H, -r); break;
        case '[': this.stack.push({
          pos: this.pos.clone(),
          H: this.H.clone(), L: this.L.clone(), U: this.U.clone()
        }); break;
        case ']': {
          const s = this.stack.pop();
          this.pos.copy(s.pos); this.H.copy(s.H);
          this.L.copy(s.L); this.U.copy(s.U);
        } break;
      }
    }
  }
}

Побудуйте об'єкт Three.js LineSegments зі зібраних пар ліній:

function buildMesh(lines, scene) {
  const positions = [];
  for (const [a, b] of lines) {
    positions.push(a.x, a.y, a.z, b.x, b.y, b.z);
  }
  const geo = new THREE.BufferGeometry();
  geo.setAttribute('position', new THREE.Float32BufferAttribute(positions, 3));
  const mat = new THREE.LineBasicMaterial({ color: 0x22c55e, linewidth: 1 });
  scene.add(new THREE.LineSegments(geo, mat));
}

7. Відкриті L-системи та параметричні розширення

Описані досі версії L-систем є закритими: граматика не взаємодіє з середовищем. Книга Прусінкевича та Ліндемаєра 1990 року The Algorithmic Beauty of Plants розширює формалізм у кількох напрямах:

• Параметричні L-системи: символи несуть числові параметри, напр. F(l, w) — крок уперед довжиною l, ширина лінії w. Правила можуть включати арифметику над параметрами, тож гілки природно звужуються: F(l, w) → F(l*0.8, w*0.7)[+F(l*0.6, w*0.5)]F(l*0.8, w*0.7).
• Відкриті L-системи: модель рослини обмінюється інформацією із симульованим середовищем. Симуляція світлового поля може «обділяти» затінені гілки, через що вони ростуть коротшими або перестають рости — реалістичне уникання тіні.
• Диференціальні L-системи: замість дискретних кроків поколінь переписування є неперервним, моделюючи безперервний ріст у часі. Використовуються у статтях про морфогенез і формування судинних візерунків.
• Картографічні L-системи (map L-systems): кодують 2D клітинні сітки, де суміжність визначає, які правила спрацьовують — початкова мотивація контекстно-залежних правил.