L-системы

Как вырастить куст из строчки текста? Возьмите короткое слово и правила замены букв. На каждом шаге все буквы заменяются одновременно, слово разрастается, а потом его читают как команды черепахе с пером: шаг вперёд, поворот, запомнить место, вернуться. Дюжина символов в правилах — и на экране кривая, заполняющая квадрат, снежинка бесконечной длины или раскидистый куст.

Как это устроено

У системы есть аксиома — начальное слово, правила и угол. Буквы F, G, A и B — шаг вперёд с пером, f — шаг без пера, + и − — поворот на угол, [ и ] — запомнить положение черепахи и вернуться к нему: так растут ветки. Остальные буквы, вроде X и Y, ничего не рисуют и только управляют ростом.

Слово никогда не выписывается целиком: черепаха обходит дерево подстановок рекурсивно, а сколько шагов даст каждая буква в каждом поколении, подсчитано заранее. Поэтому «Поколения» ограничены точно — не больше 400 тысяч отрезков, а 0 означает поколение, подобранное для системы. Если угол делит 360° нацело, направления берутся из таблицы, и кривая не сползает с решётки. «Скругление» заменяет углы дугами. «Толщина» у заполняющих кривых — доля шага, чтобы соседние ходы не слипались, а у растений ветви с каждым ярусом становятся тоньше.

Немного истории

Венгерский биолог Аристид Линденмайер придумал эти системы в 1968 году, чтобы описать рост нитчатых водорослей: клетки нити делятся одновременно — так же, как разом заменяются все буквы слова. Черепаха с пером пришла из учебного языка Logo, а соединил её с L-системами Пшемыслав Прусинкевич. Их общая с Линденмайером книга «Алгоритмическая красота растений» вышла в 1990 году, через год после смерти соавтора. Сами кривые старше. В 1890 году Джузеппе Пеано построил непрерывную кривую, проходящую через все точки квадрата, — одними формулами, без рисунка; через год Давид Гильберт дал наглядную конструкцию. В 1904-м Хельге фон Кох предъявил снежинку — кривую без касательной ни в одной точке. C-кривую Поль Леви описал в 1938 году, а кривую, прозванную flowsnake, Билл Госпер нашёл в 1970-х. Дракона в 1960-х нашли физики NASA Джон Хайтуэй, Брюс Бэнкс и Уильям Хартер; Мартин Гарднер рассказал о нём в 1967 году, а Майкл Крайтон украсил им главы «Парка юрского периода».

Что покрутить

• «Поколения» 1, 2, 3… — видно, как каждое поколение складывается из уменьшенных копий предыдущего.
• «Кривая Госпера» и «Раскраска» «вдоль пути»: цвет ложится пятнами, потому что заполняющая кривая обходит область кусок за куском.
• «Сдвиг угла» ломает решётку: уже 6° рассыпают дракона на облако курчавых островков, а у растений меняют размах ветвей.
• Кривая с «Толщиной» около 0,5 и эффект «Рельеф» сверху — выпуклый лабиринт, будто отчеканенный в металле.