Розділ 8. Фрактали

Тронний зал Чакрі Маха Прасат, Бангкок, Таїланд (фото Саада Ахтара)

Зал Чакрі Маха Прасат, розташований у Великому палаці у центрі Бангкока, Таїланд, і є архітектурним досягненням, відомим своїми складними деталями та величчю. Кожен рівень багатошарового даху повторює меншу чи більшу версію самого себе та представляє різні рівні гори Меру, центру буддійського всесвіту.

---

Колись у середній школі я вивчав курс геометрії. Можливо, ви теж пройшли такий курс, де дізналися про класичні форми в одному, двох і, можливо, навіть у трьох вимірах. Яка довжина кола? Площа прямокутника? Відстань між точкою і прямою лінією? Такий вид геометрії зазвичай називають евклідовою геометрією, на честь грецького математика Евкліда і, якщо подумати, це тема, яку я весь час розглядав у цій книзі. Щоразу, коли я використовував вектори для опису руху тіл у декартовому просторі, це була евклідова геометрія.

Однак для нас, програмістів природи, я хотів би поставити питання: чи справді наш світ можна описати за допомогою евклідової геометрії? Екран ноутбука, на який я зараз дивлюся, напевно виглядає як прямокутник. А слива, яку я їв сьогодні вранці, була кулястою. Але що, якби я подивився далі й подумав про дерева, що обсаджують вулицю, листя, що звисає з цих дерев, блискавку вчорашньої грози, цвітну капусту, яку я з’їв на вечерю, кровоносні судини в моєму тілі, гори та берегові лінії, що визначають ландшафт? Як показано на малюнку 8.1, більшість речей, які ви зустрінете у природі, виглядають зовсім не так, як ідеалізовані геометричні форми евклідової геометрії.

Якщо ви хочете розпочати створення програмних проєктів із патернами, які виходять за межі базових форм, таких як circle(), square() і line(), настав час дізнатися про інший тип геометрії, геометрію природи: фрактали. У цьому розділі розглядаються концепції фракталів, а також методи програмування для моделювання фрактальної геометрії.

Що таке фрактал?

Термін фрактал (від латинського fractus, що означає “поламаний”) був введений математиком Бенуа Мандельбротом у 1975 році. У його основоположній праці “Фрактальна геометрія природи” він визначає фрактал як “грубу або фрагментовану геометричну форму, яку можна розділити на частини, кожна з яких є (принаймні приблизно) зменшеною копією цілого”.

Я проілюструю це визначення двома простими прикладами. Спочатку подумайте про розгалужену структуру дерева, як показано на малюнку 8.2. (У прикладі 8.6 я покажу вам, як написати код для малювання цього дерева.)

Зверніть увагу, що дерево має один стовбур із з’єднаними на кінці гілками. Кожна з цих гілок також має гілки на своєму кінці, а ці гілки також мають гілки й так далі. А що, якби ви зірвали одну гілку з цього дерева й уважніше оглянули її, як на малюнку 8.3?

Збільшена гілка є точною копією цілого, як описує Мандельброт. Однак не всі фрактали повинні бути ідеально самоподібними, як це дерево. Наприклад, подивіться на малюнок 8.4, на якому показано дві ілюстрації узбережжя Гренландії (або Kalaallit Nunaat мовою корінного населення Kalaallisut).

Відсутність масштабу на цих ілюстраціях не випадкова. Я тут показую всю берегову лінію чи лише її невелику частину? Без посилання на масштаб про це неможливо дізнатися, тому що берегові лінії, подібно фракталам, виглядають практично однаково у будь-якому масштабі. (До речі, берегова лінія B показує приблизно в 3 рази збільшене зображення конкретної ділянки берегової лінії A. Я додав масштаб на малюнку 8.5.)

Берегова лінія є прикладом стохастичного фракталу, тобто вона побудована на основі ймовірностей і випадковості. На відміну від детермінованої (або передбачуваної) деревоподібної структури, стохастичний фрактал є статистично самоподібним. Це означає, що навіть якщо візерунок не є абсолютно однаковим для кожної частини меншого розміру, загальна якість форми та її загальне сприйняття залишаються незмінними незалежно від того, наскільки ви збільшуєте чи зменшуєте масштаб. Приклади в цьому розділі досліджують як детерміновані, так і стохастичні методи генерації фрактальних візерунків.

Хоча самоподібність є ключовою рисою фракталів, важливо розуміти, що сама по собі подібність не визначає фрактал. Зрештою, пряма лінія є самоподібною: вона виглядає однаково в будь-якому масштабі і її можна вважати такою, що складається з безлічі маленьких ліній. Але пряма лінія не є фракталом. Фрактали характеризуються тонкою структурою в малих масштабах (продовжуйте наближати берегову лінію, і ви продовжите знаходити флуктуації), і їх не можна описати за допомогою евклідової геометрії. Як правило, якщо ви можете сказати що “Це лінія!” тоді це не фрактал.

Множина Мандельброта

Один із найвідоміших і впізнаваних фрактальних візерунків названий на честь самого Мандельброта. Створення множини Мандельброта передбачає дослідження властивостей комплексних чисел після їх проходження через ітераційну функцію. Чи тяжіють вони до нескінченності? Чи залишаються обмеженими?

Попри захопливе математичне обговорення, цей алгоритм є менш практичним способом генерації фракталів, ніж рекурсивні способи, які ми розглянемо в цьому розділі. У будь-якому випадку код для створення множини Мандельброта включено в онлайн-приклади.

