El patrón Decorador para añadir detalles a los elementos del juego

3 comments »

Aunque no es tan interesante como el campo de batalla, un Guerrero Informático debe conocer
sus herramientas de combate y dominarlas para poder aplicarlas en un entorno hostil cuando
la cosa se ponga fea. Una de ellas es el Patrón Ninja Decorator (Decorator Pattern). Vamos
a verlo en más detalle.

Muchas veces os va a tocar añadir funcionalidad al juego que no estaba prevista. Un dia
(o varios) os vendrá el game designer, os llevará a un cuarto frio sin casi iluminación,
os ofrecerá un cafe y os dirá: “Pepito (pon aqui tu nombre), tenemos que hablar. Vamos
a tener que añadir/modificar/eliminar una serie de elementos del juego que no estaban
previstos. Sin embargo, los chicos de márqueting opinan que será muy beneficioso.Como
sabrás, tenemos unos tiempos de entrega muy ajustados por lo que vamos a tener que arrimar
el hombro para que todo salga como estaba previsto.” Esto en términos generales y como
tradución menos diplomática como: “Vas a currar nene!”. Otro escenario posible y menos
dramático será que despertareis en medio de la noche con sudores frios y gritando
“Lo tengo! El personaje tendrá habilidades especiales y cada habilidad tendrá diferentes
grados de efectividad”. Lo apuntareis, seguireis durmiendo y a la mañana siguiente os pondreis
manos a la obra. Empezaries a mirar código y direis ¿donde meto esto sin poner todo el diseño
patas arriba?. Y será entonces cuando os acordeis de este humilde post, “Como se llamaba el rollo
aquel que vi en Starco … Patrón decorador!!”.

Patron Decorator

Esta es una herramienta que nos servirá para muchas soluciones en las que es necesario dejar abierta
la inclusión de características, elementos, particularidades … etc en alguna de las clases o
entidades de nuestro sistema. En general cuando queremos dar pinceladas sobre alguno de nuestros elementos
será muy útil este patrón. Un ejemplo es el que, en un juego de rol, teniendo nuestro personaje,
queremos añadir una serie de habilidades donde cada habilidad puede tener un diferente grado de efectividad
respecto a personajes con otras habilidades.

> Elementos del patrón Decorator.

Los elementos del patrón decorador son generalmente 3.
–> Componente Concreto. La clase que define nuestra entidad inicial (un personaje, una roca, un enemigo…etc)
–> Componente Decorador. La clase o clases que definen las nuevas pinceladas (comportamientos, detalles, habilidades…etc)
–> Componente Genérico. Esta clase es la que generaliza los componentes y permite al crear una entidad, disponer
tanto de la clase inicial (El componente concreto) como de las clases decoradoras. Una clase intermedia a modo de
aglutinador de Decoraciones es ‘decorator’ que organiza todos las nuevas pinceladas

Patron Decorador

Como se aprecia en la foto la estructura es muy clara y permite añadir o quitar componentes. ¿QUe diferencia esto de la
jerarquía clásica de clases con mecanismos de herencia? Muy sencillo, que de este modo las decoraciones añadidas son independientes y pueden aplicarse a un objeto concreto. No dependen de una jerarquía sino que pueden aplicarse o no dependiendo de las necesidades del programador y crear nuevos no implica añadir el comportamiento o la ‘decoración’ en todos los nodos o partes de la jerarquía donde deberían figurar. Siempre que puede aplicarse un diseño jerárquico y por herencia es recomendable, pero en la mayoría de los casos pequeños (o grandes) detalles serán más rápidos y sencillos de añadir de esta forma.

Nuestra forma de trabajo será. Necesito un nuevo elemento que complemente a un objeto determinado (pongamos un personaje). Bien, añado una nueva clase de decoración y lo complemento. Si me conviene crear instancias de ese objeto decoradas las crearé y sino seguiré utilizando el objeto con las características iniciales.

> El ejemplo típico. Una ventana de Windows.

Para dejar claros los conceptos de decorador se utiliza generalmente uno de los ejemplos más visuales
y a los que más acostumbrados estamos: las ventanas de windows (léase linux o cualquier otro si procede). Vemos en la
imagen inferior la estructura que tendrá un componente ventana creado de forma que se utilice el patrón decorator.

Ejemplo Patron Decorador

No vas a necesitar mucho que leer despues de ver esta imagen. Como se puede apreciar. La clase Window es el componente genérico, la clase simpleWindow define lo básico de una ventana y la clase WindowDecorator engloba las diferentes instancia de  ventana que podemos encontrar. VerticalScrollBars y HorizontalScrollBarDecorator son pinceladas sobre las diferentes ventanas simples.

> Código de ejemplo para el patrón decorador.

El código asociado seria este:

// the Window interface
interface Window {
    public void draw(); // draws the Window
    public String getDescription(); // returns a description of the Window
}

// implementation of a simple Window without any scrollbars
class SimpleWindow implements Window {
    public void draw() {
        // draw window
    }

    public String getDescription() {
        return "simple window";
    }
}

Las clases de a continuación contienen los decoradores de todas las clases Window ncluyendo los propios decoradores.

// abstract decorator class - note that it implements Window
abstract class WindowDecorator implements Window {
    protected Window decoratedWindow; // the Window being decorated

    public WindowDecorator (Window decoratedWindow) {
        this.decoratedWindow = decoratedWindow;
    }
}

// the first concrete decorator which adds vertical scrollbar functionality
class VerticalScrollBarDecorator extends WindowDecorator {
    public VerticalScrollBarDecorator (Window decoratedWindow) {
        super(decoratedWindow);
    }

    public void draw() {
        drawVerticalScrollBar();
        decoratedWindow.draw();
    }

    private void drawVerticalScrollBar() {
        // draw the vertical scrollbar
    }

    public String getDescription() {
        return decoratedWindow.getDescription() + ", including vertical scrollbars";
    }
}

// the second concrete decorator which adds horizontal scrollbar functionality
class HorizontalScrollBarDecorator extends WindowDecorator {
    public HorizontalScrollBarDecorator (Window decoratedWindow) {
        super(decoratedWindow);
    }

    public void draw() {
        drawHorizontalScrollBar();
        decoratedWindow.draw();
    }

