Рисуем фракталы с помощью PHP и Cairo. Часть 2. Фракталы и грамматики Линденмайера

Данная статья будет посвящена фракталам, которые часто встречаются в природе. В ней мы рассмотрим фрактальную природу растений и способ их моделирования с помощью порождающих грамматик Линденмайера.

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

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

Аристид Линденмайер — венгерский ботаник, занимаясь изучением физиологии растений и получив свой Ph.D по данному направлению, в 1956 году глубоко задумался о том, каким образом можно описать многообразие растительных форм на простом и понятном всем языке математики. И пришёл к выводу, что это можно сделать, используя так называемые L-системы, впоследствии названные в его честь.

L-система или система Линденмайера состоит из трёх элементов:

  1. алфавита символов — множества, состоящего из переменных (заменяемых символов) и констант (незаменяемых символов)
  2. аксиомы — строки символов, определяющей начальное состояние системы
  3. порождающих правил, определяющих каким образом переменные могут быть заменены комбинациями других переменных и констант, присутствующих в алфавите

Итерируя множество порождающих правил над аксиомой в конечном и тоге мы получаем грамматику L-системы, представляющую простую строку из представленного алфавита символов. Поставив в соответствие каждому символу набор некоторых графических операций, мы получаем возможности:

  • моделировать формы растений, как делал это сам Аристид Линденмайер,
  • создавать мозаики (например Мозаика Пенроуза)
  • или генерировать другие самоподобные фигуры похожие на те, что мы создавали ранее

Черепашья графика

Тише едешь — дальше будешь

Русская народная пословица

В 1966 Уолли Фёрзег и Сеймур Пайперт разработали язык Лого, поддерживающий простую и элегантную метафору для обучения детей программированию и работы с компьютерной графикой. Метафора получила название в честь этих незатейливых рептилий, к тому же оказавшихся первыми живыми существами долетевшими до Луны! И в правду говорят: «Тише едешь — дальше будешь!».

Для справки:

В 1968 году на борту советского беспилотного космического аппарата «Зонд-5», облетевшего вокруг Луны, находились две среднеазиатские черепахи, которые вернулись живыми и похудевшими на 10 %. Одна из черепах лишилась глаза из-за перегрузок при входе в атмосферу, доходивших до 20 g. Эти черепахи стали первыми живыми существами, долетевшими до Луны. Впоследствии среднеазиатские черепахи отправлялись в космос на борту лунных космических аппаратов «Зонд-6» (разбился при посадке на Землю), «Зонд-7» и «Зонд-8» (благополучно вернулись). Выбор среднеазиатских черепах в качестве объектов космических экспериментов был связан с тем, что из-за замедленного обмена веществ в течение полёта их не надо было поить и кормить.

Информация из Википедии

Подобно нашим космическим черепахам, эта метафора, а точнее её компьютерная реализация, оказалась очень неприхотливой в плане использования синтаксических конструкций для построения более-менее сложных геометрических фигур, то есть позволила упростить язык для работы с компьютерной графикой, что всем очень понравилось, и за что она снискала всеобщую любовь и получила значительное распространение среди множества компьютерных языков, таких как Basic и Python.

К сожалению Сairo не содержит встроенной поддержки черепашьей графики, поэтому нам нужно будет реализовать её самостоятельно в виде отдельного класса. Это можно сделать несколькими способами, например используя наследование, или создав оболочку над классом Сairo-context. Второй способ более простой и лёгкий, поэтому мы пройдём по этому пути. В результате получиться что-то вроде:

Итак, здесь мы используем концепцию интерфейсов, которая заключается в определении функций, через которые мы будем взаимодействовать с нашим созданным классом. Мне очень нравиться как сделан интерфейс для библиотеки черепашьей графики на Python, поэтому я просто повторяю все необходимые функции, которые понадобятся нам в дальнейшем. Далее я имплементирую интерфейс к классу черепахи и прописываю каждую из функции интерфейса в данном классе, связывая их с обеспечивающими основной функционал private-методами.

Ещё я хочу иметь возможность обращаться с цветами по их названию. Поэтому я создаю константный массив пар типа ключ — значение из названий цветов и их RGB уровней, а так же функцию для получения значений RGB уровней по названию цвета, и помещаю их в отдельный файл colors.php:

Наша черепаха готова, и теперь мы смело можем отправляться в наше морское путешествие!

Морские водоросли

Лучшие нивы, лучшие, отборные сорта фукусов, алярия и ламинария!

– Капусту садят!
– Нет, в самом деле?
– Однако в самом деле капусту садят, – ответил Конобеев. – Морскую капусту.
– Но ведь это не капуста, а ветки бамбука.
– Ну да, ветки бамбука. Вишь ты, какая штука: когда морская капуста выпустит семя…
– Споры?
– Никаких споров.

Из книги фантаста Александра Беляева «Подводные земледельцы»

