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.

En algún post anterior hemos visto como funciona el algoritmo
A* o ‘A Estrella’ pero aqui lo repasaremos aplicándolo a la noble
vía de la búsqueda de caminos.

El aprendiz de Samurai Informático no tiene porqué conocer ningún
detalle del pathfinding para aprender lo que aqui se contará.

En primer lugar nuestro entorno quedará dividido en casillas que
representarán las posiciones alcanzables de los elementos que van
a ser desplazados. Partimos de una posición inicial y buscamos una
la lista de casillas que nos llevan a la posición final.

En nuestro entorno encontraremos obstáculos que harán que el camino
pueda variar.

A partir de ahora cada uno de los elementos de la malla los llamaremos
nodos.

>El procedimiento de búsqueda

Empezamos a estudiar el comportamiento del algoritmo. El estudio y la práctica
hacen al maestro Samurai Informático.

Tenemos 3 elementos sobre los que trabajaremos, la katana, la
armadura y el arco de batalla del algoritmo A Star aplicado al Pathfinding:

- La lista abierta de nodos. Son las casillas que requieren ser tenidas en cuenta.
- El ancestro de un nodo es el nodo a través del que se accede a este último, esto
se hace para que una vez sepamos los nodos o casillas que intervienen podamos recuperar
el orden en el que tienen que ser visitados.
- La lista cerrada de nodos. Son aquellos nodos que no deben ser tratados por el momento.

Ahora el código Samurai a seguir, nuestro Giri del A*. Debemos seguir el Giri bajo cualquier concepto.
El Giri del A* será interiorizado por todos los verdaderos Samurais Informáticos.

- 1. Empezar desde el punto inicial y añadirlo a la lista abierta de casillas a tener en cuenta.

- 2. Mirar todos los cuadrados válidos adyacentes al punto de inicio,
pasando de los inalcanzables. Añádir a la lista abierta.
Por cada uno de esos cuadrados, guarda el punto A como su ancestro.

- 3. Sacar la casilla inicial de la lista de abiertos y ponerlos en la lista cerrada.

El auténtico Samurai puede extraer ya la dinámica de lo que va a ser nuestro algoritmo de búsqueda de
caminos. Ahora lo que nos queda es repetir el proceso pero no de cualquier manera sino dotando a nuestro
sistema de la intuición genuina ancestral, es decir, lo que llamamos el heurístico. Con el visitaremos
primero los nodos más prometedores, es decir, aquellos en los que la fuerza se detecte mayor.

> Midiendo la calidad de una casilla

La calidad de una casilla es el valor que le damos para comparar entre el resto y decidir cual es el camino
más probable que debemos ir visitando. Aqui entra algo del conocimiento ancestral oculto, solo alcanzable por
los Samurais más avanzados, las matemáticas.

Cada casilla tendra un valor que vendrá determinado por la función: F(x) = G(x) + h(x)

-Donde x es la casilla concreta.
-F(x) es el valor de la función para la casilla x.
-G(x) es el coste que podemos medir. La distancia al inicio del camino
-h(x) es la esencia del algoritmo, el Tao. Aquello que se siente pero no puede ser explicado. El Tao que puede
ser explicado no es el verdadero Tao. En general, es lo que nosotros pensamos que puede quedar para llegar, nosotros
podemos calcular este valor a partir de la intuición de lo que nos queda. Siempre pueden haber obstáculos en medio
que nos perjudiquen pero en general, nos guiará hacia el verdadero Camino.

Como medimos las distancias no es problema aqui. El Samurai Verdadero buscará estas respuestas en otras fuentes, lo
realmente interesante es comprender el funcionamiento de nuestra Técnica de Combate A Estrella. No nos preocuparemos
de mejorar la eficiencia de los cálculos por el momento, esto es tarea del Experto Samurai Informático y no entra aqui
ahora, todo a su debido tiempo.

> El estimador o herístico h(x)

Este valor puede calcularse de diferentes maneras bajo diferentes conceptos, orientados a obtener una respuesta rápida
o una respuesta precisa. Generalmente nos pelearemos por buscar un compromiso entre lo rápido y lo preciso.

¿Como lo hacemos? Tenemos varias opciones.

-Primera opción. Sabemos donde estamos y donde queremos llegar, lo de en medio es una incognita. Pues bien, calcularemos la distancia
en línea recta desde nuestro punto al punto final. A esto se le llama distancia Euclidea y sin entrar en detalles será
algo del estilo d(x,y) = sqrt((y1-x1)^2 + (y2-x2)^2), es decir la raiz cuadrada de la suma de los cuadrados de las diferencias
entre las coordenadas correspondientes. Los Samurais que comprendan este concepto adquieren automáticamente una grado
adicional en materia de ‘Combate Matematico’.

-Segunda opción. Lo hacemos más sencillo. Utilizamos lo que se llama la distancia Manhattan. Es decir, calculamos lo
que nos costaría llegar si recorrieramos el tablero siguiendo las lineas de las mallas como si fueran las calles de
una ciudad dividida en manzanas. A efectos prácticos sería algo por el estilo dM(x, y) = abs(y1-x1) + abs(y2-x2), es decir
el valor absouto de la distancia en coordenadas X (pongamosle horizontal) y coordenadas y (pongamosle vertical).

