L-Системи та Рослинний Ритмізм

Граматика росту

У 1968 році ботанік Арістід Ліндемаєр розробив формалізм з переписуванням рядків для моделювання поділу клітин водоростей. L-система – це формальна граматика G = (V, ω, P): алфавіт V символів, аксіома ω (початкова ланцюг) та набір правил генерації P, які відображають кожен символ у ланцюг заміни. Що відрізняє L-системи від стандартної граматики Шмідта, так це те, що кожен символ у ланцюгу одночасно переписується на кожному поколінні – паралельне переписування, а не послідовна заміна, і саме це створює самосхожі та розгалужену структуру.

Algae (Lindenmayer's original 1968 example):
  Variables: A B      Axiom: A      Rules: A → AB, B → A

  Gen 0: A
  Gen 1: AB
  Gen 2: ABA
  Gen 3: ABAAB
  Gen 4: ABAABABA        // length grows as Fibonacci numbers: 1,2,3,5,8,13…

Графічні виводи черепашок: надання рядку символів форми

Система L складається з рядка лише тоді, коли кожен символ інтерпретується як команда для черепашки, яка тримає позицію, кут повороту та стек для розгалуження: F – рух вперед із малювання сегменту, +/− – поворот ліворуч/праворуч на фіксований кут δ і [/] – скидання та відновлення стану черепашки. Пара дужок створює гілку: скидання в основній точці, малювання бічного відростка, повернення до точно того місця, де почалася гілка.

Fractal Plant (δ=25°):  axiom X, rules  X → F+[[X]−X]−F[−FX]+X,  F → FF
Koch curve (δ=60°):     axiom F, rule   F → F+F−−F+F      // D = log4/log3 ≈ 1.262
Sierpiński (δ=60°):     F−G−G, F→F−G+F+G−F, G→GG          // D = log3/log2 ≈ 1.585

JavaScript: розгортання та малювання

Двигун має два незалежні етапи: розгортання аксиоми на n поколінь, а потім ходити по результаточному рядку один раз на Canvas 2D.

функція розгортання(аксіома, правила, покоління) {

нехай рядок = аксіома;

для покоління від 0 до покоління, якщо покоління < n:

рядок = правила[символу] ?? символ; // Замінюємо символи відповідно до правил

}

повернути рядок;

}

функція малювання(контекст, рядок, x, y, кут, крок, дельта) {

нехай стек = [];

контекст.beginPath(); контекст.moveTo(x, y);

для кожного символу в рядку:

якщо символ == 'F': x += крок*Math.cos(кут); y -= крок*Math.sin(кут); контекст.lineTo(x, y);

інакше якщо символ == '+': кут += дельта;

інакше якщо символ == '-': кут -= дельта;

інакше якщо символ == '[': стек.push({ x, y, кут });

інакше якщо символ == ']': { x, y, кут } = стек.pop();

}

контекст.stroke();

Пояснення: правило, наприклад, F → FF приблизно подвоює довжину рядка кожного покоління — 10-е покоління вже виробляє 1024 сегменти, 20-е покоління понад мільйон. Після кількох поколінь набагато дешевше пропустити матеріалізацію повної строки та інтерпретувати граматику рекурсивно з лічильником глибини, створюючи ідентичне малювання в постійному просторі стека.

function expand(axiom, rules, gens) {
  let str = axiom;
  for (let g = 0; g < gens; g++)
    str = [...str].map(ch => rules[ch] ?? ch).join('');
  return str;
}

function draw(ctx, str, x, y, angle, step, delta) {
  const stack = [];
  ctx.beginPath(); ctx.moveTo(x, y);
  for (const ch of str) {
    if (ch === 'F') { x += step*Math.cos(angle); y -= step*Math.sin(angle); ctx.lineTo(x, y); }
    else if (ch === '+') angle += delta;
    else if (ch === '-') angle -= delta;
    else if (ch === '[') stack.push({ x, y, angle });
    else if (ch === ']') ({ x, y, angle } = stack.pop());
  }
  ctx.stroke();
}

Стохастичні правила та 3D черепашки

Детерміноване правило може бути замінене декількома альтернативними продукціями, кожна з ймовірністю, яка сумується до 1 – повторне виконання тієї ж граматики призводить до двох різних рослин, що є важливим для запобігання штучній одноманітності чисто детермінованої системи. У 3D, черепашка несе повний орієнтир повороту праворуч/ліворуч/вгору замість одного кута, а символи & ^ \ / застосовуються матриці обертання навколо осей цього кадру, дозволяючи гілці звиватись та нахилятись у просторі перед тим, як F зобов’язується сегмент до буфера Three.js LineSegments.

За межами закритих граней

Prusinkiewicz і Lindenmayer у своїй книзі 1990 року The Algorithmic Beauty of Plants значно розширює базову модель: параметричні L-системи прикріплюють числа до символів (F(l,w)), щоб гілки могли звужуватися з кожним поколінням; відкриті L-системи обмінюються інформацією з імітованим середовищем, дозволяючи симуляції світлового поля виснажувати затінені гілки та створювати реалістичне уникнення тіні; контекстно-чутливі правила визначають заміну на основі сусідніх символів, моделюючи міжклітинний хімічний сигналізування, що спонукало до початкової біології Lindenmayer.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.