    private void drawHorizontalScrollBar() {
        // draw the horizontal scrollbar
    }

    public String getDescription() {
        return decoratedWindow.getDescription() + ", including horizontal scrollbars";
    }
}

Un ejemplo de programa de test quecrea una instancia de decorador completamente decorada con scrolls verticales y horizontales.

public class DecoratedWindowTest {
    public static void main(String[] args) {
        // create a decorated Window with horizontal and vertical scrollbars
        Window decoratedWindow = new HorizontalScrollBarDecorator (
                new VerticalScrollBarDecorator(new SimpleWindow()));

        // print the Window's description
        System.out.println(decoratedWindow.getDescription());
    }
}

Muy conciso. Más información en el video de a continuación:

> En Resumen

Se ha visto la utilidad del patrón Decorator para el uso en sistemas de entretenimiento. Hemos ganado una nueva herramienta que puede ser útil en cualquier contexto en el que tengamos que ‘decorar’ entidades de nuestro sistema. Este mecanismo permite aprovechar las diferentes pinceladas sobre un mismo objeto de forma que podemos utilizarlas cuando nos sea conveniente sin ceñirnos a una jerarquía concreta o a los mecanismos de herencia tradicionales.

Disfrutadlo.

Arboles de Comportamiento (Behaviour Trees) para gestionar comportamientos.

2 comments »

Este es el tercer artículo que profundiza sobre las técnicas que utilizan los
programadores de inteligencia artificial para desarrollar comportamientos que
requieren una complejidad importante. Estos son los árboles de comportamiento.

tecnotree

Los árboles de comportamiento son estructuras que se crean con la finalidad de
organizar el comportamiento de nuestro sistema y permitir trabajar con el de
forma sencilla. Saber a que parte de nuestro código ir para modificar ciertos
comportamientos y cuando invocarla es una tarea que se hace mucho más rápido
utilizando estructuras como esta. Me voy a basar en el material de Ricard Pillosu
que ha realizado una muy buena contribución al tema.

> Donde se están utilizando

A primera vista puede parecer que es más apropiado abordar el problema de forma
rápida sin tener que estar pendiente de relaciones en árbol ni de otras estructuras.
Podemos pensar que simplemente agrupando listas de instrucciones será más sencillo
y nos ahorraremos mucho tiempo. Sin embargo, nada más lejos de la realidad ya que
conforme la dificultad del entorno crece, estos mecanismos se hacen cada vez más útiles.

Algunos de los juegos que actualmente estan en el mercado utilizando estos sistemas son el
maravilloso Grand Theft Auto, el Halo o Spore. Todos ellos se basan en el uso de estas
estructuras para gestionar comportamientos y como ya debeis saber son referentes en sus
respectivos campos. De otro modo inmediatamente debeis abandonar la lectura de este material y poneros a jugarlos como locos.

Halo Wars

Spore

GTA IV

Estos modelos se utilizan para hacer más sencilla la inclusión de nuevos comportamientos
que añadan complejidad a las respuestas de nuestros agentes inteligentes, simplificar
el trabajo de creación de los propios comportamientos, permitir el prototipado y la
puesta en escena de nuevas iteraciones y optimizar el rendimiento del sistema.

> Cómo son los árboles de comportamiento:

En estas estructuras se definen varios conceptos. El nodo, que representa cada
una de las partes del árbol y que representan cada uno de los diferentes comportamientos
junto con sus condiciones para ejecutarlos.

Ejemplo árbol de comportamiento

Como se ve en la figura superior, el árbol consta de varios elementos anidados en la estructura
que tiene como condición que cada uno de ellos puede tener varios hijos pero únicamente un padre. Es decir, la estructura crece o se mantiene a medida que descendemos, no a la inversa. Diferenciamos los nodos que están en el interior de la estructura de aquellos que son terminales llamados también nodos ‘hoja’. De este modo las ‘ramas’ serán aquellos nodos que tienen algún hijo o descendiente y las ‘hojas’ aquellos que no lo tienen.

Detalle arbol de comportamiento

Entrando más en detalle, cada nodo tendrá dos componentes inicialmente. El primero de ellos serán las  condiciones, es decir, los requisitos que deben cumplirse para que el comportamiento en cuestión se ponga en marcha. En segundo lugar las acciones, es decir, el propio comportamiento que debe realizar. Este último elemento deberá ser cuanto más abstracto mejor, ya que nos encargaremos de a nivel de código definirlo con detalle.

Por ejemplo: La condición puede ser (Si Veo_Enemigo == 1). La lista de acciones sería (Alertar,
Esconderse). A nivel interno ya definiremos que implica alertar y que esconderse.

Como medida de simplificación las acciones las realizarán generalmente los nodos ‘hoja’, aunque para comportamientos muy bien definidos de los que se puede extraer características comunes podremos lanzar acciones desde nodos ‘rama’. Por ejemplo al controlar el comportamiento de la cabeza de un soldado podemos querer tener un ’supercomportamiento’ como el parpadeo ocular, independiente del estado en el qe nos encontremos  (esto significa no que adquiera superpoderes sino que el comportamiento se manifieste de forma común a los nodos descendientes que pueda tener). Los hijos pueden ser ‘patrullando’ y ’siguiendo objetivo. En el primero estableceremos un comportamiento que haga rotar la cabeza desde el frente a -45 y 45 grados respecto al plano vertical. El segundo podemos definir que la cabeza se oriente a un determinado objetivo. De forma independiente se verá el parpadeo de los ojos que es común a los dos. Comenta el Sr. Pillosu que el 99% de los nodos con acciones serán nodos hoja por lo que será bueno tenerlo en cuenta.

Al mismo tiempo que el arbol anterior podriamos tener uno trabajando en paralelo para controlar el movimiento de la boca o incluso la expresión facial. Ya a partir de este punto empezamos a ver la utilidad que tienen y la facilidad que va a tener añadir nuevos comportamientos, tanto adicionales a los que tenemos como totalmente nuevos.

> Funcionamiento

El funcionamiento, una vez vista la estructura es sencillo. Cuando pasamos por la iteración pertinente de nuestro sistema, evaluaremos las condiciones del árbol empezando por los nodos superiores.

Arbol funcionamiento

