Алгоритм Боїдів

1. Емерджентна поведінка

Емерджентність — це коли складна глобальна поведінка системи виникає з простих локальних правил взаємодії її частин. Жодна «пташка» у зграї не знає про траєкторію всієї зграї: вона реагує лише на найближчих сусідів.

Те саме відбувається у мурашиних колоніях (феромонні сліди), нейронних мережах, ринках і транспортних потоках. Боїди — найелегантніша ілюстрація цього принципу у комп'ютерній графіці.

2. Три правила Рейнольдса

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

3. Вектори та вага правил

Розлучення (Separation)

Для кожного сусіда j, що занадто близько (відстань d < r_sep), генеруємо вектор відштовхування, обернено пропорційний відстані:

Вирівнювання (Alignment)

Обчислюємо середню швидкість у групі та додаємо вектор, що «повертає» боїда до цього середнього:

Зближення (Cohesion)

Знаходимо центр мас групи та генеруємо вектор у напрямі до нього:

Комбінація

Типові ваги: w_sep = 1.5, w_align = 1.0, w_coh = 1.0. Зміна ваг кардинально міняє характер руху зграї: збільшення w_sep дає «пухку» зграю, збільшення w_coh — щільні підгрупи.

4. Радіус сприйняття та кут зору

Реальні тварини бачать лише частину навколишнього простору. Для реалістичності додають обмеження:

• Радіус сприйняття r_view — боїд бачить лише сусідів у цьому радіусі.
• Кут зору θ (наприклад, 270°) — боїд «сліпий» у мертвій зоні позаду. Перевіряємо: dot(forward, toNeighbor) > cos(θ/2).
• Мінімальна відстань розлучення r_sep < r_view — зазвичай 0.3–0.5 від r_view.

5. Просторова оптимізація

Без оптимізації пошук сусідів — O(N²). При 5000 боїдів це 25 мільйонів перевірок на кадр. Вирішення — просторовий поділ простору:

• Uniform grid — поділити зону на комірки розміром r_view. Для кожного боїда перевіряти лише 9 (2D) або 27 (3D) сусідніх комірок.
• Quadtree / Octree — адаптивне розбиття, краще для нерівномірно розподілених зграй.
• Sort + Binary search — сортуємо боїдів за Morton code (Z-order curve), бінарно шукаємо діапазон.

У нашій WebGL-симуляції використовується uniform grid з розміром комірки r_view. Це дає O(N) пошук сусідів і дозволяє симулювати 10 000+ боїдів у реальному часі у шейдерах.

6. Розширення: хижак, перешкоди, лідер

Хижак (Predator / Flee)

Додаємо правило з великою вагою: якщо хижак у радіусі r_flee, усі боїди в цьому радіусі отримують вектор утечі від хижака. Зграя «вибухає» на фрагменти і потім знову збирається.

Уникнення перешкод

Кидаємо промінь у напрямі руху боїда. Якщо знаходимо перешкоду на відстані d < r_avoid, відхиляємо курс перпендикулярно поверхні перешкоди.

Лідер зграї

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

7. Псевдокод

function stepBoids(boids, dt):

  // 1. Оновити просторовий хеш
  updateGrid(boids, cellSize = VIEW_RADIUS)

  for each boid i:

    // 2. Знайти сусідів у радіусі VIEW_RADIUS
    neighbors = getNeighbors(i, VIEW_RADIUS)
    close     = neighbors.filter(j => dist(i,j) < SEP_RADIUS)

    // 3. Правило 1: Розлучення
    v_sep = vec2(0, 0)
    for j in close:
      d = dist(i, j)
      v_sep += (pos[i] - pos[j]) / (d * d)

    // 4. Правило 2: Вирівнювання
    avg_vel = average(vel[j] for j in neighbors)
    v_align = avg_vel - vel[i]

    // 5. Правило 3: Зближення
    center = average(pos[j] for j in neighbors)
    v_coh  = center - pos[i]

    // 6. Сумарне прискорення (з вагами)
    a = W_SEP * v_sep + W_ALIGN * v_align + W_COH * v_coh

    // 7. Обмеження максимальної сили
    a = clampLength(a, MAX_FORCE)

    // 8. Оновити швидкість і позицію
    vel[i] = clampLength(vel[i] + a * dt, MAX_SPEED)
    pos[i] += vel[i] * dt

    // 9. Обернені межі (тороїдальний простір)
    pos[i] = wrap(pos[i], bounds)

Константи для старту: VIEW_RADIUS = 50, SEP_RADIUS = 20, MAX_SPEED = 200 px/s, MAX_FORCE = 400 px/s², W_SEP = 1.5, W_ALIGN = 1.0, W_COH = 1.0.