Boids: 3 reguły, zachowanie emergentne i niebo z 10 000 ptaków

Obietnica: inteligencja znikąd

Zanim zrozumiałem Boids, zakładałem, że realistyczne stadowanie musi wymagać złożonego planowania trasy: ptaki komunikujące się, budujące konsensus, zmieniające się liderem. Rzeczywistość jest niemal obraźliwie prosta. Każdy ptak zna dokładnie trzy rzeczy:

To wszystko. Bez komunikacji, bez lidera, bez stanu globalnego. Każdy agent próbkuje lokalny promień sąsiedztwa i stosuje ważone siły. Emergentny efekt wygląda niesamowicie żywo.

Naiwny algorytm — wyszukiwanie sąsiadów O(n²)

Moja pierwsza implementacja była prosta i poprawna: dla każdego boida przechodź przez wszystkie pozostałe boidy i sprawdzaj odległość. Dla N boidów daje to N × (N−1) / 2 porównań na klatkę.

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) {
      // Separacja: odpychaj od bliskich sąsiadów
      const diff = boids[i].pos.clone().sub(boids[j].pos).divideScalar(d * d);
      sep.add(diff);
      // Wyrównanie: średnia prędkość
      ali.add(boids[j].vel);
      // Kohezja: śledź środek masy
      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);
  }

  // Ważona suma → przyspieszenie
  boids[i].acc
    .add(sep.multiplyScalar(W_SEP))
    .add(ali.multiplyScalar(W_ALI))
    .add(coh.multiplyScalar(W_COH));
}

Działa świetnie przy 200 boidach. Przy 2000 zaczyna z trudem. Przy 10 000 karta przeglądarki się zawiesza — 100 milionów sprawdzeń odległości na klatkę.

Rozwiązanie: siatka hasza przestrzennego

Kluczowe spostrzeżenie: boidowi zależy tylko na sąsiadach w zasięgu PERCEPTION_RADIUS. Możemy pogrupować boidy w trójwymiarową siatkę komórek o rozmiarze PERCEPTION_RADIUS × PERCEPTION_RADIUS × PERCEPTION_RADIUS. Wtedy dla każdego boida sprawdzamy tylko 3×3×3 = 27 otaczających komórek zamiast wszystkich N boidów.

const CELL = PERCEPTION_RADIUS; // rozmiar komórki = promień percepcji

function cellKey(x, y, z) {
  // Dyskretyzuj pozycję w świecie do indeksu komórki
  const cx = Math.floor(x / CELL);
  const cy = Math.floor(y / CELL);
  const cz = Math.floor(z / CELL);
  return `${cx},${cy},${cz}`;
}

// Buduj hasz co klatkę
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);
}

// Następnie w updateBoid: sprawdzaj tylko 27 sąsiednich komórek
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;
}

Liczba boidów	Naiwne O(n²)	Hasz przestrzenny
500	60 FPS	60 FPS
2 000	22 FPS	60 FPS
10 000	<1 FPS	58 FPS

Renderowanie: stożki, nie kule

Każdy boid to ConeGeometry — skierowany w stronę lotu — renderowany przez InstancedMesh. Co klatkę aktualizuję macierz instancji, aby zwrócić się w stronę wektora prędkości, używając quaternion.setFromUnitVectors.

const UP = new THREE.Vector3(0, 1, 0); // domyślna orientacja stożka
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;

Sztuczka na wydajność: zaalokuj InstancedMesh od razu na maksymalną liczbę i nigdy jej nie zmieniaj. Aktualizacja macierzy jest szybka (kopiowanie Float32Array). Tworzenie i niszczenie buforów GPU co klatkę jest wolne.

Dostrajanie wag — tu dzieje się magia

Trzy wagi reguł całkowicie kontrolują charakter stada. Kilka przykładów z moich eksperymentów:

• Wysoka separacja, niska kohezja → ptaki rozpraszają się w luźne wstęgi, jak szpaki po ataku jastrzębia
• Wysokie wyrównanie, niska separacja → ptaki zamykają się w szyki niczym strzały, niemal wojskowe w precyzji
• Wysoka kohezja, niskie wyrównanie → ptaki skupiają się w ciasne wirujące kule — bardziej przypomina to ławicę ryb niż ptaki
• Zrównoważone (1 : 1,2 : 0,9) → domyślne odczucie „murmuracji" — faliste zmiany kierunku przetaczające się przez gęstą chmurę

Suwaki w interfejsie symulacji pozwalają eksplorować tę przestrzeń parametrów na żywo. To zaskakująco wciągające — można spędzić godzinę tylko dostrajając wagi i obserwując zmianę osobowości stada.

Dodanie drapieżnika

Najbardziej efektowne rozszerzenie to 4. reguła: ucieczka przed drapieżnikiem. Pojedynczy model jastrzębia krąży nad stadem; każdy boid w większym „promieniu zagrożenia" dodaje silny wektor odpychania. Cała murmuracja rozdziela się, ponownie się formuje i wiruje — dokładnie jak prawdziwe murmuracje szpaków reagujące na sokoła wędrownego.

// Reguła 4: ucieczka przed drapieżnikiem
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); // panika — podwójna prędkość
  boid.acc.add(flee.multiplyScalar(W_FLEE));
}

Czego się nauczyłem

Boids to projekt, który sprawił, że zakochałem się w systemach emergentnych. Wcześniej myślałem, że symulacje muszą mieć złożoną logikę, aby wyglądać na złożone. Po nim zacząłem patrzeć na każde zjawisko naturalne — ślady mrówek, przepływ ruchu drogowego, wystrzały neuronów — jako potencjalny zbiór trzech prostych lokalnych reguł czekających na odkrycie.

Wzorzec hasza przestrzennego stał się też szablonem, którego używam wszędzie: płyn SPH, dynamika molekularna, wykrywanie kolizji w symulacji bilardu. Zawsze gdy masz wielu agentów oddziałujących wyłącznie z lokalnymi sąsiadami, hasz przestrzenny to pierwsze narzędzie, po które warto sięgnąć.