Boids: Trzy Zasady Budujące Stado

Emergence in Simple Systems

The captivating behavior of a flock of birds or fish arises from remarkably simple interactions between individuals. Each animal only responds to its immediate neighbors, following basic rules about distance and direction. There's no central coordinator dictating the overall movement – this is known as emergence.

Craig Reynolds’s 1986 simulation, dubbed ‘boids,’ demonstrated this principle elegantly. The core of the simulation relies on three fundamental rules: each boid tries to match the average position of its nearby neighbors, avoids colliding with other boids, and moves at a constant speed. These simple local interactions collectively produce complex, coordinated flocking behavior – a stunning example of how order can emerge from decentralized systems.

Trzy zasady

Każda boid obserwuje sąsiadów w promieniu zasięgu wzroku i oblicza trzy wektory sterowania:

SEPARACJA – skręć w BIEGUNIE od sąsiadów, którzy są zbyt blisko. Sumuj (pozycja_self - pozycja_other), zazwyczaj ważone przez 1/odległość, tak aby najbliższy sąsiad dominował. Zapobiega kolizjom. Krótki zasięg.

ALIGNAJMENT – skręć w kierunku ŚREDNIEJ KIERUNKOWOŚCI sąsiadów. Uśrednij ich wektory prędkości, a następnie skręć, aby dopasować się. To sprawia, że stado obraca się razem. Średni zasięg.

KOHESJA – skręć w kierunku ŚREDNIEJ POZYCJI sąsiadów (ich środek masy). To zapobiega rozpadowi stada. Długi zasięg.

Zsumuj je z wagami, a to jest cały model. Subtelnością jest kolejność wielkości wag, a nie same zasady: separacja musi być wystarczająco silna na krótkim dystansie, aby pokonać kohezję, w przeciwnym razie stado się rozpada; kohezja musi pokonywać separację na dużych odległościach, w przeciwnym razie stado oparzy się. Klasyczną hierarchią jest separacja > alignament > kohezja pod względem siły, a promienie ułożone są odwrotnie — separacja działa na małym promieniu, kohezja na dużym.

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.

Steering, not teleporting

The rules produce desired velocities, not positions. Reynolds' steering formulation converts a desired velocity into a force, and this indirection is what makes the motion look alive rather than mechanical:

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 The two clamps carry all the character. maxForce limits how sharply a boid can turn — it is the turning circle, and a low value produces the wide, sweeping arcs of a large bird while a high value gives the twitchy darting of a fish. maxSpeed keeps everything in the same regime. Without the force clamp, a boid snaps instantly onto its desired velocity and the flock looks like a swarm of magnets; with it, corrections take time and the group develops the sweeping, lagging turns that read as animal.

Two refinements are almost always worth adding. A field of view: real animals cannot see behind them, so ignore neighbours outside a forward-facing arc (a dot product against the heading is enough). And a velocity-matching lag is unnecessary — but constraining the neighbour count is not. Reynolds' original used a radius; later work on real starlings suggested that birds track a roughly fixed number of nearest neighbours rather than everything inside a fixed distance, which makes the flock's cohesion scale-free. Capping the neighbour list at the k nearest (k around 6–7) is cheap and produces noticeably more robust flocks at varying densities.

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

Poszukiwanie sąsiada, który stanowi całość kosztu

Każdy ptak musi znaleźć swoich sąsiadów. Wykonanie tego naiwnie polega na przeskanowaniu wszystkich innych ptaków: O(n²) na klatkę. Jest to w porządku do kilku setek ptaków i jest to, gdzie zaczyna każda implementacja, ale to również jest mur – tysiąc ptaków oznacza milion sprawdzania odległości na klatkę, a częstotliwość działania spada dramatycznie.

Rozwiązaniem jest taka sama jednolita siatka przestrzennego haszowania, jaką używają płyny cząsteczkowe. Wybierz rozmiar komórki równy największemu promieniowi percepcji; wtedy sąsiadami ptaka mogą być tylko w jego własnej komorze i w sąsiednich – 9 komórek w 2D, 27 w 3D. Zbuduj siatkę za każdym razem (liczbownik O(n)) i zapytanie staje się proporcjonalne do lokalnej gęstości zamiast całkowitej populacji.

cellSize = maxPerceptionRadius; key(p) = hash(floor(p.x / cellSize), floor(p.y / cellSize), floor(p.z / cellSize)); // za każdym razem 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]) { ...trzy reguły... } Porównaj kwadrat odległości z kwadratem promienia, nigdy odległość – pierwiastek kwadratowy dla każdej pary, ponad milion par to strata czasu. Zbieraj trzy reguły w jednym przebiegu listy sąsiedztwa zamiast trzech oddzielnych przebiegów: sumy dla separacji, wyrównania i kohezji można zbudować z tej samej iteracji.

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... }

Osiągnięcie poza trzy zasady

Model komponuje. Każde dodanie jest po prostu kolejnym wektorem sterowania dodawanym do akumulatora, co właśnie wyjaśnia, dlaczego boidy przetrwały forty lata jako fundament systemów rzeszowych i zgrupowań:

Unikanie przeszkód wyśle sondę przed boidem; jeśli zderzy się z czymkolwiek, skręć wzdłuż normalnej powierzchni. Waż go bardzo powyżej trzech zasad społecznych — boid powinien złamać formację, zamiast latać na ścianę. Poszukiwanie celu stałe przyciąganie do punktu docelowego lub ścieżki. To tak, jak uzyskasz migrację lub zbiór ptaków, który podąża za kursorami. Zagrożenie/ucieczka silna, krótko trwająca odpychanie od oznaczonego agenta. Dodaj to i zbiór ptaków się rozdziela i ponownie formuje — efekt "fontanny" widoczny w prawdziwych szkołach ryb. Wędrowanie mała, powoli obracająca się losowa siła sterująca. Zapobiega to samotnemu boidowi lataniu prosto do przodu na zawsze, a ustalonemu zbiorem ptaków zamrażającemu się. Ta sama szkielet, z różnymi wagami, staje się rzeszą ryb, stadem bydła, tłumem ludzi, chmurą owadów lub wrogami zgrupowanymi w grze. Jest to jeden z najkrótszych dróg w programowaniu od strony zawierającej kod do czegoś, co wygląda na żywe — a wszystko to nie wymaga, aby pojedynczy boid wiedział, że istnieje zbiór ptaków.

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.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz 3D Boids — Flocking i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.