Crowd simulation: de Boids a RVO/ORCA

0. Introducción

Si vienes de Flocking / Boids, ya sabes que tres reglas locales bastan para que 50 pajaritos parezcan vivos. Ahora cambia el escenario: 500 NPCs en una plaza de Hitman, cada uno con un destino distinto, cruzándose en diagonales imposibles. Flocking se rompe — los agentes se atraviesan, se quedan trabados en cuellos de botella, dos multitudes opuestas forman un nudo que nadie deshace.

Ese es el problema que resuelven RVO y ORCA: el algoritmo de evitación local de colisiones que está debajo del NavMeshAgent de Unity, del crowd controller de Hitman y de las multitudes urbanas de Assassin’s Creed.

¿En qué se queda corto flocking para multitudes?

Flocking no tiene un goal explícito. La bandada emerge sin destino: tres pájaros tirando de tres vectores promedio. Pero un NPC de Hitman quiere ir al puesto de la fruta, no “andar con el grupo”. La separación de boids tampoco garantiza evitar colisión real — solo empuja a los vecinos lejos, y cuando dos masas chocan de frente, ambas separaciones se anulan y los agentes se meten unos dentro de otros.

¿Qué juegos usan este algoritmo?

• Hitman (IO Interactive): multitudes de 200+ NPCs en mercados, calles y eventos. RVO con LOD por distancia.
• Assassin’s Creed (Unity y posteriores): multitudes urbanas con paths individuales y RVO local.
• Watch Dogs: peatones que reaccionan a la presencia del jugador con paths dinámicos.
• Juegos de fútbol (FIFA, PES): público en gradas y jugadores moviéndose en formaciones que no se atraviesan.

En esta página vas a ver:

• Por qué los velocity obstacles son el lenguaje correcto para hablar de evitación.
• Cómo RVO (Van den Berg et al. 2008) introduce la reciprocidad y elimina la oscilación.
• Cómo ORCA (Van den Berg et al. 2011) lo convierte en una programación lineal rápida.
• Cómo combinarlo con pathfinding global y por qué necesitas un spatial hash sí o sí.

1. Demo

2. Concepto y matemáticas

RVO (Reciprocal Velocity Obstacles) y ORCA (Optimal RVO) son técnicas de evitación local de colisiones que asumen reciprocidad: si A asume que B también va a evadir, ambos pueden tomar la mitad del trabajo y converger sin oscilar. Es el algoritmo detrás de los NavMeshAgent de Unity.

La pieza clave que distingue RVO/ORCA de flocking es que trabajan en el espacio de velocidades, no en el de posiciones. En vez de preguntar “¿dónde están mis vecinos?” preguntan “¿qué velocidades me van a llevar a chocar con ellos en los próximos τ segundos?”. Esa pregunta tiene una respuesta geométrica precisa: un cono.

2.1 ¿Por qué los Boids fallan en multitudes con objetivos?

Flocking funciona porque todos los agentes comparten un comportamiento emergente. Nadie quiere ir a ningún lado en particular; lo que pasa, pasa. En una multitud real eso no aplica:

• Cada agente tiene un goal individual (su puesto de venta, la salida, el jugador objetivo).
• Los grupos se cruzan en direcciones opuestas y la separación bidireccional se cancela.
• En cuellos de botella la cohesión (si existiera) tiraría hacia el centro mientras la separación empuja afuera: empate, deadlock.

La separación de boids es reactiva y miope: solo mira posición instantánea. RVO mira velocidades y predice el futuro inmediato. Por eso un boid muere atravesado en una puerta y un agente ORCA frena antes de entrar.

2.2 Velocity obstacles (VO): el cono

Imagina dos agentes circulares: A en el origen y B en posición relativa p = pos_B − pos_A, con radios r_A y r_B. Si A se mueve a velocidad relativa v_rel = v_A − v_B, A chocará con B en algún momento futuro si y solo si esa v_rel apunta hacia el disco de Minkowski de radio r_A + r_B centrado en p.

El conjunto de velocidades relativas que llevan a colisión dentro de un horizonte de tiempo τ forma un cono truncado:

Desde A, las velocidades dentro del cono llevan a colisión con B en τ segundos. Una velocidad fuera del cono (animada) es segura.

Si A escoge una velocidad fuera del cono, está garantizado no chocar (asumiendo que B no cambia su velocidad). El cono tiene su vértice en el origen (velocidad relativa cero ⇒ no se acercan) y se abre hacia p con un ángulo que depende del radio combinado y la distancia.

