Школа программирования ProgTips Данная статья будет посвящена фракталам, которые часто встречаются в природе. В ней мы рассмотрим фрактальную природу растений и способ их моделирования с помощью порождающих грамматик Линденмайера.
Что такое L-системы?
Как уже было сказано ранее, фракталы встречаются повсюду в природе и это не удивительно,
что и в растительном царстве, мы наблюдаем их столь многочисленное разнообразие.
Аристид Линденмайер — венгерский ботаник, занимаясь изучением физиологии растений и получив свой Ph.D по данному направлению, в 1956 году глубоко задумался о том, каким образом можно описать многообразие растительных форм на простом и понятном всем языке математики. И пришёл к выводу, что это можно сделать, используя так называемые L-системы, впоследствии названные в его честь.
L-система или система Линденмайера состоит из трёх элементов:
- алфавита символов — множества, состоящего из переменных (заменяемых символов) и констант (незаменяемых символов)
- аксиомы — строки символов, определяющей начальное состояние системы
- порождающих правил, определяющих каким образом переменные могут быть заменены комбинациями других переменных и констант, присутствующих в алфавите
Итерируя множество порождающих правил над аксиомой в конечном и тоге мы получаем грамматику L-системы, представляющую простую строку из представленного алфавита символов. Поставив в соответствие каждому символу набор некоторых графических операций, мы получаем возможности:
- моделировать формы растений, как делал это сам Аристид Линденмайер,
- создавать мозаики (например Мозаика Пенроуза)
- или генерировать другие самоподобные фигуры похожие на те, что мы создавали ранее
Черепашья графика
Тише едешь — дальше будешь
Русская народная пословица
В 1966 Уолли Фёрзег и Сеймур Пайперт разработали язык Лого, поддерживающий простую и элегантную метафору для обучения детей программированию и работы с компьютерной графикой. Метафора получила название в честь этих незатейливых рептилий, к тому же оказавшихся первыми живыми существами долетевшими до Луны! И в правду говорят: «Тише едешь — дальше будешь!».
Для справки:
В 1968 году на борту советского беспилотного космического аппарата «Зонд-5», облетевшего вокруг Луны, находились две среднеазиатские черепахи, которые вернулись живыми и похудевшими на 10 %. Одна из черепах лишилась глаза из-за перегрузок при входе в атмосферу, доходивших до 20 g. Эти черепахи стали первыми живыми существами, долетевшими до Луны. Впоследствии среднеазиатские черепахи отправлялись в космос на борту лунных космических аппаратов «Зонд-6» (разбился при посадке на Землю), «Зонд-7» и «Зонд-8» (благополучно вернулись). Выбор среднеазиатских черепах в качестве объектов космических экспериментов был связан с тем, что из-за замедленного обмена веществ в течение полёта их не надо было поить и кормить.
Информация из Википедии
Подобно нашим космическим черепахам, эта метафора, а точнее её компьютерная реализация, оказалась очень неприхотливой в плане использования синтаксических конструкций для построения более-менее сложных геометрических фигур, то есть позволила упростить язык для работы с компьютерной графикой, что всем очень понравилось, и за что она снискала всеобщую любовь и получила значительное распространение среди множества компьютерных языков, таких как Basic и Python.
К сожалению Сairo не содержит встроенной поддержки черепашьей графики, поэтому нам нужно будет реализовать её самостоятельно в виде отдельного класса. Это можно сделать несколькими способами, например используя наследование, или создав оболочку над классом Сairo-context. Второй способ более простой и лёгкий, поэтому мы пройдём по этому пути. В результате получиться что-то вроде:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
<?php include 'colors.php'; /* Sea ASCII Turtle looks very pretty _,.---.---.---.--.._ _.-' `--.`---.`---'-. _,`--.._ /`--._ .'. `. `,`-.`-._\ || \ `.`---.__`__..-`. ,'`-._/ _ ,`\ `-._\ \ `. `_.-`-._,``-. ,` `-_ \/ `-.`--.\ _\_.-'\__.-`-.`-._`. (_.o> ,--. `._/'--.-`,--` \_.-' `-._ \ `---' `._ `---._/__,----` `-. `-\ /_, , _..-' `-._\ \_, \/ ._( \_, \/ ._\ `._,\/ ._\ `._// ./`-._ `-._-_-_.-' taked from source: http://turtle.ascii.uk/ */ // Declare interface TurtleInterface { public function forward($distance); // move forward public function backward($distance); // move backward public function right($angle); // turn right public function left($angle); // turn left public function setposition($x,$y); // set turtle postion public function setheading($angle); // set turtle orientation angle public function home(); // return turle to home (0,0) public function penup(); // after that turtle moves don't track on canvas public function pendown(); // after that turtle moves StarTrack on canvas public function pensize($width); // set turtle drawing size public function color($name); // set turtle drawing color public function position(); // get turtle follow position public function heading(); // get turtle follow orientation // unusual fun (absent in python turtle common lib) public function setcolor($rgb); // set color by rgb values public function getpensize(); // get turtle follow drawing size public function getcolor(); // get turtle follow drawing color } // Simple Cairo-context wrapping class class Turtle implements TurtleInterface { private $context = NULL; // our Cairo-context for drawing private $angle = M_PI; // follow angle private $x = 0; // follow x-coordinate private $y = 0; // follow y-coordinate private $size = 0; // drawing line width private $c = NULL; // drawing color // init function (doesn't work without it) public function setContext($context){ $this->context = $context; } /* * Main drawing functions */ // turn turtle by degree in radians private function turnRightLeft($angle){ $this->angle += $angle; } // turtle forward, turtle backward private function moveForwardBackward($distance){ $this->x += $distance * sin($this->angle); $this->y += $distance * cos($this->angle); $this->context->lineTo($this->x,$this->y); $this->context->stroke(); $this->context->moveTo($this->x,$this->y); } // turtle up, turtle down private function moveUpDown($direction){ if ($direction == 'Up') { $this->context->setLineWidth(0); } else { $this->context->setLineWidth($this->size); } } // place turtle to position private function moveToPostion($x, $y){ $this->x = $x; $this->y = $y; $this->context->moveTo($this->x, $this->y); } // set drawing line width private function setSize($width){ $this->size = $width; $this->context->setLineWidth($this->size); } /* * Interface functions links (look up interace to understanding) */ public function forward($distance){ $this->moveForwardBackward($distance); } public function backward($distance){ $this->moveForwardBackward(-$distance); } public function right($angle){ $this->turnRightLeft($angle); } public function left($angle){ $this->turnRightLeft(-$angle); } public function setposition($x,$y){ $this->moveToPostion($x,$y); } public function setheading($angle){ $this->angle = $angle; } public function home(){ $this->moveToPostion(0,0); } public function penup(){ $this->moveUpDown('Up'); } public function pendown(){ $this->moveUpDown('Down'); } public function pensize($width){ $this->setSize($width); } public function color($name){ $this->c = get_color($name); $this->context->setSourceRgb($this->c[0], $this->c[1], $this->c[2]); } public function position(){ return array($this->x,$this->y); } public function heading(){ return $this->angle; } public function setcolor($rgb){ $this->c = $rgb; $this->context->setSourceRgb($this->c[0], $this->c[1], $this->c[2]); } public function getpensize(){ return $this->size; } public function getcolor(){ return $this->c; } } ?> |
Итак, здесь мы используем концепцию интерфейсов, которая заключается в определении функций, через которые мы будем взаимодействовать с нашим созданным классом. Мне очень нравиться как сделан интерфейс для библиотеки черепашьей графики на Python, поэтому я просто повторяю все необходимые функции, которые понадобятся нам в дальнейшем. Далее я имплементирую интерфейс к классу черепахи и прописываю каждую из функции интерфейса в данном классе, связывая их с обеспечивающими основной функционал private-методами.
Ещё я хочу иметь возможность обращаться с цветами по их названию. Поэтому я создаю константный массив пар типа ключ — значение из названий цветов и их RGB уровней, а так же функцию для получения значений RGB уровней по названию цвета, и помещаю их в отдельный файл colors.php:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
<?php // my little happy colorset // (huh, you're never watched Bob Ross??) const colorset = array( 'black' => array(0.0,0.0,0.0), 'white' => array(1.0,1.0,1.0), 'red' => array(1.0,0.0,0.0), 'green' => array(0.0,1.0,0.0), 'blue' => array(0.0,0.0,1.0), 'cyan' => array(0.0,1.0,1.0), 'magenta' => array(1.0,0.0,1.0), 'yellow' => array(1.0,1.0,0.0), ); // return color rgb array by name function get_color($name){ if(array_key_exists($name, colorset)){ return colorset[$name]; } return colorset['black']; }; ?> |
Наша черепаха готова, и теперь мы смело можем отправляться в наше морское путешествие!
Морские водоросли
Лучшие нивы, лучшие, отборные сорта фукусов, алярия и ламинария!
– Капусту садят!
– Нет, в самом деле?
– Однако в самом деле капусту садят, – ответил Конобеев. – Морскую капусту.
– Но ведь это не капуста, а ветки бамбука.
– Ну да, ветки бамбука. Вишь ты, какая штука: когда морская капуста выпустит семя…
– Споры?
– Никаких споров.Из книги фантаста Александра Беляева «Подводные земледельцы»
Начнём мы наше погружение в мир L-систем рассмотрев простейшие виды грамматик по названию морских водорослей. Итак, первое что нам нужно сделать это генератор L-системы. Этот класс будет принимать на вход аксиому и порождающие правила, а так же количество необходимых итераций и на выходе выдавать строку из алфавита необходимой для графического построения самой L-системы. Получится следующий класс:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
<?php /* * Generator of L-System */ class LSystemGenerator { private $axiom = ''; // initial string (initiator) private $rules = NULL; // some kind of symbos replacing rules private $depth = 0; // recursion depth equivalent private $G = ''; // output grammar string // simple constructor public function LSystemGenerator($axiom, $rules, $depth){ $this->setAxiom($axiom); $this->setRules($rules); $this->setDepth($depth); } // set start axiom public function setAxiom($axiom){ $this->axiom = $axiom; } // just set rules array public function setRules($rules){ $this->rules = $rules; } // recursion depth equivalent public function setDepth($depth){ $this->depth = $depth; } // main function public function gen(){ $this->G = $this->axiom; for($i = 0; $i < $this->depth; $i++){ $NG = ''; foreach (str_split($this->G) as $alpha){ $NG .= $this->rule($alpha); } $this->G = $NG; } return $this->G; } // get the rule the from follow symbol private function rule($alpha){ if (array_key_exists($alpha, $this->rules)){ return $this->rules[$alpha]; } return $alpha; } } // Test (uncomment for checking) // some kind of bush // $axiom = 'X'; // $rules = array( // 'X' => 'F-[[X]+X]+F[+FX]-X', // 'F' => 'FF', // ); // $depth = 5; // $lsys_gene = new LSystemGenerator($axiom, $rules, $depth); // $model = $lsys_gene->gen(); // echo $model; ?> |
Здесь нет ничего сложного. Просто берём, тестируем, получаем большущую строку уже похожую на непроходимый лес саргассовых водорослей:
Теперь нам нужно это визуализировать, использовав возможности нашей виртуозной (и виртуальной!) черепахи. Мы пишем класс:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
<?php include 'drawing_window.php'; include 'turtle_graphics.php'; include 'lsystem_gene.php'; /* * Main class */ class LSystem extends FractalDrawingWindow { // two main objects private $turtle = NULL; private $generator = NULL; // and four simple drawing parameters private $angle = 0; private $step = 0; private $width = 0; private $color = NULL; // override the constructor function __construct($grammar, $depth, $step, $width, $color){ parent::__construct(); // simple transfer parameters $this->angle = deg2rad($grammar['angle']); $this->step = $step; $this->width = $width; $this->color = $color; // create generator $this->generator = new LSystemGenerator($grammar['axiom'], $grammar['rules'], $depth); } // simple return window name public function getName() { return "L-System fractal"; } protected function onDraw($context){ $width = $this->get_size()[0]; $height = $this->get_size()[1]; $this->turtle = new Turtle(); $this->turtle->setContext($context); $this->turtle->setposition($width/2, 3*$height/4); $this->turtle->pensize($this->width); $this->turtle->color($this->color); // standart $this->draw($this->turtle, $this->generator->gen(), $this->angle, $this->step); } // here we have class for interpret l-system grammar public function draw($turtle, $model, $angle, $step){ // init stack $stack = array(); // run interpreter foreach(str_split($model) as $alpha){ // loop for symbols switch($alpha){ // take symbol case 'F': // compare and run command case 'G': case 'R': case 'L': // make move $turtle->forward($step); break; case 'f': // make leap $turtle->penup(); $turtle->forward($step); break; case '+': // turn left $turtle->left($angle); break; case '-': // turn right $turtle->right($angle); break; case '[': // push state to the stack (run brackets) array_push($stack,array($turtle->position(), $turtle->heading())); break; case ']': // pop state from the stack (terminate brackets) $turtle->penup(); $ph = array_pop($stack); $turtle->setposition($ph[0][0], $ph[0][1]); $turtle->setheading($ph[1]); break; } // and don't forget put turtle to the ground in the end of the turn $turtle->pendown(); } } } // Test (uncomment for testing) // $grammar = array( // laminaria algae // 'axiom' => 'F', // 'rules' => array( // 'F' => 'F[+F]F[-F][F]', // ), // 'angle' => 20.0, // ); // $depth = 5; // $step = 5; // $width = 1; // $color = 'green'; // (new LSystem($grammar, $depth, $step, $width, $color))->fullscreen(); // Gtk::main(); ?> |
Здесь стоит обратить внимание на функцию draw, потому как в ней мы как раз и производим связь между алфавитом L-системы и способом его отрисовки. Нам понадобиться всего 9 символов, чтобы иметь возможность вырастить наш подводный лес из водорослей, создать кусты, деревья и даже нарисовать какие-нибудь другие фракталы, которые могут и не встретиться нам в живой природе…
Хм, это не очень удобно, каждый раз менять параметры L-системы, чтобы посмотреть какой-нибудь другой вид фрактала. Поэтому мы создадим ещё один файл , который будет содержать массив с различными параметрами L-систем, доступными их по конкретному наименованию. Мы будем заполнять его новыми видами систем по мере надобности. Вы можете сами поиграться с параметрами, чтобы затем сохранить понравившиеся системы в данном файле. Мне, например, приглянулись следующие примеры, которые я взял из замечательной книги Аристида Линденмайера «Алгоритмическая красота растений»:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
<?php const grammar = array( // algaes... 'macrocystis' => array( 'axiom' => 'F', 'rules' => array( 'F' => 'F[+F]F[-F]F', ), 'angle' => 25.7, ), 'laminaria' => array( 'axiom' => 'F', 'rules' => array( 'F' => 'F[+F]F[-F][F]', ), 'angle' => 20.0, ), 'sargassum' => array( 'axiom' => 'F', 'rules' => array( 'F' => 'FF-[-F+F+F]+[+F-F-F]', ), 'angle' => 22.5, ), // grasses.. 'poa' => array( 'axiom' => 'X', 'rules' => array( 'X' => 'F[+X][-X]FX', 'F' => 'FF', ), 'angle' => 25.7, ), 'hierochole' => array( // sweetgrass 'axiom' => 'X', 'rules' => array( 'X' => 'F+[[X]-X]-F[-FX]+X', 'F' => 'FF', ), 'angle' => 25.0, ), 'millefolium' => array( // yarrow 'axiom' => 'X', 'rules' => array( 'X' => 'F[+X]F[-X]+X', 'F' => 'FF', ), 'angle' => 20.0, ), ); function get_grammar($name){ if(array_key_exists($name, grammar)){ return grammar[$name]; } return grammar['laminaria']; } ?> |
Папоротник Барнсли
Тенью лёгкой и неслышной
Я замедлил у пути,
Там, где папоротник пышный
Должен будет расцвести.Константин Бальмонт, «Папоротник», 1900
Старинные русские предания гласят, что в ровно в полночь на праздник Ивана Купала в лесу зацветает папоротник. Раскалённый что уголь, с треском, он цветёт как зарница, «пламенем освещая около себя и вдали». Тот, кто завладеет цветком, обретает власть над духами, становится прозорливым, получает силы повелевать землею и водою, отыскивать клады и делаться невидимкою. Звучит очень заманчиво, но сорвать цветок не так просто: злой дух срывает голову и отправляет душу в Ад всякого, кто по неосторожности попадёт в его ловушку — откликнется на голос близкого человека или поддастся на искушения.
К счастью в мире компьютерных алгоритмов мы всегда можем сделать свою резервную копию! Поэтому мы смело продолжаем развивать нашу идею. Далее нам потребуется ещё несколько операторов для того, чтобы обеспечить возможность построения данной фигуры. Что ж, добавим в ранее созданный класс пару кейс-блоков, содержащих следующие символы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
case '@': // reduce turtle moving step $step *= $reduce0; break; case '#': // the same thing above with other coef. $step *= $reduce1; break; case '6': case '7': // just calc another yet rotation coefficient $repeat = deg2rad(intval($alpha,8) - 48) * 10; break; |
Их всего 4: 2 чтобы обеспечить последовательное уменьшение длины сегментов для отрисовки, и ещё столько же чтобы более детально задать углы для сегментов… Да, вы можете заметить, что повсюду чувствуется этот загадочный ореол числа 42…(6×7 = 42, intval(‘7’,8) — 48 = 42). Что ж, не удивляйтесь. Это плата за вход в тридесятое цифровое царство (101010 в десятичной системе счисления равно 42). Теперь вы можете начать видеть эти числа повсюду и это вовсе не паранойя, а элементарное сочетание психологических феноменов и математической теории… (Английский юмор).
В добавок нам нужно будет определить значения констант $reduce0 и $reduce1, определяющих шаг черепахи на данном этапе отрисовки. Так же нам следует ввести переменную $repeat, которая будет устанавливать количество повторов операций поворота на заранее заданный угол (нужно так же не забыть восстановить её исходное значение, после того, как осуществлена операция поворота). И ещё, так как каждую итерацию мы уменьшаем шаг черепахи, мы должны проделать такие же операции сохранения/извлечения величины шага в стеке, как мы делали это с параметрами heading и position.
Всё это мы можем сделать внутри самой функции draw. И далее всё что нам останется так это задать параметры L-системы для папоротника Барнсли. Мы просто добавляем следующие строки в файл grammars.php в самый конец массива $grammar:
|
1 2 3 4 5 6 7 8 9 |
'fern' => array( 'axiom' => 'FD', 'rules' => array( 'D' => 'C+@FD', 'C' => 'B', 'B' => '[6+#FD][7-#FD]', ), 'angle' => 5.4, ), |
Как видите, всё гениальное просто!
Добавим к этому ещё парочку грамматик, чтобы убедиться в универсальности такого подхода:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// curves 'island' => array( 'axiom' => 'F-F-F-F', 'rules' => array( 'F' => 'F+FF-FF-F-F+F+FF-F-F+F+FF+FF-F', ), 'angle' => 90.0, ), 'islands&lakes' => array( 'axiom' => 'F+F+F+F', 'rules' => array( 'F' => 'F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF', 'f' => 'ffffff', ), 'angle' => 90.0, ), 'dragon' => array( 'axiom' => 'L', 'rules' => array( 'L' => 'L+R+', 'R' => '-L-R', ), 'angle' => 90.0, ), 'tree' => array( 'axiom' => 'f', 'rules' => array( 'F' => 'FF', 'f' => '-F[+F][---f]+F-F[++++f]-f', ), 'angle' => 12.0, ), // Canary Islands dragon tree 'drago' => array( 'axiom' => 'F', 'rules' => array( 'F' => 'F[-F][+F]', ), 'angle' => 25.0, ), |
Итак, подведём итоги…
В данной статье мы рассмотрели способ генерации фракталов на основе систем Линденмайера. Мы увидели, что сравнительно простыми способами могут быть сгенерированы совершенно разнообразные формы — как существующие, так и не существующие в природе. Вообще этот подход к моделированию растений существует уже достаточно долго, и на нём в частности зиждется работа такого именитого алгоритма как SpeedTree, породившего пышную растительность планеты Пандора из фильма «Аватар». Интересен тот факт, что генерация виртуальных растений, позволяет зарабатывать разработчикам данного агоритма вполне реальные деньги. Это не плохая идея: иногда выгоднее заниматься разработкой алгоритма генерирующего определённый контент, который можно продать за деньги, нежели чем продавать сам алгоритм.
Благо на этом тема фрактальной графики не закачивается. И впереди нас ждёт ещё одна статья, которая будет посвящена фрактальным множествам на комплексной плоскости. А пока я предлагаю выполнить вам следующие задания:
- найти и воспользоваться библиотечной функцией из списка для отрисовки градиентов, чтобы создать красивый подводный фон для наших морских обитателей
- подумать как можно изменить наш основной класс, чтобы добавить сразу несколько различных видов фракталов на один холст для отрисовки (а то им так одиноко!)
Я желаю вам хороших идей и верных решений! До встречи в следующей статье!
Oченб хорошая статья. Мне пронравилась.
Спасибо.
здесь ошибка
include 'colors.php', отсутствует;я исправил и все еще ошибка http://prntscr.com/pdsxt2
Спасибо. Исправил. Исправьте у себя вместо вызова функции pi() при инициализации нужно использовать константу M_PI.