Розділ 5. Автономні агенти

Риба Моі (фото надано національним управлінням океанічних і атмосферних досліджень США)

Шестипалі ниткопери (Polydactylus sexfilis), також відомі як риби королів або мóі на гавайський манір. Риба моі мала особливий статус для гавайської королівської сім’ї й вирощувалася у спеціальних ставках, щоб забезпечити зростання її популяції та запобігти вимиранню. Зграя проявляє витончений і злагоджений танець у своєму спільному русі, при цьому кожна окрема рибина тонко впливає та реагує на своїх сусідів.

---

Досі я демонстрував неживі об’єкти, розташовані на полотні бездушні фігури, які рухаються під впливом сил свого середовища. Але це Природа коду. Що, якби я міг вдихнути життя у ці фігури? Що, якби ці фігури могли жити за своїми власними правилами? Чи можуть фігури мати надії, мрії та страхи? Запитання такого роду є предметом, що розглядається у цьому розділі. Ці питання відокремлюють бездумні об’єкти від чогось набагато цікавішого: автономних агентів.

Внутрішні сили

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

Перехід від неживих об’єктів до автономних агентів є значним концептуальним стрибком, але кодова база при цьому майже не змінюється. “Бажання” автономного агента рухатися — це просто інша сила, подібно до сили тяжіння або сили вітру. Просто тепер сила надходить зсередини.

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

• Автономний агент має обмежену здатність до сприйняття свого довкілля. Цілком зрозуміло, що жива істота повинна бути обізнаною щодо свого середовища. Однак ця досвідченість стосується не лише зовнішнього середовища, а й внутрішнього стану агента — його положення, швидкості та інших потенційних властивостей чи навіть змодельованих емоцій. У цьому розділі я розглядатиму способи, якими агенти можуть враховувати свій власний стан під час прийняття рішень. Я також розгляну техніку програмування об’єктів зі збереженням посилань на інші об’єкти для “сприйняття” агентами свого оточення. Ще важливо враховувати частину про обмежену здатність. Чи маєте ви створити всезнавчу сутність, що рухатиметься по полотну й буде обізнана одразу про всі інші елементи на цьому полотні? Чи цей агент матиме можливість розгледіти інші об’єкти лише в межах 15 пікселів від себе? Звісно, однозначної відповіді на це питання немає, все залежить від того, що ви хочете. Я розгляну кілька можливостей протягом цього розділу, але загалом обмеження — це хороша річ для симуляції, щоб вона виглядала більш “природно”. Комаха, наприклад, може бути обмежена лише видимістю і запахами, які безпосередньо її оточують. Для моделювання істоти із реального світу, можна вивчити її фактичні обмеження з наукової точки зору. На щастя, я можу просто вигадати щось і спробувати це.

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

Існує багато варіантів з яких я міг би почати своє дослідження автономних агентів. Наприклад, штучне моделювання колоній мурах і термітів є фантастичною демонстрацією системи агентів. (Для отримання додаткової інформації про цю тему я рекомендую вам прочитати роботу Мітчела Резніка під назвою “Turtles, Termites, and Traffic Jams”.) Однак я хочу почати з розгляду поведінки агентів, яка базується на основі роботи перших чотирьох розділів цієї книги: моделювання руху за допомогою векторів та сил. Тож я повернуся до постійних героїв книги — спочатку до класу Walker, далі до класу Mover, а потім до класу Particle і надам йому ще одну інкарнацію.

Агенти й керування

Наприкінці 1980-х років комп’ютерний науковець Крейг Рейнольдс розробив алгоритмічні поведінкові моделі керування анімованими персонажами. Ці поведінкові моделі дозволяли окремим елементам орієнтуватися у своєму цифровому середовищі реалістичним чином, зі стратегіями для втечі, блукання, наближення, переслідування, ухиляння тощо. Пізніше, у своїй статті 1999 року під назвою “Steering Behaviors for Autonomous Characters” Рейнольдс, для опису своїх автономних агентів, використовує слово vehicle (засіб переміщення, авто, апарат — в цілому це будь-який об’єкт, що може самостійно пересуватися). Я піду тим же слідом і назву свій клас автономних агентів Vehicle:

class Vehicle {

  constructor() {

    this.position = createVector();

    this.velocity = createVector();

    this.acceleration = createVector();

  }

  /* Що ще мені потрібно додати? */

Подібно до класів Mover і Particle, рух класу Vehicle контролюється його векторами положення, швидкості та прискорення. Це зробить реалізацію поведінкової моделі для одного автономного агента досить простою. Але створюючи систему з кількох елементів, які самостійно керуються відповідно до простих, локально залежних правил, можуть виникати несподівано дивовижні рівні складності. Найвідомішим прикладом є модель “boids” Рейнольдса для поведінки зграї або рою, яку я продемонструю пізніше у прикладі 5.11.

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

1. Вибір дії: апарат має мету (або кілька) і може вибрати дію (або комбінацію дій) на основі цієї мети. По суті, це той момент на якому я зупинив попереднє обговорення автономних агентів. Апарат розглядає своє навколишнє середовище й обирає дію на основі бажання чи потреби: “Я бачу зомбі, що йде до мене. Оскільки я не хочу, щоб мої мізки були з’їдені, я збираюся втікати від зомбі”. Метою є збереження власних мізків, а дією — втеча. Стаття Рейнольдса описує багато намірів і пов’язаних з ними дій, таких як пошук цілі, уникнення перешкоди та слідування шляхом. За мить я почну створювати ці приклади за допомогою коду p5.js.
2. Керування: після вибору дії апарат має розрахувати свій наступний рух. Цей наступний рух буде силою — точніше, керувальною силою. На щастя, Рейнольдс розробив просту формулу керувальної сили, яку я використовуватиму у прикладах цього розділу: керувальна сила = бажана швидкість – поточна швидкість. Далі я детальніше розповім про цю формулу і поясню чому вона працює так ефективно.
3. Локомоція (сукупність рухів переміщення): здебільшого я збираюся ігнорувати цей третій рівень. У випадку з втечею від зомбі локомоцію можна описати як “крок лівою ногою, крок правою, лівою, правою, якнайшвидше”. Однак в межах полотна такий реальний рух для прямокутника, кола чи трикутника не має значення. Проте це не означає, що ви повинні повністю ігнорувати локомоцію. Ви можете знайти велику користь у роздумах про дизайн локомоції вашого агента і про можливі способи його анімації. Приклади в цьому розділі залишаться візуально простими, але гарною вправою була б розробка якоїсь додаткової анімації. Наприклад, ви можете додати обертання коліс, коливання весел або перебирання кінцівок.

Зрештою, найважливішим рівнем для нашого розгляду є вибір дії. Що являють собою елементи вашої системи і які їхні цілі? У цьому розділі я збираюся охопити серію керувальних поведінок (тобто дій): пошуку, втечі, слідування шляхом, слідування полем потоків, руху у зграї тощо. Нагадаю, як я вже говорив у інших розділах, що основна ідея полягає не в тому, щоб ви використовували саме вказані способи поведінки в усіх своїх проєктах. Скоріше, суть полягає в тому, щоб показати вам як у коді моделювати керувальну поведінку — будь-яку керувальну поведінку — і надати основу для проєктування та розробки ваших власних рухомих об’єктів з новими й захопливими ідеями та поведінкою.

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

Керувальна сила

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

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

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

Або ось як це можна записати у коді p5.js:

let steer = p5.Vector.sub(desired, velocity);

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

Якщо припустити наявність вектора p5.Vector під назвою target, який визначає позицію цілі, тоді маємо наступне:

let desired = p5.Vector.sub(target, position);

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

Агент бажає рухатися до цілі з максимально можливою швидкістю.

Іншими словами, вектор desired має вказувати від поточного положення агента до цільового положення об’єкта з магнітудою, що дорівнює максимально можливій швидкості агента, як показано на малюнку 5.3.

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

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

class Vehicle {

  constructor() {

    this.position = createVector();

    this.velocity = createVector();

    this.acceleration = createVector();

    this.maxspeed = ????;

  }

Потім, при обчисленні бажаної швидкості, я буду масштабувати її відповідно до максимальної швидкості:

let desired = p5.Vector.sub(target, this.position);

desired.setMag(this.maxspeed);

Зібравши все це разом, я тепер можу написати метод під назвою seek(), який отримує ціль типу p5.Vector і обчислює керувальну силу до цієї цілі:

