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.

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.

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.

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.

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.

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.

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.

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.)

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.

- 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 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.

- 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.

- 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 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.

> 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.

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!

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.

–> 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.

> 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.

–> 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.

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.

–> 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.

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.

–>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!

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.

Una vez terminada la serie de artículos relacionados con el pathfinding
se podría pensar que ya sabemos suficiente sobre el tema y que podemos
abordar cualquier problema que requiera del uso de esta disciplina de la inteligencia
artificial. Sin embargo, nada más lejos de la realidad puesto que esto
es solo el comienzo de una gran variedad de ramas dedicadas a este concepto.

A partir de aqui los interesados en el tema pueden abordar diferentes áreas
siempre que las necesidades lo requieran. Una vez terminados los conceptos
relacionados con el pathfinding que hemos visto, el aprendizaje usa conceptos
generalmente relacionados por lo que se hace muy gratificante y comprensible en
la mayoría de los casos.

Algunos de las disciplinas que complementan el Pathfinding son:

> Caminos para Múltiples unidades. Group Pathfiding

Búsqueda de caminos para grupos. Es muy común que grupos de unidades tengan
que ser desplazados. En este caso se dan varios problemas sobre todo en
cuellos de botella del mapa o en casos en los que el grupo debe cambiar

de posición relativa.

>Más aqui

> Caminos suaves. Smooth Pathfinding

Además de generar una serie de posiciones que lleven al destino, en ocasiones
podemos buscar también que esta trayectoria sea más realista mediante el uso
de caminos suaves. Para esto existen técnicas y conceptos a tener en cuenta que
nos pueden ser muy útiles y que sirven para la mayoría de los casos en función
de cada representación del mapa.

>Ver más

> Cálculos eficientes.

Existen técnicas que se orientan a mejorar el desempeño de estos algoritmos. En
ocasiones tienen un coste muy alto en materia de cálculo y siempre están sujetos
a consumir tiempo de CPU sobre todo en las aplicaciones en las que es necesario
un desplazamiento contínuo de las unidades o agentes como puede ser una aplicación
de estrategia en tiempo real.

>Ver más

> Diferentes representaciones

A la hora de abordar estos algoritmos de búsquedas de caminos, muchas veces tenemos la
posibilidad de definir la representación del mundo en la que nos moveremos. De esa elección
partirán las diferentes necesidades del algoritmo y el grado de desempeño. En determinadas
situaciones será interesante utilizar representaciones como los quadtrees, en otras utilizaremos
grafos y en algunas nos moveremos por el entorno de casillas que ha sido el más abordado en
la lista de artículos de la materia que se ha llevado a cabo. De cualquier modo cada una de ellas
tendrá sus ventajas y sus inconvenientes y de nuestro grado de conocimiento dependerá que escojamos
la opción más adecuada.
>Ver más aqui

> Pathfinding dinámico

A veces no es necesario disponer de todo el camino sino tener de forma inmediata una dirección de
desplazamiento y una velocidad de movimiento concretas. El pathfinding dinámico se centra en generar
soluciones que van variando en el tiempo pero que acercan al agente a su objetivo final. Existen soluciones
que emulan el comportamiento animal en el aspecto de búsqueda de caminos y que trabajan conceptos como
el seguimiento de otros agentes, la evasión en caso de perseción y muchos otros comportamientos que
requieren de esta disciplina para su correcto funcionamiento.

>Ver más

Hay mucho trabajo pendiente y muchas más áreas que abordar en este campo
de la inteligencia artificial por lo que todos los interesados son bienvenidos.

A disfrutarlo!

Abordamos para terminar esta serie de artículos referentes al Pathfinding,
una solución casi óptima al problema propuesta por el Dr. Daniel Harabor.
En ella se propone hacer una búsqueda de caminos similar a la que hariamos
las personas buscando en primer lugar caminos rápidos para largas distancias
y ajustando la búsqueda una vez nos encontramos cerca del objetivo.

Nuestro problema es, por lo tanto, definir una abstracción donde a un nivel
superior se represente el mapa de una forma rápida y abordable por los algoritmos
de búsqueda. Una vez tenemos esta abstracción utilizar un procedimiento más preciso
para llegar al punto correcto. Dividiremos el mapa en sectores.

>Abstracción jerárquica

La forma en la que nos abstraemos de una forma adecuada será la siguiente:

1. En primer lugar dividimos el mapa anotado en un set de clusters adyacentes conectados por Entradas.Veremos más en detalle como.

2. En segundo lugar compactamos el grafo generado usando algunas técnicas para mejorar el resultado eliminando innecesarios con la finalidad de tener los nodos mínimos.

3. Por último describimos el Algoritmo A* Jerárquico Anotado HAA* (Hierarchical Annotated A*) algorithm (HAA*).

