Розділ 0. Випадковість

Таблиці випадкових чисел

У 1947 році корпорація RAND випустила особливу книгу під назвою “A Million Random Digits with 100,000 Normal Deviates”. Книга не була літературним твором чи філософським трактатом про випадковість. Радше, це була таблиця випадкових чисел, згенерованих за допомогою електронної симуляції колеса рулетки. Ця книга була однією з останніх у серії таблиць випадкових чисел, створених із середини 1920-х до 1950-х років. З розвитком високошвидкісних комп’ютерів генерувати псевдовипадкові числа стало швидше, ніж зчитувати їх із таблиць, тому ця ера друкованих таблиць з випадковими числами остаточно завершилася.

---

Ось ми на самому початку. Якщо ви давно не програмували на JavaScript, або не займалися математикою, цей розділ допоможе вам повернутися до обчислювального мислення. Щоб почати свою подорож із кодування природи, я познайомлю вас із деякими базовими інструментами для програмування симуляцій: випадковими числами, випадковими розподілами та шумом. Думайте про цей розділ як про перший (нульовий!) елемент масиву, який складає цю книгу, — нагадування основ та ворота до можливостей, які чекають попереду.

У Розділі 1 я розповім про концепцію вектора і про те, як він буде слугувати будівельним блоком для моделювання руху в цій книзі. Але перед цим подумаймо про те, що означає рух чого-небудь на цифровому полотні. Я розпочну з однієї із найвідоміших і найпростіших симуляцій руху: випадкового блукання.

Випадкове блукання

Уявіть собі, що ви стоїте на середині гімнастичної колоди чи рейки. Кожні 10 секунд ви підкидаєте монету. Орел — крок вперед. Решка — крок назад. Це — випадкове блукання — шлях, визначений послідовністю випадкових кроків. Обережно зійшовши на підлогу, ви можете розширити своє випадкове блукання з одного виміру (переміщення лише вперед і назад) до двох вимірів (переміщення вперед, назад, ліворуч та праворуч). Тепер, маючи чотири можливі напрямки, вам для визначення наступного кроку потрібно підкидати монету двічі:

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

• Я хотів би розглянути концепцію об’єктно-орієнтованого програмування (ООП), яка лежить в основі цієї книги. Випадковий блукач, якого я збираюся створити, послужить шаблоном при використанні об’єктно-орієнтованого проєкту для створення об’єктів, які рухатимуться на полотні комп’ютерної графіки.
• Випадкове блукання спонукає два питання, які я буду ставити знову й знову впродовж усієї книги: “Як ви визначаєте правила, що керують поведінкою ваших об’єктів?” і “Як ви втілюєте ці правила у коді?”
• Для проєктів цієї книги вам, час від часу, буде потрібне базове розуміння випадковості, ймовірності й шуму Перліна. Випадкове блукання дозволить мені продемонструвати ключові моменти, які стануть в пригоді пізніше.

Спершу я трохи розгляну ООП, закодувавши клас Walker для створення об’єктів типу Walker, які зможуть робити випадкове блукання. Тут буде лише поверхневий огляд. Якщо ви раніше ніколи не працювали з ООП, вам може знадобитися більш комплексний матеріал для ознайомлення. У такому разі я пропоную зупинитися тут і переглянути розділ “Objects” мого відеокурсу “Code! Programming with p5.js” на сайті Coding Train.

Клас випадкового блукача

Об’єкт у JavaScript — це сутність, що має як дані, так і певну функціональність. В нашому випадку, об’єкт типу Walker повинен мати дані про своє положення на полотні й функціональні можливості, такі як здатність намалювати себе чи зробити крок.

Клас є шаблоном для створення конкретних екземплярів об’єктів. Уявіть клас, як форму для печива, а об’єкти як саме печиво. Щоб створити об’єкт Walker, я почну з визначення класу Walker, що описуватиме блукача.