  seek(target) {

    let desired = p5.Vector.sub(target,this.position);
    desired.setMag(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);

    this.applyForce(steer);

  }

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

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

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

У всьому цьому азарті я пропустив останній крок. Якого типу цей рухомий агент? Це витончений швидкісний суперкар із чудовою керованістю? Або великий міський автобус, якому потрібно більше простору і завчасно входити у поворот? Граціозна панда чи незграбний слон? У прикладі коду, як він є зараз, немає можливості враховувати цю варіацію керувальної сили. Для цього мені потрібно обмежити величину керувальної сили. Я називатиму це обмеження максимальною силою (maxforce у коді):

class Vehicle {

  constructor() {

    this.position = createVector();

    this.velocity = createVector();

    this.acceleration = createVector();

    this.maxspeed = ????;

    this.maxforce = ????;

  }

Тепер мені потрібно просто залучити це обмеження перед застосуванням керувальної сили:

  seek(target) {

    let desired = p5.Vector.sub(target, this.position);

    desired.setMag(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);

    steer.limit(this.maxforce);

    this.applyForce(steer);

  }

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

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

Ось повний клас Vehicle, який включає решту елементів класу Mover з Розділу 2.

class Vehicle {

  constructor(x, y) {

    this.position = createVector(x, y);

    this.velocity = createVector(0, 0);

    this.acceleration = createVector(0, 0);

    this.r = 6.0;

    this.maxforce = 8;
    this.maxspeed = 0.2;

  }

  update() {
    this.velocity.add(this.acceleration);
    this.velocity.limit(this.maxspeed);
    this.position.add(this.velocity);
    this.acceleration.mult(0);
  }

  applyForce(force) {
    this.acceleration.add(force);
  }

  seek(target) {
    let desired = p5.Vector.sub(target, this.position);
    desired.setMag(this.maxspeed);
    let steer = p5.Vector.sub(desired, this.velocity);
    steer.limit(this.maxforce);
    this.applyForce(steer);
  }

  show() {

    let angle = this.velocity.heading();
    fill(127);
    stroke(0);
    push();
    translate(this.position.x, this.position.y);
    rotate(angle);
    beginShape();
    vertex(this.r * 2, 0);
    vertex(-this.r * 2, -this.r);
    vertex(-this.r * 2, this.r);
    endShape(CLOSE);
    pop();

  }

}

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

Поведінка наближення

Попрацювавши трохи з поведінкою пошуку ви, ймовірно, запитаєте себе: “А якщо я хочу, щоб агент сповільнювався при наближенні до цілі?” Перш ніж я зможу почати відповідати на це запитання, мені слід пояснити, чому пошукова поведінка змушує агента пролітати повз ціль, спонукаючи його розвертатися і повертатися назад. Розглянемо мозок агента в процесі пошуку. Що він думає у кожному кадрі анімації?

• Я хочу якомога швидше рухатись до цілі.
• Я хочу якомога швидше рухатись до цілі.
• Я хочу якомога швидше рухатись до цілі.
• Я хочу якомога швидше рухатись до цілі.
• Я хочу якомога швидше рухатись до цілі.
• І так далі...

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

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

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

Як ви можете реалізувати цю поведінку наближення у коді? Пригадайте метод seek(). Яка частина коду встановлює величину бажаної швидкості?

   let desired = p5.Vector.sub(target, this.position);

   desired.setMag(this.maxspeed);

Цей підхід завжди встановлює величину вектора desired рівною значенню maxspeed, як показано на малюнку 5.7.

Що, якби величина бажаної швидкості натомість дорівнювала половині відстані?

   let desired = p5.Vector.sub(target, this.position);

   desired.mult(0.5);

Я все одно хотів би обмежити величину змінної desired не більше максимальної швидкості, щоб агенти, які знаходяться дуже далеко, не рухалися надто швидко (малюнок 5.8).

Хоча ця зміна добре демонструє мету прив’язки бажаної швидкості до відстані від цілі, це не дуже хороше рішення. Зрештою, відстань у 10 пікселів вже досить близька, а бажана швидкість у 5 досить велика. Бажана швидкість з величиною рівною, наприклад, 5 відсоткам від відстані, може спрацювати краще:

  let desired = p5.Vector.sub(target, this.position);

  desired.mult(0.05);

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

Іншими словами, якщо відстань до цілі менше ніж $r$, то бажана швидкість знаходиться між 0 і максимальною швидкістю, зіставленою відповідно до цієї відстані.

  arrive(target) {

    let desired = p5.Vector.sub(target, this.position);

    let d = desired.mag();

    if (d < 100) {

      let m = map(d, 0, 100, 0, this.maxspeed);
      desired.setMag(m);

    } else {

      desired.setMag(this.maxspeed);

    }

    let steer = p5.Vector.sub(desired, this.velocity);

    steer.limit(this.maxforce);

    this.applyForce(steer);

  }

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

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

Іншими словами, магія рівняння Рейнольдса desired - velocity полягає в тому, що воно, по суті, робить керувальну силу проявом помилки поточної швидкості: “Я мав би рухатися з такою-то швидкістю в цьому напрямку, але насправді рухаюся з такою-то швидкістю в іншому напрямку. Моя помилка полягає в різниці між тим, куди я хочу потрапити й тим, куди я прямую наразі”. Іноді це може призвести до начебто несподіваних результатів, як показано на малюнку 5.10.

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

Ваші власні поведінки

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

Наприклад, подивімося, як Рейнольдс визначає бажану швидкість для своєї поведінки блукання:

Блукання — це тип випадкового керування, яке має певний довготривалий порядок: керувальний напрямок в одному кадрі пов’язаний із керувальним напрямком у наступному. Це створює цікавіший рух ніж проста генерація випадкового керувального напрямку для кожного кадру.

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

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

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

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

Наведу ще один приклад, скажімо, я хочу створити керувальну поведінку під назвою “залишатись в межах стін”. Щоб визначити бажану швидкість, я встановлю правило: якщо агент наближається до стіни на відстань $d$, тоді він бажає рухатися з максимальною швидкістю в протилежному напрямку від цієї стіни (див. малюнок 5.12).

Я можу визначити для стін простір біля краю полотна зі значенням ширини у змінній offset зі значенням 25, і написати відповідний код за допомогою послідовності умовних операторів if.

  boundaries(offset) {

    let desired = null;

    if (this.position.x < offset) {
      desired = createVector(this.maxspeed, this.velocity.y);
    } else if (this.position.x > width - offset) {
      desired = createVector(-this.maxspeed, this.velocity.y);
    }
    if (this.position.y < offset) {
      desired = createVector(this.velocity.x, this.maxspeed);
    } else if (this.position.y > height - offset) {
      desired = createVector(this.velocity.x, -this.maxspeed);
    }

    if (desired !== null) {
      desired.normalize();
      desired.mult(this.maxspeed);
      let steer = p5.Vector.sub(desired, this.velocity);
      steer.limit(this.maxforce);
      this.applyForce(steer);
    }

  }

Вам може бути цікаво, чому в цьому методі boundaries() для змінної desired я на початку встановив значення null. Чому б просто не встановити їй нульовий вектор? Пам’ятайте, що керувальна сила дорівнює бажаній швидкості мінус поточна швидкість! Якщо агент буде рухатися зі швидкістю 0, то результівна сила сповільнить рух агента до його зупинки. Ініціалізуючи змінну desired значенням null і перевіряючи, що вона не рівна null перед застосуванням її для керівної сили, ми не вплинемо на агента, коли він знаходиться на достатній відстані від країв полотна.

Поле потоків

Ще однією керованою поведінкою Рейнольдса є слідування полем потоків. Але що таке поле потоків або як інакше кажуть векторне поле? Уявіть полотно у вигляді сітки (малюнок 5.13). У кожній комірці сітки є стрілка, яка вказує у певному напрямку — певний вектор. Коли агент рухається довкола полотна, він запитує: “Привіт, який піді мною вектор? Тепер це моя бажана швидкість!”

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

Перед тим, як написати додатковий код для класу Vehicle, щоб слідувати за полем потоків, мені спочатку потрібен клас, який описуватиме це поле. Оскільки поле потоків, по суті, є сіткою векторів, то 2D масив буде зручною структурою даних для його представлення, оскільки я зможу посилатися на кожен елемент комірки за допомогою двох індексів, стовпця і рядка сітки. Якщо ви не знайомі з 2D-масивами, пропоную переглянути мій відеоурок “2D Arrays in JavaScript”.

class FlowField {