Фрактали ведуть довгу історію ще до книги Мандельброта 1975 року, з’являючись у різних формах у різних культурах. Вони практично такі ж старі, як сама природа. Корінні та стародавні суспільства часто включали фрактальні візерунки у своє мистецтво, архітектуру та текстиль задовго до офіційного вивчення фракталів у західній математиці. Наприклад, традиційне планування села Ба-Іла в Замбії та складні геометричні візерунки в ісламській архітектурі демонструють фрактальні властивості. Ці візерунки підкреслюють важливість фракталів у різноманітних культурних контекстах та їхню позачасову привабливість.

Рекурсія

Окрім самоподібності, іншим фундаментальним компонентом фрактальної геометрії є рекурсія: процес багаторазового застосування правила, відомого як породжувальне правило, яке вказує на те, що результат однієї ітерації стає відправною точкою для наступної. Рекурсія з’явилася у полі зору з першої появи фракталів у сучасній математиці, коли німецький математик Георг Кантор у 1883 році розробив прості правила генерування нескінченного набору чисел. Правила породжувального правила Кантора проілюстровано на малюнку 8.6.

У правилах Кантора діє цикл зворотного зв’язку. Візьміть одну лінію і розділіть її на дві. Потім поверніться до цих двох ліній і застосуйте те саме правило, розділяючи кожну лінію на дві. Тепер їх чотири. Поверніться до цих чотирьох ліній і застосуйте до них правило. Тепер їх вісім. І так далі. Ось як працює рекурсія: вихідні дані процесу повертаються у сам процес знову і знову. У цьому випадку результат відомий як множина Кантора. Подібно до фрактального дерева на малюнку 8.3, це приклад детермінованого, цілком передбачуваного фракталу, у якому кожна частина є точною копією цілого.

Кантора цікавило, що станеться, якщо застосувати рекурсивний набір правил нескінченну кількість разів. Однак ми з вами не маємо нескінченного часу. Крім того, програма p5.js обмежена доступним простором пікселів, тому в якийсь момент стає неможливо намалювати все менші лінії. Таким чином, для цілей цієї книги я здебільшого ігноруватиму питання та парадокси, які виникають унаслідок нескінченної рекурсії. Натомість код буде побудовано таким чином, де правила не застосовуються “вічно” (що призвело б до нескінченного циклу та зависання комп’ютера), а натомість припиняються, коли виконується певна умова.

Реалізація рекурсивних функцій

За мить я напишу програму, яка рекурсивно реалізує набір Кантора. Але спочатку розберемося, що значить мати рекурсію в коді? Все зводиться до виклику функції зсередини функції. Це, само по собі, не є чимось новим. Зрештою, ймовірно, ви весь час викликаєте функції з інших функцій. Наприклад:

function someFunction() {

  background(0);

}

Ключова відмінність рекурсії полягає у виклику функції, яку ви описуєте, у цій самій функції. Що станеться в такому випадку? Чи можна функцію someFunction() викликати всередині someFunction()?

function someFunction() {

  someFunction();

}

Це не тільки дозволено, але і заохочується! Насправді це важливо для того, як я буду реалізовувати множину Кантора. Функції, які викликають самі себе, називають рекурсивними функціями й вони добре підходять для розв'язання певних проблем. Наприклад, деякі математичні обчислення реалізуються рекурсивно: найвідомішим прикладом є факторіал.

Факторіал будь-якого числа n, зазвичай записується як n!, визначається наступним чином:

Ось нерекурсивна функція в JavaScript, яка використовує цикл for для обчислення факторіала числа:

function factorial(n) {

  let value = 1;

  for (let i = 0; i < n; i++) {
    value = value * (i + 1);
  }

  return value;

}

При уважному розгляді ви помітите щось цікаве про те, як працюють факторіали. Подумайте, як визначаються 4! і 3!:

Повне визначення 3! міститься у визначенні 4!:

У більш загальному вигляді для будь-якого натурального числа n, вірно наступне:

Записуючи це, я можу сказати, що факторіал числа n визначається як число n помножене на факторіал числа n – 1.

Визначення факторіала включає факторіал? Це схоже на визначення піци як “смачної їжі, яка містить шматочки піци”. Хоча це визначення піци, безперечно, безглузде, воно підкреслює концепцію самопосилання у визначенні та є суттю рекурсії. Застосовуючи його до визначення функції в коді це може призвести до надзвичайно елегантних рішень, таких як це рекурсивне визначення функції factorial():

function factorial(n) {

  if (n <= 1) {

    return 1;

  } else {

    return n * factorial(n - 1);

  }

}

Функція factorial() викликає сама себе у своєму власному визначенні. Спочатку це може виглядати трохи дивно, але воно працює, доки існує умова зупинки (у цьому випадку n <= 1), тому функція не зависає, викликаючи саму себе нескінченно. (Я використовую <= замість ===, щоб запобігти нескінченній рекурсії, але мені, ймовірно, слід включити додаткові перевірки помилок, щоб керувати нецілими або від’ємними вхідними даними й бути більш математично точним.) Малюнок 8.7 ілюструє кроки, які розгортаються під час виклику factorial(4).

Функція продовжує викликати саму себе, спускаючись все глибше і глибше в кролячу нору вкладених викликів функцій, доки не досягне умови зупинки. Потім вона виходить із діри, повертаючи значення, доки не повернеться додому до початкового виклику factorial(4).

