[IA] Wall Avoidance: Steering Behaviors en XNA (III de II)

Sí… esta es la parte 3 de 2… y es que en la anterior escribí una implementación de “obstacle avoidance”, pero claro, los obstáculos eran siempre circulares. En esta nueva versión, además de circulares, los obstáculos pueden ser líneas, con lo cual se puede dibujar prácticamente cualquier forma geométrica.

Esto es lo que vamos a conseguir con esta nueva versión del ejemplo:

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

Os dejo el código para que juguéis con él, y si álguien se anima a mejorarlo ya sabéis. Una de estas posibles mejoras, y que seguramente no seria muy difícil, sería aplicar un smooth a las rotaciones, es decir, impedir que el agente gire como un loco…

[IA] Robocup… que se prepare la FIFA!

Pues sí… hoy hablaremos de futbol! Hoy he descubierto (a pesar de que hace años que existe) la Robocup, algo más que una competición a nivel mundial entre robots futbolistas. Entre sus objetivos, a parte de fomentar la educación e investigación en IA (minucias…) destacan que quieren ganar el mundial de fútbol de la FIFA participando en la competición con las reglas oficiales y jugando como un equipo más contra otros equipos humanos. Este objetivo se lo han marcado para el año 2050… Viendo la web parece que les queda bastante trabajo por hacer, pero no van mal encaminados…

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

Y como no sólo de fútbol vive el hombre… también han desarrollado la competición “Robocup rescue”, es decir, robots de rescate.

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

Cabe destacar la ayuda y documentación que ofrecen para construir un robot para la competición. Sin duda todo un mundo de posibilidades..

[IA] Obstacle Avoidance: Steering Behaviors en XNA (II de II)

En el episodio anterior hablé de algunos steering behaviors básicos. Hoy hablaré de un Steering que puede solaparse a cualquiera de los anteriores, consiguiendo efectos de IA más avanzados: el Obstacle Avoidance. La idea es que podamos aplicar este comportamiento a cualquiera de los steering behaviors que ya tenemos desarrollados, de forma que cualquiera de nuestros agentes evite las colisiones con los obstáculos existentes en el “mundo” en que se desenvuelve.

Para ello nos basaremos de nuevo en los principios de Craig Reynolds, en los que define un pseudoalgoritmo efectivo para aproximar los obstáculos mediante círculos, y evitar las colisiones con los mismos mediante la proyección de un rectángulo en frente de nuestro agente (orientado hacia la dirección de avance), que testeará en cada momento posibles intersecciones entre dicho rectángulo y los obstáculos, identificando así posibles colisiones entre el agente y estos obstáculos en un “futuro” cercano. Lo malo es que el amigo Craig no nos facilita el código… sólo nos da sus mandamientos. Para ver buenos ejemplos de código tenemos la librería OpenSteer, SharpSteer, o uno de mis libros favoritos y reciente adquisición: Programming Game AI by Example. Con todo esto y un poco de imaginación vamos a conseguir lo siguiente:

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

Si vísteis mi artículo anterior de steering behaviors, la diferencia está en los obstáculos con forma de circunferencia, que están repartidos por el “mundo”, y que los agentes los esquivan, o nunca pasan por encima de ellos. ¿Cómo conseguimos esto? Con la librería que he desarrollado, en la clase Game solo habría que añadir lo siguiente:

bichoPursuit.behaviors.AddBehavior(new Pursuit(Arrive.Deceleration.normal, 50.0f));
bichoPursuit.behaviors.AddBehavior(new ObstacleAvoidance(ref gameWorld, 15.0f));

Lo cual quiere decir que al agente “bichoPursuit”, le damos primero el behavior de pursuit, y el de obstacleAvoidance. Obviamente los círculos no se renderizarian en un juego… y serían sustitidos por los sprites 2D o modelos 3D correspondientes, aquí los uso solo para desarrollar y debugar la librería. Y con esto ya está! Bueno… lógicamente en la clase que hay por detrás he hecho un trabajo extra, implementando el nuevo steering en la clase ObstacleAvoidance:

Es muy parecida a las herederas de Steering que ya hemos visto, tiene su método “CalculateSteering”. La diferencia ahora está en el uso que hace de la clase Circle para definir los obstáculos en forma de circunferencia (en una librería completa habría que definir otras formas geométricas para los obstáculos, la más flexible sería la línea). Tambien observamos un método nuevo: EnforceNonPenetrationConstraint, después veremos qué hace. La clase Circle, a pesar de ser sencilla nos va a dar mucho juego. Nunca mejor dicho 😛

CalculateSteering

Este método contiene la “chicha”. Lo primero que hará será buscar todos los obstáculos próximos al agente y guardarlos en una lista. Con esto evitaremos comprobaciones excesivas con todos los obstáculos que pudieran haber en el juego, y por tanto evitaremos perder valiosísimo tiempo del procesador. Una vez tenemos identificados los obstáculos, calcularemos la distancia a partir de la cual debemos comprobar/reaccionar ante las posibles colisiones con los obstáculos circulares.

A continuación recorremos todos los obstáculos que se encuentran en el radio de acción que hemos identificado anteriormente, y dependiendo de la distancia (o incluso penetración) del agente sobre el obstáculo, generaremos una steering force proporcional hacia la dirección que se considere oportuno.

Compensación de fuerzas

El uso en paralelo de varios steering behaviors puede provocar que un steering de Flee quiera alejar al agente de su perseguidor, por ejemplo hacia la derecha, pero hacia la derecha podría estar el círculo… así pues tenemos un conflicto. Este conflicto se puede superar de varias formas… pero la más sencilla (y no necesariamente la mejor) mediante compensación de fuerzas, esto es, dando un peso específico a cada steering sobre el total, de forma que este sea tenido en cuenta para calcular el resultado final:

En la clase SteeringBehavior tendríamos esto:

if (this.HasBehavior(BehaviorType.seek))
   this._steeringForce += this._seek.CalculateSteering(entity) * this.weightSeek;

if (this.HasBehavior(BehaviorType.obstacle_avoidance))
   this._steeringForce += this._obstacleAvoidance.CalculateSteering(entity) * this.weightObstacleAvoidance;

Donde hay que destacar la multiplicación que se hace sobre la steeringForce contra su peso establecido de forma constante en este caso (pero podría ser variable según las situaciones).  Como no podemos predecir con exactitud los resultados que van a producir la compensación de fuerzas, puede darse -y se da- la situación de que un agente termine pasando por encima de un obstáculo. Para evitarlo, el behavior ObstacleAvoidance llamará al método EnforceNonPenetrationConstraint antes de devolver el resultado calculado del steering. Esta función corregirá la posición de la entidad para asegurar que no se solapa sobre ningún obstáculo.

La verdad es que después de desarrollar este ejemplo me voy a pensar si saco o no una tercera parte… los steering behaviors dan mucho de sí… y existen otros comportamientos muy interesantes: evitar obstáculos que sean líneas, ocultarse, bloquear, asegurarse que los agentes no se solapan entre sí…

Os dejo el código en vuestras manos, tratádmelo bien! 😀

[webcast] Iniciación a los Shaders personalizados en XNA

El XNA Game Studio Product Team empieza el año fuerte… ofreciéndo a la comunidad un webcast tecnológico en directo (en inglés). En concreto Shawn Hargreaves , uno de los desarrolladores del XNA Framework. ¿Quién mejor para hablar de XNA que sus propios creadores?  Aquellos que estamos en GMT+1 no nos va mal el horario… a pesar de ser en una zona horaria lejanísima, pero tendremos que madrugar. Si no me equivoco hay -9 horas de diferencia…