  constructor() {

    this.resolution = ????;

    this.cols = ????;
    this.rows = ????;

    this.field = new Array(this.cols);
    for (let i = 0; i < this.cols; i++) {
      this.field[i] = new Array(this.rows);
    }

  }

Як заповнити пропущені значення? Припустімо, у мене є полотно 200 пікселів у ширину і 200 пікселів у висоту. Теоретично я можу створити поле потоків, яке матиме вектор для кожного окремого пікселя, що означає загалом 40 000 векторів ($200 \times 200$). Це не дуже необґрунтоване число, але у цій ситуації з вектором на піксель воно надмірне. Я можу легко обійтися, скажімо, одним вектором на кожні 10 пікселів ($20 \times 20 = 400$). Моя змінна resolution задаватиме розмір кожної комірки в пікселях. Потім я можу розрахувати кількість стовпців на основі розміру полотна, поділеного на роздільну здатність:

  constructor() {

    this.resolution = 10;

    this.cols = floor(width / this.resolution);

    this.rows = floor(height / this.resolution);

    this.field = new Array(this.cols);
    for (let i = 0; i < this.cols; i++) {
      this.field[i] = new Array(this.rows);
    }

  }

Тепер, коли я налаштував структуру даних для поля потоків, настав час визначити вектори цього поля. Як мені це зробити? Як я захочу! Можливо, я хотів би, щоб кожен вектор у полі потоків вказував направо (малюнок 5.14).

Для цього я можу просто встановити для кожного вектора значення (1, 0).

for (let i = 0; i < this.cols; i++) {
  for (let j = 0; j < this.rows; j++) {

    this.field[i][j] = createVector(1, 0);

  }

}

Можливо я захочу надати перевагу векторам, що вказують у випадкових напрямках як показано на малюнку 5.15.

Легка справа. Просто використайте метод random2D() з класу p5.Vector, щоб призначити його результівний вектор кожній комірці:

for (let i = 0; i < this.cols; i++) {

  for (let j = 0; j < this.rows; j++) {

    this.field[i][j] = p5.Vector.random2D();

  }

}

А як щодо використання 2D шуму Перліна (малюнок 5.16)?

Просто зіставте кожне значення шуму на значення кутів від $0$ до $2\pi$ та створіть з отриманого результату вектор:

let xoff = 0;

for (let i = 0; i < this.cols; i++) {

  let yoff = 0;

  for (let j = 0; j < this.rows; j++) {

    let angle = map(noise(xoff, yoff), 0, 1, 0, TWO_PI);

    this.field[i][j] = p5.Vector.fromAngle(angle);

    yoff += 0.1;

  }

  xoff += 0.1;

}

Нарешті я до чогось наближаюсь. Розрахунок напрямку векторів за допомогою шуму Перліна є чудовим способом імітації різноманітних природних ефектів, таких як нерегулярні пориви вітру або звивисте русло річки. Варто відзначити, що це відображення шуму генерує поле, яке віддає перевагу кутам спрямованим вліво. Оскільки шум Перліна має розподіл схожий на гаусівський, то більше шансів бути обраними мають кути біля значення $\pi$. Для протидії цій тенденції для створення малюнку 5.16 я використав діапазон від $0$ до $4\pi$, подібно до того, як я застосував $4\pi$ у Розділі 4, щоб представити діапазон кутів для обертання частинок конфетті. Зрештою, звісно, не існує одного правильного способу підготовки векторів поля потоків — це вам вирішувати, що ви хочете симулювати і який ефект потрібно досягти.

Вправа 5.6

Напишіть код для формування поля потоків де вектори обернені навколо центру полотна.

let x = i * width / cols;

let y = j * height / rows;

flowfield[i][j] = createVector(width / 2 - x, height / 2 - y);

flowfield[i][j].rotate(PI / 2);

Тепер, коли я маю 2D масив, у якому зберігаються вектори поля потоків, мені потрібен спосіб за допомогою якого агент зможе знайти бажану швидкість. Для цього я просто поділю $x$ і $y$ координати положення агента на роздільність сітки. Це дасть мені індекси потрібного вектора у 2D-масиві. Наприклад, якщо роздільність дорівнює 10, а агент знаходиться на координатах (100, 50), тоді мені потрібно знайти стовпець 10 і рядок 5:

let column = floor(this.position.x / this.resolution);

let row = floor(this.position.y / this.resolution);

Оскільки агент теоретично може вийти за межі полотна p5.js, корисно використовувати функцію constrain(), щоб переконатися, що ми не робимо пошук за межами масиву поля потоків. Ось метод під назвою lookup(), який я додам до класу FlowField, що приймає вектор (положення агента) і повертає відповідний вектор поля потоків для цього положення:

  lookup(position) {

    let column = constrain(floor(position.x / this.resolution), 0, this.cols - 1);
    let row = constrain(floor(position.y / this.resolution), 0, this.rows - 1);

    return this.field[column][row].copy();

  }

Перш ніж перейти до класу Vehicle, давайте розглянемо весь код класу FlowField з використанням шуму Перліна для формування векторних напрямків:

class FlowField {

  constructor(r) {

    this.resolution = r;

    this.cols = width / this.resolution;
    this.rows = height / this.resolution;

    this.field = new Array(this.cols);
    for (let i = 0; i < this.cols; i++) {
      this.field[i] = new Array(this.rows);
    }

    this.init();

  }

  init() {

    noiseSeed(random(10000));
    let xoff = 0;
    for (let i = 0; i < this.cols; i++) {
      let yoff = 0;
      for (let j = 0; j < this.rows; j++) {

        let angle = map(noise(xoff, yoff), 0, 1, 0, TWO_PI);
        this.field[i][j] = p5.Vector.fromAngle(angle);
        yoff += 0.1;

      }

      xoff += 0.1;

    }

  }

  lookup(position) {
    let column = constrain(floor(position.x / this.resolution), 0, this.cols - 1);
    let row = constrain(floor(position.y / this.resolution), 0, this.rows - 1);
    return this.field[column][row].copy();
  }

}

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

  follow(flow) {

    let desired = flow.lookup(this.position);
    desired.setMag(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);
    steer.limit(this.maxforce);
    this.applyForce(steer);

  }

Зверніть увагу, що lookup() є методом класу FlowField, а не Vehicle. Хоча натомість ви можете розмістити метод lookup() і в класі Vehicle. З моєї точки зору, розміщення його у FlowField краще відповідає принципу інкапсуляції ООП. Адже завдання пошуку полягає в отриманні вектора на основі позиції з поля потоків, який за своєю суттю прив’язаний до даних самого об’єкта FlowField.

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

Слідування шляхом

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

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

Скалярний добуток

Пам’ятаєте векторну математику, описану в Розділі 1? Додавання, віднімання, множення і ділення? На малюнку 5.17 наведено деякі із цих операцій.

Зверніть увагу, що множення представлене перемноженням вектора на скалярне значення. Це має сенс. Якщо ви хочете, щоб вектор був удвічі більшим (але мав той же напрям), помножте його на $2$. Якщо ви хочете, щоб він був удвічі меншим, помножте його на $0.5$. Однак існує кілька інших операцій, подібних до множення з використанням пари векторів, які корисні в певних сценаріях — скалярний добуток, перехресний добуток і так званий добуток Адамара. Наразі я збираюся зосередитися на скалярному добутку.

Припустимо наявність векторів $\vec{A}$ і $\vec{B}$:

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

Їх скалярний добуток це:

У p5.js це записується наступним чином:

let a = createVector(-3, 5);

let b = createVector(10, 1);

let n = a.dot(b);

Якщо ви зазирнете у код реалізації класу p5.Vector, то побачите досить просту реалізацію цього методу dot():

dot(v) {

  return this.x * v.x + this.y * v.y + this.z * v.z;

}

Ця формула досить проста, але чому скалярний добуток необхідний і коли він корисний в програмуванні? Одним з поширених використань скалярного добутку є визначення кута між двома векторами. Насправді скалярний добуток також може бути виражений як показано нижче:

Іншими словами, скалярний добуток $\vec{A}$ і $\vec{B}$ дорівнює магнітуді $\vec{A}$ помноженій на магнітуду $\vec{B}$ і помноженій на косинус тети (де тета — це кут між двома векторами $\vec{A}$ та $\vec{B}$).

Обидві формули скалярного добутку можна вивести одна з одної за допомогою тригонометрії, але я просто буду працювати з припущенням, що:

У цьому сценарії я знаю компоненти векторів, але я не знаю кут $\theta$ між ними (див. малюнок 5.18). Використовуючи формулу скалярного добутку, я можу знайти косинус $\theta$:

Щоб знайти $\theta$, я можу взяти обернений косинус, або арккосинус (у p5.js це функція acos) правої частини рівняння:

Виконаємо розрахунки з реальними числами:

У коді p5.js це виглядає так:

let a = createVector(10, 2);

let b = createVector(4, -3);

let angle = acos(a.dot(b) / (a.mag() * b.mag()));

Якщо ви ще раз покопаєтеся в нутрощах вихідного коду p5.js, то знайдете метод, який реалізує саме цей алгоритм:

  angleBetween(v) {

    let dot = this.dot(v);

    let angle = Math.acos(dot / (this.mag() * v.mag()));

    return angle;

  }

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

Є кілька речей, які варто зауважити про скалярний добуток:

• Якщо два вектори ($\vec{A}$ і $\vec{B}$) ортогональні (тобто перпендикулярні), їх скалярний добуток ($\vec{A}\cdot\vec{B}$) дорівнює 0.
• Якщо два вектори є одиничними, то їх скалярний добуток дорівнює косинусу кута між ними. Іншими словами $\vec{A}\cdot\vec{B}=\cos(\theta)$, якщо $\vec{A}$ і $\vec{B}$ мають довжину 1.

Тепер, після розгляду основи скалярного добутку, я можу повернутися до алгоритму слідування шляхом Рейнольдса.

Просте слідування шляхом

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

По-перше, як представити шлях? Для визначення шляху можна використати багато способів, але одним з простих є визначення шляху як послідовності з’єднаних точок, як показано на малюнку 5.20.

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

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

Тепер зберемо це у клас.

class Path {

  constructor() {

    this.radius = 20;

    this.start = createVector(0, height / 3);
    this.end = createVector(width, (2 * height) / 3);

  }

  show() {
    strokeWeight(this.radius * 2);
    stroke(0, 100);
    line(this.start.x, this.start.y, this.end.x, this.end.y);
    strokeWeight(1);
    stroke(0);
    line(this.start.x, this.start.y, this.end.x, this.end.y);

  }

}

Тепер припустімо, що рухомий агент знаходиться за межами радіуса шляху та переміщується з певною швидкістю, як на малюнку 5.22.

Першим кроком буде передбачення (за умови постійної швидкості), де цей агент буде в майбутньому:

let future = vel.copy();

future.setMag(25);

future.add(this.position);

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

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

Як знайти нормаль? Спочатку я можу визначити вектор (назвемо його $\vec{A}$), який вказує від початкової точки шляху до майбутнього положення агента:

let a = p5.Vector.sub(future, path.start);

Далі я можу визначити вектор (назвемо його $\vec{B}$), який вказує від початку шляху до його кінця:

let b = p5.Vector.sub(path.end, path.start);

Тепер, залучивши трішки тригонометрії (cah із sohcahtoa), я можу обчислити відстань від початку шляху до точки нормалі. Як показано на малюнку 5.24, це $||\vec{A}|| \times \cos(\theta)$.

Якби я тільки знав значення кута $\theta$, я міг знайти цю точку нормалі за допомогою наступного коду:

let d = a.mag() * cos(theta);

b.setMag(d);

let normalPoint = p5.Vector.add(path.start, b);

На щастя, якщо скалярний добуток чогось мене навчив, так це того, що за наявності двох векторів я можу обчислити кут між цими векторами!

let theta = p5.Vector.angleBetween(a, b);

let d = a.mag() * cos(theta);

b.setMag(d);

let normalPoint = p5.Vector.add(path.start, b);

Хоча цей код працюватиме, я можу зробити ще одне спрощення. Подивившись ще раз, ви побачите, що магнітуда вектора $\vec{B}$ встановлена як a.mag() * cos(theta), що являє собою:

Пригадайте наступне рівняння:

Тепер якщо $\vec{B}$ є одиничним вектором із довжиною 1, тоді:

Або простіше:

Коли $\vec{B}$ є одиничним вектором, тоді $||\vec{A}|| \times \cos(\theta)$ це те саме, що і скалярний добуток $\vec{A}$ та $\vec{B}$. Перетворити b на одиничний вектор дуже просто — достатньо викликати метод normalize(). Таким чином, я можу обійти обчислення theta за допомогою методу angleBetween() і спростити код:

let theta = p5.Vector.angleBetween(a, b);

let d = a.mag() * cos(theta);

b.setMag(d);

b.normalize();
b.setMag(a.dot(b));

let normalPoint = p5.Vector.add(path.start, b);

Цей процес масштабування $\vec{B}$ відповідно до точки нормалі широко відомий як скалярна проєкція. Ми кажемо, що $||\vec{A}||\times\cos(\theta)$ є скалярною проекцією $\vec{A}$ на $\vec{B}$, як на малюнку 5.25.

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

Я можу закодувати цю логіку за допомогою простого if оператора і використовувати свій попередній метод seek() для скерування агента, коли це необхідно:

let distance = p5.Vector.dist(future, normalPoint);

if (distance > path.radius) {

  this.seek(target);

}

Але де повинна бути ціль, якою має керуватись послідовник шляху? Алгоритм Рейнольдса передбачає вибір точки на шляху попереду нормалі. Оскільки я знаю вектор, який визначає шлях (це $\vec{B}$), я можу вичислити потрібну точку попереду додавши вектор, який вказує у напрямку $\vec{B}$ до вектора, що представляє точку нормалі, як на малюнку 5.27.

Я скажу, що ціль має бути, наприклад, на 25 пікселів попереду нормалі:

let distance = p5.Vector.dist(future, normalPoint);

if (distance > path.radius) {

  b.setMag(25);

  let target = p5.Vector.add(normalPoint, b);

  this.seek(target);

}

Зібравши все це разом, отримаємо у класі Vehicle метод слідування шляхом.

  follow(path) {

    let future = this.velocity.copy();
    future.setMag(25);
    future.add(this.position);

    let normalPoint = getNormalPoint(future, path.start, path.end);

    let b = p5.Vector.sub(path.end, path.start);
    b.setMag(25);
    let target = p5.Vector.add(normalPoint, b);

    let distance = p5.Vector.dist(normalPoint, future);
    if (distance > path.radius) {
      this.seek(target);
    }

  }

Зауважте, що замість використання коду скалярного добутку та скалярної проєкції для пошуку точки нормалі я викликаю метод getNormalPoint(). У таких випадках корисно розділити код, який виконує конкретне завдання (знаходження точки нормалі) на окремий метод, який можна викликати за потреби. Метод приймає три векторні аргументи (див. малюнок 5.28): перший визначає точку $p$ у декартовому просторі (майбутнє положення агента), а другий і третій визначають відрізок між двома точками $a$ і $b$ (шлях).

