[XNA] Flocking o movimientos colectivos

¿Quién no ha jugado alguna vez al Age of Empires? En ese juego, puedes seleccionar un grupo de unidades, y hacer que estas se muevan de forma colectiva hacia el destino que les indiques. Eso es lo que conocemos como técnicas de flocking, cuyo orígen viene de la naturaleza con los animales: bandas de pájaros, manadas, etc. La implementación de la técnica siempre será igual o muy parecida a la proporcionada en este ejemplo, por lo que casi podemos afirmar que estamos hablando de un “algoritmo de flocking”. Esto podría considerarse que está dentro del ámbito de la Inteligencia Artificial en el mundo de los videojuegos (muy básica, eso sí).

En este artículo veremos una implementación básica de flocking. Implementacones más avanzadas podrían incluir, además de los movimientos colectivos, algoritmos de pathfinding, o programación comportamientos cuando un miembro del grupo se queda desperdigado (porque queda atascado en algún obstáculo por ejemplo).

La siguiente figura simplifica la idea del flocking:

Eso sí, como las cosas en la vida nunca son tan sencillas, deberemos tener en cuenta una serie de factores cuando implementemos algoritmos flocking. Son los siguientes:

  • Separación: Los miembros no pueden estar excesivamente cerca (no queremos que se amontonen).
  • Cohesión: Queremos que los miembros vayan lo suficientemente juntos y no se “pierda” ninguno por el camino.
  • Alineamiento: Todos los miembros del grupo deben ir alineados en la misma dirección.

Implementación

La implementación se basa en el desarrollo de dos clases: Escuadron y Soldado. Son bastante autodescriptivas. Un soldado es un miembro del grupo, con una dirección, posición, velocidad, ángulo de giro y dirección deseada. Además tiene un método “Caminar”, que es el que hace que este se desplaze. La clase escuadrón es la que tiene más lógica. La veremos con mayor detalle.

La clase Escuadron contiene el destino final al que se dirige este, y distintos factores que se utilizan para calcular el desplazamiento (son los factores que he enumerado anteriormente). Además la clase contiene una lista de soldados, que se irán cargando con el método AddSoldado.


Update de la clase Escuadron

Primero estableceremos la dirección de los soldados, y posteriormente les aplicaremos los factores del algoritmo de flocking para que el movimiento sea acorde al de un grupo (y no se acaben superponiendo a medida que se acercan al destino).

// Establecemos la dirección de los soldados
foreach (Soldado soldado in soldados)
{
    Vector2 direccionDeseada = this.destinoFinal – soldado.posicion;

    direccionDeseada.Normalize();
    soldado.SetDireccion = direccionDeseada;
}

// Factores flocking
this.UpdateSeparation();
this.UpdateCohesion();
this.UpdateAlignment();

Después de aplicar los factores, los desplazaremos. Además (y sólo para hacerlo bonito), guardaremos el valor del ángulo existente entre su posición y el destino final (para que “caminen mirando” al objetivo).

foreach (Soldado soldado in soldados)
{
    // Vida sana hay que tener…
    soldado.Caminar();

    // Orientamos al miembro del grupo de forma que mire hacia el destino
    soldado.angulo = (float)System.Math.Atan2(soldado.posicion.Y – this.destinoFinal.Y, soldado.posicion.X – this.destinoFinal.X);
}

Aplicación de los factores: Separación

private void UpdateSeparation()
{
    foreach (Soldado soldado in soldados)
    {
          Vector2 direccionDeseada = soldado.direccionDeseada;
          Vector2 nuevaDireccion = Vector2.Zero;

          // Separamos cada uno de los soldados de los demás
          foreach (Soldado vecino in soldados)
          {
               if (vecino != soldado)
               {
                    Vector2 distancia = vecino.posicion – soldado.posicion;
                    float longitud = distancia.Length();
                    float factor = longitud * longitud;

                    if (factor > 0.0f)
                    {
                         nuevaDireccion -= distancia / factor;
                    }
                }
          }

          // Si hay que ajustar la dirección del soldado…
          if (nuevaDireccion.Length() > 0.0f)
          {
                nuevaDireccion.Normalize();

                direccionDeseada += nuevaDireccion * this.factorSeparacion;
                direccionDeseada.Normalize();
                soldado.SetDireccion = direccionDeseada;
          }
    }
}

