Боїди: 3 правила, емерджентна поведінка та небо з 10 000 птахів

Обіцянка: розум з нічого

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

Це все. Жодного спілкування, жодного лідера, жодного глобального стану. Кожен агент вибирає локальний радіус околиці та застосовує зважені сили. Емерджентний результат виглядає моторошно живим.

Наївний алгоритм — пошук сусідів O(n²)

Моя перша реалізація була проста й коректна: для кожного боїда пройтися по всіх інших боїдах і перевірити відстань. Для N боїдів це N × (N−1) / 2 порівнянь за кадр.

function updateBoid(i, boids) {
  let sep = new THREE.Vector3();
  let ali = new THREE.Vector3();
  let coh = new THREE.Vector3();
  let count = 0;

  for (let j = 0; j < boids.length; j++) {
    if (i === j) continue;
    const d = boids[i].pos.distanceTo(boids[j].pos);
    if (d < PERCEPTION_RADIUS) {
      // Розділення: відштовхнутись від близьких сусідів
      const diff = boids[i].pos.clone().sub(boids[j].pos).divideScalar(d * d);
      sep.add(diff);
      // Вирівнювання: середня швидкість
      ali.add(boids[j].vel);
      // Згуртованість: відстежувати центр мас
      coh.add(boids[j].pos);
      count++;
    }
  }

  if (count > 0) {
    ali.divideScalar(count).normalize().multiplyScalar(MAX_SPEED);
    coh.divideScalar(count).sub(boids[i].pos).normalize().multiplyScalar(MAX_SPEED);
  }

  // Зважена сума → прискорення
  boids[i].acc
    .add(sep.multiplyScalar(W_SEP))
    .add(ali.multiplyScalar(W_ALI))
    .add(coh.multiplyScalar(W_COH));
}

Чудово працює на 200 боїдах. На 2 000 виникають труднощі. На 10 000 вкладка браузера зависає — 100 мільйонів перевірок відстані за кадр.

Виправлення: сітка просторового хешування

Ключова ідея: боїда цікавлять лише сусіди в межах PERCEPTION_RADIUS. Можна розподілити боїдів у 3D-сітку комірок розміром PERCEPTION_RADIUS × PERCEPTION_RADIUS × PERCEPTION_RADIUS. Тоді для кожного боїда перевіряються лише навколишні 3×3×3 = 27 комірок замість усіх N боїдів.

const CELL = PERCEPTION_RADIUS; // розмір комірки = радіус сприйняття

function cellKey(x, y, z) {
  // Дискретизувати позицію у світі до індексу комірки
  const cx = Math.floor(x / CELL);
  const cy = Math.floor(y / CELL);
  const cz = Math.floor(z / CELL);
  return `${cx},${cy},${cz}`;
}

// Побудувати хеш кожен кадр
const grid = new Map();
for (const b of boids) {
  const key = cellKey(b.pos.x, b.pos.y, b.pos.z);
  if (!grid.has(key)) grid.set(key, []);
  grid.get(key).push(b);
}

// Потім у updateBoid: перевіряти лише 27 сусідніх комірок
function neighbourCells(pos) {
  const cx = Math.floor(pos.x / CELL);
  const cy = Math.floor(pos.y / CELL);
  const cz = Math.floor(pos.z / CELL);
  const cells = [];
  for (let dx = -1; dx <= 1; dx++)
    for (let dy = -1; dy <= 1; dy++)
      for (let dz = -1; dz <= 1; dz++)
        cells.push(`${cx+dx},${cy+dy},${cz+dz}`);
  return cells;
}

Кількість боїдів	Наївний O(n²)	Просторовий хеш
500	60 FPS	60 FPS
2 000	22 FPS	60 FPS
10 000	<1 FPS	58 FPS

Рендеринг: конуси, а не сфери

Кожен боїд — це ConeGeometry, спрямований у напрямку польоту, що рендериться через InstancedMesh. Кожен кадр я оновлюю матрицю екземпляра, щоб вона орієнтувалась за вектором швидкості, використовуючи quaternion.setFromUnitVectors.

const UP = new THREE.Vector3(0, 1, 0); // орієнтація конуса за замовчуванням
const dir = new THREE.Vector3();
const q = new THREE.Quaternion();

for (let i = 0; i < boids.length; i++) {
  dir.copy(boids[i].vel).normalize();
  q.setFromUnitVectors(UP, dir);

  dummy.position.copy(boids[i].pos);
  dummy.quaternion.copy(q);
  dummy.scale.setScalar(1);
  dummy.updateMatrix();
  mesh.setMatrixAt(i, dummy.matrix);
}
mesh.instanceMatrix.needsUpdate = true;

Хитрість зі швидкістю: виділити InstancedMesh на максимальну кількість один раз і ніколи не змінювати розмір. Оновлення матриць швидке (копіювання Float32Array). Створення та знищення GPU-буферів кожен кадр — повільне.

Налаштування ваг — де магія

Три ваги правил повністю контролюють характер зграї. Кілька прикладів з моїх експериментів:

• Висока розділеність, низька згуртованість → птахи розсіюються у вільні стрічки, як шпаки, що розсіюються після яструба
• Високе вирівнювання, низька розділеність → птахи вишиковуються в стрілоподібні формації, майже військової точності
• Висока згуртованість, низьке вирівнювання → птахи збираються у щільні кулі, що вирують — більше схоже на зграю риб, ніж на птахів
• Збалансовано (1 : 1,2 : 0,9) → відчуття «стандартного стайного польоту» — хвилі зміни напрямку, що прокочуються густою хмарою

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

Додавання хижака

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

// Правило 4: втеча від хижака
const threat = boid.pos.distanceTo(hawk.pos);
if (threat < FLEE_RADIUS) {
  const flee = boid.pos.clone().sub(hawk.pos)
    .normalize()
    .multiplyScalar(MAX_SPEED * 2.0); // паніка — подвійна швидкість
  boid.acc.add(flee.multiplyScalar(W_FLEE));
}

Чого я навчився

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

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