Блукачу потрібні всього лише дві частини даних: одне число для його $x$-положення і друге число для його $y$-положення. Щоб встановити початкове положення об’єкта, я ініціалізую ці координати значеннями, що відповідатимуть центру полотна. Я можу зробити це у функції-конструкторі класу, яка має відповідну назву constructor(). Ви можете розглядати конструктор як функцію setup() у програмі p5.js. Він відповідає за визначення початкових властивостей об’єкта, подібно до того, як setup() робить це для всієї програми p5.js:

class Walker {

  constructor() {

    this.x = width / 2;
    this.y = height / 2;

  }

Зверніть увагу на використання ключового слова this для додавання властивостей об’єкту всередині самого об’єкта: this.x і this.y.

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

Перший метод show() включає код для малювання об’єкта у вигляді чорної точки. При посиланні на внутрішні властивості (змінні) об’єкта завжди використовуйте синтаксис this.:

  show() {
    stroke(0);
    point(this.x, this.y);
  }

Наступний метод step(), направлятиме кроки об’єкта Walker. Це той момент, коли речі стають трохи цікавішими. Пам’ятаєте, як ви робили кроки у випадкових напрямках на підлозі? Тепер, для зображення цієї підлоги, я використовуватиму полотно p5.js. Існують чотири можливих кроки. Крок вправо можна симулювати, збільшивши координату x за рахунок операції інкременту x++; крок вліво — зменшивши x за допомогою декременту x--; вперед — піднявшись на піксель вгору (y--); і назад — спустившись на один піксель вниз (y++). Але як код може вибрати один із цих чотирьох варіантів?

Раніше я казав, що можна підкидати дві монети. Проте у p5.js, коли вам потрібно зробити випадковий вибір зі списку варіантів, ви можете просто згенерувати випадкове число за допомогою функції random(). Вона повертає випадкове число з рухомою крапкою в межах потрібного вам діапазону. Тут я використовую число 4, щоб позначити діапазон значень від 0 до 4:

let choice = floor(random(4));

Я оголосив змінну choice і присвоїв їй випадкове число, округливши його до цілочисельного значення за допомогою функції floor(). Технічно кажучи, число згенероване після виклику random(4) знаходиться у діапазоні від 0 (включно) до 4 (не включно), тобто воно ніколи не може бути 4.0. Найбільше можливе число цього діапазону буде трохи нижче від 4 — 3.999999999 (з такою кількістю дев’яток після крапки, скільки дозволяє JavaScript), яке потім округляється за допомогою функції floor() до 3, видаляючи десяткову частину. Тож я фактично присвоюю змінній choice значення 0, 1, 2 або 3.

Далі, блукач виконує відповідний крок (вліво, вправо, вгору або вниз), в залежності від того, яке випадкове число було вибрано. Ось повний код методу step(), що завершує клас Walker:

  step() {

    let choice = floor(random(4));

    if (choice === 0) {

      this.x++;

    } else if (choice === 1) {

      this.x--;

    } else if (choice === 2) {

      this.y++;

    } else {

      this.y--;

    }

  }

}

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

let walker;

Потім, у функції setup(), створіть екземпляр об’єкта посилаючись на ім'я класу з оператором new:

function setup() {

  createCanvas(640, 240);

  walker = new Walker();
  background(255);

}

Нарешті, під час кожного циклу функції draw(), блукач робить крок і малює точку:

function draw() {

  walker.step();
  walker.show();

}

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

Я міг би внести до випадкового блукача кілька коригувань. По-перше, кроки цього Walker-об'єкта обмежені чотирма варіантами: вгору, вниз, ліворуч і праворуч. Але будь-який піксель на полотні може мати вісім можливих сусідів, включаючи діагональних (див. малюнок 0.1). Можливість залишитися на місці може бути дев'ятим варіантом.

Для імплементації об'єкта Walker, який може зробити крок на будь-який сусідній піксель або залишитися на місці, я міг би вибрати число від 0 до 8 (дев'ять можливих варіантів). Однак іншим способом реалізації нашого наміру буде вибір з трьох можливих кроків вздовж вісі $x$ (-1, 0 або 1) і трьох можливих кроків вздовж вісі $y$:

  step() {

    let xstep = floor(random(3)) - 1;
    let ystep = floor(random(3)) - 1;

    this.x += xstep;

    this.y += ystep;

  }