Cuando uno de ellos cumple las condiciones, ejecutamos las acciones del nodo (si las hay) y pasamos a evaluar sus descendientes. Si alguna de las condiciones de sus hijos se cumplen en su totalidad, se continua el proceso. Acabamos de procesarlo cuando llegamos al nodo hoja. Podemos permitir que se ejecuten varios comportamientos en un mismo árbol pero será mejor que permitamos solo uno de ellos y englobemos las acciones de forma que con este funcionamiento podamos llevar a cabo la gestión de una forma correcta. De esta forma podemos controlar en cada momento que acciones se estan llevando a cabo y donde ir a buscarlas.

Una vez procesado el árbol continuamos con el siguiente y así hasta que todos los árboles de comportamiento aplicables al agente en cuestión se hayan procesado.

> Ejemplo puesto en escena

Vemos ahora un ejemplo de funcionamiento completo. Supongamos que tenemos que controlar el funcionamiento de un soldado en un entorno virtual. Para ello nos montaremos un árbol que será más o menos complejo pero que permitirá generar un comportamiento adecuado y que podremos ir aumentando en complejidad.

Despues de varias iteraciones llegamos supongamos que llegamos a esta propuesta:

Ejemplo arbol de comportamiento

Una primera respuesta sería:

Arbol de comportamiento primer ejemplo

Por otro lado en una situación diferente podria darse el comportamiento:

Ejemplo de árbol de comportamiento 2

De cualquier forma podremos cambiar cualquier condición y cualquier acción de forma ‘muy’ sencilla o mejor dicho sabremos donde hay que ir a cambiar comportamiento de forma ‘fácil’. Conforme crezca nuestro árbol ya no será tan sencillo, pero seguro que será mucho más que si utilizamos otras porpuestas que no están tan organizadas.

> En Resumen

Una vez que vamos trabajando con árboles cada vez más extensos y complejos se hace
interesante utilizar herramientas de gestión y edición de los mismos.

Es muy interesante la charla de Ricard Pillosu de Crytek que explica las virtudes de
estas estructuras de forma muy amena y desde el punto de vista de uno de los mejores
especialistas del panorama español en materia de inteligencia artificial orientada
a los sistemas de entretenimiento.

> Videos de la Charla y Bio
> Presentación PPT

En definitiva, hemos visto que es un árbol de comportamiento y cuanto mejora la organización del código. Hemos visto que no requiere una complejidad extrema para crear las estructuras necesarias y que representa una gran mejora respecto a tratar comportamientos de forma distribuida y sin orden. A partir de aqui podemos incluir parámetros estadísticos en los
nodos para añadir aleatoriedad o incluso podemos incluir aleatoriedad a nivel de acción, permitiendo que además de cambiar el comportamiento cambie la forma en que lo lleva a cabo nuestra entidad inteligente.

Arboles de comportamiento indeterministas

Planteamientos avanzados nos permitirán llevar a cabo tácticas de grupo y comportamientos más complejos donde intervienen varios agentes haciendo que la experiencia para el jugón sea mucho más divertida y le represente un mayor reto.

A partir de aqui queda en vuestras manos tener en cuenta esta esttructura, de cualquier forma siempre será una buena adquisición para vuestra caja de herramientas del Buen BricoDesarrollador de Inteligencia Artificial, fácil y sencillo amigos!

Autómatas de estados finitos Jerárquicos para el control de comportamientos (HFSM’s)

1 comment »

Una variante de los autómatas finitos son los jerárquicos. Anteriormente se ha hablado
de la versión mas simplificada de estos mecanismos. Los autómatas finitos ’simples’ cubren gran
parte de las necesidades a la hora de controlar el comportamiento de nuestros agentes inteligentes,
sin embargo, se hacen más difíciles de utilizar cuando se ponen en juego muchos estados y se
trabaja con requisitos de rehusabilidad.

Incialmente se encuentran los autómatas de estado finito. Aumentando complejidad sobre las transiciones se
definen los autómatas de estados finitos extendidos. Ofreciendo la capacidad de paralelismo se introducen los
autómatas de estados finitos concurrentes. Finalmente, en lo que respecta a nuestro interés se encuentran los
autómatas de estados finitos jerárquicos.

Los autómatas finitos jerárquicos resuelven gran parte de este problema y permiten agrupar comportamientos
haciendo que sea más sencillo rehusar y mucho más agradable la tarea de ampliar detalles en los estados o
incluso aumentar y variar los que ya tenemos.

Ejemplo de HFSM

La foto superior muestra un ejemplo de autómata finito jerárquico.

> Qué y cómo modela la máquina de estados finitos jerárquicos

Para no marear la perdiz vamos a ver desde el punto de vista del creador de sistemas de inteligencia artificial
complejos con qué propósito se utilizan las máquinas de estado finito jerárquico ya que principalmente es el concepto
lo que va a resultar interesante desde un primer punto de vista y más allá de la tecnología subyacente.

Otro ejemplo de HFSM

Lo que modela una HFSM será una serie de comportamientos que a su vez estarán divididos en una serie de comportamientos.
Por ejemplo, para controlar el movimiento de un soldado modelado con inteligencia artificial podemos tener una serie de estados superiores que indiquen a nivel conceptual los estados por los que va a pasar. Imaginemo un primer estado ‘Llamado reposo’, una transición a un segundo estado llamado ‘Bostezar’ y una tercera transición a un tercer estado que le vamos a poner ‘Patrullar’. Con este primer autómata definimos un comportamiento a grandes rasgos. Si disponemos del conocimiento necesario, usaremos los HFSM’s sobre el segundo estado: ‘Bostezar’ e iniciaremos un nuevo autómata de estados finitos que tendrá dos estados (podrian ser 15 pero dos ya son suficientes). El primero de ellos será ‘Levantar Brazos y Bostezar’, seguido de una transición a un segundo estado que será ‘Incorporarse’. Una vez procesado el segundo subestado se devolverá el cálculo al lugar en el que se dejó en el autómata del estado superior.

Visto un posible ejemplo de aplicación y puestos en escena, podemos pasar a ver que detalles cambian respecto a los autómatas de estados finitos sencillos y que capacidad adicional aportan.

> Cómo funciona la máquina HFSM