El VO de A respecto a B (en el espacio de velocidades absolutas de A, no relativas) se obtiene desplazando el cono por la velocidad de B:

VO_A|B = { v_A  :  (v_A − v_B) está dentro del cono relativo }

Si A elige una v_A fuera de VO_A|B, no chocará con B en τ segundos.

2.3 ¿Qué problema tiene VO y cómo lo resuelve RVO?

VO puro tiene un bug feo. Imagina A y B caminando uno hacia el otro:

1. Frame 0: A calcula VO_A|B asumiendo que B mantiene su velocidad. A elige una v_A que esquiva por la izquierda.
2. Frame 0: B hace exactamente lo mismo. Asume que A mantiene su velocidad. B esquiva por la izquierda (de B, que es la derecha de A).
3. Frame 1: ambos vuelven a estar de frente, ahora desviados. Repiten el cálculo. Ambos vuelven a esquivar de más.

El resultado es oscilación: A y B se balancean lado a lado sin avanzar. El problema es que cada uno asume “el otro no va a hacer nada”. Cuando ambos hacen lo opuesto, sobre-corrigen.

RVO (Van den Berg, Lin, Manocha, 2008) lo arregla con una idea simple: reciprocidad. A asume que B también va a esquivar, así A solo necesita hacer la mitad del esquive. Geométricamente:

v_RVO = (v_A_actual + v_libre) / 2

donde v_libre es una velocidad fuera del cono VO. El punto medio entre tu velocidad actual y la velocidad de escape implica que tu compañero hará la otra mitad. Si ambos asumen esto, convergen sin oscilar.

2.4 ORCA: half-planes y programación lineal

RVO funciona, pero elegir la “mejor” velocidad fuera del cono no es trivial cuando tienes 20 vecinos: tienes 20 conos que evitar, y la intersección de “fuera de los conos” puede ser compleja, disconexa o vacía.

ORCA (Optimal Reciprocal Collision Avoidance, Van den Berg et al. 2011) linealiza el problema. Para cada vecino, en vez de un cono curvo define un half-plane lineal: una línea recta tal que cualquier velocidad de un lado garantiza no colisionar.

La construcción:

1. Calcula el vector u: el vector más corto desde la velocidad relativa actual v_rel hasta el borde del cono VO. Es la “corrección mínima” que sacaría a v_rel del cono.
2. Por reciprocidad, A solo aplica 0.5 · u. La línea ORCA pasa por el punto v_A + 0.5·u y es perpendicular a u.
3. El half-plane permitido es el lado de la línea hacia donde u apunta.

Visualizado en 2D (espacio de velocidades de A):

La línea ORCA parte el espacio de velocidades en dos: el lado permitido (verde) y el prohibido. El vector u apunta perpendicular a la línea; v_pref se proyecta al lado válido.

Con N vecinos, A obtiene N líneas ORCA. La intersección de los N half-planes es la región de velocidades válidas. Dentro de ella, A elige la velocidad más cercana a su velocidad preferida v_pref (la que va hacia el goal). Eso es programación lineal en 2D: hay algoritmos O(N) aleatorizados (Seidel) que la resuelven en microsegundos.

Si la intersección es vacía (multitud demasiado densa, no hay velocidad libre), ORCA usa una versión 3D de la programación lineal con una variable de holgura: encuentra la velocidad que viola lo mínimo posible todos los half-planes. Mejor incumplir un poquito que congelarse.

2.5 ¿Cómo se combina con pathfinding?

ORCA es evitación local, no pathfinding. Si pones un agente en un laberinto sin más, ORCA lo lleva en línea recta al goal y se estrella contra la primera pared. La arquitectura estándar es de dos capas:

   [ Global path planner ]      A*, NavMesh, HPA*, flow field…
            |
            v
     waypoint siguiente
            |
            v
   [ Local avoidance: ORCA ]    ajusta velocity para no chocar con otros agentes
            |
            v
        velocity final

El planner global te da una secuencia de waypoints sobre el NavMesh. El v_pref que pasas a ORCA es la dirección al siguiente waypoint, escalada a maxSpeed. ORCA solo ajusta esa velocidad para esquivar a otros agentes dinámicos. Cuando llegas al waypoint, pasas al siguiente.

Los obstáculos estáticos también pueden representarse como half-planes ORCA (línea por el borde del obstáculo). Así un solo solver maneja agentes y muros con el mismo formalismo.

2.6 Performance: spatial hashing es obligatorio

Con N agentes consultando vecinos, brute force es O(N²). Para 200 agentes son 40.000 chequeos por frame, y cada chequeo construye un half-plane. A 60 FPS, eso es 2.4 millones de half-planes por segundo. No funciona.

