L-системы: рекурсивные грамматики, которыми выращивают растения

Что такое L-система

L-система (система Линденмайера) — формальная грамматика, которую в 1968 году придумал венгерский биолог Aristid Lindenmayer не для программирования, а чтобы математически описать, как растут нитчатые водоросли. Идея проста: есть строка символов (алфавит), стартовая строка (аксиома) и набор правил, по которым каждый символ заменяется на новую подстроку. Применяя правила к результату снова и снова, получаем всё более сложную и детализированную строку.

Сама по себе строка — просто текст. Чтобы превратить её в картинку, используют «черепашью графику» (turtle graphics): курсор-черепашка читает символы один за другим и либо рисует отрезок, либо поворачивает, либо запоминает текущее положение, чтобы потом к нему вернуться — так рождаются ветвления.

Где это используется в играх

• Деревья и растительность — от одиночных декоративных кустов до целых процедурных лесов, где каждое дерево уникально, но выглядит правдоподобно.
• Корневые и сосудистые системы — трещины на камне, молнии, реки, разветвлённые пещерные ходы описываются той же логикой ветвления.
• Планировка улиц и городов — некоторые генераторы городских кварталов строят уличную сеть по тем же принципам рекурсивного ветвления.

Как это работает изнутри

Возьмём классический пример «растения» Линденмайера. Аксиома — символ X. Правило переписывания: X → F+[[X]-X]-F[-FX]+X, а символ F дополнительно удлиняется правилом F → FF. После нескольких итераций короткая строка превращается в текст из тысяч символов — и именно длина этой строки определяет, насколько ветвистым получится растение.

Дальше в дело вступает черепашка: F — шаг вперёд с рисованием линии, + и - — поворот на фиксированный угол вправо или влево, [ — «запомнить» текущее положение и направление (сохранить в стек), ] — вернуться к последнему запомненному состоянию. Именно пара скобок создаёт развилку: ветка рисуется, а затем черепашка «телепортируется» обратно к точке ветвления и продолжает рисовать основной ствол.

// 1. Переписывание строки по правилам грамматики
function generate(axiom, rules, iterations):
    result = axiom

    repeat iterations times:
        next = ""
        for symbol in result:
            next += rules[symbol] or symbol
        result = next

    return result

// 2. Интерпретация строки черепашьей графикой
function draw(str, angle, step):
    stack = []
    for symbol in str:
        if symbol == "F":
            moveForwardAndDrawLine(step)
        elif symbol == "+":
            turnRight(angle)
        elif symbol == "-":
            turnLeft(angle)
        elif symbol == "[":
            stack.push(currentPositionAndAngle())
        elif symbol == "]":
            restorePositionAndAngle(stack.pop())

Меняя только угол поворота и число итераций, из одной и той же грамматики получают совершенно разные силуэты — от тонкого хвойного деревца до раскидистого куста. А заменив правила на другие (их существуют десятки готовых наборов), тем же алгоритмом рисуют папоротники, кораллы и даже кривую Коха.