Para simplificar supondremos dos niveles jerárquicos y nos referiremos al grupo de los de nivel superior como estados y a los de nivel inferior como subestados. Todo subestado formará parte de un estado de mayor grado jerárquico.

Ejemplo HFSM

Además de los componentes de un autómata de estados finito, encontramos nodos de entrada y nodos de salida. Estos nodos son el destino o la fuente de las transiciones que nos llevan de un superestado a un estado y de un estado a un superestado respectivamente. Supongamos que sería el equivalente a bajar un nivel en la jerarquía y volver a subirlo una vez terminados los estados.

Una transición que quede activa de un superestado a otro interrumpe el proceso que esté actualmente en marcha en grados jerárquicos menores. Respecto al resto de elementos, el funcionamiento es exactamente el mismo a las máquinas de estados finitos definidas en otros artículos.

> En Resumen

Hemos adquirido una nueva herramienta con un alto grado de adecuación a entornos en los que es necesario identificar subestados y se hace común reutilizar estados. Este mecanismo nos ofrece la capacidad de responder a diferentes eventos de una forma sencilla evitando transiciones desde cada uno de los estados, necesitando simplemente transiciones desde los superestados. Actualmente se utiliza en un gran número de propuestas comerciales por lo que ha demostrado con creces su capacidad.

Os ofrezco un documento en el que se detalla de forma muy exhaustiva el funcionamiento de los HFSM’s creado por Rajeev Alur en honor a Zohar Manna Taormina. En el vais a poder aprender de una forma más completa acercade este tipo de autómatas.

> Formal Analysis of Hierarchical State Machines

Disfutadlos!

Gestión del comportamiento mediante Autómatas de estados finitos (FSM’s)

No comments »

Un primer enfoque que podemos abordar cuando la cosa se pone fea en
materia de control de comportamiento son los Autómatas de Estados Finitos o Finite States Machines. Se pone fea cuando el número de comportamientos crece y se pone mucho más fea cuando crecen los diferentes entornos y condiciones bajo los que manifestar estos comportamientos.

Por controlar el comportamiento entendemos la necesidad de que a partir de unos determinados eventos o acciones del usuario, nuestro agente inteligente responda de una forma concreta. De este modo deberemos gestionar el comportamiento de NPCs (Personajes No Jugador), de mascotas, de plantas, puertas …etc. En definitiva, todo lo que requiera un cierto grado de reacción ante determinados
eventos.

Autómata

Una de las propuestas sencillas para llevar un poco la distribución
del comportamiento son los FSMs. Estas herramientas utilizadas inicialmente en informática teórica cobran importancia cuando queremos estructurar el comportamiento. Algunos ingenieros informáticos verán devueltas a la realidad sus peores pesadillas de sus años mozos cuando estudiaban teoría de la computación. Otros,
simplemente pensad que el infierno de Dante era el paraiso al lado de
los estudiantes de este tipo de estructuras. De cualquier modo, lo que en su dia fue una herramienta perfecta de tortura a los alumnos, ahora se torna en una buena manera de trabajar y conseguir resultados aceptables para sistemas que no alcanzan una complejidad extrema.

Pasamos a ver que son y cómo se utilizan. Los FSMs constan de varios elementos: estados, transiciones y acciones. El formalismo matemático será para aquellos interesados, bastante más riguroso. Sin embargo, el objetivo aqui es saber que son y cómo se aplican para resolver este problema.

> Partes de los autómatas FSM

Empezamos identificando cada elemento y lo aplicamos a nuestro propósito, que es utilizarlos como gestores de comportamiento. En un
autómata como el nuestro encontraremos varios elementos: estados, transiciones y comportamientos. Definimos un estado inicial que será a partir del que se procesen los cambios.

El tema es sencillo, los estados representan el momento concreto de la acción, es decir, de entre todos los posibles momentos, cuál es el que está vigente ahora. Un ejemplo claro es el del autómata de las estaciones: Empezando por un esto inicial llamado por ejemplo: ‘Primavera’, el resto de estados serán ‘Verano’,'otoño’ e ‘Invierno’.

Otro elemento es el de las transiciones. En nuestro autómata de las estaciones serán flechas que vinculan un estado con otro y que representan el paso de un estado al siguiente. Tendremos transiciones del estado ‘Primavera’ al estado ‘Verano’ y así sucesivamente para cada uno.

Finalmente tendremos las acciones, que serán propias de cada estado. Por ejemplo en nuestro caso, el autómata tendrá en el estado ‘Primavera’ asociada la acción florecer();, en invierno heladas(); y así sucesivamente. Cada estado tendrá una serie de acciones que definirán el comportamiento.

En nuestro caso un posible autómata aplicado a un juego de estrategia en tiempo real que defina el comportamiento previsto como estrategia general será:

-Estados: ‘Minar recursos’, ‘Crear Ejercito’, ‘Mejorar la tecnología’, ‘Fortificar’ y ‘Atacar’. Con un estado ‘Defender’.

Las transiciones serían las lógicas, una detrás de otra, añadiendo una transición que va al estado ‘Defender’ si ataca el oponente y que retorna al estado del que proviene una vez neutralizado el ataque.

> Funcionamiento

A partir del estado final y en función de las transiciones vamos pasando de un estado a otro ejecutando la lista de acciones que tenemos asignadas a cada estado. Cuanto más alto nivel se aplique a las acciones, más sencillo será interpretar el código. Cuanto mejor estructurado esté el autómata, mayor será la capacidad de incluir nuevos estados o mejorar los actuales.

Si una imagen vale más que mil palabras un video valdrá: “1000*Fotogramas * segundo * segundos de video” veces que una palabra. así que aqui teneis una muy breve pero concisa explicación.

Una herramienta constructora de autómatas se puede ver aqui:

> En resumen

Hemos visto qué son y cómo se utilizan los Autómatas de Estados Finitos para la resolución de problemas en los que es necesario estructurar de una forma aceptable los comportamientos que se darán lugar en nuestro sistema de inteligencia artificial.

Estos son una herramienta muy utilizada ya no solo en entornos de inteligencia artificial sino de ingeniería en general por lo que resulta una buena adquisición de conocimiento y un buen paradigma a la hora de plantear resultados a problemas que requieren de un cierto grado de división en estados.