  getNormalPoint(position, a, b) {

    let vectorA = p5.Vector.sub(position, a);

    let vectorB = p5.Vector.sub(b, a);

    vectorB.normalize();
    vectorB.mult(vectorA.dot(vectorB));

    let normalPoint = p5.Vector.add(a, vectorB);

    return normalPoint;

  }

Що я вже маю? У мене є клас Path, який визначає шлях як лінію між двома точками. У мене є клас Vehicle з методом слідування шляхом (за допомогою керування для пошуку цілі вздовж шляху). Загалом, це вже гідний приклад, але все ще до біса обмежений. Чого ще не вистачає?

Зробіть глибокий подих. Ми майже на місці.

Слідування шляхом з кількома сегментами

Що, якщо мені потрібно, щоб агент слідував складнішим шляхом, ніж просто одна пряма лінія? Можливо це, криволінійний шлях, який вигинається у різних напрямках, як на малюнку 5.29?

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

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

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

Якщо у вас є точка і нескінченно довга лінія, у вас завжди буде точка нормалі, яка торкається до лінії. Але якщо у вас є точка і скінченний відрізок, ви не обов’язково знайдете нормаль, що лежить на цьому відрізку. Якщо це станеться для будь-якого із сегментів, я можу виключити ці нормалі. Після того, як у мене залишаться лише ті нормалі, які знаходяться на шляху (лише дві на малюнку 5.31), я оберу найкоротшу з них.

Для переведення цього плану у код, я розширю клас Path, щоб у ньому був масив точок (а не лише початкова і кінцева).

class Path {

  constructor() {

    this.radius = 20;

    this.points = [];

  }

  addPoint(x, y) {
    let pathPoint = createVector(x, y);
    this.points.push(pathPoint);
  }

  show() {

    stroke(200);
    strokeWeight(this.radius * 2);
    noFill();
    beginShape();
    for (let pathPoint of this.points) {
      vertex(pathPoint.x, pathPoint.y);
    }
    endShape();

    stroke(0);
    strokeWeight(1);
    beginShape();
    for (let pathPoint of this.points) {
      vertex(pathPoint.x, pathPoint.y);
    }
    endShape();

  }

}

Тепер, коли клас Path оновлено, настала черга агента навчитися пристосовуватися до кількох лінійних сегментів. До цього він просто знаходив нормаль для одного сегмента. За допомогою циклу він може знайти нормалі для всіх сегментів:

for (let i = 0; i < path.points.length - 1; i++) {

  let a = path.points[i];

  let b = path.points[i + 1];

  let normalPoint = getNormalPoint(future, a, b);

Наступним кроком буде перевірка, чи точка нормалі дійсно знаходиться між точкам a і b. Оскільки я знаю, що в цьому прикладі шлях йде зліва направо, то можу перевірити чи x-компонента нормалі normalPoint знаходиться поза x-компонентами a і b:

   if (normalPoint.x < a.x || normalPoint.x > b.x) {

     normalPoint = b.copy();

   }

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

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

let target = null;

let worldRecord = Infinity;

for (let i = 0; i < path.points.length - 1; i++) {

  let a = path.points[i];

  let b = path.points[i + 1];

  let normalPoint = getNormalPoint(future, a, b);

  if (normalPoint.x < a.x || normalPoint.x > b.x) {

    normalPoint = b.copy();

  }

  let distance = p5.Vector.dist(future, normalPoint);

  if (distance < worldRecord) {
    worldRecord = distance;
    target = normalPoint.copy();
  }

  let dir = p5.Vector.sub(b, a);
  dir.setMag(25);
  target.add(dir);

}

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

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

Складні системи

Я сказав, що метою цього розділу було вдихнути життя в об’єкти, які рухаються на полотні p5.js. Ви пройшли довгий шлях, навчившись писати код для автономного агента і погравшись із прикладами його індивідуальної поведінки. Але це ще не місце для зупинки. Так, наш рухомий агент — це симульована істота, яка приймає рішення про те, як шукати, рухатися і слідувати. Але що то за життя, проведене в самотності, без любові й підтримки інших?

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

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

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

Ось три ключові принципи, якими я буду керуватися у своїй роботі зі складними системами:

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

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

• Нелінійність: цей аспект складних систем часто називають ефектом метелика — виразом придуманим математиком і метеорологом Едвардом Нортоном Лоренцом, піонером у дослідженні теорії хаосу. У 1961 році Лоренц вдруге запустив комп’ютерну симуляцію погоди й, можливо, щоб заощадити трохи часу, ввів вхідне початкове значення 0.506 замість 0.506127. Кінцевий результат повністю відрізнявся від результату першої симуляції. Говорячи більш виразно, теорія полягає в тому, що змах крила метелика на одному кінці світу, може спричинити значущі погодні зміни на іншому та зіпсувати ваші вихідні на пляжі. Його називають нелінійним, оскільки між зміною початкових умов і зміною результату немає лінійного відношення. Невелика зміна початкових умов може мати величезний вплив на результат. Нелінійні системи є надмножиною хаотичних систем. У Розділі 7 ви побачите, що навіть якщо у системі з багатьох нулів і одиниць ви зміните лише один біт, результат буде зовсім іншим.
• Конкуренція і співпраця: одним з інгредієнтів, який часто робить складну систему працездатною, є одночасна наявність конкуренції та співпраці між її елементами. У майбутній системі зграї буде три правила: вирівнювання, згуртованість і відокремлення. Вирівнювання і згуртованість вимагатимуть від елементів “співпраці”, щоб вони намагалися залишатися разом та рухатися разом. Однак правило відокремлення вимагатиме від елементів “конкурувати” за простір. Коли прийде час, спробуйте у симуляції відмовитися від співпраці чи конкуренції й ви побачите, як система втратить свою складність. Конкуренція і співпраця зустрічаються разом у живих складних системах, на відміну від неживих складних систем, таких як погода.
• Зворотний зв’язок: складні системи часто включають певний цикл, де вихідні дані системи повертаються у систему, щоб впливати на її поведінку в позитивному або негативному напрямку. Припустимо, ви вирішили їздити на роботу громадським транспортом щодня, оскільки це найнадійніше та найвигідніше рішення і ви невдоволені заторами та впливом автомобілів на навколишнє середовище. Ви не самотні: інші також переходять на громадський транспорт. Система стає більш ефективною і привабливою, обслуговуючи більше людей за ті ж ресурси, а тим часом рух автотранспорту зменшується. Однак з часом системі може бути важко задовольнити зростання попиту, що призведе до перевантаженості, затримок і підвищення тарифів для фінансування інфраструктурних поліпшень. У результаті ви й інші починаєте повертатися на автівки, збільшуючи транспортні затори та знову знижуючи ефективність громадського транспорту. З погіршенням трафіку, кошти від підвищення тарифів використовуються для покращення інфраструктури громадського транспорту (сподіваємось), що знову робить його привабливішим. Таким чином, вартість і ефективність громадського транспорту є одночасно вхідними даними системи (що визначають, чи вирішите ви ним користуватися, чи ні) і вихідними (ступінь завантаженості транспорту і подальші витрати та ефективність). Економічні моделі є лише одним із прикладів людської складної системи. Інші включають моду і тенденції, вибори, натовпи та транспортні потоки.

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

Імплементація групової поведінки (або давайте не будемо врізатися один в одного)

Управління групою об’єктів, звичайно, не нова концепція. Ви вже бачили це раніше — у Розділі 4, де я розробив клас Emitter для представлення загальної системи частинок. Там я використовував масив для збереження списку окремих частинок. Я почну з того з підходу тут і зберігатиму об’єкти Vehicle в масиві:

let vehicles;

function setup() {

  vehicles = [];
  for (let i = 0; i < 100; i++) {
    vehicles.push(new Vehicle(random(width), random(height)));

  }

}

Тепер, коли настав час маніпулювати всіма агентами у функції draw(), я можу перебирати масив і викликати необхідні методи:

function draw() {

  for (let vehicle of vehicles) {

    vehicle.update();

    vehicle.show();

  }

}

Можливо, варто додати якусь поведінку, силу для застосування до всіх агентів. Це може бути слідування за курсором:

    vehicle.seek(mouseX, mouseY);

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

    vehicle.separate();

Це виглядає добре, але не зовсім правильно. Чогось не вистачає? У випадку з методом seek(), я казав: “Шукайте mouseX і mouseY”. У випадку з методом separate(), я кажу: “Відокремтеся від усіх інших”. Хто такі усі інші? Це список усіх інших агентів або об’єктів:

    vehicle.separate(vehicles);

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

let vehicles;

function setup() {

  createCanvas(640, 240);

  vehicles = [];

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

    vehicles.push(new Vehicle(random(width), random(height)));

  }

}

function draw() {

  background(255);

  for (let vehicle of vehicles) {

    vehicle.separate(vehicles);

    vehicle.update();

    vehicle.show();

  }

}

Звісно, це тільки початок. Справжня робота відбувається всередині самого методу separate(). Рейнольдс визначає поведінку відокремлення як “Керування для уникнення скупчення”. Іншими словами, якщо певний об’єкт занадто близько до вас, відхиляйтеся від нього. Звучить знайомо? Пам’ятаєте поведінку пошуку, коли агент спрямовується до цілі? Змініть цю силу на протилежну й отримаєте поведінку втечі, яку слід застосувати тут, щоб досягти відокремлення (див. малюнок 5.32).

Але що, якщо занадто близько знаходиться більше одного об’єкта? У цьому випадку я визначу відокремлення як середнє значення всіх векторів, спрямованих від будь-яких близьких об’єктів (малюнок 5.33).

Як перетворити це на код? Повернемося до методу під назвою separate(), який приймає як аргумент масив об’єктів типу Vehicle:

separate(vehicles) {

}

У цьому методі я переберу всі передані об’єкти та перевірю, чи є серед них такі, що розташовані занадто близько:

  let desiredSeparation = 20;

  for (let other of vehicles) {

    let d = p5.Vector.dist(this.position, other.position);

    if (this !== other && d < desiredSeparation) {

    }

  }

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

Якщо об’єкти знаходяться надто близько, я обчислюю вектор, що спрямований від об’єкта, який порушує правило відстані:

    if (this !== other && d < desiredseparation) {

      let diff = p5.Vector.sub(this.position, other.position);
      diff.normalize();

    }

  let sum = createVector();

  let count = 0;

  for (let other of vehicles) {

    let d = p5.Vector.dist(this.position, other.position);

    if (this !== other && d < desiredseparation) {

      let diff = p5.Vector.sub(this.position, other.position);

      diff.normalize();

      sum.add(diff);
      count++;

    }

  }

  if (count > 0) {

    sum.div(count);

  }

Отриманий середній вектор (збережений у змінній sum), можна масштабувати до максимальної швидкості та зробити бажаною швидкістю — агент бажає рухатися в цьому напрямку з максимальною швидкістю! (Насправді мені більше не потрібно ділити на count, оскільки магнітуду задано вручну.) І як тільки у мене буде бажана швидкість, матимемо ту саму стару історію Рейнольдса — steering = desired - velocity:

  if (count > 0) {

    sum.setMag(this.maxspeed);

    let steer = p5.Vector.sub(sum, vel);

    steer.limit(this.maxforce);

    this.applyForce(steer);

  }

У наступному прикладі цей метод показано у повному обсязі.

  separate(vehicles) {

    let desiredSeparation = this.r * 2;

    let sum = createVector();

    let count = 0;

    for (let other of vehicles) {

      let d = p5.Vector.dist(this.position, other.position);

      if (this !== other && d < desiredSeparation) {

        let diff = p5.Vector.sub(this.position, other.position);

        diff.setMag(1 / d);

        sum.add(diff);

        count++;

      }

    }

    if (count > 0) {

      sum.setMag(this.maxspeed);

      let steer = p5.Vector.sub(sum, this.velocity);

      steer.limit(this.maxforce);

      this.applyForce(steer);

    }

  }

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

Поєднання поведінок

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

Коли у програмі залучено кілька керувальних сил, потрібен механізм для їх управління. Ви можете подумати: “Тут нічого нового. Ми весь час жонглюємо кількома силами”. І матимете рацію. Фактично, цей підхід з’явився ще у Розділі 2:

  let wind = createVector(0.001, 0);

  let gravity = createVector(0, 0.1);

  mover.applyForce(wind);

  mover.applyForce(gravity);

Тут є об’єкт типу Mover, який реагує на дві сили. Все це добре працює завдяки тому, що клас Mover був розроблений для акумулювання векторних сил у його вектор прискорення. Однак у цьому розділі сили випливають із внутрішніх бажань рухомих об’єктів (які тепер називаються vehicles). І ці бажання можуть мати вагу, щоб одні з них мали більший вплив, ніж інші. Наприклад, розглянемо програму, де всі агенти мають два бажання:

• Пошук позиції курсора.
• Відокремлення від об’єктів, які знаходяться занадто близько.

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

Для початку я додам метод з назвою applyBehaviors() до класу Vehicle для управління всіма поведінками:

applyBehaviors(vehicles) {

  this.separate(vehicles);

  this.seek(createVector(mouseX, mouseY));

}

Тут один метод відповідає за виклик інших методів, які застосовують сили — separate() і seek(). Я міг би почати порпатися всередині цих методів, щоб налаштувати вагу сили, яку вони обчислюють, але простіше було б попросити ці методи просто обчислити й повернути обраховану силу. Тоді я зможу налаштувати величину сил і застосувати їх до прискорення об’єкта в межах методу applyBehaviors():

  applyBehaviors(vehicles) {

    let separate = this.separate(vehicles);

    let seek = this.seek(createVector(mouseX, mouseY));

    this.applyForce(separate);
    this.applyForce(seek);

  }

Ось як цей новий підхід змінює метод seek():

  seek(target) {

    let desired = p5.Vector.sub(target, this.position);

    desired.setMag(this.maxspeed);

    let steer = p5.Vector.sub(desired, this.velocity);

    steer.limit(this.maxforce);

    this.applyForce(steer);

    return steer;

  }

Це незначна зміна, але надзвичайно важлива: вона дозволяє налаштувати величину цих сил в одному місці.

applyBehaviors(vehicles) {

  let separate = this.separate(vehicles);

  let seek = this.seek(createVector(mouseX, mouseY));

  separate.mult(1.5);
  seek.mult(0.5);

  this.applyForce(separate);

  this.applyForce(seek);

}

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

Флокування

Флокування (флокінг) або поведінка зграї — це групова поведінка тварин, характерна для багатьох живих істот, таких як птахи, риби й комахи. У 1986 році Рейнольдс створив комп’ютерну симуляцію поведінки зграї й задокументував алгоритм у своїй статті “Flocks, Herds, and Schools: A Distributed Behavioral Model”. Відтворення цієї симуляції в p5.js дозволить об’єднати всі концепції цього розділу:

1. Для реалізації правил флокування, я буду використовувати формулу керівної сили ($steering = desired - velocity$).
2. Ці керувальні сили будуть груповою поведінкою і вимагатимуть, щоб кожен агент сприймав усі інші об’єкти.
3. Я поєднаю і надам вагу декільком силам.
4. Результатом буде складна система — розумна групова поведінка виникне з простих правил флокування без наявності централізованої системи чи лідера.

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

Перш ніж почати, я повинен зауважити, що збираюся змінити назву класу Vehicle (знову). Щоб описати елементи системи зграї Рейнольдс використовує термін boid (боід або боїд — вигадане слово, що означає птахоподібний об’єкт). Я зроблю так само.

Є три правила, які регулюють зграю:

• Відокремлення (також відоме як уникнення або розділення): направлений рух для уникнення зіткнення з сусідами.
• Вирівнювання (також відоме як копіювання або узгодженість): направлений рух у тому ж напрямку, що й у сусідів.
• Когезія (також відоме як центрування або згуртованість): направлений рух у сторону центральної області своїх сусідів для того, щоб залишатися з групою.

Ці правила проілюстровано на малюнку 5.34.

Так само як у прикладі 5.8, де я поєднав відокремлення і пошук, я хочу, щоб клас Boid мав єдиний метод керування всіма трьома поведінками. Я назву його flock():

  flock(boids) {

    let separation = this.separate(boids);
    let alignment = this.align(boids);
    let cohesion = this.cohere(boids);

    separation.mult(1.5);
    alignment.mult(1.0);
    cohesion.mult(1.0);

    this.applyForce(separation);
    this.applyForce(alignment);
    this.applyForce(cohesion);

  }

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

  align(boids) {

    let sum = createVector(0, 0);
    for (let other of boids) {
      sum.add(other.velocity);
    }
    sum.div(boids.length);

    sum.setMag(this.maxspeed);

    let steer = p5.Vector.sub(sum, this.velocity);
    steer.limit(this.maxforce);
    return steer;

  }

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

У методі align(), я наразі розраховую середню швидкість усіх боїдів, хоча насправді маю враховувати лише боїди на певній відстані (див. малюнок 5.35). Цей поріг відстані, звісно, може бути змінним. Ви можете розробити боїди, які будуть бачити лише на відстань у 20 пікселів, або на відстань у 100 пікселів.

Я вже застосовував подібну логіку, коли впроваджував відокремлення, обчислюючи силу лише на основі інших об’єктів на певній відстані. Тепер я хочу зробити те саме для вирівнювання (і, зрештою, згуртованості):