Ви можете застосувати той самий рекурсивний принцип, який ілюструє функція factorial() до графіки на полотні, тільки замість повернення значень ви малюватимете фігури. Це саме те, що ви побачите в прикладах цього розділу. Для початку, ось проста рекурсивна функція, яка малює дедалі менші кола.

function drawCircles(x, y, r) {

  circle(x, y, r * 2);

  if (r > 4) {

    r *= 0.75;

    drawCircles(x, y, r);

  }

}

Функція drawCircles() малює коло на основі набору параметрів, які вона отримує як аргументи. Потім вона викликає сама себе з тими самими параметрами, дещо змінюючи їх. У результаті виходить серія кілець, кожне з яких намальовано всередині попереднього.

Подібно до того, як функція factorial() припиняє рекурсію, коли n дорівнює 0, функція drawCircles() рекурсивно викликає саму себе, лише якщо радіус більший за 4. Це важливий момент. Як і у випадку з ітерацією, усі рекурсивні функції повинні мати умову виходу! Ви, мабуть, уже знаєте, що цикли for і while повинні включати логічний вираз, який зрештою вираховується як false, таким чином виходячи з циклу. Без нього програма потрапила б у нескінченний цикл. Те саме можна сказати й про рекурсію. Якщо рекурсивна функція викликає сама себе постійно без виходу, у більшості випадків ви отримаєте непривітний, завмерлий екран. Однак браузер має вбудовані засоби захисту, і замість того, щоб остаточно зависнути, він закриває програму із повідомленням про помилку Maximum call stack size exceeded. Це просто популярний спосіб сказати: “Забагато рекурсивних викликів однієї функції, час зупинитися!”

Приклад 8.1 був досить тривіальним, цього можна легко досягти простою ітерацією за допомогою циклу for або while. Однак результати стають цікавішими, коли функція визначена із викликом самої себе більше одного разу. У таких сценаріях рекурсія стає надзвичайно елегантною. Для ілюстрації я зроблю функцію drawCircles() складнішою. Для кожного кола, що зображається, ми намалюємо всередині ще два кола, удвічі меншого розміру: одне ліворуч від центру, а інше — праворуч.

function setup() {

  createCanvas(640, 240);

}

function draw() {

  background(255);

  drawCircles(width / 2, height / 2, 320);

}

function drawCircles(x, y, radius) {

  stroke(0);

  noFill();

  circle(x, y, radius * 2);

  if (radius > 4) {

    drawCircles(x + radius / 2, y, radius / 2);
    drawCircles(x - radius / 2, y, radius / 2);

  }

}

Додайте ще два рядки коду, і тепер кожне коло міститиме чотири кола — ліворуч, праворуч, над і під центром.

function drawCircles(x, y, radius) {

  stroke(0);

  noFill();

  circle(x, y, radius * 2);

  if (radius > 16) {

    drawCircles(x + radius / 2, y, radius / 2);
    drawCircles(x - radius / 2, y, radius / 2);
    drawCircles(x, y + radius / 2, radius / 2);
    drawCircles(x, y - radius / 2, radius / 2);

  }

}

Спробуйте відтворити цю програму за допомогою ітерації замість рекурсії!

Малювання множини Кантора за допомогою рекурсії

Тепер, коли я продемонстрував, як використовувати рекурсивні функції, я готовий візуалізувати множину Кантора. З чого мені почати? Добре, я знаю, що набір Кантора починається з лінії, тому я почну з цього і напишу функцію, яка малює лінію:

function cantor(x, y, length) {

  line(x, y, x + length, y);

}

Ця функція малює лінію з довжиною, вказаною у змінній length, яка починається в піксельних координатах $(x, y)$. Лінія проведена горизонтально, але це довільне рішення. Припустимо, функція викликається наступним чином:

cantor(10, 20, width - 20);

Ви побачите щось схоже на малюнок 8.8.

Правило Кантора діє шляхом дублювання оригінальної лінії та стирання її середньої третини, залишаючи дві бічні лінії: одну від початку оригінального положення до однієї третини довжини, а іншу від положення двох третин до кінця лінії (див. малюнок 8.9). Я можу застосувати це правило вручну, викликавши функцію line() ще два рази, перемістивши $y$-позицію вниз на 20 пікселів, щоб наступне покоління ліній з’явилося нижче першого.

function cantor(x, y, length) {

  line(x, y, x + length, y);

  line(x, y + 20, x + length / 3, y + 20);

  line(x + (2 * length) / 3, y + 20, x + length, y + 20);

}

Малюнок 8.10 показує результат.

Це працює для двох поколінь, але продовження ручних викликів функції line() швидко стане громіздким. Для наступних поколінь мені знадобиться 4, потім 8, потім 16 викликів line(). Цикл for — це звичайний спосіб розв'язання подібної проблеми, але спробуйте і ви побачите, що розрахунок для кожної ітерації швидко виявиться надзвичайно складним. Однак не впадайте у відчай, бо тут на допомогу приходить рекурсія!

  line(x, y + 20, x + length / 3, y + 20);

Замість того, щоб безпосередньо викликати функцію line(), чому б не викликати функцію cantor()? Зрештою, що робить функція cantor()? Вона малює лінію в позиції $(x, y)$ із заданою довжиною length. Значення x залишається незмінним, y збільшується на 20, а довжина дорівнює length / 3:

  cantor(x, y + 20, length / 3);

Цей виклик функції cantor() еквівалентний попередньому виклику функції line(). І для наступної лінії у другому поколінні я можу знову викликати cantor():

  cantor(x + (2 * length / 3), y + 20, length / 3);

