Понятие L-систем появилось в 1968 году благодаря Аристриду Линденмайеру, датскому математику и биологу [3]. При этом вначале их предполагалось использовать лишь при изучении формальных языков и в некоторых биологических моделях селекции. Однако выяснилось, что на основе L-систем могут быть построены многие известные фракталы, такие как ковер Серпинского, снежинка Коха, и другие [1, 2, 4-6].
Несколько позже L-системы стали использовать для генерации растительных форм, таких как листья, кусты и деревья (в большинстве компьютерных игр растения ландшафтов генерируются именно L-системами).
При графической реализации L-систем используется turtle-графика — так называемая "черепашья" графика. Правила в этой графике весьма просты, и заключаются в следующем. Точка (черепашка) дискретными шагами движется по экрану и прочерчивает за собой след, при необходимости возможно перемещение точки без оставления следа. В каждый момент времени координаты и состояние точки определяется тремя параметрами на плоскости: координаты точки и направление, в котором будет двигаться точка. Точка может распознавать и выполнять некоторую последовательность команд, состоящую из последовательностей символов (или групп символов в более сложном случае), читающихся слева направо. Ниже в таблице 1 приведены наиболее часто используемые символы последовательности и их назначение.
Символ последовательности | Назначение (интерпретация) |
F | Перемещение на 1 шаг вперед с прорисовкой следа. |
b | Перемещение на 1 шаг вперед без прорисовки следа. |
[ | Открыть ветвь. |
] | Закрыть ветвь. |
+ | Увеличение угла на указанную величину. |
– | Уменьшение угла на указанную величину. |
Поэтому фактически, любая L-система состоит из алфавита, слова инициализации (аксиомы) и набора порождающих правил. Порождающие правила указывают, как необходимо преобразовать аксиому при переходе от уровня к уровню (переходе между итерациями). Рассмотрим простой пример:
Аксиома: F
Порождающее правило: FbF+
После нескольких применений правила из аксиомы получаются, в зависимости от номера итерации, следующие строки:
1. FbF+
2. FbF+bFbF++
3. FbF+bFbF++bFbF+bFbF+++
4. FbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF++++
5. FbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF++++bFbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF+++++
Рекурсивная природа L-систем позволяет строить на основе них геометрические фракталы. Так, при количестве итераций, больших 8, на основе приведенной аксиомы и порождающего правила получим вполне определенное изображение фрактала (следует принять приращение угла, равное 90 градусов).
В приведенной таблице символы "[" и "]" выступают в качестве команд ветвления, — они используются при построении растений и деревьев. При этом, если в последовательности символов встречается символ "[", то запоминается положение и направление движения точки (тройка чисел (x,y,a)), к этим параметрам будет осуществлен возврат позднее. Обычно для хранения таких троек чисел при программной реализации алгоритма используется стек: новые значения параметров записываются в конец стека. В случае, когда ветвь закрывается (встречается символ "]"), тройкам чисел (x,y,a) присваиваются значения, считанные с конца стека, после чего эти значения из стека удаляются.
Часто в L-системы вводят дополнительные переменные (X, Y, Z и другие), которые призваны облегчить построение системы. Также могут использоваться не только отдельные символы, но и их группы, а также цифры и числа. Числа, например, могут использоваться для задания конкретных цветов при графическом построении.
Рассмотрим теперь некоторые примеры аксиом и порождающих правил для L-системы, задаваемой на основе символов из таблицы 1, а также результаты построения, получаемые на основе этих правил. Для удобства представим аксиомы и порождающие правила в виде таблицы 2 (все правила получены автором работы). Результаты построения приведены ниже на рис. 1-15, и выполнены в разрабатываемой автором программе (цифры в правилах отвечают за цвет рисуемого участка). Отмечу, что для рис. 9 получаются замкнутые фрактальные изображения при четном количестве итераций, а для рис. 10 — при нечетном. Рис. 12 и 15 представлены в работе в уменьшенном масштабе, изображения в полном разрешении представлены в [7, 8].
Аксиома и порождающее правило | Приращение угла | Вложенность | Начальный угол | Рисунок |
Аксиома: F+F-FbF Правило: b-3Fb4F-b | 11 | 12 | -90 | 1 (а) |
17 | 1(б) | |||
Аксиома: FF+F-FF-F+FF Правило: [3F]-2F++2F-[3F] | 25 | 4 | -90 | 2 |
Аксиома: F+F-FF Правило: -F+[FF++FF++FF]-F+ | 12 | 4 | -60 | 3 |
Аксиома: F+F-[F+Fb+F]-[F-F] Правило: -2F-[-1Fb+bF]+[bb4Fb-b2F+4F-bb2F]+[bF+b3FbF]-3bF+ | 30 | 3 | 0 | 4 |
Аксиома: F-F Правило: -F-[FbF-FbF]+-+[FF]+F-FF+[FF+FF] | 30 | 3 | 0 | 5 |
Аксиома: F-F Правило: -F-[FF-FF]+[FF+FF]+F-F-[FF+FF+F]+F+ | 30 | 3 | 0 | 6 |
Аксиома: F-F Правило: -F-[FF+FF]+[F]+FF-[-FFF]+[FF+FF] | 15 | 3 | -60 | 7 |
Аксиома: F-F Правило: -2F-[1F1F-3FF-F4F]+[F+FbFF]+FF-[-FF+FF]+[FbF+FF+FF-F] | 15 | 3 | -60 | 8 |
Аксиома: F++F++F Правило: -2F3F- | 60 | 8 | -60 | 9 |
10 | ||||
12 | ||||
14 | ||||
Аксиома: F++F++F Правило: -FF- | 75 | 7 | -90 | 10 |
11 | ||||
13 | ||||
15 | ||||
Аксиома: F++F++F++F Правило: +FF--FF+ | 45 | 2 | -90 | 11 |
3 | ||||
4 | ||||
5 | ||||
Аксиома: F Правило: -2F3F4F-F+F+F-4F3F2F- | 90 | 6 | -90 | 12 |
Аксиома: F++F++F Правило: +2F3F--4F3F++3F4F-3-F2F+ | 60 | 2 | -60 | 13 |
3 | ||||
4 | ||||
Аксиома: F++F++F++F++F++F Правило: +FF--[F+F]++[F+F]--FF+ | 30 | 4 | -90 | 14 |
Аксиома: F++F-F++F Правило: FF+[-FF-F+F+F]F- | 30 | 6 | -90 | 15 |















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