Aqui teneis una clase rápida (1 hora) del funcionamiento de estos cacharros, cortesia del Instituto Indio de Tecnología Madras.

Y otra muy buena del mismo tipo:

De cualquier forma, vale la pena darle un poco de caña al asunto por lo que os recomiendo a aquellos que no conoceis a fondo estos mecanismos que les echeis un vistazo. La documentación es muy abundante.

Hasta la próxima

Modelos matemáticos ampliamente extendidos para la gestión del comportamiento.

No comments »

Una vez que se conocen los diferentes elementos que toman parte en la escena de
un sistema que requiere inteligencia artificial más compleja y elaborada, llega
el momento de plantearse la forma en la que vamos a gestionar el comportamiento.

Para facilitar las diferentes características que son deseables en la gestión de
entidades dotadas de inteligencia artificial (rehusabilidad de comportamientos, paralelismo,
independencia del agente
, entre otras.) se han propuesto varios modelos
matemáticos y mecanismos que permiten fcilitarnos el trabajo y adquirir muchas de
estas características deseables de un sistema complejo de inteligencia artificial.

En este artículo veremos que áreas se han extendido en mayor grado y cuál es la tendencia de
los desarrolladores en materia de gestión del comportamiento.

En primer lugar se expandieron los sistemas que usaban listas complejas y elaboradas de acciones que aplicadas a determinados contextos producian el comportamiento deseado de los agentes. Este enfoque era válido puesto que en los primeros sistemas de entretenimiento en este caso no era necesario un alto grado de complejidad ni existía un indeterminismo inherente alentorno en el que nos encontrabamos.

Controlador Play 4 (Fake Alert)
Un ejemplo de este comportamiento podía ser el de simuladores de lucha como Street Fighter donde se regian reglas del estilo a: Si (el usuario ataca) Y (Nivel de juego = alto) entonces -> Ejecuta contraataque.

Street Fighter Alpha

Posteriormente a medida que crece la complejidad se introducen elementos que aportan algo de indeterminismo para hacer menos predecible el comportamiento de los agentes. Se introducen parámetros estadísticos y medidas donde las reglas dependen en parte del azar. Un ejemplo sería, al igual que el anterior: Si (el usuario ataca) Y
(Nivel de juego = alto) Y (tiro un dado y sale mayor que 3) entonces -> Ejecuta contraataque.

Como se aprecia, la tendencia era incluir más ‘Y’s a medida que añadiamos dificultad. Conforme avanzan los sistemas de entretenimiento crecen tanto los elementos relativos al entorno como el número de agentes implicados, lo que hace que las reglas de este estilo, en su dia muy válidas y rápidas de computar, sean insuficientes y presenten soluciones de inviabilidad creciente. Un ejemplo sería el sistema de Heavenly Sword donde intervienen muchos agentes sobre entornos
muy diferentes y con habilidades distintas.

Heavenly Sword
Esta complejidad empieza a requerir un grado de organización mayor y requiere estructuras que soporten una rehusabilidad, una escalabilidad y una cambiabilidad acordes a las variaciones de puntos de vista de los departamentos de diseño y de márqueting de las productoras de juegos. El creador de inteligencia artificial debía ahora poder modificar de forma rápida los comportamientos en función de decisiones de diseño o por requisitos de diferentes plataformas. Empiezan a surgir soluciones que tiran del modelo matemático de autómatas de estados finitos (Finite State Machines) donde cada momento queda definido por un estado y a cada estado se puede llegar mediante transiciones (eventos/peticiones del usuario/azar). Cada uno de estos estados tendría asociada una lista de acciones o comportamientos a llevar a cabo por el agente o agentes que tiene asociado.

Automata de Estados Finitos

Conforme la complejidad de los sistemas de entretenimiento aumentan la propuesta de Autómatas de Estados Finitos para modelar el comportamiento deja de ser efectiva. Se hace necesario agrupar comportamientos, definir nuevos cambios de estado y aplicar estructuras más flexibles y complejas al mismo tiempo. Surgen propuestas con lo que llamamos autómatas de estados finitos Jerárquicos (o Hierarchical Finite State Machines HFSM). Con ellos se resuelve en gran parte la rehusabilidad y se añade variabilidad en los comportamientos.

Autómata de Estados Finitos Jerárquico

Los HFSM siguen siendo complejos y requieren un alto grado de comprensión por parte de los desarrolladores de IA. Lo que los hace poco competitivos en un entorno tan cambiante como el de la Industria del Entretenimiento. Si bien cumplen su comentido, les falta un grado de intuitividad que aportan otras soluciones como los Árboles de Comportamiento (Behaviour Trees). En este último enfoque organiza del mismo modo los comportamientos de forma jerárquica pero permitiendo agrupaciones en forma de árbol que permite agrupar comportamientos y hacer efectivos diferentes estructuras de forma mucho más intuitiva cuando el sistema empieza a ser realmente complejo.

Detalle arbol de comportamiento

Cada uno de estos enfoques es válido en su entorno correcto y no se puede decir a priori que uno sea mejor o peor, siempre es necesario aplicarlo al entorno en el que nos vamos a mover y solo la experiencia te permitirá descartar una opción u adoptar otra con un mayor grado de seguridad.

El resultado de cualquier modo, será que cumplirás tus objetivos pero la dificultad será mayor o menor. Y por otro lado cuando tengas que añadir o modificar comportamientos, te será más o menos complejo. Te animo a que le eches un vistazo a los artículos que profundizan un poco
más en cada uno de los enfoques.

Disfrútalo.

Distribución jerárquica de las responsabilidades. Comandantes y subcomandantes

3 comments »

A medida que los sistemas se tornan más complejos, nos será necesario distribuir el comportamiento y categorizarlo de forma que podamos gestionar de forma independiente cada uno de ellos.

Será necesario distribuir de algún modo la forma en la que se abordan los diferentes problemas que van surgiendo. En el caso de un juego de estrategia, puede ser necesario llevar una estrategia a varios niveles, por ejemplo en un nivel superior se pretenderá planificar un desarrollo típico (minar recursos, construir un ejército y atacar) y a un nivel más bajo puede pretenderse explorar el mapa o crear estrategias inferiores de mejoras de edificios y unidades.