Я також можу позбутися функції floor() і напряму використовувати вихідні числа з рухомою крапкою від функції random(), щоб створити безперервний діапазон можливих довжин кроків від -1 до 1, як показано далі:

  step() {

    let xstep = random(–1, 1);
    let ystep = random(–1, 1);

    this.x += xstep;

    this.y += ystep;

  }

Всі ці варіації традиційного випадкового блукання мають спільну рису: в будь-який момент часу ймовірність того, що блукач зробить крок у певному напрямку, дорівнює ймовірності, що він зробить цей крок й у будь-якому іншому напрямку. Іншими словами, якщо є чотири можливих кроки, то шанс того, що блукач зробить будь-який з них дорівнює 1 з 4 (або 25%). З дев'ятьма можливими кроками цей шанс 1 з 9 (близько 11.1%).

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

let randomCounts = [];

let total = 20;

function setup() {

  createCanvas(640, 240);

  for (let i = 0; i < total; i++) {

    randomCounts[i] = 0;

  }

}

function draw() {

  background(255);

  let index = floor(random(randomCounts.length));
  randomCounts[index]++;

  stroke(0);

  fill(127);

  let w = width / randomCounts.length;

  for (let x = 0; x < randomCounts.length; x++) {
    rect(x * w, height - randomCounts[x], w - 1, randomCounts[x]);
  }

}

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

Імовірність і нерівномірний розподіл

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

Подумайте про те, коли ви вперше почали програмувати з p5.js. Можливо, ви хотіли намалювати багато кругів на екрані й сказали собі: “О, я знаю! Я намалюю всі ці круги у випадкових положеннях, із випадковими розмірами та випадковими кольорами”. Подібне засівання полотна за допомогою випадковості є цілком розумною відправною точкою коли ви вивчаєте основи комп’ютерної графіки, але в цій книзі я прагну будувати системи за зразком тих, що ми бачимо в природі, і рівномірна випадковість не завжди підходить для цього. Іноді терези випадковості потрібно схилити на певну користь.

Створення нерівномірного розподілу випадкових чисел буде корисним впродовж усієї книги. Наприклад, у Розділі 9 про генетичні алгоритми мені знадобиться методологія відбору — які представники популяції повинні бути вибрані, щоб передати свою ДНК наступному поколінню? Це схоже на дарвінівську концепцію виживання найпристосованіших. Скажімо, у вас є популяція мавп, що розвивається. Не кожна мавпа має рівні шанси на розмноження. Щоб симулювати дарвінівський природний відбір, ви не можете просто вибрати двох випадкових мавп для батьківства. Більш “пристосовані” повинні мати більше шансів для відбору. Це можна вважати ймовірністю найпристосованіших.

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

Якщо у вас є сценарій, де кожен результат так само вірогідний, як і інші, ймовірність виникнення даної події дорівнює кількості результатів, які відповідають цій події, поділеній на загальну кількість всіх можливих результатів. Простим прикладом є підкидання монети — воно має лише два можливі результати: орел або решка. Є лише один спосіб отримати орла, тому ймовірність того, що монета випаде орлом дорівнює одиниці поділеній на два: 1/2 або 50 відсотків.

Візьмемо колоду з 52 карт. Порахуємо ймовірність витягнути туза з цієї колоди:

Імовірність витягнути бубнову масть вираховується наступним чином:

Ви також можете обчислити ймовірність кількох послідовних подій, перемноживши окремі ймовірності кожної події. Наприклад, ймовірність того, що монета тричі поспіль випаде орлом, становить:

Це означає, що монета випадатиме орлом догори тричі поспіль в середньому один раз із восьми. Якби ви підкидували монету тричі поспіль 500 разів, то могли очікувати побачити результат із трьох послідовних орлів у середньому в одному із восьми випадків, або приблизно 63 рази.

let stuff = [1, 1, 2, 3, 3];

let value = random(stuff);

print(value);

