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.
> 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.
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.
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.
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
Leave a Reply