Boids — це модель штучного життя, створена Крейгом Рейнольдсом 1987 року, яка відтворює зграї птахів, косяки риб і рої комах. Кожен «боїд» дотримується лише трьох простих локальних правил, проте група в цілому породжує напрочуд живий, узгоджений рух — класичний приклад емерджентності. Сьогодні ті самі ідеї застосовують у масових сценах фільмів та ігор, для координації роїв дронів і у вивченні колективної поведінки тварин.
v' = v + w_s·S + w_a·A + w_c·C — нова швидкість
v' дорівнює старій швидкості v плюс зважені сили
розділення S, вирівнювання A та згуртованості
C. Ваги w_s, w_a, w_c —
це значення повзунків; кожна сила обмежена максимумом, щоб рух лишався плавним.
Boids від Рейнольдса дебютував у кіно у фільмі «Бетмен повертається» (1992) для анімації роїв кажанів і навали пінгвінів — одне з найперших застосувань автономних агентів-зграй у кінематографі.
Алгоритм Boids Крейга Рейнольдса показує, як три прості правила — розподіл, вирівнювання та злиття — породжують складну реалістичну поведінку зграї птахів, риб та комах.
Три правила керують кожним агентом: уникай сусідів (розподіл), рухайся в середньому напрямку групи (вирівнювання), тримайся поруч із центром групи (злиття). З цих локальних взаємодій виникає складна поведінка всієї зграї.
Перетягуй повзунки для налаштування сили кожного правила. Збільш злиття для щільних зграй, розподіл — для розосередженого руху. Зміни швидкість або напрямок вітру.
Алгоритм Boids опублікував Крейг Рейнольдс у 1987 році. У 1992-му він використовувся у фільмі «Бетмен повертається» для симуляції зграй кажанів — один із перших прикладів ШІ-масовки в кіно.
Ця симуляція запускає модель Boids Крейга Рейнольдса на до 600 автономних агентів у справжньому 3D-просторі, відрендереному за допомогою WebGL. Кожен конусоподібний агент керується лише трьома локальними правилами — розділенням, вирівнюванням і згуртованістю — застосованими до сусідів, знайдених у межах радіуса сприйняття. Жодної глобальної хореографії не існує; узгоджений рух зграї є суто емерджентним. Просторова хеш-сітка робить пошук сусідів ефективним, тож сотні боїдів плавно оновлюються щокадру всередині обмежувальної рамки з м'якими стінками.
Алгоритм зграї Рейнольдса 1987 року. Щокадру кожен боїд підсумовує три зважені сили керування — розділення (відштовхування від дуже близьких сусідів), вирівнювання (узгодження із середнім напрямком сусідів) та згуртованість (дрейф до середньої позиції сусідів) — після чого його швидкість стає v' = v + w_s·S + w_a·A + w_c·C, причому кожна сила обмежена, щоб рух лишався плавним.
Повзунки задають Count (50–600 боїдів), Speed, ваги Separation, Alignment та Cohesion (по 0–3 кожна) і Perception radius (1–12). Увімкніть Predator, щоб випустити червоного хижака, від якого зграя тікає, з власним повзунком Pred. speed. Натисніть Rebuild, щоб скинути, перетягуйте для обертання камери та прокручуйте для масштабування.
Boids від Рейнольдса дебютував у кіно у фільмі «Бетмен повертається» (1992), анімуючи рої кажанів і навалу пінгвінів — одне з найперших застосувань автономних агентів-зграй на екрані.
Boids — це алгоритм штучного життя, опублікований Крейгом Рейнольдсом 1987 року для відтворення зграй птахів, косяків риб і роїв комах. Кожен агент (об'єкт-птах, або боїд) дотримується трьох локальних правил керування без лідера й без централізованого плану, проте узгоджений груповий рух виникає сам собою. Це класична демонстрація того, як прості локальні взаємодії можуть породжувати складну глобальну поведінку.
Для кожного боїда симуляція сканує найближчих агентів у межах радіуса сприйняття й обчислює три вектори керування: розділення відштовхує від сусідів, що підійшли занадто близько, вирівнювання підлаштовує його напрямок під середню швидкість сусідів, а згуртованість тягне його до їхньої середньої позиції. Вони зважуються повзунками, обмежуються максимальною силою й додаються до поточної швидкості щокадру.
Кожен повзунок задає вагу (від 0 до 3) одного з правил керування. Підвищення Cohesion дає щільніші, густіші зграї; підвищення Separation розосереджує агентів і запобігає скупченню; підвищення Alignment змушує групу рухатися в єдинішому напрямку. Саме балансування цих трьох дає природний, закручений рух зграї, а екстремальні значення можуть розбити зграю чи стиснути її.
Радіус сприйняття (від 1 до 12 одиниць) задає, наскільки далеко кожен боїд може відчувати інших агентів. Малий радіус означає, що боїди реагують лише на найближчих сусідів, даючи розпорошеніші, фрагментованіші групи; великий радіус дозволяє кожному боїду реагувати на багатьох інших, породжуючи більші, синхронніші зграї. Симуляція також використовує цей радіус як розмір комірки своєї просторової хеш-сітки для швидкого пошуку сусідів.
Вона відображає головний принцип, підтверджений біологами — що зграйність виникає з локальних правил, а не з централізованого контролю — і лишається стандартною навчальною моделлю. Однак реальні шпаки відстежують приблизно фіксовану кількість найближчих сусідів (близько семи), а не все в межах фіксованого радіуса, і реальні тварини додають такі чинники, як обмеження зору та реакцію на хижака. Ця версія є вірним, ілюстративним наближенням, а не точною біологічною реконструкцією.
Симуляція Boids моделює зграйну поведінку птахів, косяки риб і рої комах за допомогою трьох простих локальних правил керування, винайдених Крейгом Рейнольдсом 1987 року. Кожен агент — так званий боїд, скорочення від «bird-oid object» — незалежно застосовує розділення (уникати скупчення), вирівнювання (узгоджувати напрямок із сусідами) та згуртованість (рухатися до центру сусідів) щокадру, без жодного центрального керування. Результат — напрочуд живий, узгоджений рух, що виникає повністю з локальних взаємодій, тому Boids є підручниковим прикладом емерджентної складності у штучному житті.
Рейнольдс уперше опублікував алгоритм на конференції SIGGRAPH 1987 року, і вже того ж десятиліття його застосували в кіно: фільм Тіма Бертона «Бетмен повертається» (1992) використав Boids для процедурної анімації роїв кажанів і навали пінгвінів. Сьогодні ця модель лежить в основі симуляції натовпу в іграх, координації роїв автономних дронів і біологічних досліджень колективної поведінки тварин.
Боїд (bird-oid object) — це змодельований автономний агент, який дотримується трьох локальних правил керування: розділення, вирівнювання та згуртованості. Модель створив Крейг Рейнольдс 1987 року, щоб відтворити емерджентну зграйність птахів, косяки риб і рої комах без жодної централізованої хореографії. Спостереження за кількома сотнями боїдів дає той самий закручений, злагоджений груповий рух, що спостерігається в реальних скупченнях тварин.
Повзунок Count задає кількість агентів (від 50 до 600); Speed — їхню базову швидкість руху. Повзунки Separation, Alignment і Cohesion зважують кожне з правил керування від 0 до 3 — підвищуйте Cohesion для щільніших зграй, підвищуйте Separation, щоб розосередити агентів, підвищуйте Alignment для синхронізованіших напрямків руху. Повзунок Perception radius (від 1 до 12 одиниць) керує тим, наскільки далеко кожен боїд відчуває сусідів. Увімкніть прапорець Predator, щоб випустити червоного хижака, від якого тікає зграя, і натисніть Rebuild, щоб скинути позиції. Перетягуйте, щоб обертати камеру; прокручуйте, щоб масштабувати.
Емерджентна поведінка виникає, коли глобальні патерни системи неможливо передбачити, розглядаючи лише окремі її частини. У Boids кожен агент дотримується всього трьох правил, що стосуються найближчих сусідів, проте група в цілому породжує узгоджені, схожі на пташині зграї, що розділяються навколо перешкод, знову збираються після порушень і обертаються разом. Жодне правило не каже «утвори зграю» — зграя є емерджентною властивістю локальних взаємодій, тому Boids лишається одним із найцитованіших прикладів у науці про складність і штучному житті.
Щокадру для боїда i зі швидкістю v і позицією p симуляція обчислює три вектори керування в межах радіуса сприйняття r: розділення S = сума (p_i - p_j) / |p_i - p_j|^2 для близьких сусідів j; вирівнювання A = середня швидкість сусідів, нормалізована до цільової швидкості; згуртованість C = (середня позиція сусідів - p_i), нормалізована й масштабована до цільової швидкості. Нова швидкість дорівнює v' = v + w_s * S + w_a * A + w_c * C, де w_s, w_a, w_c — ваги повзунків. Кожен вектор сили обмежується максимальною величиною (MAX_FORCE), щоб рух лишався плавним, а підсумкова швидкість обмежується 1.4 базової швидкості.
Наївна реалізація перевіряла б близькість кожної пари боїдів, що коштує O(N^2) операцій щокадру — надто повільно для 600 агентів при 60 кадрах на секунду. Ця симуляція використовує просторову хеш-сітку: щокадру всі боїди розподіляються по комірках сітки розміром із радіус сприйняття. Щоб знайти сусідів, боїд перевіряє лише навколишні 3x3x3 = 27 комірок замість повного списку, знижуючи середню вартість до O(N * k), де k — кількість боїдів у локальній комірці. Рендерер WebGL InstancedMesh потім малює всі конуси одним викликом відмальовки, мінімізуючи навантаження на GPU.
Емпіричні дослідження підтверджують, що реальна зграйність є локальною й децентралізованою, що узгоджується з принципом Boids. Однак дослідження шпакових зграй (зокрема Ballerini та ін., 2008) показують, що реальні шпаки взаємодіють із приблизно фіксованою кількістю найближчих сусідів — близько шести-семи — незалежно від щільності, а не з усіма агентами в межах фіксованого радіуса. Реальні тварини також враховують такі чинники, як обмеження кута зору, толерантність до шуму та специфічні маневри уникнення хижака. Boids є точною якісною моделлю механізму емерджентності, але не точною кількісною біологічною реконструкцією.
Крейг В. Рейнольдс, тоді працюючи в компанії Symbolics, представив алгоритм Boids у статті «Flocks, Herds, and Schools: A Distributed Behavioral Model» на конференції SIGGRAPH 1987 року. Рейнольдс придумав слово «боїд» як скорочення від «bird-oid object». Стаття мала революційне значення, оскільки показала, що переконливий колективний рух тварин може виникати з кількох простих локальних правил, а не зі сценарних траєкторій, і фактично започаткувала галузь симуляції автономних агентів у комп'ютерній графіці.
Boids належить до ширшої родини агентних та роїних моделей. Тісно пов'язані з ним: оптимізація мурашиною колонією (ACO), де віртуальні мурахи залишають феромонні сліди, що спрямовують колонію до їжі; оптимізація роєм часток (PSO), яка використовує подібні до Boids оновлення швидкості для пошуку оптимальних розв'язків; пізніші поведінки керування Рейнольдса (пошук, втеча, переслідування, ухилення, блукання); і клітинні автомати на кшталт «Гри в життя» Конвея. У біології той самий підхід використовують для моделювання роїв сарани, косяків сардин і навіть колективного руху бактерій та пішоходів.
Алгоритм Рейнольдса, або його похідні, застосовують у штучному інтелекті натовпу й трафіку у відеоіграх (серія Half-Life, системи ШІ Unreal Engine), у кіновізуальних ефектах для масових сцен із істотами (Володар перснів, Світова війна Z) та в архітектурному моделюванні потоку пішоходів для безпеки стадіонів і транспортних вузлів. У робототехніці та аерокосмічній галузі координація роїв кількох БПЛА використовує ту саму структуру розділення-вирівнювання-згуртованості, щоб утримувати формації дронів без зіткнень під час виконання спільної мети. Boids також з'являється в дослідженнях мережевої маршрутизації, де пакети розглядають як агентів, що орієнтуються в заторах.
Активні напрями досліджень включають топологічні правила взаємодії (сусіди визначаються за рангом, а не за відстанню), стійку до шуму зграйність поблизу переходу порядок-безлад (зв'язок зі статистичною фізикою й активною матерією), боїдів, каліброваних на основі GPS-траєкторій реальних тварин, та неоднорідні рої, де агенти мають різні ролі чи можливості. З інженерного боку, децентралізоване керування сотнями фізичних дронів у реальному часі — лише з локальним бездротовим зв'язком і бортовими сенсорами — залишається відкритою проблемою, що спирається на теорію Boids, як і проєктування стійких роїв, що зберігають згуртованість при відмові частини агентів.