Тепер функція cantor() виглядає так:

function cantor(x, y, length) {

  line(x, y, x + len, y);

  cantor(x, y + 20, length / 3);
  cantor(x + (2 * length / 3), y + 20, length / 3);

}

Оскільки функція cantor() тепер рекурсивна, те саме правило буде застосовано до наступної лінії й до наступної й до наступної поки cantor() викликатиме себе знову і знову! Але поки що не запускайте цей код. У програмі відсутній важливий елемент: умова виходу. У якийсь момент вона має припинити рекурсію. Тут я виберу умову для зупинки, якщо довжина лінії менше або дорівнює одному пікселю. Іншими словами, продовжуйте, поки значення length більше ніж 1.

function cantor(x, y, length) {

  if (length > 1) {

    line(x, y, x + length, y);

    cantor(x, y + 20, length / 3);

    cantor(x + (2 * length) / 3, y + 20, length / 3);

  }

}

Написання функції, яка рекурсивно викликає саму себе є простим, елегантним способом для генерації фрактального візерунка, але це не дозволяє мені зробити нічого, окрім малювання візерунка. Наприклад, що потрібно зробити, якщо я хочу, щоб лінії у множині Кантора існували як окремі об’єкти, які можна переміщувати незалежно? Для цього мені потрібно використати інший підхід програмування, який застосовуватиме рекурсію в поєднанні з масивом, що відстежуватиме всі його окремі частини. Це саме те, що я буду робити далі!

Крива Коха

Тепер я звернуся до іншої відомої фрактальної моделі — кривої Коха — відкритої у 1904 році шведським математиком Гельґе фон Кохом. На малюнку 8.11 наведено правила створення цього фракталу. Зверніть увагу, що правила починаються так само як і набір Кантора, з однієї лінії, яка потім ділиться на три рівні частини.

На малюнку 8.12 показано, як фрактал розвивається протягом кількох повторень цих кроків.

Я міг би діяти так само як і з множиною Кантора й написати рекурсивну функцію, яка послідовно застосовує правила Коха знову і знову. Натомість я збираюся виконувати цю задачу інакше, розглядаючи кожен сегмент кривої Коха як окремий об’єкт. Це відкриє деякі захопливі дизайнерські можливості. Наприклад, якщо кожен сегмент є об’єктом, він може незалежно рухатися зі свого початкового положення та брати участь у фізичному моделюванні. Крім того, візуальний вигляд кожного сегмента може відрізнятися, якщо об’єкт містить настроювані властивості кольору, товщини лінії тощо.

Щоб досягти мети у створенні кожного сегменту як окремого об’єкту, я повинен спочатку вирішити, яким цей об’єкт повинен бути в першу чергу. Які дані він повинен зберігати? Які методи він повинен мати? Крива Коха — це ряд з’єднаних ліній, тому я буду розглядати кожен сегмент як лінію Коха — KochLine. Кожен об’єкт KochLine матиме початкову точку a і кінцеву точку b. Ці точки будуть представлені як об’єкти p5.Vector, а лінія малюватиметься за допомогою функції line():

class KochLine {

  constructor(a, b) {

    this.start = a.copy();
    this.end = b.copy();

  }

  show() {

    stroke(0);

    line(this.start.x, this.start.y, this.end.x, this.end.y);

  }

}

Тепер, коли у мене є клас KochLine, я можу перейти до роботи з функціями setup() і draw(). Мені знадобиться структура даних, щоб відстежувати те, що згодом стане багатьма об’єктами KochLine, і JavaScript масив цілком підійде (перегляньте Розділ 4 для перегляду масивів):

let segments = [];

function setup() {

  createCanvas(640, 240);

  let start = createVector(0, 200);

  let end = createVector(width, 200);

  segments.push(new KochLine(start, end));

}

Потім у функції draw() усі об’єкти KochLine (наразі лише один) можна відобразити за допомогою циклу for...of:

function draw() {

  background(255);

  for (let segment of segments) {

    segment.show();

  }

}

Це моя основа для програми. У мене є клас KochLine, який відстежує лінію від точки start до точки end, і є масив, який відстежує всі об’єкти KochLine. Маючи ці елементи, як і де я маю застосувати правила Коха та принципи рекурсії?

Пам’ятаєте клітинний автомат Гра Життя з Розділу 7? У тій симуляції я завжди відстежував два покоління: поточне та наступне. Коли я закінчував обчислення наступного покоління, наступне ставало поточним, і я переходив до обчислень нового наступного покоління. Тут я збираюся застосувати подібний підхід. У мене є масив segments із переліком поточного набору відрізків ліній (на початку програми є лише один). Тепер мені потрібен другий масив (я назву його next) куди я зможу додавати усі нові об’єкти KochLine, створені у результаті застосування правил Коха. Для кожного окремого елемента KochLine поточного масиву буде додано чотири нові сегменти до next. Коли я закінчу, масив next стане новим масивом segments (див. малюнок 8.13).

Ось як зараз виглядає код:

function generate() {

  let next = [];

  for (let segment of segments) {

    next.push(new KochLine(????, ????));
    next.push(new KochLine(????, ????));
    next.push(new KochLine(????, ????));
    next.push(new KochLine(????, ????));

  }

  segments = next;

}