П’ятиелементний масив має дві одиниці, тому для вибору одиниці цей код дає ймовірність 2 із 5 (2/5 або 40%). Подібним чином маємо ймовірність у 20 відсотків для виведення двійки й 40 відсотків для трійки.

Ви також можете згенерувати випадкове число й дозволити якійсь події відбутися лише якщо це число знаходиться у певному діапазоні. Для спрощення розглянемо лише випадкові значення від 0 до 1, наприклад:

let probability = 0.1;

let r = random(1);

if (r < probability) {
  print("Співай!");
}

Одна десята усіх значень від 0 до 1 буде меншою за 0.1, тому цей код призведе до співу лише у 10 відсотках випадків.

Ви можете використовувати той самий підхід, щоб застосувати нерівні ваги до кількох результатів. Скажімо, ви хочете, щоб спів відбувався з ймовірністю у 60 відсотків, танці — з ймовірністю у 10 відсотків, а сон — з ймовірністю у 30 відсотків. Знову ж таки, ви можете вибрати випадкове число від 0 до 1 і подивитися в який діапазон воно потрапляє:

• Від 0.0 до 0.6 (60 відсотків) → Спів
• Від 0.6 до 0.7 (10 відсотків) → Танці
• Від 0.7 до 1.0 (30 відсотків) → Сон

let num = random(1);

if (num < 0.6) {
  print("Співай!");

} else if (num < 0.7) {
  print("Танцюй!");

} else {
  print("Спи!");
}

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

• Імовірність руху вгору: 20 відсотків
• Імовірність руху вниз: 20 відсотків
• Імовірність руху вліво: 20 відсотків
• Імовірність руху вправо: 40 відсотків

  step() {

    let r = random(1);

    if (r < 0.4) {
      this.x++;

    } else if (r < 0.6) {

      this.x--;

    } else if (r < 0.8) {

      this.y++;

    } else {

      this.y--;

    }

  }

Нормальний розподіл випадкових чисел

Ще одним способом створення нерівномірного розподілу випадкових чисел є використання нормального розподілу, де більшість чисел групується навколо середнього значення. Щоб зрозуміти, чому це корисно, повернімось до імітації популяції мавп і припустімо, що ваша програма генерує тисячу об’єктів Monkey, кожен із випадковим значенням висоти від 200 до 300 (оскільки це світ мавп зі зростом від 200 до 300 пікселів):

let h = random(200, 300);

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

Саме так працює нормальний розподіл. Іноді його називають розподілом Гаусса на честь математика Карла Фрідріха Гаусса. Графік цього розподілу, неофіційно відомий як дзвоноподібна крива. Ця крива генерується математичною функцією, яка визначає ймовірність появи будь-якого даного значення як функцію середнього (часто записується грецькою літерою мю — $μ$) і стандартного відхилення (позначається грецькою літерою сигма — $σ$).

У випадку значень для зросту між 200 і 300 ви, ймовірно, маєте інтуїтивне відчуття, що середнє значення становить 250. Однак що, якщо я скажу, що стандартне відхилення дорівнює 3? Або 15? Що це означає для чисел? Графік, зображений на малюнку 0.2, повинен дати вам підказку.

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

Результати обчислюються наступним чином: у певній популяції 68 відсотків її членів матимуть значення в діапазоні одного стандартного відхилення від середнього, 95 відсотків — у межах двох стандартних відхилень, і 99.7 відсотків — у межах трьох стандартних відхилень. При стандартному відхиленні у 5 пікселів, лише 0.3 відсотка мавп будуть нижче 235 пікселів (три стандартних відхилення нижче середнього 250) або вище за 265 пікселів (три стандартних відхилення вище від середнього 250). Тим часом зріст 68 відсотків мавп буде між 245 і 255 пікселями.

На щастя, для використання нормального розподілу випадкових чисел у програмах p5.js, вам не потрібно робити жодні з цих обчислень вручну. Функція randomGaussian() виконує всю необхідну математику і повертає випадкові числа з нормальним розподілом:

function draw() {

  let num = randomGaussian();

}

