Flocking / Boids: separación, alineación, cohesión

0. Introducción

Si vienes de Steering Behaviors I, ya sabes calcular una force para un agente individual. Flocking es lo mismo, pero en plural: cada agente — un boid — mira a sus vecinos y deriva su force de ellos.

¿Qué es un boid?

Un boid (de bird-oid object) es exactamente lo mismo que el Agent que ya conoces: tiene position, velocity, maxSpeed y maxForce. Lo único que cambia es cómo decide su force: en vez de mirar un target único, mira a los demás boids.

¿Qué es un “vecino”?

Un vecino es cualquier otro boid dentro de un radio de percepción (perception). Si dos boids están a más de perception uno del otro, no se “ven” — para todos los efectos no existen el uno para el otro. Esto es lo que hace que la simulación sea local: no hay un coordinador central, cada boid decide con información reducida.

¿Qué aporta este tutorial sobre lo que ya viste?

Cada regla de flocking — separación, alineación, cohesión — devuelve una force, igual que seek o flee. Eso significa que se enchufan al SteeringController del tutorial III sin tocar la arquitectura. Lo “nuevo” no es el mecanismo; es que ahora el target deja de ser un punto y pasa a ser un conjunto de vecinos.

Cuando necesitas que 200 enemigos no se amontonen en un punto, que sigan al jugador sin pisarse y que giren como si tuvieran un GPS común, flocking es la respuesta más barata. Craig Reynolds lo describió en 1987 con tres reglas que, sumadas, producen un comportamiento colectivo impresionante.

No es para todo. Flocking asume agentes homogéneos y libres en un espacio abierto. Si tus enemigos necesitan cubrirse detrás de objetos o tomar decisiones tácticas, necesitas algo más arriba (Behavior Trees, Utility AI). Flocking es la capa de movimiento.

En esta página vas a ver:

• Las tres reglas con una viz dedicada para cada una.
• Cómo evitar el cuello de botella O(n²) con un spatial hash, también con viz.
• El snippet Unity representativo y un quiz con casos prácticos.

1. Demo

2. Concepto y matemáticas

Cada boid mira a sus vecinos dentro de un radio de percepción y calcula tres forces. Ese es todo el cerebro. Vamos una por una y al final las combinamos.

2.1 Separación

Pregunta que resuelve: “¿cómo evito chocarme con los vecinos demasiado cercanos?”

Para cada vecino dentro de un radio corto de separación (sepDist, mucho menor que perception), el agente acumula una force que lo empuja en sentido contrario, más fuerte cuanto más cerca esté el vecino.

Paso a paso

1. Inicializa el acumulador.

   sep = Vec2(0, 0) ; count = 0

2. Para cada vecino con distance < sepDist:

   away = normalize(self.position - neighbor.position)
   sep += away / distance
   count += 1
   

   La división por distance es la clave: un vecino pegado contribuye con magnitud grande; uno al borde del radio aporta poco.

3. Si hubo vecinos, normaliza y conviértelo en una force de steering:

   sep   = (sep / count).normalize() * maxSpeed
   force = limit(sep - velocity, maxForce)
   

Sube el sepDist y mira cómo los agentes se desparraman uniformemente. Sin alineación ni cohesión, no hay sentido de grupo: solo es un campo de repulsiones mutuas. Eso es la separación, sola y desnuda.

2.2 Alineación

Pregunta que resuelve: “¿cómo me muevo en la misma dirección que mis vecinos?”

Promedia las velocity de todos los vecinos dentro del radio de perception y apunta hacia esa dirección promedio.

Paso a paso

1. Inicializa el acumulador.

   align = Vec2(0, 0) ; count = 0

2. Para cada vecino con distance < perception:

   align += neighbor.velocity
   count += 1
   

3. Si hubo vecinos, normaliza y deriva la force:

   align = (align / count).normalize() * maxSpeed
   force = limit(align - velocity, maxForce)
   

Por sí sola, la alineación genera un enjambre direccional sin forma de grupo: los agentes terminan moviéndose paralelos, pero no hay nada que los junte ni los separe. Es alineación pura.

2.3 Cohesión

Pregunta que resuelve: “¿cómo me mantengo cerca del grupo?”

Promedia las position de los vecinos dentro del radio de perception (eso te da el centroide del grupo local) y aplica un seek hacia ese punto.

Paso a paso

1. Inicializa el acumulador.

   coh = Vec2(0, 0) ; count = 0

2. Para cada vecino con distance < perception:

   coh += neighbor.position
   count += 1
   

3. Si hubo vecinos:

   centroid = coh / count
   desired  = normalize(centroid - self.position) * maxSpeed
   force    = limit(desired - velocity, maxForce)
   

Con solo cohesión, los agentes colapsan en un grumo alrededor del centroide. Es el opuesto de la separación: ningún agente tiene razón para alejarse de los demás, y todos convergen.

2.4 Combinando las tres

La magia está en sumarlas con pesos. Cada peso afecta visualmente el comportamiento de la bandada:

Los valores por defecto razonables que la demo principal usa están alrededor de sep=1.5, ali=1.0, coh=1.0 con perception=48 y sepDist=22. Desde ahí afinas según el feel que busques.

2.5 Spatial hashing — el problema y la solución

Si cada agente pregunta a todos los demás “¿eres mi vecino?”, con 200 agentes son 40.000 comprobaciones por frame. Con 1000, son un millón. Eso es O(n²) y se cae en cualquier dispositivo móvil.

La solución estándar: una grid espacial (también llamada spatial hash). Divides el mundo en celdas del tamaño del radio de percepción. Cada agente se inserta en la celda donde cae su position. Para buscar vecinos, solo consultas la celda actual + las 8 vecinas, no toda la lista.

Paso a paso

1. Define cellSize = perception (la clave: si las celdas son del tamaño del radio, los vecinos siempre caen en las 9 celdas adyacentes).

2. Cada frame, vacía la grid y reinserta todos los agentes en su celda actual.

   cell(p) = (floor(p.x / cellSize), floor(p.y / cellSize))

3. Para consultar vecinos de un agente:

   for dx in [-1, 0, 1]:
       for dy in [-1, 0, 1]:
           for each neighbor in cells[cellX + dx][cellY + dy]:
               if distance(self, neighbor) < perception:
                   procesar(neighbor)
   

4. El coste por frame baja a O(n · k) donde k es el promedio de vecinos por celda — típicamente 5–20 según densidad. Para 1000 agentes: ~10.000 comprobaciones, un orden de magnitud menos que el millón de O(n²).

El agente rojo es el “yo”: solo consulta su celda y las 8 vecinas (verdes). Los agentes que efectivamente revisa se pintan de violeta; los demás quedan en gris. La métrica de abajo compara las consultas reales contra el peor caso ingenuo.

3. Pseudocódigo

function flock(agent: Agent, neighbors: Agent[]) -> Vec2
    sep   = Vec2(0, 0)
    align = Vec2(0, 0)
    coh   = Vec2(0, 0)
    nSep = 0; nAlign = 0; nCoh = 0

    for each n in neighbors
        d = distance(agent, n)
        if d >= PERCEPTION: continue

        # separación pesa más con cercanía
        if d < SEP_DIST and d > 0
            sep   += normalize(agent.position - n.position) / d
            nSep  += 1

        align += n.velocity
        coh   += n.position
        nAlign += 1
        nCoh   += 1

    result = Vec2(0, 0)
    if nSep > 0:   result += weight_sep   * steer_towards(sep / nSep,                       agent)
    if nAlign > 0: result += weight_align * steer_towards(align / nAlign,                   agent)
    if nCoh > 0:   result += weight_coh   * steer_towards((coh / nCoh) - agent.position,    agent)

    return limit(result, agent.maxForce)

function steer_towards(direction: Vec2, agent: Agent) -> Vec2
    desired = normalize(direction) * agent.maxSpeed
    return limit(desired - agent.velocity, agent.maxForce)

steer_towards es exactamente el patrón de Steering I: normalizar, escalar a maxSpeed, restar la velocity actual, limitar a maxForce.

4. Implementación en Unity / C#

using UnityEngine;
using System.Collections.Generic;

public class Boid : MonoBehaviour {
    public float maxSpeed = 5f;
    public float maxForce = 12f;
    public float perception = 3f;
    public float sepDist = 1.2f;
    public float wSep = 1.5f, wAlign = 1f, wCoh = 1f;

    public Vector3 velocity = Random.insideUnitSphere;

    public void Step(IList<Boid> neighbors, float dt) {
        Vector3 sep = Vector3.zero, ali = Vector3.zero, coh = Vector3.zero;
        int nS = 0, nA = 0, nC = 0;

        foreach (var n in neighbors) {
            if (n == this) continue;
            var offset = transform.position - n.transform.position;
            var d = offset.magnitude;
            if (d >= perception || d < 0.001f) continue;

            if (d < sepDist) { sep += offset.normalized / d; nS++; }
            ali += n.velocity; nA++;
            coh += n.transform.position; nC++;
        }

        Vector3 steer = Vector3.zero;
        if (nS > 0) steer += wSep   * SteerTo(sep / nS);
        if (nA > 0) steer += wAlign * SteerTo(ali / nA);
        if (nC > 0) steer += wCoh   * SteerTo((coh / nC) - transform.position);

        velocity = Vector3.ClampMagnitude(velocity + Vector3.ClampMagnitude(steer, maxForce) * dt, maxSpeed);
        transform.position += velocity * dt;
    }

    Vector3 SteerTo(Vector3 desiredDir) {
        var desired = desiredDir.normalized * maxSpeed;
        return Vector3.ClampMagnitude(desired - velocity, maxForce);
    }
}

5. En otros engines

• Godot: un MultiMeshInstance3D acepta miles de transforms de un solo script. Actualizá multimesh.set_instance_transform(i, ...) cada frame.
• Unreal: Niagara con un módulo Neighbor Grid 2D hace flocking en GPU para cantidades grandes. Para 200 agentes, un AActor con Tick y un query de OverlapSphere alcanza.
• JavaScript / Canvas: la demo de arriba. El spatial hash está en ~/lib/viz/sim/grid.ts; es reutilizable para cualquier algoritmo de vecinos.

6. Quiz