El objetivo de manejar varios terrenos y abstraernos del mapa se ha conseguido pero con
el coste de disponer de mucha información redundante.

> Primer paso. Definir Sectores y entradas

Ahora que hemos visto el procedimiento a realizar a grandes pasos, vamos
por partes. Crearemos los sectores y definiremos las entradas. Esto se puede
hacer de forma jerárquica definiendo varios niveles por ejemplo doblando el
tamaño de los sectores.

-Buscamos los valores del grafo:

En el ejemplo de autor identificamos dos tipos de terreno, tierra (ground) y agua
(water) la capacidad queda marcada como capability y el grado de claridad como clearance.
En función del espacio libre el valor de claridad será mayor.

Vemos los valores a marcar en el algoritmo entre los sectores C1 y C3.

-Identificamos las entradas entre clusters

Una entrada queda definida como un área libre de obstáculos con el máximo
tamaño que existe entre el borde de los clusters. Se representa con un
punto de transición que marca que un agente de tamaño menor o igual puede
pasar al sector concreto. Se marca como una arista de peso 1 y con un tipo
concreto y una claridad concreta. La nueva representación será por tanto
una lista de aristas a modo de grafo donde cada una tendrá las transiciones
de un sector a otro y la claridad y tipo de terreno asociado.

En la foto superior se aprecia que hay gran cantidad de aristas redundantes.

> Segundo paso. Eliminar información redundante.

Este segundo paso pretende compactar la información para reducir el volumen
de datos que se está manejando y hacer por lo tanto que los algoritmos de búsqueda
sean más rápidos a la hora de encontrar una solución.

Para ello vamos a aplicar dos técnicas diferentes propuestas por el autor.

- Dominancia fuerte. Si dos aristas de longitud igual conectan el mismo par
de nodos y los dos son travesables por la mismas unidades solo es necesaria
la de claridad mayor. Esto se llama así porque una de las aristas, la de mayor
claridad, domina a la otra. En la foto inferior de la derecha vemos el resultado.

- Dominancia débil. En este caso se tratará de minimizar el número de transiciones
entre sectores. Para conseguir esto analizaremos cada par de aristas internas del
sectores probando que si eliminamos una de ellas el mapa sigue representando la
misma información. Solo las aristas que son travesables por el mayor número de
agentes son retenidas, el resto se eliminarán. El resultado se aprecia en la foto
superior de la izquierda.

El resultado de aplicar los dos procedimientos es el que vemos en la figura
inferior.

El resultado de aplicar estas técnicas puede suponer de un 3 a un 10% de incremento
en la longitud de los caminos encontrados pero sin embargo disminuye en un 50% de media
el tamaño de la memoria requerida para almacenar los mapas y el desempeño del algoritmo
aumenta considerablemente.

> Tercero. Aplicamos el algoritmo A* Jerárquico Anotado

El proceso de encontrar el camino será directo. Como detalle general
se distinguen dos procesos.

1. Insertamos dos nodos temporales en el grafo abstracto que representen
el inicio y final del camino. Conectamos el grafo con estos dos nodos
buscando un camino desde las dos posiciones a cada transición en el
sector local.

2. Utilimos A* para encontrar el camino más corto en el grafo abstracto
que hemos generado. Al final de la búsqueda eliminamos ambos nodos que
hemos incluido.

Se incluye en el algoritmo los conceptos de tamaño del agente y de capacidad
que expresa las vias que puede recorrer el agente en cuestión.

> En Resumen

Este algoritmo nos permite generar de forma rápida caminos para los entornos
que nos propongamos de una forma mediante la que generando una correcta abstracción
del mundo, nos acercamos a la forma en la que los seres humanos planificamos la
búsqueda de caminos, es decir, partiendo de bloques más grandes conectados y afinando
la precisión conforme nos acercamos al destino.

Se ofrece el código fuente completo, agradeciendo el material al Dr. Daniel Harabor:

>Codigo
>Artículo del algoritmo (paper)

En este pequeño comentario se abordará el procedimiento para conseguir un
algoritmo de pathfinding apropiado para unidades de diferente tamaño y diferentes
capacidades (anfibias, terrestres, aereas …etc). Para ello se utilizará el concepto
de Algoritmo A Estrella Anotado.

Este algoritmo se basa en el A* Simple y tiene en cuenta un grafo de claridad
para manejar el entorno.

La variante respecto al algoritmo simple de A * es subyace en el hecho de que en el propio
algoritmo tenemos que pasar el tamaño del agente y su capacidad. El pseudocódigo es el siguiente:

almacenamos posición de inicio en la lista de abiertos.
para cada casilla de la lista de elementos abiertos
si la casilla actual es el destino,
retorna camino.
sino,
para cada vecino adyacente al actual
si el vecino es de la lista de cerrados pasarlo
sino,
si el vecino ya está en la lista de abiertos, actualizamos el peso.
sino,
si la claridad del vecino con su capacidad > tamaño de la unidad,
ponemos al vecino en la lista de abiertos
sino, eliminamos al vecino
ponemos el nodo actual en la lista de cerrados.
si la lista de abiertos está vacia, retornamos error.


Se ofrece el código fuente escrito por Daniel Harabor
> Código
> Código adicional de la librería de Pathfinding de la Universidad de Alberta

Hasta la próxima

Abordamos el tema del Pathfinding desde un punto de vista más formal
donde definiremos una estructura matemática que nos permitirá buscar
de una forma óptima y precisa el camino a encontrar.

Este procedimiento es válido tanto en entornos virtuales aplicados a
juegos, como a entornos reales donde por ejemplo debemos fijar el modo
de desplazamiento de un robot móvil.

Estos procedimientos tienen un coste importante en materia de cálculo
por lo que no serán válidos en todos los aspectos. Mover un volumen de
unidades alto en tiempo real será una tarea difícil aplicándolo desde el
punto de vista convencional. Sin embargo, existen adaptaciones de los
procedimientos que veremos a continuación que permiten utilizarlos tambien
con un grado de desempeño importante.

> Definimos el entorno

En primer lugar vamos a fijar los elementos que intervienen en este
paradigma de pathfinding. El cálculo se hace en base a las 2 dimensiones
pero puede ser extrapolado a 3D sin mucha complicación.

Sea el destino un punto g € del grupo de los reales R2
Sea el agente a desplazar r € a los reales R2

El paradigma es el de una carga que se ve atraida por el punto de destino
y repelida por los diferentes obstáculos. A partir de funciones matemáticas
nos construiremos:

-Primero un entorno que represente la idea
-Segundo un mecanismo que nos permita desplazar la carga hasta su destino,
es decir, calcular el camino.

En primer lugar podemos ver el mundo a construir como una forma de
distribución de energía potencial. En este caso lo veríamos como una
cuesta inclinada donde nuestro vehículo movil sería una bola de acero
que por su energía potencial se desplaza al punto de destino (con energía
potencial más bajo que el resto). Los obstáculos serían protuberancias o
badenes sobre la propia cuesta inclinada, por así decirlo.

> Definimos una función potencial:

Ahora fijamos la función potencial como una suma de dos valores, para
hacernos la vida más fácil.

U(q) = Uatt(q) + Urep(q)

Donde:

-Uatt(q) representa las fuerzas de atracción, es decir, una cuesta inclinada
que nos lleva diréctamente al punto de destino y que no contempla los obstáculos.
Lo llamaremos el potencial de atracción,

-Urep(q) representa las fuerzas de repulsión. Aquellas que hacen que cuando la
carga (nuestro agente movil) se acerque, sea repelido.

> El potencial de atracción

Nos interesa que el potencia de atracción sea una cuesta inclinada
sin saltos y mónotona decreciente, es decir, desde el punto de partida
hasta el de destino, siempre sea decreciente. Moverse en dirección opuesta
al destino debe venir acompañado de un aumento de potencial y por tanto no
ser viable.

Algunas de las funciones a considerar pueden ser las que vemos en la figura,
se muestra también el gradiente negativo, es decir, como disminuirían
estas funciones:

Combinamos el potencial aplicando una función si estamos a una distancia
mayor de d* del destino y otra para menos de d*. Podemos ir incluyendo
diferentes comportamientos añadiendo sectores nuevos en función de la distancia.

El resultado es el de la figura, una función monótona decreciente sobre la que
podemos aplicar mecanismos de optimización que nos lleven al mínimo absoluto, que
coincide con nuestro destino.

Puesto que la velocidad de nuestro agente dependerá de la velocidad con la que
se descienda la ‘cuesta’, nos puede interesar aplicar diferentes inclinaciones
a medida que nos alejamos del punto de partida.

> El potencial de repulsión

Ahora tenemos que incluir los obstáculos que nos encontramos en el camino para que
no hayan colisiones. Para ello utiliazremos el potencial de repulsión.

Para cada obstáculo buscaremos crear lo siguiente:

Para ello utilizaremos una función que cree un ‘cilindro’ como el que vemos. Es posible
crear funciones más suaves pero para ejemplificar y entender el mecanismo ya nos vale. En
general es bueno tener funciones decrecientes sin saltos y no podemos dar por válida esta
función potencial por el hecho de que al sumar a la de potencial de atracción tendremos como
resultado una función monótona decreciente.

Se añade el gradiente, la forma en la que disminuye.

El resultado conjunto será:

> Ahora aplicamos las fuerzas para mover al agente