Викликаючи функцію generate() знову і знову, правила кривої Коха будуть рекурсивно застосовані до набору сегментів KochLine, що вже існують. Але, звісно, я пропустив реальну роботу функції: як мені насправді розбити один відрізок лінії на чотири, як описано у правилах? Мені потрібен спосіб обчислення початкової та кінцевої точок кожної лінії.

Оскільки у класі KochLine для зберігання початкової та кінцевої точок використовуються об’єкти p5.Vector, це чудова нагода попрактикуватися в усій цій векторній математиці з Розділу 1, а також застосувати трохи тригонометрії з Розділу 3. По-перше, я повинен визначити обсяг проблеми: скільки точок мені потрібно обчислити для кожного об’єкта KochLine? Відповідь показано на малюнку 8.14.

Як показано на малюнку, мені потрібно перетворити дві точки (start, end) на п’ять (a, b, c, d, e), щоб створити чотири нові відрізки ($a → b$, $b → c$, $c → d$, $d → e$):

    next.add(new KochLine(a, b));

    next.add(new KochLine(b, c));

    next.add(new KochLine(c, d));

    next.add(new KochLine(d, e));

Де отримати ці точки? Чому б не попросити об’єкт KochLine розрахувати їх за мене?

function generate() {

  let next = [];

  for (let segment of segments) {

    let [a, b, c, d, e] = segment.kochPoints();
    next.push(new KochLine(a, b));
    next.push(new KochLine(b, c));
    next.push(new KochLine(c, d));
    next.push(new KochLine(d, e));

  }

  segments = next;

}

Зачекайте, придивімось на один рядок коду трохи уважніше:

    let [a, b, c, d, e] = segment.kochPoints();

Як ви можете пригадати з Розділу 6, я пояснював деструктуризацію об’єкта як спосіб витягування властивостей з об’єкта та присвоєння їх окремим змінним. Вгадайте що? Ви можете робити те саме з масивами! Тут, якщо метод kochPoints() повертає масив із п’яти елементів, я можу зручно розпакувати та призначити їх, відповідним змінним: a, b, c, d та e. Це чудовий спосіб обробки кількох повернених значень. Так само як і з об’єктами, деструктуризація масиву підтримує акуратність коду.

Тепер мені потрібно просто написати новий метод kochPoints() у класі KochLine, який повертатиме масив об’єктів p5.Vector, що представляють точки від a до e, які показані на малюнку 8.15. Спочатку я пропишу найпростіші точки a та e — вони є лише копіями точок start та end з початкової лінії:

  kochPoints() {

    let a = this.start.copy();

    let e = this.end.copy();

Як щодо точок b і d? Точка b лежить на одній третій довжини від початку відрізка, а d — це відстань, що складає дві третини від початку лінії. Як показано на малюнку 8.15, якщо я створю вектор $\vec{v}$, що вказує від оригінального значення start до кінцевого end, тоді я можу знайти нові точки, масштабуючи його магнітуду до однієї третини для нової точки b і двох третин для нової точки d.

Ось як це виглядає у коді:

    let v = p5.Vector.sub(this.end, this.start);

    v.div(3);

    let b = p5.Vector.add(a, v);

    let d = p5.Vector.add(b, v);

Остання точка c є найскладнішою для обчислення. Однак, якщо врахувати, що всі кути рівностороннього трикутника дорівнюють 60 градусам, це одразу полегшить нашу роботу. Якщо ми знаємо як знайти нову точку b із вектором, що становить одну третину довжини прямої, то можна повернути той самий вектор на 60 градусів (або $\pi/3$ радіан) і додати його до b, як на малюнку 8.16. Тоді ми прийдемо до точки c!

    v.rotate(-PI / 3);

    let c = p5.Vector.add(b, v);

Нарешті, після обчислення п’яти точок, я можу повернути їх усі разом у масиві. Це відповідатиме коду для деструктуризації масиву на п’ять окремих змінних, як було описано раніше:

    return [a, b, c, d, e];
  }

Тепер залишається лише викликати функцію generate() певну кількість разів (скажімо, п’ять), щоб у функції setup() обчислити відрізки лінії Коха до вказаного покоління.

let segments = [];

function setup() {

  createCanvas(640, 240);

  let start = createVector(0, 200);

  let end = createVector(width, 200);

  segments.push(new KochLine(start, end));

  for (let i = 0; i < 5; i++) {
    generate();
  }

}

У цьому прикладі я вирішив викликати функцію generate(). Щоразу, коли застосовуються правила Коха, кількість відрізків лінії зростає експоненціально. Після п’яти ітерацій я матиму 1024 сегменти, які забезпечують значну деталізованість для перегляду патерну. Однак ви можете використовувати підхід, застосований у попередніх прикладах, встановивши порогове значення для мінімальної довжини сегмента і викликаючи функцію generate() доки сегменти не стануть занадто малими. Крім того, ви можете розглянути інтерактивний варіант із кнопкою, яка з кожним натисканням розвиватиме форму до наступного покоління.

Вправа 8.5

Використайте рекурсію, щоб намалювати трикутник Серпінського (як показано в елементарному КА Вольфрама у Розділі 7).

Дерева

Фрактали, представлені до цього моменту у цьому розділі, були детермінованими: у них немає випадковості й вони завжди дають однаковий результат кожного разу, коли їх запускають. Хоча вони стали чудовим вступом до класичних фрактальних візерунків і методів програмування, що лежать в основі їх малювання, результати виявилися занадто точними, щоб здаватися справді органічними.