Що далі? Що якщо, наприклад, нашою метою є призначення $x$-позиції для малювання фігури?

За замовчуванням функція randomGaussian() повертає нормальний розподіл випадкових додатних і від'ємних чисел із середнім значенням 0 і стандартним відхиленням 1. Що відомо як стандартний нормальний розподіл. Однак часто ці параметри за замовчуванням не підходять. Наприклад, ви хочете призначити випадковим чином $x$-позицію для фігури за допомогою нормального розподілу із середнім значенням 320 (центральний горизонтальний піксель у вікні шириною 640 пікселів) і стандартним відхиленням у 60 пікселів. У цьому випадку ви можете налаштувати параметри, передавши функції randomGaussian() два аргументи: середнє значення та стандартне відхилення.

function draw() {

  let x = randomGaussian(320, 60);

  noStroke();

  fill(0, 10);

  circle(x, 120, 16);

}

Тут я використовував аргументи для налаштування виклику функції randomGaussian(), але зауважте, що математика для реалізації цього налаштування досить проста: все, що вам потрібно зробити, це помножити значення стандартного нормального розподілу на стандартне відхилення, а потім додати середнє значення. Іншими словами, результат виконання функції randomGaussian(320, 60) з буде такий самий, що й у наступному коді:

let x = 60 * randomGaussian() + 320;

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

Власний розподіл випадкових чисел

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

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

Раніше я писав, що ви можете генерувати власні кастомізовані розподіли ймовірностей, заповнюючи масив певними значеннями (деякі з них можуть дублюватися для їх частішого вибору) або орієнтуючись на певні результати функції random(). Одним зі способів реалізації польоту Ле́ві може бути визначення 1-відсоткової ймовірності для того, щоб блукач робив великий крок:

let r = random(1);

if (r < 0.01) {
  xstep = random(-100, 100);
  ystep = random(-100, 100);

} else {

  xstep = random(-1, 1);

  ystep = random(-1, 1);

}

Однак це зводить ймовірність до фіксованої кількості варіантів: 99 відсотків часу — невеликі кроки, 1 відсоток часу — великі кроки. Що, якби ви натомість хотіли створити більш загальне правило: чим вище число, тим більша ймовірність його вибору. Наприклад, 0.8791 матиме більше шансів на вибір, ніж 0.8532, навіть якщо ця ймовірність лише трошки вища. Іншими словами, якщо $x$ є випадковим числом, то ймовірність його вибору можна зобразити на осі $y$ за допомогою функції $y = x$ (малюнок 0.3).

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

Одним із рішень для власного розподілу є вибір двох випадкових чисел замість одного. Перше випадкове число — це саме випадкове число. Однак друге я називатиму кваліфікаційним випадковим значенням. Воно вирішить чи використовувати це перше число, чи відкинути його та вибрати інше. Числа, які проходять легший відбір, вибиратимуться частіше, а числа з рідшою кваліфікацією — нечасто. Ось відповідні кроки де наразі я розглядаю лише випадкові значення від 0 до 1:

1. Виберіть випадкове число: r1.
2. Обчисліть ймовірність p, що визначатиме кваліфікацію для r1. Спробуємо p = r1.
3. Виберіть інше випадкове число: r2.
4. Якщо r2 менше за p, тоді ви знайшли своє число для використання і це r1!
5. Якщо r2 не менше за p, поверніться до кроку 1 і почніть спочатку.

Тут ймовірність того, що випадкове значення буде кваліфіковано, дорівнює самому випадковому числу, як зображено на малюнку 0.3. Наприклад, якщо r1 дорівнює 0.1, тоді r1 матиме 10-відсотковий шанс пройти кваліфікацію. Якщо r1 дорівнює 0.83, його ймовірність на кваліфікацію становитиме 83 відсотки. У цьому прикладі, чим вище число, тим більша ймовірність, що воно буде використано.

Цей процес називається алгоритмом прийняття-відхилення і є різновидом методу Монте-Карло (названого на честь казино Монте-Карло). У наступному прикладі представлено функцію, яка реалізує алгоритм прийняття-відхилення, повертаючи випадкове значення від 0 до 1.