En la foto las distancias marcadas con color amarillo, azul y rojo son las que representan la distancia Manhattan, cualquiera de ellas es válida. Para el cálculo nos quedamos con la amarilla o la roja (suma de distancia vertical y de distancia horizontal o al revés).
-Otras formas. Para aquellos Samurais más versados comentar que existen más métodos que intentan mejorar la eficacia y
eficiencia de este cálculo, ya que en definitiva es un estimador de lo buena que creemos que es la solución. Una de ellas
es el uso de la distancia Euclidea cuadrada, d2(x,y) = (y1-x1)^2 + (y2-x2)^2 donde se elimina el cálculo de la raiz. Esta
no es propiamente la distancia entre los puntos x e y pero al aplicarlo sobre todos los elementos, el valor relativo de
cada uno sigue representando la calidad estimada y por tanto nos sirve para guiar a la Espada del A Estrella hacia su objetivo.

> Seguimos la búsqueda.

De entre todos los bloques que hemos insertado en la lista de abiertos elegimos el que menos valor tenga en F, es decir,
el que la suma de la distancia al origen G y la distancia estimada h sea menor. Con esto dirigiremos la búsqueda.

Ahora el Samurai Informático novicio adquirirá los conceptos necesarios para ampliar definitivamente su conocimiento en
materia de IA para Juegos por lo que se recomienda atención.

Primero – Sacar este elemento de la lista de abiertos y añadir a la lista de cerrados.

Segundo – Repetir el paso de añadir los adyacentes que sean transitables pasando de los que están en la lista de cerrados
Añadirlos a la lista de abiertos si no están ya y poner al cuadro actual como Ancestro de los nuevos cuadros.

Tercero – Si el cuadro adyacente ya está en la lista de abiertos, mira si el camino a ese cuadro es mejor que este.
es decir, si la G de ese cuadro es más baja que la del que estamos usando para ir allí (llegamos más rápido por aqui)
. Si el coste G del nuevo camino es más bajo, cambia el ancestro del cuadro adyacente al cuadro seleccionado
y recalcula la F y la G de ese cuadrado.

Este paso es el que representa el mayor desafio al Samurai novicio, una vez superado le servirá tanto para generar
caminos como para otras muchas cosas en su vida de Samurai Informático.

Para terminar, comentaros que esta es la base del aprendizaje. A partir de aqui se puede trabajar en mejorar las soluciones
creando caminos más suaves, haciendo cálculos más rápidos y adaptando la solución a nuestro problema en concreto por ejemplo con
diferentes tamaños de unidades y diferentes tipos de terreno transitable (arena/asfalto/etc…).

Aqui teneis el código fuente del A* para el Pathfinding provisto por el Samurai Informático Experto Patrick Lester.

Disfrutadlo!

Cuando trabajamos con representaciones del mundo como las
que se utilizan en los juegos de estrategia, nos interesa
tener una abstracción máxima del entorno que represente toda
la información necesaria para el correcto desarrollo, con el
mínimo espacio.

Esto se consigue con el grafo de claridad, que en cada posición
definirá a que distancia se encuentran los obstáculos de la casilla
en cuestión.

Se propone para crear este grafo el algoritmo de Brushfire o tambien
llamado Wavefront. Sin embargo, este algoritmo presenta algunos problemas
desde el punto de vista de un entorno en el que se moverán elementos
de diferente tamaño. Podemos encontrar cuellos de botella que interfieren
en el correcto desarrollo.

Debido a esto, se propone una variante del cálculo para la obtención del
grafo de claridad para diferentes tamaños de unidades. El método en cuestión
se trata de, para cada celda ir ampliando un bloque de NxN creciente hasta
colisionar con un obstáculo, es decir, hasta que en las celdas que pertenecen
al bloque incluyan algún elemento no travesable.

Vemos un ejemplo extremadamente sencillo en las siguientes imágenes donde el
tamaño del bloque crece de izquierda a derecha y de arriba a abajo.

Quedando de esta forma:

Este procedimiento solventa parcialmente el problema pero no lo resuelve completamente.
Existen, del mismo modo, puntos que no son alcanzables cuando si debieran serlo. Esto es debido
a la orientación del crecimiento de los bloques que crecen en una dirección concreta.

Para esto se propone añadir complejidad O(1) al algoritmo, que no supone un impacto excesivo
al desempeño y que consigue resultados mucho mejores. Se trata de, por un lado repetir el proceso desde
las 4 esquinas del entorno, creciendo en direcciones diferentes para cada propuesta y adquiriendo
el máximo de las distancias obtenidas, esto indica que si bien no se puede llegar desde una dirección
concreta, se puede llegar perfectamente por otra.

Con esto ya tenemos una abstracción adecuada al cálculo de nuestro problema. Conseguir un camino será cuestión
de establecer un procedimiento que respete las restricciones. Esto es lo que veremos más adelante.

Os animo a implementarlo por vuestra cuenta, se trata de un ejercicio sencillo y un buen entrenamiento!