Para esto utilizaremos estructuras que permitan distribuir y definir los diferentes factores y estrategias. Una solución factible es el uso de comandantes es decir la utilización de una distribución jerárquica.

> Comandantes y subcomandantes en inteligencia artificial.

Del mismo modo en el que se distribuirian las tareas en cualquier sistema jerárquico, al aplicar este concepto en IA tenemos que distribuir objetivos por un lado y abstracción por otro. Conforme bajamos en la escala jerárquica tendremos una distribución de objetivos más cercana a bajos niveles de abstracción (encontrar minas, proteger perímetro, etc) y conforme subimos en la escala serán menos precisos y abstractos (obtener solvencia económica, forjar ejército etc.)

Comandante

Un comandante tendrá una serie de elementos a su cargo y será el indicado de distribuir sus recursos a los subcomandantes. Por otro lado, los subcomandantes serán los encargados de pedir recursos a su superior y de administrar los que tienen para llegar al objetivo concreto.

El comandante puede crear, substituir y relevar subcomandantes conforme a la estrategia de juego. En un momento determinado un subcomandante puede ser necesario para, por ejemplo escrutar el terreno con la finalidad de obtener la posición de las minas. Una vez conseguido este objetivo, los recursos pueden ser liberados tanto los vinculados al juego como los vinculados a memoria interna.

Un posible escenario es el de un comandante que tiene por objetivos atacar al oponente. Inicia la actividad con tres subcomandantes: un administrador de recursos, un scout, un constructor y un subcomandante de guerra. Para ello en las primeras fases del juego suministrará mayores recursos al administrador de recursos y una vez se cumplan los requisitos variará su estrategia. De este modo al inicio el subcomandante bélico no tendrá demasiada relevancia y en los momentos más avanzados del juego cobrará mayor responsabilidad.

> Distribución de subcomandantes apropiada en un juego de estrategia.

Aunque hay una infinidad de propuestas posibles que pueden resultar perfectamente válidas, los más probable es que de una u otra forma las responsabilidades que se distribuyen en esta taxonomía de comandantes figuren completamente o en su gran mayoría.

Encontraremos por tanto varios tipos de subcomandantes, entre ellos los que se comentan a continuación:

- Subcomandante recolector. Se encargará de minar minerales utilizando trabajadores. Hará los cálculos pertinentes para definir el número y la distribución óptima de los trabajadores entre los diferentes centros y puntos de obtención de recursos.

Sus órdenes pueden varias en función de la estrategia general de sus superiores en este caso el del General.

The Daimyo Ladies Procession

- Subcomandante constructor. Se encarga de distribuir los diferentes edificios necesarios en cada momento del juego. Actualiza las construcciones en función de si son eliminadas, sufren daños o si hay excedente de materiales necesarios.

Subcomandante Ingeniero

- Subcomandante de inteligencia. Se encarga de descubrir información acerca del entorno y del enemigo. Tendrá asignados una serie de recursos que harán que sea más o menos presente en el desarrollo. En un primer lugar puede tomar estrategias de eliminación de la niebla del entorno y una vez alcanzados estos objetivos puede distribuir sus scouts para patrullar determinadas áreas susceptibles y dar el aviso al General en caso de que tropas enemigas penetren en el perímetro.

Comandante de Exploracion

- Subcomandante de defensa. Establece regiones con diferentes grados de seguridad y se encarga de defender y fortificar las bases en función de la estrategia que se le haya definido. Puede acceder a la información general obteniendo datos de esto de las areas. Distribuye las unidades de forma que sean efectivas para la defensa y actua en consecuencia cuando se detecta un ataque. Será encargado de establecer edificios y unidades defensivas.

Defense Commander

- Subcomandante de ataque. Crea el ejército y engloba la estrategia de ataque y las tácticas de combate. Buscará puntos donde emboscar y acechará unidades. Distribuirá las unidades propias de forma que sean lo más efectivas posibles.

Subcomandante de Ataque

- Subcomandante de científico. Pone en marcha las estrategias de evolución de unidades militares y civiles así como la mejora de los edificios o la consecución de tecnologías. Será el encargado de aumentar las capacidades de los elementos de la civilización.

Subcomandante Científico

> Ejemplos de enfoque estratégico.

Utilizando estos mecanismos, nos podemos encontrar en la necesidad de generar estrategias diferentes para conseguir nuestros objetivos. Vemos tres enfoques diferentes de lo que podian ser los planes a ejecutar durante el desarrollo de un juego.

—> Juego o escenario primero (reunión de recursos). El ‘Comandante General’ instancia un ‘Subcomandante Recolector’ y le pasa todas las unidades disponibles. Recursos y capacidad de producción totalmente para el recolector.

­—> Segundo escenario. El General genera escuadrones y agrupaciones diferentes. Estos escuadrones son asignados al ‘Subcomandante de Ataque’ y son distribuidos para empezar a atacar.

El General se encarga básicamente de distribuir los recursos entre las diferentes bases en función del grado de necesidad previsto para cada una de ellas. Se puede basar en el análisis del terreno para detectar areas ‘calientes’ o con un mayor valor estratégico. Es posible delegar parte del trabajo a los subcomandantes para que hagan un preproceso de sus necesidades en función del terreno, de este modo la asignación de recursos por parte del General se hará en base a las diferentes peticiones de los Subcomandantes o la las distribuciones propuestas por el o ellos mismos segun sea el caso.

—> Juego tercero. El General gestiona un grupo de bases de forma independiente acorde a la estrategia general de:

1) Generar un nivel de producción aceptable.
2) Construir un cuartel
3) Producir simultaneamente trabajadores y guerreros mientras sea posible.
4) Si hay al menos dos bases que reciben recursos construir una factoria.
5) Producir marines y tanques a la mayor velocidad posible.

Estos son solo algunos de los ejemplos que nos podemos encontrar. Un juego actual está formado por un gran conjunto de reglas de este estilo que son distribuidas de forma más o menos eficiente entre las estructuras internas del programa.

Este es uno de los elementos que incluye totalmente funcionales el juego de estrategia open source ORTS que ya se ha tratado en artículos anteriores. Los más interesados podeis estudiar la IA de este sistema a fondo sabiendo que una de las bases es la gestión mediante el uso de comandantes.

