Boids: як 3 прості правила створюють поведінку зграї

Крейг Рейнольдс і народження Boids

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

Результат він опублікував у 1987 році в статті SIGGRAPH під назвою «Flocks, Herds, and Schools: A Distributed Behavioral Model» («Зграї, череди та косяки: розподілена поведінкова модель»). Симульовані агенти отримали назву Boids — скорочення від «bird-oid objects» («птахоподібні об'єкти»). Стаття стала однією з найцитованіших робіт у комп'ютерній графіці, а описаний у ній алгоритм використовується й досі, майже чотири десятиліття потому.

Глибоке відкриття полягало ось у чому: для отримання складної скоординованої поведінки не потрібні складні правила координації. Трьох простих локальних правил достатньо, щоб згенерувати реалістичну на вигляд поведінку зграї з будь-якої кількості незалежних агентів.

Три правила

Кожен boid дивиться на своїх сусідів у межах радіуса сприйняття і одночасно застосовує три керівні сили:

Правило 1: Розділення

Уникати сусідів, що надто близько.

Для кожного boid знаходять усіх сусідів у межах радіуса «надто близько» (зазвичай меншого за радіус сприйняття). Обчислюється вектор відштовхування, спрямований від кожного такого сусіда, зважений за близькістю — ближчі сусіди штовхають сильніше. Ці вектори підсумовуються, утворюючи керівну силу розділення.

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

Правило 2: Вирівнювання

Рухатися відповідно до середнього напрямку сусідів поруч.

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

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

Правило 3: Згуртованість

Рухатися до середньої позиції сусідів поруч.

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

Реалізація правил у коді

Базовий цикл оновлення для одного boid виглядає так:

for each boid b:
    neighbours = find_neighbours(b, perception_radius)

    sep = separation_force(b, neighbours)
    ali = alignment_force(b, neighbours)
    coh = cohesion_force(b, neighbours)

    b.velocity += sep * w_sep
                + ali * w_ali
                + coh * w_coh

    b.velocity = clamp(b.velocity, max_speed)
    b.position += b.velocity * dt

Простота вражає. Жодного центрального контролера, жодного обміну повідомленнями, жодного глобального стану. Кожен boid знає лише про свою безпосередню околицю. Проте запустіть це для 500 boids — і ви отримаєте поведінку, яку не відрізнити від справжньої хмари шпаків.

Емерджентна складність із локальних правил

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

Зграя не запрограмована. Зграя і є колективною поведінкою особин, що дотримуються локальних правил. У коді жодного окремого boid неможливо знайти «зграю». Вона існує лише на рівні сукупності.

Цей самий принцип виявляється в природі й науці всюди:

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

Налаштування параметрів

Класична модель Boids має кілька параметрів налаштування, які кардинально змінюють характер зграї:

• Радіус сприйняття — більший радіус означає, що кожен boid бачить більше сусідів. Утворюються більші зграї; поведінка стає скоординованішою, але менш реактивною.
• Вага розділення — збільште її, і особини розсіюються; зграя перетворюється на розсіяну хмару. Зменшіть, і boids щільно скупчуються, нереалістично проходячи один крізь одного.
• Вага вирівнювання — висока вага вирівнювання породжує щільні, дисципліновані формації. Низька — вихроподібні, органічні скупчення.
• Вага згуртованості — клей, що утримує зграю разом. Занадто висока — і зграя стискається в точку; занадто низька — і вона розсіюється.
• Максимальна швидкість — швидшим boids потрібно більше обчислювальних кроків на одиницю простору, щоб не пропустити взаємодії.
• Поле зору — справжні птахи не бачать безпосередньо позаду себе. Додавання сліпої зони позаду кожного boid робить поведінку реалістичнішою.

Застосування поза анімацією

Первісна мета Рейнольдса полягала в анімації для кіно, і Boids використовувався у незліченних постановках — рої кажанів у «Бетмен повертається», стадо гну в «Королі Леві» та багато інших. Але застосування нині виходять далеко за межі розваг.

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

Алгоритми оптимізації, натхненні Boids, включають оптимізацію рою частинок (Particle Swarm Optimisation, PSO), де популяція кандидатних розв'язків рухається простором пошуку, використовуючи аналоги розділення, вирівнювання та згуртованості. PSO конкурує з генетичними алгоритмами для задач неперервної оптимізації і має перевагу у вигляді дуже малої кількості гіперпараметрів для налаштування.

Симуляція дорожнього руху використовує похідні Boids моделі для динаміки пішохідних натовпів — евакуацій, фестивальних натовпів, виходу зі стадіонів. Парадигма «особина слідує локальним правилам» природно відтворює те, як люди орієнтуються в натовпі.

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

Розширення Boids

Оригінальна модель із трьома правилами — лише відправна точка. Дослідники та розробники додали безліч розширень:

• Уникнення перешкод — додайте силу відштовхування від стін і перешкод, зважену за близькістю. Boids навігують крізь складну геометрію.
• Динаміка «хижак-жертва» — додайте поведінку «втечі», що активується, коли хижак потрапляє в радіус сприйняття. Це породжує реалістичні патерни розсіювання й повторного об'єднання.
• Прагнення до цілі — додайте слабку силу, що притягує всіх boids до цільового місця. Зграя мігрує, зберігаючи внутрішню структуру.
• Гетерогенні агенти — різні види з різними правилами можуть співіснувати, породжуючи змішані зграї, подібні до тих, що спостерігаються у справжніх міграціях птахів.