В этом посте я объясню, как ваш компьютер может выращивать красивые деревья и растения. Удивительно, но там будет задействована черепаха…

Я поклонник самоорганизующихся систем и сложности, которая может возникнуть из простых правил. Сегодня я хочу рассказать вам о такой очень простой системе, которая может рисовать красивые структуры, похожие на растения. В конце шестидесятых годов венгерский биолог Аристид Линденмайер разработал так называемые L-системы (да, L означает его фамилию), формальную грамматику для моделирования роста и развития растений.

Что такого особенного и увлекательного в этих L-системах? Ну, во-первых, лежащие в основе принципы относительно просты, но они могут привести к очень сложному поведению; Я приведу вам несколько примеров ниже, потерпите меня немного. Во-вторых, даже математическое обозначение этих систем легко понять (клянусь, не бегайте и не паникуйте, потому что я сказал математику :-D).

Основы L-Systems: встречайте счастливую черепаху!

По сути, L-системы — это генеративные грамматики, то есть набор правил перезаписи символов и строк. Я пропущу формальное определение, а вместо этого приведу пример. Рассмотрим следующие два правила:

A -> ABA

B -> A

Стрелку можно интерпретировать как заменить элемент слева другим элементом справа. В этом примере символ A будет заменен строкой ABA, а B просто на A. Важно, чтобы оба правила применялись одновременно, а не одно за другим. Кроме того, мы можем повторять замены строк столько раз, сколько захотим.

Допустим, мы начинаем с символа A. После первой итерации A будет заменено на
ABA. Второе правило B -> A применить нельзя, так как B еще не существует. Затем второе применение правила, установленного на ABA, даст ABAAABA (заменив оба As на ABA и одиночное B на A). Мы могли бы продолжать в третий, четвертый или пятый раз, сколько вам угодно.

Ну, этот хороший набор правил позволяет нам генерировать экспоненциально растущие строки. Тем не менее, это не очень похоже на рост растений. Первым шагом в этом направлении являются знаменитые черепашьи рисунки. Старшие поколения могут помнить их по образовательному языку программирования LOGO.

Представьте себе черепаху, живущую на бумажном самолетике. Более того, кто-то очень подлый проткнул бедное животное карандашом. Однако черепаха не умирает от ужасного удара карандашом. Вместо этого, если черепаха будет бродить по бумажному самолетику, она прочертит линию своего пути на земле. Это также очень послушная черепаха, она пойдет в любом направлении, куда вы ей прикажете. На самом деле, черепаха знает три команды: F для перемещения на фиксированную длину вперед, + для поворота влево на фиксированный угол и - для поворота вправо в противоположном направлении. См. ниже черепаху с углом поворота 90 градусов. Видите, как радостно он рисует кубик?

Теперь мы можем использовать наш набор символов F, + и - в сочетании с грамматикой L-Systems для рисования красивых структур. Например, давайте посмотрим на это очень простое правило:

F -> F+F--F+F

При этом мы можем итеративно генерировать следующие строки:
Мы начинаем с F, затем получаем F+F--F+F (1-я итерация), затем F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F (2-я итерация) и так далее.

Мы можем остановиться на некоторой итерации по нашему выбору и позволить нашей черепашке нарисовать результирующую строку
, используя угол 60 градусов для + (слева) и - (справа). Наша черепашка будет читать строку символ за символом и рисовать для нас. Например, возьмем F+F--F+F, в этом случае черепаха начнет двигаться вперед, затем повернется налево, вперед, дважды вправо, снова вперед, влево и еще раз в последний раз вперед. Полученные фрактальные графики называются кривыми Коха:

Вы видите начальный запуск Fв левом верхнем углу, за которым следует первое приложение F+F--F+F в правом верхнем углу и так далее.

Мы можем нарисовать несколько более сложные структуры. Если мы скажем черепахе двигаться вперед не только на букву F, но и на G, мы можем накормить ее следующей грамматикой:

F -> F-G+F+G-F

G -> GG

Начиная со строки F-G-G и используя угол поворота 120 градусов, черепаха может рисовать так называемые треугольники Серпинского:

Красивые деревья и растения во второй части, Pinky Promise!

Прежде чем превратить нашу черепаху в идеального садовника, давайте сделаем здесь перерыв. Но обещаю, в следующей части мы доберемся до красивых растений! Если вы не можете ждать и хотите сами поиграть с L-Systems, я предоставил небольшой скрипт Python для этого в моем профиле Github.

Часть 2

Вы можете найти часть 2 сейчас ЗДЕСЬ!

Первоначально опубликовано на steemit.com 8 января 2018 г.