Las clases están completadas y podeis encontrar todos los tipos de comandantes anteriormente comentados y puestas en escena de las diferentes estrategias de juego.

En definitiva, hemos visto que el uso de comandantes en sistemas de IA permite organizar y dividir las necesidades de estrategia y de distribución de la lógica de nuestro sistema de una forma intuitiva y abordable. Conforme la dificultad o la precisión crecen se pueden incluir mayores rangos para los diferentes gestores, es decir, mayor precisión en las responsabilidades.

Hasta la próxima.

Gestión del comportamiento en sistemas de entretenimiento.

No comments »

El comportamiento aplicado a los sistemas informáticos se refiere a la forma en que nuestro sistema responde en el tiempo y a la forma en la que resuelve los problemas. Conforme avanza la complejidad del sistema, se hace más necesario definir una lógica interna organizada y capaz de ser utilizada de forma eficaz y escalable.

La gestión de la lógica será un elemento cada vez más importante en sistemas que requieran un amplio abanico de funcionalidades y que dependan de entornos no siempre fijados ni fijables y de comportamientos del usuario no definidos ni definibles. Si en nuestro sistema pudieramos definir punto por punto el comportamiento que se requiere, no sería necesario ningún sistema de gestión del comportamiento puesto que todo evento vendría determinado por una o varias acciones. En nuestro caso nos enfrentaremos a situaciones en las que no todo está definido (la forma en que la unidad se desplaza por el terreno, la forma en la que se recibe un ataque, la forma en la que se distribuyen y minan los recursos…etc). Será necesario definir comportamientos más complejos que los basados en reglas.

El comportamiento en los sistemas de entretenimiento cada vez cobra mayor importancia. Desde esta perspectiva se puede observar que durante el desarrollo de un juego actual se llevan a cabo muchos cálculos relativos al comportamiento y sobre unidades y elementos muy diferentes. El comportamiento no solo es el asignado a unidades que representan humanos o criaturas con diferentes objetivos sino que se aplica también a elementos más sencillos como los que forman parte del entorno o del escenario. Gestionar bien el comportamiento es una tarea crítica cuando abordamos el diseño de un sistema medianamente complejo que requiera del uso de componentes de inteligencia artificial.

La planificación será clave, es decir, la capacidad de organizar y llevar a cabo tareas más o menos abstractas y finalizarlas con éxito con un determinado propósito. En un juego de estrategia planificar podría ser: explotar recursos, amurallar el perímetro, reunir un ejército, mejorar el estado de las unidades y atacar al enemigo.

Es importante tener la capacidad de rehusar estados y de agrupar comportamientos. Cuando el sistema crece, se suelen añadir muchos requisitos y condiciones que hacen que el control lógico crezca de forma exponencial y la rehusabilidad del mismo decrezca en la misma medida.

La gestión concurrente de los comportamientos también se hace necesaria. Muy frecuentemente será necesario manejar un comportamiento en paralelo como el manejo del desplazamiento o pathfinding sobre una misma unidad mientras que se gestiona el comportamiento de la animación por otro lado.

Para llevar este comportamiento se suelen utilizar algunos mecanismos como los gestores de comportamiento que se basan generalmente en el uso de autómatas de estados finitos (FSM), autómatas de estados finitos Jerárquicos (HFSM) o en árboles de Comportamiento (BT).

Otro de los conceptos que manejaremos serán las respuestas a eventos y por lo tanto las variaciones del comportamiento en base a los estímulos o señales recibidos. Deberemos ser capaces de modificar el comportamiento en función del entorno, del tiempo o de la situación en la que nos encontremos.

Estos son detalles que son necesarios conocer así que manos a la obra!

Agentes inteligentes. Precursores del Agente Smith

No comments »

Uno de los conceptos ampliamente utilizados en la inteligencia artificial es el concepto de Agente. Un agente como descripción general es un elemento lógico que definimos con un propósito concreto y que toma acción en un momento determinado de la ejecución con la finalidad de acercarnos a la consecución de nuestros objetivos.

> 1. Estructura del agente

Un agente tiene generalmente una estructura en la que se identifican 4 elementos: capacidad de percepción, capacidad de acción, objetivos y entorno.

Agente Smith

–> 1.1 La capacidad de percepción viene definida por los elementos capaces de reconocer de los que dispone el agente. Pueden ser sistemas sencillos en los que la percepción puede ser la detección o no de intrusos en su área de acción (definida fácilmente con un booleano) o bien mecanismos más complejos como una matriz de NxM que refleje la visión del agente en una orientación y momento concreto del tiempo y que requerirá un proceso más intenso e incluso una abstracción para agilizar cálculos.

–> 1.2 La capacidad de acción vendría definida por el conjunto de los movimientos, cálculos o respuestas en general que puede llevar a cabo el agente. Pueden ser tan sencillos como (giro izquierda/giro derecha/avanzar/retroceder) o más complejos como (evadir/emboscar/atacar/confundir).

–> 1.3 Los objetivos son la esencia del agente. El comportamiento del mismo irá orientado a la consecución de los mismos.

–> 1.4 El entorno es una característica externa al agente pero que condiciona su comportamiento. Puede ser un mundo tridimensional o una abstracción del mismo reducida a eventos. En otros casos puede ser una
matriz la que modele el entorno o incluso un grafo que represente una topología concreta.

Agentes Inteligentes

> 2. Tipos de agentes

Existe una primera clasificación de los agentes en función de diferentes aspectos como su grado de percepción del entorno o de su capacidad de proceso lógico.

Agentes de mAtrix

–> 2.1 Agentes de reflejo simple

El primero de ellos se basa en reglas sencillas y utiliza aserciones lógicas para llevar a cabo el proceso lógico que decide que acción tomar a cabo. No se tiene en cuenta el entorno donde se desenvuelve más que en la creación de las reglas.

Agentes de lógica Simple

Son rápidos y muy apropiados si el mundo es fácilmente modelable y las acciones generan el resultado apropiado de forma determinista y predecible.

–> 2.2 Agentes bien informados de todo lo que pasa

En este aspecto se requiere un modelo más preciso del entorno donde las acciones que llevamos a cabo produzcan un resultado concreto y podamos observar la evolución del mundo.

Agentes bien informados

–> 2.3 Agentes basados en metas

