Симуляція рою дронів — флокінг та керування формацією

1. Архітектура агента

Кожен дрон — це легкий об'єкт даних. Тримайте фізику та рендеринг окремо — цикл фізики виконується з фіксованим часовим кроком (напр., 60 Гц), тоді як Three.js рендерить із тією частотою, яку дозволяє GPU.

class Drone {
  constructor(id, x, y, z) {
    this.id       = id;
    this.pos      = new THREE.Vector3(x, y, z);
    this.vel      = new THREE.Vector3();
    this.acc      = new THREE.Vector3();
    this.target   = new THREE.Vector3();  // слот формації
    this.state    = 'FLOCK';              // FLOCK | FORM | AVOID | RETURN
    this.maxSpeed = 5.0;
    this.maxForce = 0.3;
    this.mesh     = null;                 // призначається рендерером
  }

  applyForce(f) {
    this.acc.add(f);
  }

  update(dt) {
    this.vel.addScaledVector(this.acc, dt);
    this.vel.clampLength(0, this.maxSpeed);
    this.pos.addScaledVector(this.vel, dt);
    this.acc.set(0, 0, 0);
  }
}

2. Рівень 1: флокінг Boids

Рівень Boids відповідає за уникнення зіткнень між дронами і надає рою органічного руху. Поєднуються три керувальні сили — ті самі правила, що й у класичному алгоритмі Рейнольдса (1987), але налаштовані для 3D:

function boidsForces(drone, drones) {
  const SEP_RADIUS  = 4;    // особистий простір (еквівалент у метрах)
  const VIEW_RADIUS = 12;
  const W_SEP       = 1.8;
  const W_ALI       = 1.0;
  const W_COH       = 0.8;

  const sep = new THREE.Vector3();
  const ali = new THREE.Vector3();
  const coh = new THREE.Vector3();
  let ns = 0, nv = 0;

  for (const other of drones) {
    if (other === drone) continue;
    const d = drone.pos.distanceTo(other.pos);
    if (d < SEP_RADIUS) {
      sep.addScaledVector(
        new THREE.Vector3().subVectors(drone.pos, other.pos).normalize(),
        1 / d); // зважуємо за оберненою відстанню
      ns++;
    }
    if (d < VIEW_RADIUS) {
      ali.add(other.vel);
      coh.add(other.pos);
      nv++;
    }
  }

  const total = new THREE.Vector3();
  if (ns > 0) total.addScaledVector(
    seek(drone, drone.pos.clone().add(sep)), W_SEP);
  if (nv > 0) {
    ali.divideScalar(nv).normalize().multiplyScalar(drone.maxSpeed);
    total.addScaledVector(steer(drone, ali), W_ALI);
    coh.divideScalar(nv);
    total.addScaledVector(seek(drone, coh), W_COH);
  }
  return total;
}

// Seek: керуємо до цілі на максимальній швидкості
function seek(drone, target) {
  const desired = new THREE.Vector3()
    .subVectors(target, drone.pos).normalize()
    .multiplyScalar(drone.maxSpeed);
  return steer(drone, desired);
}

function steer(drone, desired) {
  return desired.sub(drone.vel).clampLength(0, drone.maxForce);
}

3. Рівень 2: патерни формацій

Рівень формації призначає кожному дрону цільовий слот у світовому просторі. Далі дрон керує собою до свого слота. Коли drone.state === 'FORM', вага згуртованості Boids зменшується і додається сильна сила прямування до слота.

V-подібна формація (перелітні птахи)

function vFormationSlots(n, spacing = 4) {
  const slots = [];
  for (let i = 0; i < n; i++) {
    const side = i % 2 === 0 ? 1 : -1;
    const rank = Math.ceil(i / 2);
    slots.push(new THREE.Vector3(
      side * rank * spacing,    // X: ліве/праве крило
      0,                        // Y: та сама висота
      -rank * spacing * 0.8   // Z: позаду лідера
    ));
  }
  return slots; // slot[0] = лідер у початку координат
}

Формація кола

function circleFormationSlots(n, radius = 10) {
  return Array.from({length: n}, (_, i) => {
    const angle = (i / n) * Math.PI * 2;
    return new THREE.Vector3(
      Math.cos(angle) * radius, 0, Math.sin(angle) * radius);
  });
}

Формація сітки

function gridFormationSlots(n, cols = 4, spacing = 5) {
  return Array.from({length: n}, (_, i) => {
    const col = i % cols, row = Math.floor(i / cols);
    return new THREE.Vector3(
      (col - (cols - 1) / 2) * spacing,
      0,
      row * spacing);
  });
}

Щоб призначити слоти дронам, використовуйте жадібне призначення за найближчим сусідом, щоб мінімізувати сумарну відстань переміщення — або, для оптимального призначення з-понад ~30 дронами, розв'яжіть задачу про лінійне призначення (угорський алгоритм) через JavaScript-порт функції linear_sum_assignment зі scipy.