Aplicación de los factores: Cohesión

        private void UpdateCohesion()
        {
            if (soldados.Count > 0)
            {
                // Localizamos el centro del grupo
                Vector2 centro = Vector2.Zero;

                foreach (Soldado soldado in soldados)
                {
                    centro += soldado.posicion;
                }

                centro = centro / soldados.Count;

                // Miramos la distancia hasta el centro y se suma un vector proporcional
                // a la dirección deseada
                foreach (Soldado soldado in soldados)
                {
                    Vector2 nuevaDireccion = centro – soldado.posicion;

                    if (nuevaDireccion.Length() > 0.0f)
                    {
                        nuevaDireccion.Normalize();
                        nuevaDireccion = nuevaDireccion * this.factorCohesion;
                        nuevaDireccion += soldado.direccionDeseada;
                        nuevaDireccion.Normalize();

                        soldado.SetDireccion = nuevaDireccion;
                    }
                }
            }       
        }

Aplicación de los factores: Alineamiento

        private void UpdateAlignment()
        {
            if (soldados.Count > 0)
            {
                // Calculamos la media aritmética de la dirección de los miembros
                Vector2 mediaDireccion = Vector2.Zero;

                foreach (Soldado soldado in soldados)
                {
                    mediaDireccion += soldado.direccionDeseada;
                }

                mediaDireccion = mediaDireccion / soldados.Count;

                // Añadimos a la dirección deseada el factor del promedio
                foreach (Soldado soldado in soldados)
                {
                    Vector2 nuevaDireccion = mediaDireccion – soldado.direccionDeseada;

                    if (nuevaDireccion.Length() > 0.5f)
                    {
                        nuevaDireccion.Normalize();
                        nuevaDireccion = nuevaDireccion * this.factorAlineamiento;
                        nuevaDireccion += soldado.direccionDeseada;
                        nuevaDireccion.Normalize();

                        soldado.SetDireccion = nuevaDireccion;
                    }
                }
            }
        }


Utilizando el escuadrón y los soldados

Primero inicializaremos un objeto Escuadron en la clase Game:

escuadron = new Escuadron(new Vector2(400, 400), 0.35f, 0.15f, 0.30f);

A continuación añadimos soldados al escuadrón:

escuadron.AddSoldado(new Soldado(new Vector2(10,50), new Vector2 (0.55f, 0.55f)));
escuadron.AddSoldado(new Soldado(new Vector2(50, 50), new Vector2(0.55f, 0.55f)));
escuadron.AddSoldado(new Soldado(new Vector2(25, 65), new Vector2(0.55f, 0.55f)));
escuadron.AddSoldado(new Soldado(new Vector2(5, 15), new Vector2(0.55f, 0.55f)));
escuadron.AddSoldado(new Soldado(new Vector2(55, 10), new Vector2(0.55f, 0.55f)));

Además, añadiremos un nuevo soldado al escuadrón cada 2 segundos para darle más vidilla al asunto:

if (tiempoDesdeUltimoUpdate >= 2000.0f)
{
     escuadron.AddSoldado(new Soldado(new Vector2(55, 10), new Vector2(0.55f, 0.55f)));
     tiempoDesdeUltimoUpdate = 0.0f;
}

tiempoDesdeUltimoUpdate += (float)gameTime.ElapsedGameTime.TotalMilliseconds;

El resultado final

En el vídeo se puede ver el resultado. El algoritmo es mejorable, con la introducción por ejemplo de pathfinding, o hacer que los miembros del grupo sólo avancen si no están girando, hacer que los miembros del grupo no se amontonen en el último momento (cuando alcanzan el objetivo), etc.

[View:http://www.youtube.com/watch?v=OGz7jCYVv3E:550:0]

El código puede ser descargado en este enlace.

Otras implementaciones

Se me ha ocurrido buscar en youtube otras implementaciones de Flocking y… he visto un par de interesantes:

[View:http://www.youtube.com/watch?v=KyunEojjts8:550:0]

[View:http://www.youtube.com/watch?v=oTFx0uZc6Eo:550:0]

4 comentarios en “[XNA] Flocking o movimientos colectivos”

  1. Buen ejemplo, ni idea que habia un nombre para ese tipo de comportamiento.
    Flocking curioso palabro! la traducción sería quizas Flocado, eso si, en la RAE no viene nada. 🙂

    Gracias!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *