Boids: Три Правила, Якими Будується Стадо

Нікого не становить керівництво

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

У результаті отримується звичайний приклад емерджентного явища – поведінка, яка існує на рівні групи, але ніде не зафіксована в окремих тваринах. Немає правила, яке би казало «утворюйте стаю». Існують три правила щодо сусідів, і стая виникає як наслідок.

Три правила

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

РОЗ'ЄДНАННЯ – повертайтеся від сусідів, які занадто близько. Сумуйте (різницю між позицією бойда та позицією іншого бойда), зазвичай з вагою 1/відстані, щоб найближчий сусід домінував. Це запобігає зіткненням. Робота на короткій відстані.

СИНХРОНІЗАЦІЯ – повертайтеся в напрямку середнього значення орієнтації сусідів. Усереднюйте їх вектори швидкості, а потім керуйтеся, щоб відповідати. Це пояснює, чому зграя обертається разом. Робота на середній відстані.

ЗГІДНІСТЬ – повертайтеся до середньої позиції сусідів (їх центр маси). Це запобігає розчиненню зграї. Робота на великій відстані.

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

SEPARATION   steer AWAY from neighbours that are too close.
             Sum of (self.pos − other.pos), usually weighted by
             1/distance so that the nearest neighbour dominates.
             Prevents collisions. Short range.

ALIGNMENT    steer toward the AVERAGE HEADING of the neighbours.
             Average their velocity vectors, then steer to match.
             This is what makes the flock turn together. Mid range.

COHESION     steer toward the AVERAGE POSITION of the neighbours
             (their centre of mass). This is what keeps the flock
             from dissolving. Long range.

Направлення, а не телепортація

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

steer = desired − velocity // необхідна корекція steer = clamp(steer, maxForce) // у птаха обмежена сила м'язів acceleration += steer * weight // накопичуємо всі три правила velocity += acceleration; velocity = clamp(velocity, maxSpeed); // у птаха є максимальна швидкість position += velocity; acceleration = 0; // скидаємо кожним кадром Два обмеження несуть всю суть. maxForce обмежує різкість повороту, яку може зробити птах – це радіус повороту, і низьке значення дає широкі, плавні дуги великого птаха, а високе – миттєві ривки маленької риби. maxSpeed підтримує все в одному режимі. Без обмеження сили птах миттєво пристосовується до бажаної швидкості, і зграя виглядає як натовп магнітів; з ним корекції відбуваються поступово, і зграя набуває широких, відстаючих поворотів, які здаються природними. Два покращення майже завжди варті додавання. Поле зору: справжні тварини не бачать за собою, тому ігноруйте сусідів поза переднім кутом огляду (достатньо скалярного добутку з напрямком). І затримка з відповідністю швидкості непотрібна – але обмеження кількості сусідів необхідне. Оригінальна робота Рейнольдса використовувала радіус; пізніші дослідження на основі поведінки зірок вказали на те, що птахи відстежують приблизно фіксовану кількість найближчих сусідів, а не все в межах фіксованої відстані, що робить згуртованість зграї масштабованою. Обмеження списку сусідів до k найближчих (k близько 6–7) є дешевим і забезпечує значно більш стійкі зграї при різних щільностях.

steer = desired − velocity        // the correction needed
steer = clamp(steer, maxForce)    // a bird has finite muscles
acceleration += steer * weight    // accumulate all three rules

velocity += acceleration;
velocity  = clamp(velocity, maxSpeed);   // a bird has a top speed
position += velocity;
acceleration = 0;                        // reset every frame

Пошук сусідів – це основна вартість

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

Рішення те саме – рівномірна просторова хеш-сітка, яка використовується для частинок у рідинах. Виберіть розмір комірки, що дорівнює найбільшому радіусу сприйняття; тоді сусідів бойда можуть бути лише в його власній комірці та сусідніх – 9 комірок у 2D та 27 у 3D. Перебудовуйте сітку кожного кадру (це займає O(n) операцій, що є сортуванням), і запит стає пропорційним місцевій щільності замість загальної популяції.

cellSize = maxPerceptionRadius; key(p) = hash(floor(p.x / cellSize), floor(p.y / cellSize), floor(p.z / cellSize)); // кожен кадр buckets.clear(); for (const b of boids) buckets[key(b.pos)].push(b); for (const b of boids) for (const cell of the 27 cells around key(b.pos)) for (const other of buckets[cell]) { ...три правила... } Порівнюйте квадрат відстані з квадратом радіуса, а не саму відстань – це марна трата часу, тобто обчислення квадратного кореня для кожної пари, що становить мільйони пар. І накопичуйте три правила в одній проходці по списку сусідів замість трьох окремих проходів: суми для розділення, вирівнювання та згуртування можна побудувати за один крок – це значно ефективніше.

cellSize = maxPerceptionRadius;
key(p)   = hash(floor(p.x / cellSize), floor(p.y / cellSize),
                floor(p.z / cellSize));

// each frame
buckets.clear();
for (const b of boids) buckets[key(b.pos)].push(b);
for (const b of boids)
  for (const cell of the 27 cells around key(b.pos))
    for (const other of buckets[cell]) { ...three rules... }

За межами трьох правил

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

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

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

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

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

obstacle avoidance   cast a probe ahead of the boid; if it will hit
                     something, steer along the surface's normal. Weight
                     it far above the three social rules — a boid should
                     break formation rather than fly into a wall.

goal seeking         a steady pull toward a target point or path. This
                     is how you get migration, or a flock that follows
                     the cursor.

predator / flee      a strong, short-lived repulsion from a marked
                     agent. Add it and the flock splits and re-forms —
                     the "fountain effect" seen in real fish schools.

wander               a small, slowly-rotating random steering force.
                     Stops an isolated boid from flying dead straight
                     forever, and stops a settled flock from freezing.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте 3D Boids — Flocking і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.