function acceptreject() {

  while (true) {

    let r1 = random(1);

    let probability = r1;

    let r2 = random(1);

    if (r2 < probability) {
      return r1;
    }

  }

}

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

let step = 10;
let stepx = random(-step, step);
let stepy = random(-step, step);
this.x += stepx;
this.y += stepy;

Більш плавний підхід з шумом Перліна

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

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

Кен Перлін розробив оригінальний алгоритм шуму Перліна під час роботи над фільмом “Трон” на початку 1980-х років. Пізніше за цю роботу він отримав Оскар за досягнення у технічній сфері. Алгоритм був розроблений для створення процедурних текстур для комп’ютерних ефектів. Процедурний означає генерування візуальних елементів алгоритмічно, на відміну від художника, що розробляє їх вручну. Протягом багатьох років різні автори розробили низку інших шумів на різні смаки. Серед відомих: Value noise (шум Значення), Worley noise (шум Ворлі) та Simplex noise (Симплекс-шум, розроблений самим Перліном у 2001). Ви можете дізнатися більше про історію шуму на вебсайті Кена Перліна, а також про його варіації впродовж років у моєму відео “Що таке OpenSimplex шум?” на вебсайті Coding Train.

Бібліотека p5.js містить реалізацію класичного алгоритму шуму Перліна з 1983 року у функції під назвою noise(). Вона може приймати один, два або три аргументи, оскільки шум обчислюється в одному, двох або трьох вимірах. Я почну з демонстрації одновимірного (1D) шуму.

Скажімо, ви хочете намалювати на полотні круг у випадковому горизонтальному положенні. За звичкою ви можете використати для цього функцію random():

let x = random(0, width);

circle(x, 180, 16);

Тепер, замість випадкової $x$-позиції, вам потрібна плавніша $x$-позиція шуму Перліна. Ви можете подумати, що вам потрібно лише замінити функцію random() аналогічним викликом функції noise(), наприклад так:

let x = random(0, width);

let x = noise(0, width);
circle(x, 180, 16);

Концептуально це саме те, що ви хочете зробити — вираховувати значення $x$, яке знаходиться у межах від 0 до ширини полотна за допомогою функції шуму Перліна, але це не правильна реалізація. Аргументи функції random() вказують на діапазон можливих значень між мінімумом і максимумом, проте функція noise() працює іншим чином. Натомість вона має фіксований вихідний діапазон і завжди повертає значення від 0 до 1. За мить ви побачите, що можете легко обійти це обмеження за допомогою функції map(), але спочатку розглянемо, які саме аргументи очікує від вас функція noise().

Одновимірний шум Перліна можна розглядати як лінійну послідовність значень у часі. Наприклад:

Щоб отримати доступ до певного значення шуму, вам потрібно обрати “момент часу” і передати його функції noise(). Наприклад:

let n = noise(3);

Згідно з наведеною вище таблицею, noise(3) повертає 0.364. Наступним кроком є використання змінної для часу і постійне отримання значення шуму у функції draw():

let t = 3;

function draw() {

  let n = noise(t);

  print(n);

}

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

let t = 0;

function draw() {

  let n = noise(t);

  print(n);

  t += 0.01;

}

Я вирішив збільшувати змінну t на 0.01, але використання інших значень вплине на плавність шуму. Більші стрибки в часі, які перескакують вперед через простір шуму і повертають значення, виглядають менш плавно та більш випадково (малюнок 0.5).

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

Діапазони шуму

Коли у вас є значення шуму в діапазоні від 0 до 1, то ви можете зробити мапінг (зіставлення, масштабування, проєкціювання) цього діапазону на будь-який інший, який відповідає вашим цілям (малюнок 0.6). Зробити це найпростіше з функцією p5.js під назвою map(). Вона приймає п’ять аргументів. Перше — це значення, яке потрібно зіставити, у цьому випадку n. Далі вказується поточний діапазон значення (мінімум і максимум), а потім бажаний діапазон.