A hands-on demonstration of how to apply custom shaders to 2D sprites. Forget the complex 3D math, and no previous shader experience required – the goal is to achieve cool and interesting 2D effects in a simple and practical manner.

Para registrarse, hay que hacerlo en la siguiente URL: http://creators.xna.com/en-US/developerseries antes del 13/01/2010.

[OT] Eureca!, portal de enlace al conocimiento

La Generalitat de Catalunya ha presentado el portal Eureca (Enlace Unificado a Recursos Electrónicos de Catalunya) , disponible en catalán, castellano e inglés. Contiene ingente información y documentación de universidades y otras instituciones culturales (Centro de Supercomputación, Instituto Cartográfico, etc). Para ser exactos contiene 170.000 documentos (y sigue creciendo).

www.eureca.cat

[IA] Steering Behaviors en XNA (I de II)

Los Steering Behaviors son formas de comportamiento autónomas para agentes de un videojuego. El concepto y definición de los mismos proviene de Craig Reynolds. En esta serie de artículos propondré una implementación para algunos de estos steering behaviors, intentando hacerlo con un diseño lo más desacoplado, flexible y extensible posible. Todo ello intenentando superar mi primera aventura en el ámbito en este post anterior.

En este “episodio” os ofrezco la implementación de estos steering behaviors (uso denominaciones en inglés, ya que son las usadas en el mundillo y las que os facilitarán encontrar más información si lo necesitáis). No entro demasiado en la definición funcional de cada steering behavior, ya que puede encontrarse en el blog de Craig Reynolds. Ahí va un pequeño resumen:

  • Seek: Consiste en perseguir un objetivo o Target, intentando acercarse a él de forma directa.
  • Flee: Huye del Target, alejándose de él.
  • Arrive: El mismo behavior que el Seek, sólo que este reduce la velocidad suavemente antes de alcanzar el objetivo.
  • Pursuit: Persigue al Target con mayor “inteligencia”, es decir, en vez de acercarse de forma directa al objetivo, realizaremos una estimación de su posición futura teniendo en cuenta el vector de velocidad en cada momento.
  • Evade: Al igual que el pursuit, intenta escapar del Target intentando estimar la posición futura del perseguidor, en lugar de alejarse de forma directa.
  • Wander: El agente se desplaza de forma errática, calculando un punto aleatório del área de un círculo situado enfrente del agente.

Mis favoritos son el Pursuit, que con un sencillo algoritmo genera una sensación de “inteligencia”, y el Wander, que nos permite tener un agente que se desplaza de forma totalmente autónoma. Otro elemento a destacar es el diseño de esta implementación. Creo que es bastante flexible, aunque seguro es mejorable. Permite fácilmente integrar una máquina de estados finitos, para que el agente pueda cambiar de behavior en cualquier momento. Además podrían solaparse varios steering behaviors en un mismo agente a la vez… (aunque no tiene sentido solapar un seek y un flee, la utilidad de esto la veremos en la siguiente “entrega”).

En el siguiente diagrama vemos que la clase SteeringBehaviors tiene instancias de otras clases, que representan cada uno de los comportamientos. Esto lo he hecho así para dotar de mayor flexibilidad a la implementación, y hacer el código menos complejo y por tanto más fácil de entender, mantener y extender. Cuando utilizemos esta clase desde cualquier juego para nuestros agentes, deberemos añadirles el Behavior con el método sobrecargado AddBehavior (con una sobrecarga para cada tipo de Behavior), y posteriormente llamando al método Update. El método update, el solito se encargará de ejecutar todos los steering behaviors que correspondan al agente. ¿Fácil, verdad?

Todos los steerings tienen una estructura común, aunque sus especializaciones pueden contener distintos atributos y métodos, como muestra este diagrama de ejemplo (no se incluyen todos los behaviors que contiene el código):

Como siempre os dejo el código adjunto para que lo provéis/uséis a vuestra conveniencia. Este vídeo refleja el resultado de la ejecución del programa:

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