La solución es la misma de flocking: spatial hashing. Cada agente solo mira vecinos en su celda y las 8 adyacentes. Coste: O(N · K) donde K es el promedio de vecinos por celda (5–20 según densidad).

Cada agente se asigna a una celda según su posición. Para consultas, solo se examinan la celda propia y las 8 adyacentes (resaltadas).

Una optimización adicional específica de RVO: limitar el número de half-planes a los K más cercanos (típicamente K=10). Más allá de los 10 vecinos más próximos, el agente no necesita restricciones extra — los lejanos ya están filtrados por el τ del horizonte temporal.

2.7 Deadlocks: cuando dos multitudes se traban

Dos multitudes cruzándose en sentidos opuestos en un pasillo estrecho pueden quedar trabadas: cada agente encuentra que no hay velocidad permitida (la intersección de half-planes es vacía) y se queda parado. El otro grupo, espejo, también se para. Bloqueo mutuo.

Dos flujos opuestos convergen en un punto de conflicto. En perfecta simetría, ningún agente cede y la región factible se vacía: deadlock.

Mitigaciones estándar:

• Tie-break aleatorio: cuando hay empate en velocidades válidas, romper con un sesgo rand() pequeño. Suficiente para destrabar simétricos perfectos.
• Sesgo temporal: si un agente lleva t > t_block frenado, aumentar su v_pref o reducir su radio efectivo temporalmente. “Empuja” un poco más fuerte.
• Courtesy scaling: agentes que llevan más tiempo en la simulación tienen prioridad (escalan menos su velocidad). Útil para que NPCs nuevos cedan ante NPCs ya en movimiento.
• Path replanning: si el bloqueo persiste, recalcula el path global por una ruta alternativa. ORCA no resuelve macro; el planner sí.

2.8 Limitaciones honestas

ORCA asume agentes circulares y velocidad libre (holonomía total). En la realidad:

• Esquinas en L estrechas: ORCA puede meter al agente en una posición sin salida porque no ve más allá del horizonte τ.
• Agentes con física compleja (vehículos con turning radius, animaciones con root motion): la velocidad calculada por ORCA puede ser imposible de ejecutar. Necesitas un filtro adicional que respete la cinemática.
• Multitudes muy densas (más de ~10 agentes por m²): la región factible se vuelve vacía con frecuencia y los agentes vibran. Para concierto-de-rock-densidad, se usan modelos de fluido (Treuille et al., continuum crowds).
• ORCA es anti-colisión, no anti-trabamiento. Resuelve no atravesarse; los deadlocks necesitan capa extra.

3. Pseudocódigo

function step(agent: Agent, neighbors: List<Agent>, dt: Float)
    # 1. velocidad preferida hacia el goal (viene del pathfinding global)
    prefVel = normalize(agent.goal - agent.position) * agent.maxSpeed

    # 2. construir las restricciones ORCA, una por vecino
    halfPlanes = []
    for each n in neighbors
        hp = computeORCALine(agent, n, TAU)
        halfPlanes.append(hp)

    # 3. resolver programación lineal 2D: velocidad mas cercana a prefVel
    #    que respete todos los half-planes y |v| <= maxSpeed
    newVel = solveLP(halfPlanes, prefVel, agent.maxSpeed)

    # 4. integrar
    agent.velocity = newVel
    agent.position += agent.velocity * dt


function computeORCALine(a: Agent, b: Agent, tau: Float) -> HalfPlane
    relPos    = b.position - a.position
    relVel    = a.velocity - b.velocity
    combRad   = a.radius + b.radius

    # cono VO centrado en relPos/tau con radio combRad/tau (horizonte tau)
    # encontrar el punto del borde del cono mas cercano a relVel -> vector u
    u = closestPointOnConeBoundary(relVel, relPos, combRad, tau) - relVel

    # ORCA: linea perpendicular a u, desplazada 0.5*u desde la velocidad
    # actual de A (reciprocidad: A hace la mitad, B la otra mitad)
    point     = a.velocity + 0.5 * u
    direction = perpendicular(u)
    return HalfPlane(point, direction)

La parte densa real está en closestPointOnConeBoundary y solveLP. Ambas son geometría 2D estándar; el paper de Van den Berg incluye pseudocódigo completo y existe una implementación de referencia abierta en C++ (RVO2 library) que vale más leer que reimplementar.

4. Implementación en Unity / C#

En Unity la opción honesta es usar NavMeshAgent: ya implementa RVO bajo el capó con su flag obstacleAvoidanceType. Reimplementar ORCA desde cero tiene sentido solo si necesitas multitudes muy específicas (sin NavMesh, con miles de agentes en Job System, etc.).

using UnityEngine;
using UnityEngine.AI;

[RequireComponent(typeof(NavMeshAgent))]
public class CrowdAgent : MonoBehaviour {
    public Transform goal;
    public float repathInterval = 0.5f;

    NavMeshAgent agent;
    float nextRepath;

    void Awake() {
        agent = GetComponent<NavMeshAgent>();

        // Calidad de la evitacion local (RVO interno de Unity).
        // HighQualityObstacleAvoidance -> ORCA con 8 muestras de half-planes.
        // GoodQuality -> ORCA con 4 muestras (mas barato).
        // None -> sin evitacion: solo NavMesh "puro".
        agent.obstacleAvoidanceType = ObstacleAvoidanceType.HighQualityObstacleAvoidance;

        // Prioridad: 0 = mas alto. Agentes de baja prioridad ceden ante los de alta.
        // Util para NPCs "background" que no deben bloquear al jugador.
        agent.avoidancePriority = 50;

        // Radio efectivo para ORCA. Mas grande = mas espacio personal,
        // mas riesgo de deadlock en pasillos estrechos.
        agent.radius = 0.4f;
    }

    void Update() {
        if (goal == null) return;

        // Repath periodico, no cada frame: A* sobre NavMesh es caro.
        // ORCA local se encarga de los otros agentes en cada frame de update.
        if (Time.time >= nextRepath) {
            agent.SetDestination(goal.position);
            nextRepath = Time.time + repathInterval;
        }
    }
}

Lo que el asset empaqueta sobre esto:

• Manager con LOD por distancia a la cámara: agentes lejanos bajan a LowQualityObstacleAvoidance o tiquean cada 3 frames.
• Spatial hash propio para queries de vecinos custom (cuando necesitas ignorar a ciertos grupos).
• Detección de deadlock: si un agente lleva más de T segundos quieto y debería estar moviéndose, dispara un repath con desvío forzado.
• Variantes de prioridad según avoidancePriority para multitudes con jerarquía (VIPs, peatones, jugador).

5. En otros engines

• Godot: NavigationAgent3D integra RVO vía el plugin RVO2 (port de la librería de referencia de la UNC). Configuras avoidance_enabled = true y ajustas radius y time_horizon. Misma idea que Unity.
• Unreal: dos opciones. CharacterMovementComponent con bUseRVOAvoidance = true activa una variante de RVO simplificada. Para multitudes serias, usar DetourCrowdAIController que delega en Detour/Recast (capa crowd de Recast Navigation). Hitman y similares van por esta vía.
• JavaScript / motor propio: la librería original RVO2 (Van den Berg et al.) está portada a JS. Sirve para visualizaciones web y prototipos. Para producción en motor propio, suele compensar reimplementar la programación lineal O(N) y mantener el solver bajo tu control.

6. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. Tu multitud se queda paralizada en un cuello de botella. Todos los agentes están frenados y nadie pasa. ¿Qué falta o sobra?

   • AFalta un tie-break o sesgo temporal: la región factible está vacía y todos ceden a la vez.
   • BSobra evitación: bajar la prioridad del agente solucionaría todo.
   • CFalta cohesión: necesitan atraerse para empujarse mutuamente.

2. Implementas VO sin reciprocidad (sin RVO). ¿Qué síntoma característico ves?

   • AOscilación: los agentes se balancean lado a lado al cruzarse, porque ambos esquivan de más.
   • BAtravesamiento: los agentes pasan unos a través de otros.
   • CLos agentes ignoran el goal y se quedan quietos.

3. Necesitas que 1000 agentes corran ORCA en tiempo real sin que el CPU se queme. ¿Cuál es la optimización de primer orden?

   • ASpatial hashing + limitar a los K vecinos más cercanos (típicamente K=10).
   • BSubir el horizonte τ para que el agente vea más lejos y planifique mejor.
   • CEliminar el solver LP y elegir cualquier velocidad fuera de los conos.

4. Tu agente esquiva paredes con A* sobre NavMesh y agentes con ORCA. A veces atraviesa una esquina cerrada. ¿Por qué?

   • AORCA opera en el espacio de velocidades libre y no respeta restricciones de geometría estática a menos que las añadas como half-planes adicionales.
   • BEl horizonte τ es demasiado corto y no ve la esquina a tiempo.
   • CFalta repath de A*: el camino global está desactualizado.