У цьому випадку, хоча шум має діапазон від 0 до 1, я хотів би намалювати круг з $x$-позицією в діапазоні від 0 до ширини полотна:

let t = 0;

function draw() {

  let n = noise(t);

  let x = map(n, 0, 1, 0, width);

  ellipse(x, 180, 16, 16);

  t += 0.01;

}

Таку ж логіку можна застосувати до випадкового блукання, використовуючи шум Перліна та відповідний мапінг для його $x$- і $y$-властивостей. Це створює плавніше, більш органічне випадкове блукання.

class Walker {

  constructor() {

    this.tx = 0;

    this.ty = 10000;

  }

  step() {

    this.x = map(noise(this.tx), 0, 1, 0, width);
    this.y = map(noise(this.ty), 0, 1, 0, height);

    this.tx += 0.01;
    this.ty += 0.01;

  }

}

Зверніть увагу, що для цього прикладу потрібна нова пара змінних: tx і ty. Це тому, що мені потрібно відстежувати дві змінні часу: одну для $x$-положення об’єкта Walker, а іншу для $y$-положення. Але в цих змінних є щось трохи дивне. Чому tx починається з 0, а ty з 10 000?

Хоча ці числа є довільними, я навмисно ініціалізував дві часові змінні різними значеннями, оскільки функція шуму є детермінованою: для певного часу t вона кожного разу повертає той самий результат. Якби я запитав значення шуму t одночасно для x і y, тоді x та y завжди були б однаковими, тобто об’єкт Walker рухався б лише по діагоналі. Замість цього я використовую дві різні частини простору шуму, починаючи з 0 для x і 10 000 для y, так що поведінка x та y положень виглядають незалежними одна від одної (малюнок 0.7).

По правді кажучи, тут немає фактичної концепції часу. Це корисна метафора, яка допомагає описати, як працює функція шуму, але насправді ви маєте справу з простором, а не часом. Графік на малюнку 0.7 зображує лінійну послідовність значень шуму в 1D просторі, розташованих вздовж лінії. Значення беруться у певній $x$-позиції, тому в прикладах ви часто побачите змінну з назвою xoff, яка вказує на зміщення по осі $x$ уздовж графіка шуму, а не змінну t для часу.

Двовимірний шум

Дослідивши концепцію значень шуму в одновимірному просторі, розгляньмо, як вони можуть існувати також і у двовимірному просторі (2D). У 1D шумі існує послідовність значень в якій будь-яке дане значення подібне до свого сусіда. Уявіть аркуш міліметрового паперу або папір в клітинку, де значення одновимірного шуму записані в одному рядку, одне значення на комірку. Оскільки ці значення знаходяться в одному вимірі, кожне має лише двох сусідів: значення, яке йде перед ним (ліворуч), і значення, яке йде після нього (праворуч), як показано зліва на малюнку 0.8.

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

Якщо ви візуалізуєте цю сітку із кожним значенням, зіставленим із яскравістю кольору, то отримаєте щось схоже на хмари. Білий колір сидить поруч зі світло-сірим, який сидить поруч із сірим, який сидить поруч із темно-сірим, який сидить поруч із чорним, який сидить поруч із темно-сірим і так далі (малюнок 0.9).

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

Якщо ви хочете розфарбувати кожен піксель полотна випадковим чином за допомогою функції random(), вам знадобиться вкладений цикл для перебору пікселів у рядках і стовпцях та вибір для них випадкової яскравості. Зауважте, що у p5.js пікселі послідовно розміщені в масиві з чотирма слотами на кожен піксель: червоним, зеленим, синім і альфа-каналом. Щоб отримати більше інформації, перегляньте відеоурок про масив пікселів у розділі “Pixels” на вебсайті Coding Train.

loadPixels();

for (let x = 0; x < width; x++) {

  for (let y = 0; y < height; y++) {

    let index = (x + y * width) * 4;

    let bright = random(255);

    pixels[index] = bright;
    pixels[index + 1] = bright;
    pixels[index + 2] = bright;

    pixels[index + 3] = 255;

  }

}