Начнём мы наше погружение в мир L-систем рассмотрев простейшие виды грамматик по названию морских водорослей. Итак, первое что нам нужно сделать это генератор L-системы. Этот класс будет принимать на вход аксиому и порождающие правила, а так же количество необходимых итераций и на выходе выдавать строку из алфавита необходимой для графического построения самой L-системы. Получится следующий класс:

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

Теперь нам нужно это визуализировать, использовав возможности нашей виртуозной (и виртуальной!) черепахи. Мы пишем класс:

Здесь стоит обратить внимание на функцию draw, потому как в ней мы как раз и производим связь между алфавитом L-системы и способом его отрисовки. Нам понадобиться всего 9 символов, чтобы иметь возможность вырастить наш подводный лес из водорослей, создать кусты, деревья и даже нарисовать какие-нибудь другие фракталы, которые могут и не встретиться нам в живой природе…

Хм, это не очень удобно, каждый раз менять параметры L-системы, чтобы посмотреть какой-нибудь другой вид фрактала. Поэтому мы создадим ещё один файл , который будет содержать массив с различными параметрами L-систем, доступными их по конкретному наименованию. Мы будем заполнять его новыми видами систем по мере надобности. Вы можете сами поиграться с параметрами, чтобы затем сохранить понравившиеся системы в данном файле. Мне, например, приглянулись следующие примеры, которые я взял из замечательной книги Аристида Линденмайера «Алгоритмическая красота растений»:

Папоротник Барнсли

Тенью лёгкой и неслышной
Я замедлил у пути,
Там, где папоротник пышный
Должен будет расцвести.

Константин Бальмонт, «Папоротник», 1900

Старинные русские предания гласят, что в ровно в полночь на праздник Ивана Купала в лесу зацветает папоротник. Раскалённый что уголь, с треском, он цветёт как зарница, «пламенем освещая около себя и вдали». Тот, кто завладеет цветком, обретает власть над духами, становится прозорливым, получает силы повелевать землею и водою, отыскивать клады и делаться невидимкою. Звучит очень заманчиво, но сорвать цветок не так просто: злой дух срывает голову и отправляет душу в Ад всякого, кто по неосторожности попадёт в его ловушку — откликнется на голос близкого человека или поддастся на искушения.

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

Их всего 4: 2 чтобы обеспечить последовательное уменьшение длины сегментов для отрисовки, и ещё столько же чтобы более детально задать углы для сегментов… Да, вы можете заметить, что повсюду чувствуется этот загадочный ореол числа 42…(6×7 = 42, intval(‘7’,8) — 48 = 42). Что ж, не удивляйтесь. Это плата за вход в тридесятое цифровое царство (101010 в десятичной системе счисления равно 42). Теперь вы можете начать видеть эти числа повсюду и это вовсе не паранойя, а элементарное сочетание психологических феноменов и математической теории… (Английский юмор).

В добавок нам нужно будет определить значения констант $reduce0 и $reduce1, определяющих шаг черепахи на данном этапе отрисовки. Так же нам следует ввести переменную $repeat, которая будет устанавливать количество повторов операций поворота на заранее заданный угол (нужно так же не забыть восстановить её исходное значение, после того, как осуществлена операция поворота). И ещё, так как каждую итерацию мы уменьшаем шаг черепахи, мы должны проделать такие же операции сохранения/извлечения величины шага в стеке, как мы делали это с параметрами heading и position.

Всё это мы можем сделать внутри самой функции draw. И далее всё что нам останется  так это задать параметры L-системы для папоротника Барнсли. Мы просто добавляем следующие строки в файл grammars.php в самый конец массива $grammar:

Как видите, всё гениальное просто!

Добавим к этому ещё парочку грамматик, чтобы убедиться в универсальности такого подхода:

Итак, подведём итоги…

В данной статье мы рассмотрели способ генерации фракталов на основе систем Линденмайера. Мы увидели, что сравнительно простыми способами могут быть сгенерированы совершенно разнообразные формы — как существующие, так и не существующие в природе. Вообще этот подход к моделированию растений существует уже достаточно долго, и на нём в частности зиждется работа такого именитого алгоритма как SpeedTree, породившего пышную растительность планеты Пандора из фильма «Аватар». Интересен тот факт, что генерация виртуальных растений, позволяет зарабатывать разработчикам данного агоритма вполне реальные деньги. Это не плохая идея: иногда выгоднее заниматься разработкой алгоритма генерирующего определённый контент, который можно продать за деньги, нежели чем продавать сам алгоритм.

Благо на этом тема фрактальной графики не закачивается. И впереди нас ждёт ещё одна статья, которая будет посвящена фрактальным множествам на комплексной плоскости. А пока я предлагаю выполнить вам следующие задания:

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

Я желаю вам хороших идей и верных решений! До встречи в следующей статье!

Комментарии 4

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.