Далі у цьому розділі я зроблю на крок ближче до світу природи, розгляну приклад розгалуженого фрактального дерева. Я почну з детермінованої версії. Потім введу елемент випадковості, щоб проілюструвати методи генерації стохастичних (або недетермінованих) фракталів, результат яких може щоразу змінюватися.

Детермінована версія

На малюнку 8.17 показано детермінований набір породжувальних правил для малювання фрактального дерева.

І знову я маю гарний фрактал із рекурсивним визначенням: гілка — це лінія з двома гілками, з’єднаними з нею. Що робить цей фрактал дещо складнішим, ніж попередні, так це використання у правилах фракталу поворотів. Кожна нова гілка повинна повертатися відносно попередньої гілки, яка обертається відносно всіх своїх попередніх гілок. На щастя, p5.js має механізм для відстеження поворотів: transformations.

Я вже торкався трансформацій у Розділі 3. Це набір функцій, таких як translate(), rotate(), scale(), push() і pop(), які дозволяють змінювати положення, орієнтацію та масштаб фігур у вашій програмі. Функція translate() переміщує систему координат, rotate() обертає її, а push() і pop() допомагають зберегти та відновити поточний стан трансформації. Якщо ви не знайомі з цими функціями, у мене є набір відео про перетворення в p5.js, що доступні на вебсайті Coding Train.

Я почну з малювання однієї гілки, стовбура дерева. Оскільки я збираюся використовувати функцію rotate(), мені потрібно переконатися, що я постійно переміщуюсь вздовж гілок під час малювання. Пам’ятайте, коли ви робите повороти у p5.js, ви завжди обертаєтеся навколо початку координат або точки $(0, 0)$, тому у випадку з деревом ми маємо завжди переміщувати ці координати відліку на початок наступної гілки, що малюється (еквівалент кінця попередньої гілки). Оскільки гілка починається знизу, мені спочатку потрібно перемістити початкові координати полотна саме туди:

translate(width / 2, height);

line(0, 0, 0, -100);

Після того, як я намалював лінію, я повинен переміститися в її кінець і зробити поворот під кутом, щоб намалювати наступну гілку, як показано на малюнку 8.18. (Зрештою мені потрібно буде об’єднати те, що я зараз роблю, у рекурсивну функцію, але спочатку я розберуся з окремими кроками.)

Ось код для процесу, зображеного на малюнку 8.18. Я використовую кут у 30 градусів або $\pi/6$ радіан:

translate(0, -100);

rotate(PI / 6);
line(0, 0, 0, -100);

Тепер, коли у мене є гілка праворуч, мені потрібна гілка ліворуч (див. малюнок 8.19). Для цього я маю використати функцію push() , щоб зберегти стан трансформації перед поворотом і малюванням правої гілки. Тоді, після малювання правої гілки, я зможу викликати функцію pop() , щоб відновити цей стан, повернувши себе у потрібне попереднє положення для нового повороту та малювання лівої гілки.

translate(width / 2, height);

line(0, 0, 0, -100);

translate(0, -100);

push();
rotate(PI / 6);
line(0, 0, 0, -100);
pop();

rotate(-PI / 6);
line(0, 0, 0, -100);

Уявіть кожен виклик функції line() як гілку і ви зможете зрозуміти, як цей код імплементує процес розгалуження лінії, яка має дві лінії, з’єднані з її кінцями. Я міг би продовжувати додавати нові й нові виклики функції line() для все нових і нових розгалужень, але як і з множиною Кантора та кривою Коха, мій код незабаром став би неймовірно складним і громіздким. Замість цього я використаю код, який вже написав, як основу для функції branch(), замінивши другий і третій виклики функції line() рекурсивними викликами функції branch() всередині самої себе:

function branch() {

  line(0, 0, 0, -100);

  translate(0, -100);

  push();

  rotate(PI / 6);
  branch();

  pop();

  push();

  rotate(-PI / 6);
  branch();

  pop();

}

Зверніть увагу, що я використовую функції push() і pop() навколо кожної пари rotate() та branch(). Це одне з тих елегантних програмних рішень, яке виглядає як магія. Перед кожним наступним викликом функції branch(), програмі потрібен момент, щоб запам’ятати початкову позицію цієї гілки, щоб вона могла повернутися до неї пізніше. Якщо ви на мить уявите себе на місці p5.js і спробуєте простежити за рекурсивною функцією з олівцем та папером у руках, то помітите, що спочатку малюєте всі гілки праворуч. У самому кінці правої сторони функція pop() поверне вас назад уздовж усіх намальованих гілок, щоб ви могли намалювати гілки ліворуч.

Вправа 8.6

Дотримуйтеся рекурсивного алгоритму малювання гілок і пронумеруйте їх на діаграмі у тому порядку, в якому кожну з них малює p5.js.

Можливо ви помітили, що написана рекурсивна функція має серйозну проблему: вона не має умови виходу, тому застрягне у нескінченних рекурсивних викликах самої себе. Крім того, гілки дерева повинні ставати коротшими на кожному рівні, але наразі я жорстко закодував довжину кожної гілки у 100 пікселів. Розв'язки цих двох проблем взаємопов’язані. Якщо гілки зменшуються від одного покоління до іншого, я можу змусити функцію припинити рекурсію, коли гілки стануть занадто короткими:

function branch(len) {

  line(0, 0, 0, -len);

  translate(0, -len);

  len *= 0.67;

  if (len > 2) {

    push();

    rotate(angle);

    branch(len);

    pop();

    push();

    rotate(-angle);

    branch(len);

    pop();

  }

}

