Глава 44. L-системы

Это изображение получено с помощью программы XaoS, которую мы очень рекомендуем установить (из пакета xaos, если у вас Linux) и попробовать в работе. Есть и другая хорошая программа, Fractint, которая так же позволяет изучать и рассматривать фрактальные множества, в том числе построенные с помощью L-систем. Мы ещё вернёмся к этому изображению в главе 48. «Множество Мандельброта».

Фрактальные множества — сравнительно недавно открытые объекты. Черты фрактальных множеств несут в себе многие природные объекты: растения, облака, горные вершины, дельты рек (см. рисунок 44.2. «Дельта реки Лена» с сайта http://ru.wikipedia.org), галактики. Да и сама вселенная в некотором смысле фрактальна.

Полюбоваться на изображения фрактальных множеств можно на сайте lenta.ru или в этом блоге.

Рисунок 44.2. Дельта реки Лена

Фракталы возникают и в математических моделях физических процессов. На рисунке 44.3. «Стохастическая паутина» показана фазовая картина стандартного отображения Чирикова — модели маятника с периодически колеблющейся точкой подвеса. Координаты чёрных точек имеют смысл угла отклонения маятника и его угловой скорости, взятые через промежутки времени, равные периоду колебаний подвеса. Координаты $\left(x^{\prime },y^{\prime }\right)$ следующей точки получаются из координат $\left(x,y\right)$ предыдущей по очень простому правилу: $$\begin{array}{l}{x}^{\prime }=x+y\hfill \\ y^{\prime }=y+\sin x\hfill \end{array}$$ При подходящем выборе начальной точки на плоскости последовательность точек, порождённая этим правилом, заполняет паутину с дырками (островами устойчивости). Каждый остров окружён несколькими островами поменьше, те в свою очередь тоже окружены островами, и так до бесконечности (конечно, самые мелкие острова, чей размер сравним с размером точек, мы не сможем увидеть на рисунке).

Рисунок 44.3. Стохастическая паутина

Скобочные L-системы и деревья

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

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

Такое свойство дерева можно было бы взять в качестве основы для модели, однако оно допускает деревья с бесконечным количеством веток (чего в природе не встречается). Глубина дерева (то есть максимальная длина последовательности «ствол, первичная ветка, вторичная ветка, третичная ветка, …, самая последняя ветка») должна быть конечной.

Поэтому определим дерево глубины $n$ (дерево $n$-ого порядка). Деревом $n$-ого порядка будем называть ствол с растущими на нём ветками, которые является деревьями $\left(n-1\right)$-го порядка. Чтобы такое определение не привело к деревьям с отрицательной глубиной, скажем, что дерево нулевого порядка — это голый ствол.

Дерево неудобно рисовать одним росчерком карандаша. Оно является не ломаной, а, скорее, набором отрезков. Черепаха позволяет рисовать наборы отрезков, не связанные в ломаную, и для такого рисования имеется два средства. Во-первых, это возможность поднимать и опускать карандаш и сдвигаться вперёд с поднятым карандашом. Во-вторых, это возможность запоминать и восстанавливать состояние. Мы попробуем второй способ.

Дерево в нулевом поколении представляет собой единственную почку. В следующем, первом поколении из почки вырастает нижняя половинка побега, затем почка для будущей ветки, наклонённой влево на $20°$, затем верхняя половинка побега с двумя почками, наклонёнными влево и вправо на те же $20°$. В следующих поколениях старые половинки побега удлиняются в два раза, а с почками происходят те же самые метаморфозы, что и при переходе от нулевого к первому поколению. На следующей иллюстрации изображены три первых поколения дерева:

поколения	изображение
0, 1, 2

Здесь почки показаны как короткие красные отрезки только для пояснения, в итоговом изображении они не появятся. Чтобы компенсировать рост размеров изображения, длины отрезков на каждом шаге сокращаются вдвое.

Если переложить всё сказанное на язык L-систем, получим следующее описание:

аксиома	правила	интерпретация
X	F$\to$FF X$\to$F[+X]F[-X]+X	F$\to$FORWARD 1 +$\to$ROTATE 20 -$\to$ROTATE -20 [$\to$SAVE ]$\to$RESTORE

Здесь требуется пояснение. Символы X и F обозначают соответственно почку и половинку побега. Хотя почки невидимы (для символа X отсутствует интерпретация), они отмечают место для будущих побегов. Предшествующие им символы + и - показывают, что всё, что из них вырастет, будет повёрнуто. Фразы [+X] и [-X] в правиле X$\to$F[+X]F[-X]+X означают, что после рисования побега, выросшего на месте почки, состояние черепахи будет восстановлено. Правило F$\to$FF отвечает за удвоение длины побега.

Приводим изображения первых восьми поколений дерева, полученные такой L-системой:

поколения	изображение
0, 1, 2, 3
4, 5, 6, 7

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

Теперь разберём пример построения более реалистичного дерева с помощью L-системы. Отрезки, образующие дерево, разделим на два типа. Отрезок типа X — это ветвь, на которой в следующем поколении вырастут две ветви потоньше, покороче и светлее, и, кроме того, наклонённые вправо и влево на случайный угол, равномерно распределённый в пределах от $0°$ до $45°$. Отрезок типа F — это ветвь, от которой уже ответвились две ветви. Ветви типа X назовём терминальными (конечными), а ветви типа F — нетерминальными. Дерево в нулевом поколении представляет собой одну терминальную ветвь.

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

Теперь займёмся правилом L-системы. В каждом цикле развития дерева каждая терминальная ветвь превращается в нетерминальную, от которой что-то ответвилось: X$\to$F[…]. Эту ответвившуюся растительность мы заключаем в скобки, в которые первым делом помещает символ @, ответственный за осветление, утоньшение и укорачивание ветвей. Затем рисуем правую ветвь: [-X]. Скобки здесь нужны для того, чтобы запомнить положение и направление черепахи; ведь предстоит поворот на случайный угол. Рисуем левую ветвь: +X.

Итак, мы приходим к следующему описанию L-системы:

аксиома	правило	интерпретация
X	X$\to$F[@[-X]+X]	F$\to$FORWARD 1 X$\to$FORWARD 1 +$\to$ROTATE RANDOM 45 -$\to$ROTATE -RANDOM 45 [$\to$SAVE ]$\to$RESTORE @$\to$…

Несколько последующих циклов развития дерева приведены на рисунке:

поколения	изображение
0
1
2
3
4
5
6
7
8
9
10
11
12
13

Другой, рекурсивный подход к построению такого дерева описан в нашем пособии METAPOST. Краткий курс в разделе «Макрокоманды».

Готовая программа		Идеи реализации