  align(boids) {

    let neighborDistance = 50;

    let sum = createVector(0, 0);

    let count = 0;

    for (let other of boids) {

      let d = p5.Vector.dist(this.position, other.position);

      if ((this !== other) && (d < neighborDistance)) {

        sum.add(other.velocity);

        count++;

      }

    }

    if (count > 0) {

      sum.setMag(this.maxspeed);

      let steer = p5.Vector.sub(sum, this.velocity);

      steer.limit(this.maxforce);

      return steer;

    } else {
      return createVector(0, 0);
    }

  }

Як і у методі separate(), я додав умову this !== other, яка гарантує, що боїд не враховуватиме сам себе під час обчислення середньої швидкості. Ймовірно, це все одно працювало б, але постійне впливання кожного боїда на його власну швидкість може призвести до зворотного зв’язку, який порушить загальну поведінку.

Вправа 5.15

Чи можете ви переписати метод align(), щоб боїди бачили лише ті об’єкти, які потрапляють у зону їх прямої видимості?

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

  cohesion(boids) {

    let neighborDistance = 50;

    let sum = createVector(0, 0);

    let count = 0;

    for (let other of boids) {

      let d = p5.Vector.dist(this.position, other.position);

      if ((this !== other) && (d < neighborDistance)) {

        sum.add(other.position);
        count++;

      }

    }

    if (count > 0) {

      sum.div(count);

      return this.seek(sum);

    } else {

      return createVector(0, 0);

    }

  }

Також варто витратити час на написання класу Flock, який управлятиме всією групою боїдів. Він буде практично ідентичним класу ParticleSystem з Розділу 4, лише з однією невеликою зміною: коли я викликатиму метод run() на кожному об’єкті Boid (як я це робив для кожного об’єкта Particle), я передаватиму посилання на весь масив боїдів:

class Flock {

  constructor() {

    this.boids = [];

  }

  run() {

    for (let boid of this.boids) {

      boid.run(this.boids);

    }

  }

  addBoid(boid) {

    this.boids.push(boid);

  }

}

Залишається лише ініціалізувати зграю у функції setup() і запустити її у функції draw().

let flock;

function setup() {

  createCanvas(640, 240);

  flock = new Flock();

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

    let boid = new Boid(width / 2, height / 2);

    flock.addBoid(boid);

  }

}

function draw() {

  background(255);

  flock.run();

}

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

Вправа 5.17

У своїй книзі “Computational Beauty of Nature” (Bradford Books, 2000), Гері Флейк описує четверте правило для поля зору зграї: “Відсуньтеся убік від будь-якого боїда, який блокує поле зору”. Нехай ваші боїди дотримуються цього правила.

Ефективність алгоритмів (або чому моя програма працює так повільно?)

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

Зазвичай, коли я говорю про повільну роботу програм p5.js, то маю на увазі повільне малювання на самому полотні — чим більше елементів малюється, тим повільніше працює програма. Якщо ви пам’ятаєте обговорення з Розділу 4, то перехід на WebGL рендерер іноді полегшує цю проблему, дозволяючи малювати велику систему частинок швидше. Але у симуляціях подібних до флокінгу, сповільнення походить від самого алгоритму. Комп’ютерні вчені розглядають цю проблему у термінах великого $O$ (O-нотація), де $O$ означає порядок (від слова order). Це скорочення для опису ефективності алгоритму, щоб описати відносну кількість обчислювальних циклів потрібних для виконання алгоритму.

Розглянемо просту пошукову задачу. У вас є кошик, що містить 100 шоколадних ласощів і лише одна із них з чистого чорного шоколаду. Саме та, яку ви хочете з’їсти. Щоб знайти її, ви дістаєте солодощі із кошика по одній штуці. Можливо, вам пощастить і ви знайдете її з першої спроби, але у найгіршому випадку вам доведеться перевірити всі 100, перш ніж знайти потрібну. Щоб знайти одну річ зі 100, вам потрібно перевірити 100 речей (або щоб знайти одну річ серед $N$ речей, вам потрібно зробити перевірку $N$ разів). Для цього завдання велика $O$-нотація записується як $O(N)$. До речі, ця ж велика $O$-нотація описує й ефективність простої системи частинок. Якщо у вас $N$ частинок, вам потрібно пройти та відобразити ці частинки $N$ разів.

Тепер подумаймо про групову поведінку, таку як зграя. Для кожного об’єкта Boid вам потрібно перевірити швидкість і положення кожного іншого об’єкта Boid, перш ніж ви зможете розрахувати його керувальну силу. Припустимо, що у вас 100 боїдів. Для боїда №1 вам потрібно перевірити 100 боїдів, для боїда №2 потрібно перевірити 100 боїдів і так далі. Всього для 100 боїдів потрібно виконати 10 000 перевірок ($100 \times 100 = \text{10,000}$).

Ви можете подумати: “Не проблема. Комп’ютери швидкі. Вони досить легко можуть виконувати 10 000 операцій”. Але що, якщо у нас 1000 боїдів? Тоді ви маєте наступне:

Це вже дещо сповільнює програму, але вона певною мірою залишається доволі керованою. А як щодо 10 000 об’єктів?

Тепер все дійсно стає повільним. Дуже, дуже, дуже повільним.

Помітили закономірність? Коли кількість елементів збільшується у 10 разів, тоді кількість необхідних циклів збільшується у 100 разів. Тобто, зі збільшенням кількості елементів у $N$ разів, кількість необхідних циклів збільшується у $N \times N$ разів або $N^2$. У великій $O$-нотації це записується як $O(N^2)$.

Можливо, ви думаєте: “Не проблема. У зграї мені потрібно перевірити лише ті об’єкти, які поруч до поточного боїда. Отже, навіть якщо у мене 1000 боїдів, я можу просто переглянути, скажімо, по 5 найближчих об’єктів до кожного з них і тоді мені потрібно лише 5000 циклів обчислення”. Ви спиняєтеся на мить і починаєте думати: “Тож для кожного боїда мені просто потрібно перевірити всі об’єкти й знайти 5 найближчих і все в порядку!” Побачили заковику? Навіть якщо ви хочете переглянути лише найближчі елементи, єдиний спосіб дізнатися, які з них найближчі — це перевірити їх усіх.

Чи є якийсь інший спосіб?

Просторовий поділ

У своїй статті 2000 року “Interaction with Groups of Autonomous Characters”, Рейнольдс (сюрприз, сюрприз) запропонував метод для оптимізації алгоритмів зграй та інших групових дій, який називається bin-lattice spatial subdivision (часто скорочено називають binning) — поділ простору двовимірною сіткою. Цей метод полягає у розділенні простору симуляції на сітку менших клітин або комірок.

Уявіть, що полотно поділено на сітку з 10 рядків і 10 стовпців, що загалом складає 100 клітинок ($10 \times 10 = 100$). Тепер припустимо, що у вас є 2000 боїдів — число досить мале для ваших реальних бажань, але достатньо велике, щоб програма працювала доволі повільно ($\text{2,000} \times \text{2,000} = \text{4,000,000 циклів)}$. У будь-який момент кожен боїд потрапляє у певну клітину сітки, як показано на малюнку 5.36. Маючи 2000 боїдів і 100 клітин, на кожну комірку в середньому припадає приблизно по 20 об’єктів ($\text{2,000} \div 100 = 20$).

Тепер скажемо, що для застосування правил поведінки зграї для кожного боїда, вам потрібно переглянути лише ті об’єкти, які знаходяться у клітині цього боїда. Із середнім значенням у 20 боїдів на клітину, кожна комірка потребує 400 операцій ($20 \times 20 = 400$), а для 100 клітин це загалом 40 000 ($400 \times 100 = \text{40,000}$). Це значна економія порівняно з 4 000 000 циклів!

Для реалізації алгоритму двовимірного просторового поділу у p5.js мені знадобляться кілька масивів. Перший масив потрібен для зберігання всіх боїдів, так само як у початковому прикладі флокінгу:

let boids = [];

Другий — це 2D масив (перероблений з коду прикладу 5.4), який представляє клітини сітки:

let resolution = 40;

let cols = floor(width / resolution);
let rows = floor(height / resolution);

let grid = new Array(cols);
for (let i = 0; i < grid.length; i++) {
  grid[i] = new Array(rows);
}

Кожне значення у 2D масиві сітки саме по собі буде також масивом, який міститиме посилання на об’єкти Boid, які наразі знаходяться у цій комірці сітки. Якщо ви ведете облік, то це масив у масиві всередині масиву:

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

