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:
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
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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:
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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!
En el anterior artículo hemos visto que en el algoritmo de Brushfire
sencillo podemos encontrar un camino aplicando un valor creciente desde
el punto de destino propagando valores hasta el punto final.
Esto sin embargo, no genera un grafo adecuado para ser calculado desde
cualquier punto sino que es necesario propagar la ‘ola’ para cada una
de las posiciones de destino.
La variante que se propone ahora es válida para cualquier posición del
entorno. En este caso cada elemento no travesable, es decir, cada obstáculo
es considerado como un generador de ‘Ola’ por lo que en cada posición
se representará la distancia al obstáculo más cercano.
El procedimiento de cálculo será el que vemos en la fotografía inferior.
Definido en pseudocódigo lo podremos calcular de la siguiente manera para conectividad 4:
check node A at [0][0]
now look north, south, east, and west of this node
(boundary nodes)
if (boundary node is a wall)
ignore this node, go to next node B
else if (boundary node is robot location && has a number in it)
path found!
find the boundary node with the smallest number
return that direction to robot controller
robot moves to that new node
else if (boundary node has a goal)
mark node A with the number 3
else if (boundary node is marked with a number)
find the boundary node with the smallest number
mark node A with (smallest number + 1)
if (no path found)
go to next node B at [0][1]
(sort through entire matrix in order)
if (no path still found after full scan)
go to node A at [0][0]
(start over, but do not clear map)
(sort through entire matrix in order)
repeat until path found
if (no path still found && matrix is full)
this means there is no solution
clear entire matrix of obstacles and start over
this accounts for moving objects! adaptivity!
Os incluyo el código fuente de la variante más sencilla del algoritmo de
Wavefront para que modifiqueis libremente y lo convirtais en la variante
que se explica aqui.
El algoritmo Brushfire o Wavefront para grafos de Claridad presenta dos variantes, la de un solo emisor y la de varios emisores. Veremos las dos variantes.
Los grafos de claridad representan el mundo donde se mueven los agentes como medidas al obstáculo más cercano, es decir, se abstraen del entorno generando una representación más ligera del mismo y computacionalmente más apropiada.
Un ejemplo de grafo de claridad es el que vemos a continuación, en el se
pueden apreciar las distancias al objeto no travesable más cercano. En este
caso para simplificar el cálculo se divide en zeldas el mundo y se calcula a partir de
aqui. Para generalizar se define una unidad de grid o generalizada, que define que tamaño tiene cada una de ellas en pixels. Las unidades usarán tambien esta medida, por ejemplo un soldado ocupará 1×1 grids un tanque 2×2 …etc.
Conforme la complejidad del entorno crece, se necesitan los Grafos de claridad con varios tipos de terreno,
es decir, cada zelda vendrá identificada con un valor de terreno {agua/tierra/aire…etc}.
Para calcular este grafo de claridad se emplea el algoritmo Brushfire o tambien llamado wavefront.
Este algoritmo se utiliza tambien en robótica móvil para generar caminos de forma dinámica en función del entorno.
De esta forma, lo que aprendeis aqui os sirve también para cualquier entorno donde podamos dividir en
malla el mundo: robots moviles, juegos, aplicaciones industriales…etc. Esta variante se centra en la meta como único
emisor de la ‘Ola’
Cómo calculamos la distancia a los obstaculos. Lo vemos mediante un ejemplo, en el que de momento no se tienen en cuenta los tamaños de las unidades.
-Primero.Creamos el mundo
-Segundo. Rellenamos con los valores adecuados.
-Tercero. Aplicamos el Wavefront o Brushfire
>1.Creando el mundo
Lo primero que tenemos que hacer es calcular el mallado a partir de nuestro mundo. Esto se hará
como hemos comentado anteriormente definiendo el tamaño de malla y creando el entorno a partir de
estos valores.
>2. Rellenando con valores adecuados
En este paso definimos un punto de inicio y otro de meta. {Start/Goal points}
Marcamos todos los elementos de la malla que no son obstáculos con un 0
y todos los demás con un 1. El punto de meta lo marcamos con un 2, por ejemplo.
>3. Desde la casilla de meta aplicamos la ola o el wavefront asignando a todos los
valores adyacentes el valor de la casilla mas una unidad.
>4. Buscamos el camino recorriendo los adyacentes de la casilla desde el punto de
partida siempre disminuyendo en 1 los valores. Esto hace que sobre caminos cerrados
no se propague la ‘ola’ y siempre encuentre el camino a la meta, si este existe.
Este es uno de los métodos más sencillos para aplicar pathfinding, hay otros mucho más
eficientes que veremos posteriormente. Lo siguiente será ver la variante de este algoritmo donde no solo el destino genera la ‘Ola’ sino cada obstáculo es emisor, por lo que se puede aplicar a diferentes tamaños de unidades.
El cube mapping se utiliza entre otras aplicaciones para encuadrar el entorno de nuestro mundo utilizando 6 imágenes que engloban las diferentes caras de un cubo.
Como se puede apreciar en la imagen el cube mapping engloba la escena por lo que un observador desde dentro debe percibir mediante la interpolación de las 6 imágenes un entorno adecuado 360 grados.
Un ejemplo de cube mapping para englobar la escena sería:
El reflejo generado en un material de tipo espejo o transparente sería el seguiente:
Los resultados suelen ser buenos y actualmente existen soluciones que permiten e cálculo de los refejos producidos por el entorno (el cubo) en tiempo real.
Otro ejemplo de cube mapping para definir el entorno es el siguiente:
Calculado a partir de un cubo con el de la imagen posterior.
El cube mapping nos permite por lo tanto englobar la escena por medio de 6 imágenes que forman el cubo contenedor.
Como medimos las distancias no es problema aqui. El Samurai Verdadero buscará estas respuestas en otras fuentes, lo
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).
No comments »