Я також включив для кута змінну angle. У готовому прикладі кут контролюється позицією змінної mouseX.

let angle;

function setup() {

  createCanvas(640, 240);

}

function draw() {

  background(255);

  angle = map(mouseX, 0, width, 0, HALF_PI);

  translate(width / 2, height);
  stroke(0);
  strokeWeight(2);
  branch(80);

}

Рекурсивна функція branch() забезпечує простий і елегантний спосіб малювання дерева з малою кількістю рядків коду. Однак такий підхід обмежує потенціал для анімації. Використовуючи підхід, застосований у кривій Коха і зберігаючи кожен сегмент як об’єкт у масиві, ви можете розкрити творчі способи для анімації росту дерева або навіть застосувати до гілок фізику!

Стохастична версія

На перший погляд (і під прямим кутом) може здатися, що у попередньому прикладі я намалював доволі переконливе дерево, але при ближчому розгляді результат виходить занадто ідеальним. Подивіться на справжнє дерево ззовні й ви помітите, що довжина гілок і кути різняться від гілки до гілки, не кажучи вже про те, що не всі гілки розходяться рівно на дві менші гілки. Фрактальні дерева є чудовим прикладом того, як додавання нотки випадковості може зробити кінцевий результат більш природним. Ця частинка випадковості також перетворює фрактал із детермінованого на стохастичний — кожний конкретний результат буде відрізнятися від малюнка до малюнка, зберігаючи при цьому загальні характеристики розгалуженої деревоподібної структури.

По-перше, як щодо рандомізації кута для кожної гілки? Це досить легко зробити, просто використавши функцію random():

  let angle = random(0, PI / 3);

В оригінальному прикладі функція branch() завжди викликала себе двічі. Тепер для додаткової різноманітності я замість цього виберу випадкову кількість гілок (кожна з випадковим кутом) для кожної гілки.

function branch(length) {

  line(0, 0, 0, -length);

  translate(0, -length);

  length *= 0.67;

  if (length > 2) {

    let n = Math.floor(random(1, 4));
    for (let i = 0; i < n; i++) {

      let angle = random(-PI / 2, PI / 2);
      push();
      rotate(angle);
      branch(length);
      pop();

    }

  }

}

Приклад 8.7 демонструє використання випадковості для кутів і кількості гілок, але, можливо, він заходить занадто далеко: отримані дерева все ще не виглядають особливо органічними. Для більш природного вигляду дерева ви можете спробувати трохи обмежити діапазон випадкових кутів, або використати шум Перліна для більш поступових змін кутів.

L-системи

У 1968 році угорський ботанік Арістід Лінденмаєр розробив засновану на граматиці систему для моделювання моделей росту рослин. Ця система використовує текстові символи та певний набір правил для створення шаблонів, подібно до того, як граматика мови визначає правила побудови речень зі слів. Ця техніка, відома як L-система (скорочення від Lindenmayer system), може бути використана для генерації рекурсивних фрактальних візерунків, продемонстрованих у цьому розділі. L-системи також цінні, оскільки вони забезпечують механізм використання простих символів для управління фрактальними структурами, які вимагають складних і багатогранних правил створення.

Імплементація L-системи у p5.js вимагає роботи з рекурсією, трансформаціями та рядками тексту. У цьому розділі вже розглядалися рекурсії й перетворення, але використання рядків є новим. Ось короткий фрагмент коду, який демонструє три аспекти роботи з текстом, важливих для L-систем — створення, конкатенація та повторення рядків:

let message1 = "Hello!";

let message2 = message1 + " Goodbye!";

for (let i = 0; i < message.length; i++) {

  let character = message.charAt(i);

}

L-система складається з трьох основних компонентів:

• Алфавіт. Алфавіт L-системи містить допустимі символи, які можна включити. Наприклад, я міг би сказати, що алфавіт це $ABC$, тобто будь-яке валідне “речення” (рядок символів) у L-системі може містити лише ці три символи.
• Аксіома. Аксіома — це речення (створене за допомогою символів алфавіту), яке описує початковий стан системи. Наприклад, для алфавіту $ABC$ можливою аксіомою може бути рядок $AAA$ або $B$, або $ACBAB$.
• Правила. Правила створення L-системи описують способи трансформації речення. Правила застосовуються рекурсивно, починаючи з аксіоми, генеруючи нові речення знову і знову. Правило L-системи включає два речення: попереднє і наступне. Наприклад, правило $A → AB$ означає, що де б у реченні не зустрічалося $A$ (попередник), у наступному поколінні його слід замінити на $AB$ (наступника).

Я почну з простої L-системи. Фактично, це оригінальна L-система Лінденмаєра, яка моделює ріст водоростей. Ось її компоненти:

L-система має алфавіт із двох символів і два простих правила: замінити $A$ на $AB$ і замінити $B$ на $A$. Як і у випадку з рекурсивними фрактальними фігурами, я можу вважати кожне наступне застосування правил L-системи поколінням. Покоління 0, за визначенням, є аксіомою (тут це $A$), і кожне наступне покоління показує результат застосування породжувальних правил до поточного покоління. На малюнку 8.20 показано кілька поколінь розвитку цієї L-системи.

Як я можу реалізувати цю L-систему за допомогою коду? Я почну зі збереження рядка, що містить аксіому, у змінній. Я назву змінну current, оскільки вона завжди зберігатиме поточне покоління (починаючи з аксіоми):

let current = "A";