Este tipo de agentes son más complejos puesto que requieren estructuras más complejas para garantizar comportamientos donde puede ser necesario el uso de técnicas de planificación o de búsqueda complejas que lleven al propio agente a la consecución de sus objetivos.

Agentes por metas

Se modificará el comportamiento en base a la retroalimentación recibida de aplicar las acciones concretas variando así su planificación o sus parámetros de búsqueda.

–> 2.4 Agentes basados en utilidad

Estos se utilizan cuando no solo es necesario llegar a unos determinados objetivos de forma concreta sino que es necesario llegar de una forma eficiente.

Para ello se utiliza una función de utilidad acotada entre 0 y 1 que determina el grado de acercamiento a la meta que producirá el abanico de acciones disponibles. Distribuyendo dicho contenido en un acercamiento nulo (funcion de utilidad igual a cero) y una consecución de la meta (valor igual a uno).

De la correcta definición de la función de utilidad depende el grado de desempeño del agente.

> 3. Arquitectura de un agente

Existen diferentes arquitecturas actualmente.

Codigo Fuente de Agentes de Matrix

–>3.1 Basadas en la Lógica.

Conocidos también como agentes deliberativos, toman decisiones basadas en funciones lógicas que caracterizan el comportamiento. Un ejemplo sería: SI sensor_choque == ACTIVADO ENTONCES dirección = atrás.

–>3.2 Agentes reactivos

Este tipo de agentes actúa en función de los estímulos externos sin tener en cuenta el tiempo pasado del entorno ni el futuro del mismo. Responden de forma directa proporcionando un tiempo de respuesta y de proceso muy alto.

–>3.3 Arquitectura creencia-deseo-intención.

La toma de decisiones pasa por la interacción y el proceso de los elementos almacenados en las estructuras de creencias, deseos e intenciones. Se basan en deliberar primero que hay que hacer en base a los deseos utilizando las creencias y seleccionando posteriormente las acciones a realizar del grupo de intenciones.

–>3.4 Arquitecturas híbridas.

Se tienen en cuenta varias capas que utilizan conceptos del resto de arquitecturas. Suelen ser muy eficaces para el entorno concreto en el que se desarrollan pero poco generalizables a problemas que no sean muy similares.

La elección de una o de otra será en base a nuestro entorno por lo que no hay una mejor o peor solución sin la aplicación al problema en concreto.

> 4. Los tipos de Entornos o Ambientes

A la hora de construir un agente inteligente se tendrá muy en cuenta el entorno para el que se crea. Podemos encontrar varios tipos de entorno.

–> 4.1 Accesibles/No accesibles.

Si a través de los sensores el agente tiene acceso al estado completo del entorno, este es accesible.

–> 4.2 Deterministras/No deterministas.

Si es posible conocer a partir del estado actual y la decisión tomada del agente, el estado futuro del propio entorno y del mismo agente.

–> 4.3 Episódicos/No Episódicos.

Es posible dividir el estado del agente en episodios con características propias.

–> 4.4 Estáticos/Dinámicos.

El ambiente puede cambiar mientras el agente toma una decisión.

–> 4.5 Discretos/Continuos.

Cuando es posible concretar todos los estados del entorno, este es discreto. Cuando no es posible debido a la cantidad y al tipo de variables que intervienen, este será continuo.

Los entornos por lo tanto condicionas en gran medida al agente que queremso construir. De la experiencia dependerá que creemos agentes más precisos y adaptados al entorno y que desempeñen por tanto su trabajo con un mayor grado de precisión y eficiencia.

Hasta la próxima!

Conceptos para la Solución de problemas de Estrategia mediante técnicas de Inteligencia Artificial

No comments »

A la hora de abordar un problema de estrategia utilizando inteligencia artificial deberemos tener en cuenta una serie de
conceptos que toman parte en el panorama actual de soluciones y
que son tremendamente útiles y necesarios en muchos casos.

Este resumen da lugar a una serie de artículos orientados a describir con más detalle cada uno de los elementos y permitirte profundizar en el mundo de la Estrategia utilizando IA.

> Que se aborda y que se resuelve …

Principalmente se resuelven problemas en los que es necesario llevar a cabo acciones no sencillas de coordinar y bajo un desarrollo largo
en el que sería difícil describir de forma directa todos los pasos tener en cuenta.

Se orienta a problemas en los que es necesario reaccionar al entorno
y tener una estrategia diferente en función del mismo.

Un ejemplo claro es el de juego de estrategia donde es necesario llevar un plan maestro (reunir recursos, fortificar la base, crear un ejército y atacar) pero además se necesita tener un alto grado de
libertad para responder a eventos en los que el plan varía, por ejemplo el enemigo ataca la base.

Estos mecanismos se pueden abordar de una forma directa tratando caso
por caso pero el resultado será un código que crecerá exponencialmente y que será difícilmente rehusable, lo que hará que al primer cambio importante nos veamos incapaces de resolverlo en un tiempo aceptable.

Para ello, se han ido desarrollando una serie de técnicas y poniendo en práctica conceptos tanto de la teoría de autómatas como de otros entornos académicos con resultados aceptables y gran difusión entre los desarrolladores.

> Qué elementos intervienen…

Los temas a tener en cuenta en un primer estadio de conocimiento, son los siguientes:

- > Agentes inteligentes.
- >Control de comportamiento.
- >Distribución jerárquica de las responsabilidades.
- >>Comandantes.
- >>>Distribución de subcomandantes en un juego de estrategia.

- >Gestores de comportamiento lógico
- >>>Autómatas de estados finitos (FSM)
- >>>Autómatas de estados finitos Jerárquicos (HFSM)
- >>>Áboles de Comportamiento (BT)
- >Planificadores
- >Paralelizadores

- >Táctica a bajo/alto nivel.

- >Estrategia de combate.
- >>>Táctica VS Estrategia

> En resumen

Cada uno de estos apartados son claves y aportan parte del conocimiento básico necesario para afrontar un problema de inteligencia artificial orientado tanto a los juegos de estrategia como a cualquier otro problema donde se requiera aplicar sistemas con un alto grado de planificación, elementos lógicos e incertidumbre por lo que os servirá para cualquier problema de esta índole.

Disfrutadlo.