    for (let j = 0; j < rows; j++) {

      grid[i][j] = [];

    }

  }

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

function draw() {

  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j] = [];
    }
  }

  for (let boid of flock.boids) {

    let column = floor(boid.position.x / resolution);
    let row = floor(boid.position.y / resolution);

    column = constrain(column, 0, cols - 1);
    row = constrain(row, 0, rows - 1);

    grid[column][row].push(boid);

  }

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

  run(boids) {

    let column = floor(this.position.x / resolution);

    let row = floor(this.position.y / resolution);

    column = constrain(column, 0, cols - 1);

    row = constrain(row, 0, rows - 1);

    let neighbors = grid[column][row];
    this.flock(neighbors);
    this.update();
    this.borders();
    this.render();

  }

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

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

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

Структура даних квадродерева є ключовою для алгоритму Барнса-Хата, на який я посилався під час побудови симуляції N тіл у Розділі 2. Під час обчислення гравітаційних сил, цей метод використовує дерево квадрантів для апроксимації групи тіл в одне. Це суттєво зменшує кількість необхідних обчислень, дозволяючи симуляціям з великою кількістю тіл працювати ефективніше. Ви можете дізнатися більше про створення квадродерева і його застосування до системи флокінгу у відео Coding Challenge #98 на вебсайті Coding Train.

Ще кілька хитрощів оптимізації

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

• Використовуйте квадрат магнітуди (іноді кажуть квадрат відстані).
• Використовуйте синуси й косинуси з пошукових таблиць.
• Не створюйте безліч непотрібних об’єктів p5.Vector.

Кожну з цих порад докладно описано далі.

Використовуйте квадрат магнітуди

Що таке квадрат магнітуди й коли його слід використовувати? Згадайте, як обчислюється магнітуда вектора:

function mag() {

  return sqrt(x * x + y * y);

}

Магнітуда потребує добування квадратного кореня. Так і повинно бути! Зрештою, якщо вам потрібна магнітуда вектора, ви повинні розв’язати теорему Піфагора (ми робили це в Розділі 1). Однак, якщо ви можете якось уникнути добування квадратного кореня, ваш код працюватиме швидше.

Скажімо, ви просто хочете знати відносну магнітуду деякого вектора v. Наприклад, чи ця магнітуда більша за 10?

if (v.mag() > 10) {

  /* Якісь дії! */

}

Цей запис еквівалентний наступному:

if (v.magSq() > 100) {

  /* Якісь дії! */

}

А як розраховується квадрат магнітуди?

function magSq() {

  return x * x + y * y;

}

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

Використовуйте синуси й косинуси з пошукових таблиць

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

function draw() {

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

    print(sin(PI));

  }

}

Певно, це абсолютно безглуздий фрагмент коду, який ви б ніколи не написали. Але він ілюструє певну думку: якщо ви обчислюєте синус числа $\pi$ 10 000 разів, чому б просто не обчислити його один раз, зберегти це значення і звертатися до нього, коли це потрібно?

Це принцип, що лежить в основі таблиці пошуку синусів і косинусів. Замість виклику функцій синуса і косинуса у вашому коді щоразу, коли вони вам потрібні, ви можете створити масив, який зберігає результати синусів й косинусів для різних кутів від $0$ до $2\pi$ та просто отримувати попередньо обчислені значення, коли вони знадобляться. Наприклад, ось два масиви, які зберігають значення синусів і косинусів для кожного цілого кута від $0$ до $359$ градусів. Для спрощення я використовую тут режим обчислення кутів у градусах angleMode(DEGREES), але ту саму техніку можна застосувати з радіанами:

angleMode(DEGREES);

let sinvalues = [];

let cosvalues = [];

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

  sinvalues[i] = sin(i);

  cosvalues[i] = cos(i);

}

А що, якщо тепер вам потрібно надрукувати синус кута $\pi$ (або 180 градусів)?

let angle = 180;

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

  print(sinvalues[angle]);

}

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

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

Не створюйте безліч непотрібних об’єктів p5.Vector

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

Мушу визнати, що я можливо є найбільшим порушником, коли мова йде про створення надмірних об’єктів. Для написання чітких і зрозумілих прикладів я часто вирішую створювати додаткові об’єкти типу p5.Vector, коли це абсолютно не потрібно. Здебільшого це зовсім не проблема. Але іноді може нею бути. Подивіться на цей приклад:

function draw() {

  for (let v of vehicles) {

    let mouse = createVector(mouseX, mouseY);

    v.seek(mouse);

  }

}

Скажімо, у масиві vehicles 1000 об’єктів. Це означає, що я також створюю 1000 нових об’єктів типу p5.Vector для позиції курсора мишки кожного разу під час виконання функції draw(). На будь-якому сучасному ноутбуці або настільному комп’ютері ця програма, швидше за все, не викличе скарги, не працюватиме повільно і не матиме жодних проблем. Все-таки сучасні комп’ютери мають велику кількість оперативної пам’яті, тож JavaScript зможе створити й видалити 1 000 тимчасових об’єктів без жодних проблем.

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

function draw() {

  let mouse = createVector(mouseX, mouseY);

  for (let v of vehicles) {

    v.seek(mouse);

  }

}

Тепер я створюю лише 1 вектор замість 1000. Що ще краще, я можу зробити цей вектор глобальною змінною, а потім просто змінювати значення для властивостей x і y за допомогою методу set():

let mouse;

function setup() {

  mouse = createVector();

}

function draw() {

  mouse.set(mouseX, mouseY);

  for (let v of vehicles) {

    v.seek(mouse);

  }

}

Тепер я ніколи не створюю новий об’єкт p5.Vector, а просто використовую один і той самий об’єкт у всій програмі!

Я вже зізнався, що є головним порушником цього правила. Тож у прикладах книги ви знайдете багато можливостей зменшити кількість тимчасових об’єктів. Наприклад, ось уривок методу seek() із цього розділу:

    let desired = p5.Vector.sub(target, this.position);

    desired.normalize();

    desired.mult(this.maxspeed);

    let steer = p5.Vector.sub(desired,this.velocity);

    steer.limit(this.maxforce);

    return steer;

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

    let desired = p5.Vector.sub(target, this.position);

    desired.normalize();

    desired.mult(this.maxspeed);

    desired.sub(this.velocity);
    desired.limit(this.maxforce);
    return desired;

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

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

Використовуйте концепцію керувальних сил для керування поведінкою створінь у вашій екосистемі. Ось деякі ідеї та можливості:

• Створюйте зграї створінь.
• Використовуйте для створінь пошукову поведінку, щоб шукати їжу (для погоні за рухомою здобиччю розгляньте переслідування).
• Використовуйте поле потоків для налаштування середовища екосистеми. Наприклад, як поводиться ваша система, якщо створіння живуть у текучій річці?
• Створіть створіння з безліччю керувальних поведінок (розумну кількість, яку ви зможете додати). Подумайте про способи зміни ваги поведінок, щоб ви могли збільшувати чи зменшувати їх вплив, змінюючи значення на льоту. Як встановлюються початкові ваги для поведінок створінь? Які правила керують зміною ваги з часом?
• Складні системи можуть бути вкладеними. Чи можете ви зі зграї боїдів створити єдину істоту? І чи можете потім створити зграю таких створінь?
• Складні системи можуть мати пам’ять і бути адаптивними. Чи може історія вашої екосистеми вплинути на її поведінку у поточному стані? (Це може бути рушійною причиною того, як істоти регулюють свої ваги поведінкових сил.)