// Жадібне призначення слотів: кожен дрон бере найближчий до нього слот
function assignSlots(drones, slots) {
  const used = new Set();
  for (const d of drones) {
    let best = -1, bestDist = Infinity;
    for (let j = 0; j < slots.length; j++) {
      if (used.has(j)) continue;
      const dist = d.pos.distanceTo(slots[j]);
      if (dist < bestDist) { bestDist = dist; best = j; }
    }
    d.target.copy(slots[best]);
    used.add(best);
  }
}

4. Керування «лідер-послідовник»

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

function leaderFollowerForce(follower, leader, offsetLocal) {
  // Перетворюємо зміщення з локальної системи лідера у світову
  const leaderQ = new THREE.Quaternion()
    .setFromUnitVectors(
      new THREE.Vector3(0, 0, 1),
      leader.vel.clone().normalize()
    );
  const worldTarget = offsetLocal.clone()
    .applyQuaternion(leaderQ)
    .add(leader.pos);

  // Керування прибуттям: сповільнюємося, наближаючись до слота
  const d = follower.pos.distanceTo(worldTarget);
  const SLOW_RADIUS = 6;
  const speed = d < SLOW_RADIUS
    ? follower.maxSpeed * (d / SLOW_RADIUS)
    : follower.maxSpeed;

  const desired = worldTarget.clone()
    .sub(follower.pos).normalize().multiplyScalar(speed);
  return desired.sub(follower.vel).clampLength(0, follower.maxForce);
}

5. Уникнення перешкод — штучні потенціальні поля

Перешкоди створюють відштовхувальне потенціальне поле. Цілі створюють притягальне поле. Дрон рухається за сумарним градієнтом. Це швидко (O(1) на перешкоду) і добре працює для опуклих перешкод.

function obstacleAvoidForce(drone, obstacles) {
  const OBS_RADIUS = 8;  // радіус впливу
  const force = new THREE.Vector3();

  for (const obs of obstacles) {
    const diff = drone.pos.clone().sub(obs.center);
    const d = diff.length() - obs.radius; // відстань зазору
    if (d < OBS_RADIUS && d > 0) {
      // APF: F = k * (1/d - 1/OBS_RADIUS) * (1/d²) * unitVec
      const k = 50;
      const mag = k * (1 / d - 1 / OBS_RADIUS) * (1 / (d * d));
      force.addScaledVector(diff.normalize(), mag);
    }
  }
  return force.clampLength(0, drone.maxForce * 3);
}

6. Скінченний автомат агента

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

function updateDrone(drone, drones, obstacles, formation, dt) {
  const obsForce = obstacleAvoidForce(drone, obstacles);
  const inDanger = obsForce.length() > 0.5;

  if (inDanger) {
    drone.state = 'AVOID';
  } else if (drone.state === 'AVOID') {
    drone.state = formation ? 'FORM' : 'FLOCK';
  }

  switch (drone.state) {
    case 'FLOCK':
      drone.applyForce(boidsForces(drone, drones));
      break;
    case 'FORM':
      drone.applyForce(boidsForces(drone, drones).multiplyScalar(0.3));
      drone.applyForce(seek(drone, drone.target).multiplyScalar(2.0));
      break;
    case 'AVOID':
      drone.applyForce(obsForce);
      drone.applyForce(boidsForces(drone, drones).multiplyScalar(1.5));
      break;
  }

  drone.applyForce(obsForce); // застосовується завжди
  drone.update(dt);
}

7. Рендеринг у Three.js з InstancedMesh

Для 100+ дронів використовуйте THREE.InstancedMesh, щоб рендерити всіх дронів за один виклик відмалювання. Положення та кватерніон кожного дрона записуються в матрицю екземплярів щокадру.

// Створюємо instanced mesh для N дронів
const geo = new THREE.ConeGeometry(0.3, 1.0, 6);
geo.rotateX(Math.PI / 2);  // спрямовуємо вздовж осі Z
const mat = new THREE.MeshStandardMaterial({ color: 0x34d399 });
const mesh = new THREE.InstancedMesh(geo, mat, drones.length);
scene.add(mesh);

const dummy = new THREE.Object3D();
const _up    = new THREE.Vector3(0, 1, 0);

function syncInstancedMesh() {
  for (let i = 0; i < drones.length; i++) {
    const d = drones[i];
    dummy.position.copy(d.pos);
    if (d.vel.lengthSq() > 0.001) {
      dummy.quaternion.setFromUnitVectors(_up, d.vel.clone().normalize());
    }
    dummy.updateMatrix();
    mesh.setMatrixAt(i, dummy.matrix);
  }
  mesh.instanceMatrix.needsUpdate = true;
}

8. Посібник із налаштування