Знову ж таки, як і у випадку з Грою Життя та кривою Коха, тепер мені потрібен окремий рядок для наступного покоління:

let next = "";

Тепер настав час застосувати правила генерації до рядка current і записати результати до рядка next:

for (let i = 0; i < current.length; i++) {

  let c = current.charAt(i);

  if (c === "A") {

    next += "AB";

  } else if (c === "B") {

    next += "A";

  }

}

Після завершення циклу for, значення змінної current присвоюється у змінну next:

current = next;

Щоб переконатися, що цей код працює, я запакую його у функцію під назвою generate() і використаю цикл для кількох її послідовних викликів, малюючи поточний рядок на полотні.

let current = "A";

function setup() {

  createCanvas(640, 160);

  background(255);

  noLoop();

  for (let i = 0; i < 9; i++) {
    generate();

    textSize(16);
    textFont("courier");
    text(i + ": " + current, 4, 20 + i * 16);

  }

}

function generate() {

  let next = "";

  for (let i = 0; i < current.length; i++) {

    let c = current.charAt(i);

    if (c === "A") {
      next += "AB";
    } else if (c === "B") {
      next += "A";
    }

  }

  current = next;

}

Прямо зараз ви можете подумати: “Це все дуже цікаво, але в чому саме сенс? Зрештою, хіба цей розділ не має бути про малювання фрактальних візерунків? Я бачу, як рекурсивна природа структури речень L-системи пов’язана з рекурсивною природою фракталів, але як саме це візуально моделює ріст рослин? Наскільки я знаю, немає жодної рослини, яка дає паростки із літер $A$ і $B$”.

Досі я залишив недомовленим те, що в ці речення L-системи вбудовано інструкції для малювання, завдяки чому Лінденмаєр зміг перекласти рядки символів в органічні структури рослин. Щоб побачити як це працює, ось інший приклад системи:

Щоб перетворити це на малюнок, я перекладу алфавіт системи таким чином:

Озброївшись цим перекладом, я можу сприймати речення кожного покоління як інструкцію для малювання. На малюнку 8.21 показано результат.

Здається знайомим? Ця L-система породила множину Кантора!

Для простоти я використовую $AB$ як алфавіт, але багато L-систем замість них використовують символи $F, G, +, –, [, ]$. Ось що вони означають:

line(0, 0, 0, length);
translate(0, length);

translate(0, length);

rotate(angle);

rotate(-angle);

push();

pop();

Припускаючи, що я генерую речення з L-системи, я можу повторювати речення символ за символом і виконувати відповідний код для кожного символу:

for (let i = 0; i < sentence.length; i++) {

  let c = sentence.charAt(i);

  if (c === 'F') {
    line(0, 0, length, 0);
    translate(length, 0);
  } else if (c === 'G') {
    translate(length, 0);
  } else if (c === '+') {
    rotate(angle);
  } else if (c === '-') {
    rotate(-angle);
  } else if (c === '[') {
    push();
  } else if (c === ']') {
    pop();
  }

}

За допомогою цього коду та правильних умов L-системи я можу малювати неймовірно складні структури схожі на рослини. Ось L-система, яку я буду використовувати для наступного прикладу:

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

• rules: JavaScript об’єкт, який зберігає пари рядків-попередників і рядків-наступників для правила L-системи
• LSystem: клас для ітерації нового покоління L-системи
• Turtle: клас для керування читання речення L-системи й виконання його інструкцій для малювання на екрані

Я не буду описувати тут ці класи, оскільки вони просто дублюють код, який я вже опрацьовував у цьому розділі. Натомість я покажу, як усі елементи поєднуються в основному файлі sketch.js.

let lsystem;

let turtle;

function setup() {

  createCanvas(640, 240);

  let rules = {
    "F": "FF+[+F-F-F]-[-F+F+F]",
  };

  lsystem = new LSystem("F", rules);

  for (let i = 0; i < 4; i++) {
    lsystem.generate();
  }

  turtle = new Turtle(4, radians(25));
}

function draw() {

  background(255);

  translate(width / 2, height);

  turtle.render(lsystem.sentence);

}

У цій книзі я детально розглядав ООП у контексті таких класів, як Particle і p5.Vector. Однак у прикладі 8.9 ви можливо помітили простий об’єкт, який я використав під час ініціалізації змінної rules. Замість визначення класу Rule і виклику його конструктора з ключовим словом new, я ініціалізував змінну літералом об’єкта JavaScript. Завдяки парам ключ-значення це зручна структура даних для визначення правил перетворення для L-системи. Кожен ключ представляє символ у поточному поколінні, який потрібно замінити (у цьому випадку є лише один "F"), а значення цього ключа визначає заміну ("FF+[+F-F-F]-[-F+F+F]"). Хоча в цьому прикладі лише одне правило, ви можете створити додаткові правила як інші пари ключ-значення в літералі об’єкта.

Проєкт “Екосистема”

Залучіть у свою екосистему фрактали. Ось кілька можливостей:

• Додайте до середовища екосистеми рослиноподібні створіння.
• Скажімо, одна з ваших рослин схожа на фрактальне дерево. Чи можете ви додати листя, чи квіти на кінці гілок? Що робити, якщо листя може опадати з дерева (залежно від сили вітру)? Що, якщо додати фрукти, які істоти зможуть зривати та їсти?
• Спроєктуйте створіння з фрактальним візерунком.
• Використайте L-систему, щоб створити інструкції для руху створіння або його поведінки.