Tenemos ya nuestra representación del mundo como la queriamos

Utilizaremos el gradiente descendiente como una forma sencilla
de llegar al mínimo de potencial

El gradiente nos especifica, por así decirlo, hacia donde se movería
una carga que está sometida a todas las fuerzas que actúan en ese punto.
Por lo tanto indica la dirección de desplazamiento de la carga en cada uno
de los puntos.

Cada carga actúa sobre el punto concreto y el gradiente del potencial es por
tanto la dirección de la fuerza resultante y el grado con el que esta actúa.

El algoritmo que seguiremos para aplicar el gradiente descendente será:

Definimos € como la variación mínima que estamos dispuestos a tomar como un nuevo valor delalgoritmo. Si las variaciones son muy bajas ya damos por buena la solución.

Fijamos el parámetro alfa como un valor que escala el gradiente [0, 1] , es dicer, le da mayor o menor grado a cada paso. Reducirlo aumenta la precisión pero ralentiza el proceso. Puede ser una función que dependa de ‘i’ como es este el caso.

A cada momento la nueva posición es calculada en base a la anterior y al decremento de gradiente concreto.

Para entenderlo mejor, un vehículo movil que este en una posición q(qx, qy) le corresponderá una nueva posición qn(qnx, qny) calculada a partir de la suma de la actual y el gradiente que en este caso será una componente en x (gx) y otra en y  (gy). Resultando:

qn(qnx, qny) = q(qx, qy) + g(gx, gy) como una suma de vecotores normal componente a componente.

> Ajustes sobre el algoritmo

Utilizar este procedimiento matemático puede ser costoso si queremos
buscar un camino desde el inicio hasta la meta, sin embargo, podemos
tratar dos valores fundamentales para hacer que el coste de cálculo se
facilite en detrimento de la precisión del camino y de las posiciones
destino parciales a anotar.

En primer lugar podemos hacer un cálculo basado en un parámetro que
aplique el cálculo de forma iterativa un número Ndeterminado de veces
y con esto iniciar el desplazamiento en la dirección adecuada. Para N=1
ya podemos calcular la dirección de este modo:

-Sea pactual(q) la posición actual del agente móvil
-Sea p1(q) la posición obtenida por la aplicación del procedimiento anterio
-La dirección de movimiento del agente ya puede ser comunicada como
direccion(q) = arctg(p1(qm1)-pactual(qm1) / p1(qm1)-pactual(qm1))

-La fuerza de desplazamiento se corresponde con el módulo del vector generado,
nos sirve como parámetro para decidir con que velocidad moveremos el
agente.

fuerza(q) = sqrt(p1(qm1)-pactual(qm1)^2 + p1(qm2)-pactual(qm2)^2)

En segundo lugar podemos variar la amplitud de cada paso (nuestro parámetro alfa)
del algoritmo haciendo que la precisión baje a costa de una gran mejora en materia de coste
de cálculo. Esto sería aplicado a nuestro caso, hacer que las unidades reciban
menos instrucciones de movimiento a costa de tener un camino menos continuo.

Aunque hay muchas propuestas y documentación al respecto,
un buen artículo que resume este funcionamiento es el propuesto
por GDHager, descargalo aqui.

Y hasta aqui hemos llegado, a ver quien es el primero que envía una
implementación de este procedimiento.

Hasta la próxima

Hoy os presento una maravilla de cara a generar trayectorias y movimientos
para entidades autónomas de forma optima y con un realismo magnífico, la
librería OpenSteer.

Se trata de un libreria creada en C++ que permite definir diferentes comportamientos
a entidades genéricas que necesitan ser dotadas de movimiento. Con ella podemos por
ejemplo guiar un elementos a una posición concreta calculando caminos de forma suave
y no limitados a un mallado.

Es una librería muy flexible que permite ser utilizada en cualquier motor de juego que
tenga un mínimo de compatibilidad con entidades externas. Simplemente por herencia podemos
crear los diferentes vehículos (entidades motrices) y hacer que estos sigan un determinado
comportamiento.

Podemos por ejemplo crear un vehiculo que huya y varios vehiculos que lo persigan de forma
sencilla. Lo más destacable de esta libreria es que permite prototipar de forma muy rápida
para posteriormente definir con más detalle los comportamientos. También implementa los mecanismos
más avanzados de guiado realista y óptimo. Los resultados son impresionantes.

Nos vale tanto para Linux, como para Mac o Windows por lo que prácticamente todos podemos
jugar con esta herramienta.

Hay que agradecer esta joya a los chicos del equipo de OpenSteer y al soporte de Sony Computer
Entertainment America puesto que se ofrece como open source software bajo licencia MIT.

> Aqui una demo
> Y aqui el código completo

No os la perdais.