L-системи та turtle graphics

1. Що таке L-система?

Систему Ліндермаєра (L-система) представив у 1968 році біолог Арістід Ліндермаєр для моделювання росту водоростей і рослин клітина за клітиною. Основна ідея оманливо проста: почати з одного символу (аксіоми) і багаторазово замінювати кожен символ рядка на довший рядок за фіксованим набором правил породження. Після кількох ітерацій один символ виростає у рядок довжиною тисячі символів — і якщо інтерпретувати цей рядок як інструкції для малювання, отримуємо впізнавану рослину, сніжинку чи криву.

Магія в тому, що L-системи контекстно-незалежні (у найпростішому варіанті): правило переписування символу не зважає на те, що його оточує, проте сукупний результат все одно відтворює самоподібне розгалуження, яке ми бачимо у справжніх папоротях і деревах, бо саме біологічне зростання здебільшого є повторюваним локальним правилом, застосованим у кожній точці росту.

2. Переписування рядків: аксіома та правила

L-систему визначають три речі: алфавіт символів, аксіома (початковий рядок) та набір правил породження, що зіставляють кожен символ із рядком заміни. Розглянемо найпростіший приклад:

Застосування правил покоління за поколінням:

Довжина рядка точно слідує послідовності Фібоначчі — нагадування, що L-системи, патерни росту і числові послідовності часто є однією й тією самою ідеєю в різному вбранні.

3. Turtle graphics: від рядка до пікселів

Рядок літер — ще не картинка. Turtle graphics (з мови Logo Сеймура Пейперта, 1967) надає значення кожному символу, інтерпретуючи рядок як послідовність команд для уявної черепахи, яка носить позицію (x, y) і кут напрямку:

Прогнати черепаху через цілий переписаний рядок, символ за символом, — і відрізки, які вона малює, окреслюють форму, закодовану в граматиці.

4. Стандартний алфавіт черепахи

Лише два числа контролюють усю візуальну родину: довжина кроку (наскільки далеко рухає кожен F) і кут повороту δ (наскільки різко + та - обертають напрямок). Зміна δ з 20° на 25° може перетворити охайний геометричний патерн на дикий органічний.

5. Розгалуження через стек: [ та ]

Рослини розгалужуються — стебло розділяється на два, кожне з яких може розділитися знову. Одна черепаха може дивитися лише в одному напрямку водночас, тож розгалуження моделюється стеком: [ зберігає поточну позицію та напрямок черепахи, черепаха малює бічну гілку, а ] відновлює збережений стан, щоб основне стебло продовжилося саме там, де зупинилося.

Після 4-5 поколінь це триряткове правило дає впізнавано кущисту силует — доказ того, що більшість візуальної складності рослини не закодована явно, а виникає з короткого правила, застосованого рекурсивно.

6. Класичні приклади

Крива Коха (фрактальна берегова лінія)

Крива дракона

Трикутник Серпінського (arrowhead)

Папороть у стилі Барнслі

7. Псевдокод

Генерація й малювання L-системи у двох чітких фазах:

// Фаза 1: переписування рядка
function rewrite(axiom, rules, generations):
  s = axiom
  for g in range(generations):
    s = join(rules[c] or c for c in s)
  return s

// Фаза 2: інтерпретація черепахою
function drawTurtle(str, stepLength, angleDeg):
  x, y, heading = 0, 0, -90  // старт напрямом вгору
  stack = []

  for ch in str:
    if ch in "FG":
      nx = x + cos(heading) * stepLength
      ny = y + sin(heading) * stepLength
      drawLine(x, y, nx, ny)
      x, y = nx, ny
    elif ch == "f":
      x += cos(heading) * stepLength
      y += sin(heading) * stepLength
    elif ch == "+":
      heading += angleDeg
    elif ch == "-":
      heading -= angleDeg
    elif ch == "[":
      stack.push({x, y, heading})
    elif ch == "]":
      { x, y, heading } = stack.pop()

Зверніть увагу на розділення відповідальностей: rewrite нічого не знає про малювання, а drawTurtle нічого не знає про правила граматики. Той самий інтерпретатор черепахи малює криву Коха, папороть чи криву дракона — змінюється лише аксіома, правила та кут.