updatePixels();

Щоб забарвити кожен піксель з більш плавним переходом, ви можете зробити те саме, тільки замість виклику функції random() викликати функцію noise():

let bright = map(noise(x, y), 0, 1, 0, 255);

Концептуально це хороший початок — код обчислює значення шуму для кожної позиції $(x, y)$ у 2D просторі. Проблема в тому, що результат не матиме плавної хмарності, яку ви хочете. Одиниця буде завеликим стрибком для переходу через простір шуму від одного пікселя до наступного. Пам’ятайте, що з 1D шумом на кожний кадр анімації я збільшував змінну часу на 0.01, а не на 1!

Досить хорошим розв’язання цієї проблеми є використання інших змінних для аргументів шуму, ніж ті, які ви використовуєте для доступу до пікселів на полотні. Наприклад, у вкладених циклах ви можете збільшувати змінну під назвою xoff на 0.01 кожного разу, коли x збільшується на 1 для горизонтального напрямку, і змінну yoff на 0.01 кожного разу, коли y збільшується на 1 для вертикального напрямку, як показано далі:

let xoff = 0.0;

for (let x = 0; x < width; x++) {

  let yoff = 0.0;

  for (let y = 0; y < height; y++) {

    let bright = map(noise(xoff, yoff), 0, 1, 0, 255);

    let index = (x + y * width) * 4;

    pixels[index] = bright;
    pixels[index + 1] = bright;
    pixels[index + 2] = bright;
    pixels[index + 3] = 255;

    yoff += 0.01;

  }

  xoff += 0.01;

}

Мушу зізнатися, що зробив щось досить заплутане. Я використовував 1D шум, щоб встановити значення двом змінним (this.x і this.y), що контролюють 2D рух блукача. Потім я швидко перейшов до використання 2D шуму, щоб встановити значення одній змінній (bright) для контролю яскравості кожного пікселя на полотні.

Ключова відмінність тут полягає в тому, що моя мета для блукача полягала в тому, щоб він мав два незалежних 1D значення шуму. Це просто збіг, що я використовую їх для переміщення об’єкта у 2D просторі. Спосіб досягнення цього полягає у використанні двох різних зміщень (this.tx і this.ty), щоб отримувати значення з різних частин того самого 1D простору шуму. Тим часом у прикладі з 2D-шумом обидві змінні xoff і yoff починаються з 0, оскільки я шукаю лише одне значення (яскравість пікселя) для певної точки у 2D просторі шуму. Блукач фактично рухається двома окремими 1D шляхами шуму, тоді як пікселі є окремими значеннями у 2D просторі.

У цьому розділі я навів кілька традиційних способів використання шуму Перліна. Я присвоїв положенню об’єкта плавні значення 1D шуму, щоб налаштувати видимість блукання. За допомогою 2D шуму, використовуючи плавні значення, я створив хмароподібну текстуру на площині пікселів. Однак важливо пам’ятати, що значення шуму Перліна це просто значення. Вони за своєю суттю не прив’язані до розташування пікселів або якихось кольорів.

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

Так само як ви можете зловживати випадковістю, легко потрапити й у пастку надмірного використання шуму Перліна. Як об’єкт повинен рухатися? Шум Перліна! Як його розфарбувати? Шум Перліна! Як швидко він повинен зростати? Шум Перліна! Якщо це стає вашою відповіддю на кожне запитання, тоді продовжуйте читати! Моя мета — познайомити вас із всесвітом нових можливостей для визначення правил ваших систем. Зрештою, ви самі визначаєте ці правила, і що більше можливостей у вашому розпорядженні, то більш обґрунтований та усвідомлений вибір ви зможете зробити. Випадковість і шум Перліна — лише перші зірки у величезному космосі творчості, який ми досліджуватимемо у цій книзі.

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

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

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

Ось ілюстрація, яка допоможе вам згенерувати ідеї щодо створення екосистеми на основі тем, розглянутих у цій книзі. Спостерігайте за її розвитком із появою нових концепцій і технік у кожному наступному розділі.

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